Comparability and permutation graphs#
This module implements method related to Wikipedia article Comparability_graph and Wikipedia article Permutation_graph, that is, for the moment, only recognition algorithms.
Most of the information found here can also be found in [ST1994] or [Sha1997].
The following methods are implemented in this module
Tests whether the graph is a comparability graph (MILP) 

Tests whether the graph is a comparability graph (greedy algorithm) 

Tests whether the graph is a comparability graph and returns certificates (greedy algorithm) 

Tests whether the graph is a comparability graph 

Tests whether the graph is a permutation graph. 

Tests whether the digraph is transitive. 
Author:
Nathann Cohen 201204
Graph classes#
Comparability graphs
A graph is a comparability graph if it can be obtained from a poset by adding an edge between any two elements that are comparable. Cocomparability graph are complements of such graphs, i.e. graphs built from a poset by adding an edge between any two incomparable elements.
For more information on comparability graphs, see the Wikipedia article Comparability_graph.
Permutation graphs
Definitions:
A permutation \(\pi = \pi_1\pi_2\dots\pi_n\) defines a graph on \(n\) vertices such that \(i\sim j\) when \(\pi\) reverses \(i\) and \(j\) (i.e. when \(i<j\) and \(\pi_j < \pi_i\). A graph is a permutation graph whenever it can be built through this construction.
A graph is a permutation graph if it can be build from two parallel lines are the intersection graph of segments intersecting both lines.
A graph is a permutation graph if it is both a comparability graph and a cocomparability graph.
For more information on permutation graphs, see the Wikipedia article Permutation_graph.
Recognition algorithm for comparability graphs#
Greedy algorithm
This algorithm attempts to build a transitive orientation of a given graph \(G\), that is an orientation \(D\) such that for any directed \(uv\)path of \(D\) there exists in \(D\) an edge \(uv\). This already determines a notion of equivalence between some edges of \(G\) :
In \(G\), two edges \(uv\) and \(uv'\) (incident to a common vertex \(u\)) such that \(vv'\not\in G\) need necessarily be oriented the same way (that is that they should either both leave or both enter \(u\)). Indeed, if one enters \(G\) while the other leaves it, these two edges form a path of length two, which is not possible in any transitive orientation of \(G\) as \(vv'\not\in G\).
Hence, we can say that in this case a directed edge \(uv\) is equivalent to a directed edge \(uv'\) (to mean that if one belongs to the transitive orientation, the other one must be present too) in the same way that \(vu\) is equivalent to \(v'u\). We can thus define equivalence classes on oriented edges, to represent set of edges that imply each other. We can thus define \(C^G_{uv}\) to be the equivalence class in \(G\) of the oriented edge \(uv\).
Of course, if there exists a transitive orientation of a graph \(G\), then no edge \(uv\) implies its contrary \(vu\), i.e. it is necessary to ensure that \(\forall uv\in G, vu\not\in C^G_{uv}\). The key result on which the greedy algorithm is built is the following (see [ST1994]):
Theorem – The following statements are equivalent :
\(G\) is a comparability graph
\(\forall uv\in G, vu\not\in C^G_{uv}\)
The edges of \(G\) can be partitionned into \(B_1,...,B_k\) where \(B_i\) is the equivalence class of some oriented edge in \(GB_1\dotsB_{i1}\)
Hence, ensuring that a graph is a comparability graph can be done by checking that no equivalence class is contradictory. Building the orientation, however, requires to build equivalence classes step by step until an orientation has been found for all of them.
Mixed Integer Linear Program
A MILP formulation is available to check the other methods for correction. It is easily built :
To each edge are associated two binary variables (one for each possible direction). We then ensure that each triangle is transitively oriented, and that each pair of incident edges \(uv, uv'\) such that \(vv'\not\in G\) do not create a 2path.
Here is the formulation:
Note
The MILP formulation is usually much slower than the greedy algorithm. This MILP has been implemented to check the results of the greedy algorithm that has been implemented to check the results of a faster algorithm which has not been implemented yet.
Certificates#
Comparability graphs
The yescertificates that a graph is a comparability graphs are transitive orientations of it. The nocertificates, on the other hand, are odd cycles of such graph. These odd cycles have the property that around each vertex \(v\) of the cycle its two incident edges must have the same orientation (toward \(v\), or outward \(v\)) in any transitive orientation of the graph. This is impossible whenever the cycle has odd length. Explanations are given in the “Greedy algorithm” part of the previous section.
Permutation graphs
Permutation graphs are precisely the intersection of comparability graphs and
cocomparability graphs. Hence, negative certificates are precisely negative
certificates of comparability or cocomparability. Positive certificates are a
pair of permutations that can be used through
PermutationGraph()
(whose
documentation says more about what these permutations represent).
Implementation details#
Test that the equivalence classes are not selfcontradictory
This is done by a call to Graph.is_bipartite()
, and here is how :
Around a vertex \(u\), any two edges \(uv, uv'\) such that \(vv'\not\in G\) are equivalent. Hence, the equivalence class of edges around a vertex are precisely the connected components of the complement of the graph induced by the neighbors of \(u\).
In each equivalence class (around a given vertex \(u\)), the edges should all have the same orientation, i.e. all should go toward \(u\) at the same time, or leave it at the same time. To represent this, we create a graph with vertices for all equivalent classes around all vertices of \(G\), and link \((v, C)\) to \((u, C')\) if \(u\in C\) and \(v\in C'\).
A bipartite coloring of this graph with colors 0 and 1 tells us that the edges of an equivalence class \(C\) around \(u\) should be directed toward \(u\) if \((u, C)\) is colored with \(0\), and outward if \((u, C)\) is colored with \(1\).
If the graph is not bipartite, this is the proof that some equivalence class is selfcontradictory !
Note
The greedy algorithm implemented here is just there to check the correction of more complicated ones, and it is reaaaaaaaaaaaalllly bad whenever you look at it with performance in mind.
Methods#
 sage.graphs.comparability.greedy_is_comparability(g, no_certificate=False, equivalence_class=False)#
Tests whether the graph is a comparability graph (greedy algorithm)
This method only returns nocertificates.
To understand how this method works, please consult the documentation of the
comparability module
.INPUT:
no_certificate
– whether to return a nocertificate when the graph is not a comparability graph. This certificate is an odd cycle of edges, each of which implies the next. It is set toFalse
by default.equivalence_class
– whether to return an equivalence class if the graph is a comparability graph.
OUTPUT:
If the graph is a comparability graph and
no_certificate = False
, this method returnsTrue
or(True, an_equivalence_class)
according to the value ofequivalence_class
.If the graph is not a comparability graph, this method returns
False
or(False, odd_cycle)
according to the value ofno_certificate
.
EXAMPLES:
The Petersen Graph is not transitively orientable:
sage: from sage.graphs.comparability import greedy_is_comparability as is_comparability sage: g = graphs.PetersenGraph() sage: is_comparability(g) False sage: is_comparability(g, no_certificate=True) (False, [2, 1, 0, 4, 3, 2])
But the Bull graph is:
sage: g = graphs.BullGraph() sage: is_comparability(g) True
 sage.graphs.comparability.greedy_is_comparability_with_certificate(g, certificate=False)#
Tests whether the graph is a comparability graph and returns certificates(greedy algorithm).
This method can return certificates of both yes and no answers.
To understand how this method works, please consult the documentation of the
comparability module
.INPUT:
certificate
(boolean) – whether to return a certificate. Yesanswers the certificate is a transitive orientation of \(G\), and a no certificates is an odd cycle of sequentially forcing edges.
EXAMPLES:
The 5cycle or the Petersen Graph are not transitively orientable:
sage: from sage.graphs.comparability import greedy_is_comparability_with_certificate as is_comparability sage: is_comparability(graphs.CycleGraph(5), certificate=True) (False, [2, 1, 0, 4, 3, 2]) sage: g = graphs.PetersenGraph() sage: is_comparability(g) False sage: is_comparability(g, certificate=True) (False, [2, 1, 0, 4, 3, 2])
But the Bull graph is:
sage: g = graphs.BullGraph() sage: is_comparability(g) True sage: is_comparability(g, certificate = True) (True, Digraph on 5 vertices) sage: is_comparability(g, certificate = True)[1].is_transitive() True
 sage.graphs.comparability.is_comparability(g, algorithm='greedy', certificate=False, check=True, solver=None, verbose=0)#
Tests whether the graph is a comparability graph
INPUT:
algorithm
– choose the implementation used to do the test."greedy"
– a greedy algorithm (see the documentation of thecomparability module
)."MILP"
– a Mixed Integer Linear Program formulation of the problem. Beware, for this implementation is unable to return negative certificates ! Whencertificate = True
, negative certificates are always equal toNone
. True certificates are valid, though.
certificate
(boolean) – whether to return a certificate. Yesanswers the certificate is a transitive orientation of \(G\), and a no certificates is an odd cycle of sequentially forcing edges.check
(boolean) – whether to check that the yescertificates are indeed transitive. As it is very quick compared to the rest of the operation, it is enabled by default.solver
– (default:None
); Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve()
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.
EXAMPLES:
sage: from sage.graphs.comparability import is_comparability sage: g = graphs.PetersenGraph() sage: is_comparability(g) False sage: is_comparability(graphs.CompleteGraph(5), certificate=True) (True, Digraph on 5 vertices)
 sage.graphs.comparability.is_comparability_MILP(g, certificate=False, solver=None, verbose=0)#
Tests whether the graph is a comparability graph (MILP)
INPUT:
certificate
(boolean) – whether to return a certificate for yes instances. This method cannot return negative certificates.solver
– (default:None
); Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve()
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.
EXAMPLES:
The 5cycle or the Petersen Graph are not transitively orientable:
sage: from sage.graphs.comparability import is_comparability_MILP as is_comparability sage: is_comparability(graphs.CycleGraph(5), certificate=True) # needs sage.numerical.mip (False, None) sage: g = graphs.PetersenGraph() sage: is_comparability(g, certificate=True) # needs sage.numerical.mip (False, None)
But the Bull graph is:
sage: g = graphs.BullGraph() sage: is_comparability(g) # needs sage.numerical.mip True sage: is_comparability(g, certificate=True) # needs sage.numerical.mip (True, Digraph on 5 vertices) sage: is_comparability(g, certificate=True)[1].is_transitive() # needs sage.numerical.mip True
 sage.graphs.comparability.is_permutation(g, algorithm='greedy', certificate=False, check=True, solver=None, verbose=0)#
Tests whether the graph is a permutation graph.
For more information on permutation graphs, refer to the documentation of the
comparability module
.INPUT:
algorithm
– choose the implementation used for the subcalls tois_comparability()
."greedy"
– a greedy algorithm (see the documentation of thecomparability module
)."MILP"
– a Mixed Integer Linear Program formulation of the problem. Beware, for this implementation is unable to return negative certificates ! Whencertificate = True
, negative certificates are always equal toNone
. True certificates are valid, though.
certificate
(boolean) – whether to return a certificate for the answer given. ForTrue
answers the certificate is a permutation, forFalse
answers it is a nocertificate for the test of comparability or cocomparability.check
(boolean) – whether to check that the permutations returned indeed create the expected Permutation graph. Pretty cheap compared to the rest, hence a good investment. It is enabled by default.solver
– (default:None
); Specify a Linear Program (LP) solver to be used. If set toNone
, the default one is used. For more information on LP solvers and which default solver is used, see the methodsolve()
of the classMixedIntegerLinearProgram
.verbose
– integer (default:0
); sets the level of verbosity. Set to 0 by default, which means quiet.
Note
As the
True
certificate is aPermutation
object, the segment intersection model of the permutation graph can be visualized through a call toPermutation.show
.EXAMPLES:
A permutation realizing the bull graph:
sage: from sage.graphs.comparability import is_permutation sage: g = graphs.BullGraph() sage: _ , certif = is_permutation(g, certificate=True) sage: h = graphs.PermutationGraph(*certif) sage: h.is_isomorphic(g) True
Plotting the realization as an intersection graph of segments:
sage: true, perm = is_permutation(g, certificate=True) sage: p1 = Permutation([nn+1 for nn in perm[0]]) sage: p2 = Permutation([nn+1 for nn in perm[1]]) sage: p = p2 * p1.inverse() sage: p.show(representation="braid") # needs sage.plot
 sage.graphs.comparability.is_transitive(g, certificate=False)#
Tests whether the digraph is transitive.
A digraph is transitive if for any pair of vertices \(u,v\in G\) linked by a \(uv\)path the edge \(uv\) belongs to \(G\).
INPUT:
certificate
– whether to return a certificate for negative answers.If
certificate = False
(default), this method returnsTrue
orFalse
according to the graph.If
certificate = True
, this method either returnsTrue
answers or yield a pair of vertices \(uv\) such that there exists a \(uv\)path in \(G\) but \(uv\not\in G\).
EXAMPLES:
sage: digraphs.Circuit(4).is_transitive() False sage: digraphs.Circuit(4).is_transitive(certificate=True) (0, 2) sage: digraphs.RandomDirectedGNP(30,.2).is_transitive() False sage: D = digraphs.DeBruijn(5, 2) # needs sage.combinat sage: D.is_transitive() # needs sage.combinat False sage: cert = D.is_transitive(certificate=True) # needs sage.combinat sage: D.has_edge(*cert) # needs sage.combinat False sage: bool(D.shortest_path(*cert)) # needs sage.combinat True sage: digraphs.RandomDirectedGNP(20,.2).transitive_closure().is_transitive() # needs networkx True