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

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:

  • Nathann Cohen 2012-04

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. 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 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 co-comparability 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 \(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:

\[\begin{split}\mbox{Maximize : }&\mbox{Nothing}\\ \mbox{Such that : }&\\ &\forall uv\in G\\ &\cdot o_{uv}+o_{vu} = 1\\ &\forall u\in G, \forall v,v'\in N(v)\text{ such that }vv'\not\in G\\ &\cdot o_{uv} + o_{v'u} - o_{v'v} \leq 1\\ &\cdot o_{uv'} + o_{vu} - o_{vv'} \leq 1\\ &\forall u\in G, \forall v,v'\in N(v)\text{ such that }vv'\in G\\ &\cdot o_{uv} + o_{v'u} \leq 1\\ &\cdot o_{uv'} + o_{vu} \leq 1\\ &o_{uv}\text{ is a binary variable}\\\end{split}\]

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 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).

Implementation details#

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 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 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.

Methods#

sage.graphs.comparability.greedy_is_comparability(g, no_certificate=False, equivalence_class=False)[source]#

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:

  • no_certificate – whether to return a no-certificate 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 to False 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 returns True or (True, an_equivalence_class) according to the value of equivalence_class.

  • If the graph is not a comparability graph, this method returns False or (False, odd_cycle) according to the value of no_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])

>>> from sage.all import *
>>> from sage.graphs.comparability import greedy_is_comparability as is_comparability
>>> g = graphs.PetersenGraph()
>>> is_comparability(g)
False
>>> 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

>>> from sage.all import *
>>> g = graphs.BullGraph()
>>> is_comparability(g)
True
sage.graphs.comparability.greedy_is_comparability_with_certificate(g, certificate=False)[source]#

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. Yes-answers the certificate is a transitive orientation of \(G\), and a no certificates is an odd cycle of sequentially forcing edges.

EXAMPLES:

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, [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])

>>> from sage.all import *
>>> from sage.graphs.comparability import greedy_is_comparability_with_certificate as is_comparability
>>> is_comparability(graphs.CycleGraph(Integer(5)), certificate=True)
(False, [2, 1, 0, 4, 3, 2])
>>> g = graphs.PetersenGraph()
>>> is_comparability(g)
False
>>> 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

>>> from sage.all import *
>>> g = graphs.BullGraph()
>>> is_comparability(g)
True
>>> is_comparability(g, certificate = True)
(True, Digraph on 5 vertices)
>>> is_comparability(g, certificate = True)[Integer(1)].is_transitive()
True
sage.graphs.comparability.is_comparability(g, algorithm='greedy', certificate=False, check=True, solver=None, verbose=0)[source]#

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 the comparability module).

    • "MILP" – a Mixed Integer Linear Program formulation of the problem. Beware, for this implementation is unable to return negative certificates ! When certificate = True, negative certificates are always equal to None. True certificates are valid, though.

  • certificate (boolean) – whether to return a certificate. Yes-answers 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 yes-certificates 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 to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve() of the class MixedIntegerLinearProgram.

  • 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)

>>> from sage.all import *
>>> from sage.graphs.comparability import is_comparability
>>> g = graphs.PetersenGraph()
>>> is_comparability(g)
False
>>> is_comparability(graphs.CompleteGraph(Integer(5)), certificate=True)
(True, Digraph on 5 vertices)
sage.graphs.comparability.is_comparability_MILP(g, certificate=False, solver=None, verbose=0)[source]#

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 to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve() of the class MixedIntegerLinearProgram.

  • verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

EXAMPLES:

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)                    # needs sage.numerical.mip
(False, None)
sage: g = graphs.PetersenGraph()
sage: is_comparability(g, certificate=True)                                       # needs sage.numerical.mip
(False, None)

>>> from sage.all import *
>>> from sage.graphs.comparability import is_comparability_MILP as is_comparability
>>> is_comparability(graphs.CycleGraph(Integer(5)), certificate=True)                    # needs sage.numerical.mip
(False, None)
>>> g = graphs.PetersenGraph()
>>> 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

>>> from sage.all import *
>>> g = graphs.BullGraph()
>>> is_comparability(g)                                                         # needs sage.numerical.mip
True
>>> is_comparability(g, certificate=True)                                       # needs sage.numerical.mip
(True, Digraph on 5 vertices)
>>> is_comparability(g, certificate=True)[Integer(1)].is_transitive()                    # needs sage.numerical.mip
True
sage.graphs.comparability.is_permutation(g, algorithm='greedy', certificate=False, check=True, solver=None, verbose=0)[source]#

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 to is_comparability().

    • "greedy" – a greedy algorithm (see the documentation of the comparability module).

    • "MILP" – a Mixed Integer Linear Program formulation of the problem. Beware, for this implementation is unable to return negative certificates ! When certificate = True, negative certificates are always equal to None. True certificates are valid, though.

  • certificate (boolean) – whether to return a certificate for the answer given. For True answers the certificate is a permutation, for False answers it is a no-certificate for the test of comparability or co-comparability.

  • 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 to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve() of the class MixedIntegerLinearProgram.

  • verbose – integer (default: 0); sets the level of verbosity. Set to 0 by default, which means quiet.

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.

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

>>> from sage.all import *
>>> from sage.graphs.comparability import is_permutation
>>> g = graphs.BullGraph()
>>> _ , certif = is_permutation(g, certificate=True)
>>> h = graphs.PermutationGraph(*certif)
>>> 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

>>> from sage.all import *
>>> true, perm = is_permutation(g, certificate=True)
>>> p1 = Permutation([nn+Integer(1) for nn in perm[Integer(0)]])
>>> p2 = Permutation([nn+Integer(1) for nn in perm[Integer(1)]])
>>> p = p2 * p1.inverse()
>>> p.show(representation="braid")                                            # needs sage.plot
sage.graphs.comparability.is_transitive(g, certificate=False)[source]#

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 returns True or False according to the graph.

    • If certificate = True, this method either returns True 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

>>> from sage.all import *
>>> digraphs.Circuit(Integer(4)).is_transitive()
False
>>> digraphs.Circuit(Integer(4)).is_transitive(certificate=True)
(0, 2)
>>> digraphs.RandomDirectedGNP(Integer(30),RealNumber('.2')).is_transitive()
False
>>> D = digraphs.DeBruijn(Integer(5), Integer(2))                                               # needs sage.combinat
>>> D.is_transitive()                                                         # needs sage.combinat
False
>>> cert = D.is_transitive(certificate=True)                                  # needs sage.combinat
>>> D.has_edge(*cert)                                                         # needs sage.combinat
False
>>> bool(D.shortest_path(*cert))                                              # needs sage.combinat
True
>>> digraphs.RandomDirectedGNP(Integer(20),RealNumber('.2')).transitive_closure().is_transitive()    # needs networkx
True