Comparability and permutation graphs
This module implements method related to Comparability graphs and Permutation graphs, that is, for the moment, only recognition algorithms.
Most of the information found here can alo be found in [Cleanup] or [ATGA].
The following methods are implemented in this module
is_comparability_MILP() | Tests whether the graph is a comparability graph (MILP) |
greedy_is_comparability() | Tests whether the graph is a comparability graph (greedy algorithm) |
greedy_is_comparability_with_certificate() | Tests whether the graph is a comparability graph and returns certificates (greedy algorithm) |
is_comparability() | Tests whether the graph is a comparability graph |
is_permutation() | Tests whether the graph is a permutation graph. |
is_transitive() | Tests whether the digraph is transitive. |
Author:
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. Co-comparability 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 comparablity graphs, see the corresponding wikipedia page
Permutation graphs
Definitions:
For more information on permutation graphs, see the corresponding wikipedia page.
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 [Cleanup]):
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 \(G-B_1-\dots-B_{i-1}\)
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 2-path.
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.
Comparability graphs
The yes-certificates that a graph is a comparability graphs are transitive orientations of it. The no-certificates, 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 co-comparability graphs. Hence, negative certificates are precisely negative certificates of comparability or co-comparability. Positive certificates are a pair of permutations that can be used through PermutationGraph() (whose documentation says more about what these permutations represent).
Test that the equivalence classes are not self-contradictory
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 classe 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 self-contradictory !
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.
[ATGA] | Advanced Topics in Graph Algorithms, Ron Shamir, http://www.cs.tau.ac.il/~rshamir/atga/atga.html |
[Cleanup] | (1, 2) A cleanup on transitive orientation, Orders, Algorithms, and Applications, 1994, Simon, K. and Trunz, P., ftp://ftp.inf.ethz.ch/doc/papers/ti/ga/ST94.ps.gz |
Tests whether the graph is a comparability graph (greedy algorithm)
This method only returns no-certificates.
To understand how this method works, please consult the documentation of the comparability module.
INPUT:
OUTPUT:
EXAMPLE:
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, [9, 6, 1, 0, 4, 9])
But the Bull graph is:
sage: g = graphs.BullGraph()
sage: is_comparability(g)
True
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:
EXAMPLE:
The 5-cycle 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, [3, 4, 0, 1, 2, 3])
sage: g = graphs.PetersenGraph()
sage: is_comparability(g)
False
sage: is_comparability(g, certificate = True)
(False, [9, 6, 1, 0, 4, 9])
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
Tests whether the graph is a comparability graph
INPUT:
EXAMPLE:
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)
TESTS:
Let us ensure that no exception is raised when we go over all small graphs:
sage: from sage.graphs.comparability import is_comparability
sage: [len([g for g in graphs(i) if is_comparability(g, certificate = True)[0]]) for i in range(7)]
[1, 1, 2, 4, 11, 33, 144]
Tests whether the graph is a comparability graph (MILP)
INPUT:
EXAMPLE:
The 5-cycle 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)
(False, None)
sage: g = graphs.PetersenGraph()
sage: is_comparability(g, certificate = True)
(False, None)
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
Tests whether the graph is a permutation graph.
For more information on permutation graphs, refer to the documentation of the comparability module.
INPUT:
Note
As the True certificate is a Permutation object, the segment intersection model of the permutation graph can be visualized through a call to Permutation.show.
EXAMPLE:
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")
TESTS:
Trying random permutations, first with the greedy algorithm:
sage: from sage.graphs.comparability import is_permutation
sage: for i in range(20):
... p = Permutations(10).random_element()
... g1 = graphs.PermutationGraph(p)
... isit, certif = is_permutation(g1, certificate = True)
... if not isit:
... print "Something is wrong here !!"
... break
... g2 = graphs.PermutationGraph(*certif)
... if not g1.is_isomorphic(g2):
... print "Something is wrong here !!"
... break
Then with MILP:
sage: from sage.graphs.comparability import is_permutation
sage: for i in range(20):
... p = Permutations(10).random_element()
... g1 = graphs.PermutationGraph(p)
... isit, certif = is_permutation(g1, algorithm = "MILP", certificate = True)
... if not isit:
... print "Something is wrong here !!"
... break
... g2 = graphs.PermutationGraph(*certif)
... if not g1.is_isomorphic(g2):
... print "Something is wrong here !!"
... break
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:
EXAMPLE:
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: digraphs.DeBruijn(5,2).is_transitive()
False
sage: digraphs.DeBruijn(5,2).is_transitive(certificate = True)
('00', '10')
sage: digraphs.RandomDirectedGNP(20,.2).transitive_closure().is_transitive()
True