Convexity properties of graphs¶

This class gathers the algorithms related to convexity in a graph. It implements the following methods:

`ConvexityProperties.hull()`	Return the convex hull of a set of vertices
`ConvexityProperties.hull_number()`	Compute the hull number of a graph and a corresponding generating set
`geodetic_closure()`	Return the geodetic closure of a set of vertices
`is_geodetic()`	Check whether the input (di)graph is geodetic

Some of these methods can be used through the ConvexityProperties object returned by Graph.convexity_properties().

Methods¶

class sage.graphs.convexity_properties.ConvexityProperties[source]¶

Bases: object

This class gathers the algorithms related to convexity in a graph.

Definitions

A set \(S \subseteq V(G)\) of vertices is said to be convex if for all \(u,v\in S\) the set \(S\) contains all the vertices located on a shortest path between \(u\) and \(v\). Alternatively, a set \(S\) is said to be convex if the distances satisfy \(\forall u,v\in S, \forall w\in V\backslash S : d_{G}(u,w) + d_{G}(w,v) > d_{G}(u,v)\).

The convex hull \(h(S)\) of a set \(S\) of vertices is defined as the smallest convex set containing \(S\).

It is a closure operator, as trivially \(S\subseteq h(S)\) and \(h(h(S)) = h(S)\).

What this class contains

As operations on convex sets generally involve the computation of distances between vertices, this class’ purpose is to cache that information so that computing the convex hulls of several different sets of vertices does not imply recomputing several times the distances between the vertices.

In order to compute the convex hull of a set \(S\) it is possible to write the following algorithm:

For any pair \(u,v\) of elements in the set \(S\), and for any vertex \(w\) outside of it, add \(w\) to \(S\) if \(d_{G}(u,w) + d_{G}(w,v) = d_{G}(u,v)\). When no vertex can be added anymore, the set \(S\) is convex

The distances are not actually that relevant. The same algorithm can be implemented by remembering for each pair \(u, v\) of vertices the list of elements \(w\) satisfying the condition, and this is precisely what this class remembers, encoded as bitsets to make storage and union operations more efficient.

Note

This class is useful if you compute the convex hulls of many sets in the same graph, or if you want to compute the hull number itself as it involves many calls to hull()
Using this class on non-connected graphs is a waste of space and efficiency ! If your graph is disconnected, the best for you is to deal independently with each connected component, whatever you are doing.

Possible improvements

When computing a convex set, all the pairs of elements belonging to the set \(S\) are enumerated several times.

There should be a smart way to avoid enumerating pairs of vertices which have already been tested. The cost of each of them is not very high, so keeping track of those which have been tested already may be too expensive to gain any efficiency.
The ordering in which they are visited is currently purely lexicographic, while there is a Poset structure to exploit. In particular, when two vertices \(u, v\) are far apart and generate a set \(h(\{u,v\})\) of vertices, all the pairs of vertices \(u', v'\in h(\{u,v\})\) satisfy \(h(\{u',v'\}) \subseteq h(\{u,v\})\), and so it is useless to test the pair \(u', v'\) when both \(u\) and \(v\) where present.
The information cached is for any pair \(u,v\) of vertices the list of elements \(z\) with \(d_{G}(u,w) + d_{G}(w,v) = d_{G}(u,v)\). This is not in general equal to \(h(\{u,v\})\) !

Nothing says these recommendations will actually lead to any actual improvements. There are just some ideas remembered while writing this code. Trying to optimize may well lead to lost in efficiency on many instances.

EXAMPLES:

Sage

sage: from sage.graphs.convexity_properties import ConvexityProperties
sage: g = graphs.PetersenGraph()
sage: CP = ConvexityProperties(g)
sage: CP.hull([1, 3])
[1, 2, 3]
sage: CP.hull_number()                                                          # needs sage.numerical.mip
3

Python

>>> from sage.all import *
>>> from sage.graphs.convexity_properties import ConvexityProperties
>>> g = graphs.PetersenGraph()
>>> CP = ConvexityProperties(g)
>>> CP.hull([Integer(1), Integer(3)])
[1, 2, 3]
>>> CP.hull_number()                                                          # needs sage.numerical.mip
3

hull(vertices)[source]¶

Return the convex hull of a set of vertices.

INPUT:

vertices – list of vertices

EXAMPLES:

Sage

sage: from sage.graphs.convexity_properties import ConvexityProperties
sage: g = graphs.PetersenGraph()
sage: CP = ConvexityProperties(g)
sage: CP.hull([1, 3])
[1, 2, 3]

Python

>>> from sage.all import *
>>> from sage.graphs.convexity_properties import ConvexityProperties
>>> g = graphs.PetersenGraph()
>>> CP = ConvexityProperties(g)
>>> CP.hull([Integer(1), Integer(3)])
[1, 2, 3]

hull_number(value_only=True, verbose=False)[source]¶

Compute the hull number and a corresponding generating set.

The hull number \(hn(G)\) of a graph \(G\) is the cardinality of a smallest set of vertices \(S\) such that \(h(S)=V(G)\).

INPUT:

value_only – boolean (default: True); whether to return only the hull number (default) or a minimum set whose convex hull is the whole graph
verbose – boolean (default: False); whether to display information on the LP

COMPLEXITY:

This problem is NP-Hard [HLT1993], but seems to be of the “nice” kind. Update this comment if you fall on hard instances \(:-)\)

ALGORITHM:

This is solved by linear programming.

As the function \(h(S)\) associating to each set \(S\) its convex hull is a closure operator, it is clear that any set \(S_G\) of vertices such that \(h(S_G)=V(G)\) must satisfy \(S_G \not \subseteq C\) for any proper convex set \(C \subsetneq V(G)\). The following formulation is hence correct

\[\begin{split}\text{Minimize :}& \sum_{v\in G}b_v\\ \text{Such that :}&\\ &\forall C\subsetneq V(G)\text{ a proper convex set }\\ &\sum_{v\in V(G)\backslash C} b_v \geq 1\end{split}\]

Of course, the number of convex sets – and so the number of constraints – can be huge, and hard to enumerate, so at first an incomplete formulation is solved (it is missing some constraints). If the answer returned by the LP solver is a set \(S\) generating the whole graph, then it is optimal and so is returned. Otherwise, the constraint corresponding to the set \(h(S)\) can be added to the LP, which makes the answer \(S\) infeasible, and another solution computed.

This being said, simply adding the constraint corresponding to \(h(S)\) is a bit slow, as these sets can be large (and the corresponding constraint a bit weak). To improve it a bit, before being added, the set \(h(S)\) is “greedily enriched” to a set \(S'\) with vertices for as long as \(h(S')\neq V(G)\). This way, we obtain a set \(S'\) with \(h(S)\subseteq h(S')\subsetneq V(G)\), and the constraint corresponding to \(h(S')\) – which is stronger than the one corresponding to \(h(S)\) – is added.

This can actually be seen as a hitting set problem on the complement of convex sets.

EXAMPLES:

The Hull number of Petersen’s graph:

Sage

sage: from sage.graphs.convexity_properties import ConvexityProperties
sage: g = graphs.PetersenGraph()
sage: CP = ConvexityProperties(g)
sage: CP.hull_number()                                                      # needs sage.numerical.mip
3
sage: generating_set = CP.hull_number(value_only=False)                     # needs sage.numerical.mip
sage: CP.hull(generating_set)                                               # needs sage.numerical.mip
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Python

>>> from sage.all import *
>>> from sage.graphs.convexity_properties import ConvexityProperties
>>> g = graphs.PetersenGraph()
>>> CP = ConvexityProperties(g)
>>> CP.hull_number()                                                      # needs sage.numerical.mip
3
>>> generating_set = CP.hull_number(value_only=False)                     # needs sage.numerical.mip
>>> CP.hull(generating_set)                                               # needs sage.numerical.mip
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

sage.graphs.convexity_properties.geodetic_closure(G, S)[source]¶

Return the geodetic closure of the set of vertices \(S\) in \(G\).

The geodetic closure \(g(S)\) of a subset of vertices \(S\) of a graph \(G\) is in [HLT1993] as the set of all vertices that lie on a shortest \(u-v\) path for any pair of vertices \(u,v \in S\). We assume that \(g(\emptyset) = \emptyset\) and that \(g(\{u\}) = \{u\}\) for any \(u\) in \(G\).

Warning

This operation is not a closure function. Indeed, a closure function must satisfy the property that \(f(f(X))\) should be equal to \(f(X)\), which is not always the case here. The term closure is used here to follow the terminology of the domain. See for instance [HLT1993].

Here, we implement a simple algorithm to determine this set. Roughly, for each vertex \(u \in S\), the algorithm first performs a breadth first search from \(u\) to get distances, and then identifies the vertices of \(G\) lying on a shortest path from \(u\) to any \(v\in S\) using a reversal traversal from vertices in \(S\). This algorithm has time complexity in \(O(|S|(n + m))\) for SparseGraph, \(O(|S|(n + m) + n^2)\) for DenseGraph and space complexity in \(O(n + m)\).

INPUT:

G – a Sage graph
S – a subset of vertices of \(G\)

EXAMPLES:

The vertices of the Petersen graph can be obtained by a geodetic closure of four of its vertices:

Sage

sage: from sage.graphs.convexity_properties import geodetic_closure
sage: G = graphs.PetersenGraph()
sage: geodetic_closure(G, [0, 2, 8, 9])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Python

>>> from sage.all import *
>>> from sage.graphs.convexity_properties import geodetic_closure
>>> G = graphs.PetersenGraph()
>>> geodetic_closure(G, [Integer(0), Integer(2), Integer(8), Integer(9)])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

The vertices of a 2D grid can be obtained by a geodetic closure of two vertices:

Sage

sage: G = graphs.Grid2dGraph(4, 4)
sage: c = G.geodetic_closure([(0, 0), (3, 3)])
sage: len(c) == G.order()
True

Python

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(4), Integer(4))
>>> c = G.geodetic_closure([(Integer(0), Integer(0)), (Integer(3), Integer(3))])
>>> len(c) == G.order()
True

If two vertices belong to different connected components of a graph, their geodetic closure is trivial:

Sage

sage: G = Graph([(0, 1), (2, 3)])
sage: geodetic_closure(G, [0, 2])
[0, 2]

Python

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(2), Integer(3))])
>>> geodetic_closure(G, [Integer(0), Integer(2)])
[0, 2]

The geodetic closure does not satisfy the closure function property that \(f(f(X))\) should be equal to \(f(X)\):

Sage

sage: G = graphs.DiamondGraph()
sage: G.subdivide_edge((1, 2), 1)
sage: geodetic_closure(G, [0, 3])
[0, 1, 2, 3]
sage: geodetic_closure(G, geodetic_closure(G, [0, 3]))
[0, 1, 2, 3, 4]

Python

>>> from sage.all import *
>>> G = graphs.DiamondGraph()
>>> G.subdivide_edge((Integer(1), Integer(2)), Integer(1))
>>> geodetic_closure(G, [Integer(0), Integer(3)])
[0, 1, 2, 3]
>>> geodetic_closure(G, geodetic_closure(G, [Integer(0), Integer(3)]))
[0, 1, 2, 3, 4]

sage.graphs.convexity_properties.is_geodetic(G)[source]¶

Check whether the input (di)graph is geodetic.

A graph \(G\) is geodetic if there exists only one shortest path between every pair of its vertices. This can be checked in time \(O(nm)\) for SparseGraph and \(O(nm+n^2)\) for DenseGraph in unweighted (di)graphs with \(n\) nodes and \(m\) edges. Examples of geodetic graphs are trees, cliques and odd cycles. See the Wikipedia article Geodetic_graph for more details.

(Di)graphs with multiple edges are not considered geodetic.

INPUT:

G – a graph or a digraph

EXAMPLES:

Trees, cliques and odd cycles are geodetic:

Sage

sage: T = graphs.RandomTree(20)
sage: T.is_geodetic()
True
sage: all(graphs.CompleteGraph(n).is_geodetic() for n in range(8))
True
sage: all(graphs.CycleGraph(n).is_geodetic() for n in range(3, 16, 2))
True

Python

>>> from sage.all import *
>>> T = graphs.RandomTree(Integer(20))
>>> T.is_geodetic()
True
>>> all(graphs.CompleteGraph(n).is_geodetic() for n in range(Integer(8)))
True
>>> all(graphs.CycleGraph(n).is_geodetic() for n in range(Integer(3), Integer(16), Integer(2)))
True

Even cycles of order at least 4 are not geodetic:

Sage

sage: all(graphs.CycleGraph(n).is_geodetic() for n in range(4, 17, 2))
False

Python

>>> from sage.all import *
>>> all(graphs.CycleGraph(n).is_geodetic() for n in range(Integer(4), Integer(17), Integer(2)))
False

The Petersen graph is geodetic:

Sage

sage: P = graphs.PetersenGraph()
sage: P.is_geodetic()
True

Python

>>> from sage.all import *
>>> P = graphs.PetersenGraph()
>>> P.is_geodetic()
True

Grid graphs are not geodetic:

Sage

sage: G = graphs.Grid2dGraph(2, 3)
sage: G.is_geodetic()
False

Python

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(2), Integer(3))
>>> G.is_geodetic()
False

This method is also valid for digraphs:

Sage

sage: G = DiGraph(graphs.PetersenGraph())
sage: G.is_geodetic()
True
sage: G = digraphs.Path(5)
sage: G.add_path([0, 'a', 'b', 'c', 4])
sage: G.is_geodetic()
False

Python

>>> from sage.all import *
>>> G = DiGraph(graphs.PetersenGraph())
>>> G.is_geodetic()
True
>>> G = digraphs.Path(Integer(5))
>>> G.add_path([Integer(0), 'a', 'b', 'c', Integer(4)])
>>> G.is_geodetic()
False