GenericGraph Cython functions

AUTHORS:

  • Robert L. Miller (2007-02-13): initial version
  • Robert W. Bradshaw (2007-03-31): fast spring layout algorithms
  • Nathann Cohen : exhaustive search
class sage.graphs.generic_graph_pyx.GenericGraph_pyx

Bases: sage.structure.sage_object.SageObject

class sage.graphs.generic_graph_pyx.SubgraphSearch

Bases: object

This class implements methods to exhaustively search for copies of a graph \(H\) in a larger graph \(G\).

It is possible to look for induced subgraphs instead, and to iterate or count the number of their occurrences.

ALGORITHM:

The algorithm is a brute-force search. Let \(V(H) = \{h_1,\dots,h_k\}\). It first tries to find in \(G\) a possible representative of \(h_1\), then a representative of \(h_2\) compatible with \(h_1\), then a representative of \(h_3\) compatible with the first two, etc.

This way, most of the time we need to test far less than \(k! \binom{|V(G)|}{k}\) subsets, and hope this brute-force technique can sometimes be useful.

Note

This algorithm does not take vertex/edge labels into account.

cardinality()

Returns the number of labelled subgraphs of \(G\) isomorphic to \(H\).

Note

This method counts the subgraphs by enumerating them all ! Hence it probably is not a good idea to count their number before enumerating them :-)

EXAMPLES:

Counting the number of labelled \(P_3\) in \(P_5\):

sage: from sage.graphs.generic_graph_pyx import SubgraphSearch
sage: g = graphs.PathGraph(5)
sage: h = graphs.PathGraph(3)
sage: S = SubgraphSearch(g, h)
sage: S.cardinality()
6
next()

x.next() -> the next value, or raise StopIteration

sage.graphs.generic_graph_pyx.binary_string_from_dig6(s, n)

A helper function for the dig6 format.

INPUT:

  • s – a graph6 string
  • n – the length of the binary string encoded by s.

EXAMPLES:

sage: from sage.graphs.generic_graph_pyx import binary_string_from_dig6
sage: binary_string_from_dig6('?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?', 63)
'0000000000000000000000000000001000000000010000000001000010000000000000000000110000000000000000010100000010000000000001000000000010000000000...10000000000000000000000000000000010000000001011011000000100000000001001110000000000000000000000000001000010010000001100000001000000001000000000100000000'
sage: binary_string_from_dig6('???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????', 32)
'0000000000000000000001000000000000010000100000100000001000000000000000100000000100000...010000000000000100010000001000000000000000000000000000001010000000001011000000000000010010000000000000010000000000100000000001000001000000000000000001000000000000000000000000000000000000'
sage.graphs.generic_graph_pyx.binary_string_from_graph6(s, n)

Decodes a binary string from its graph6 representation

This helper function is the inverse of \(R\) from [McK].

INPUT:

  • s – a graph6 string
  • n – the length of the binary string encoded by s.

EXAMPLES:

sage: from sage.graphs.generic_graph_pyx import binary_string_from_graph6
sage: binary_string_from_graph6('?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?', 63)
'0000000000000000000000000000001000000000010000000001000010000000000000000000110000000000000000010100000010000000000001000000000010000000000...10000000000000000000000000000000010000000001011011000000100000000001001110000000000000000000000000001000010010000001100000001000000001000000000100000000'
sage: binary_string_from_graph6('???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????', 32)
'0000000000000000000001000000000000010000100000100000001000000000000000100000000100000...010000000000000100010000001000000000000000000000000000001010000000001011000000000000010010000000000000010000000000100000000001000001000000000000000001000000000000000000000000000000000000'
sage.graphs.generic_graph_pyx.binary_string_to_graph6(x)

Transforms a binary string into its graph6 representation.

This helper function is named \(R\) in [McK].

INPUT:

  • x – a binary string.

EXAMPLES:

sage: from sage.graphs.generic_graph_pyx import binary_string_to_graph6
sage: binary_string_to_graph6('110111010110110010111000001100000001000000001')
'vUqwK@?G'

REFERENCES:

[McK](1, 2, 3, 4) McKay, Brendan. ‘Description of graph6 and sparse6 encodings.’ http://cs.anu.edu.au/~bdm/data/formats.txt (2007-02-13)
sage.graphs.generic_graph_pyx.find_hamiltonian(G, max_iter=100000, reset_bound=30000, backtrack_bound=1000, find_path=False)

Randomized backtracking for finding Hamiltonian cycles and paths.

ALGORITHM:

A path P is maintained during the execution of the algorithm. Initially the path will contain an edge of the graph. Every 10 iterations the path is reversed. Every reset_bound iterations the path will be cleared and the procedure is restarted. Every backtrack_bound steps we discard the last five vertices and continue with the procedure. The total number of steps in the algorithm is controlled by max_iter. If a Hamiltonian cycle or Hamiltonian path is found it is returned. If the number of steps reaches max_iter then a longest path is returned. See OUTPUT for more details.

INPUT:

  • G – graph
  • max_iter – maximum number of iterations
  • reset_bound – number of iterations before restarting the
    procedure
  • backtrack_bound – number of iterations to elapse before
    discarding the last 5 vertices of the path.
  • find_path – (default: False) if set to True, will
    search a Hamiltonian path; if False, will search for a Hamiltonian cycle

OUTPUT:

A pair (B, P), where B is a Boolean and P is a list of vertices.

  • If B is True and find_path is False, P represents a Hamiltonian cycle.
  • If B is True and find_path is True, P represents a Hamiltonian path.
  • If B is False, then P represents the longest path found during the execution of the algorithm.

Warning

May loop endlessly when run on a graph with vertices of degree 1.

EXAMPLES:

First we try the algorithm in the Dodecahedral graph, which is Hamiltonian, so we are able to find a Hamiltonian cycle and a Hamiltonian path:

sage: from sage.graphs.generic_graph_pyx import find_hamiltonian as fh
sage: G=graphs.DodecahedralGraph()
sage: fh(G)
(True, [12, 11, 10, 9, 13, 14, 15, 5, 4, 3, 2, 6, 7, 8, 1, 0, 19, 18, 17, 16])
sage: fh(G,find_path=True)
(True, [10, 0, 19, 3, 4, 5, 15, 16, 17, 18, 11, 12, 13, 9, 8, 1, 2, 6, 7, 14])

Another test, now in the Möbius-Kantor graph which is also Hamiltonian, as in our previous example, we are able to find a Hamiltonian cycle and path:

sage: G=graphs.MoebiusKantorGraph()
sage: fh(G)
(True, [15, 10, 2, 3, 4, 5, 13, 8, 11, 14, 6, 7, 0, 1, 9, 12])
sage: fh(G,find_path=True)
(True, [10, 15, 7, 6, 5, 4, 12, 9, 14, 11, 3, 2, 1, 0, 8, 13])

Now, we try the algorithm on a non Hamiltonian graph, the Petersen graph. This graph is known to be hypohamiltonian, so a Hamiltonian path can be found:

sage: G=graphs.PetersenGraph()
sage: fh(G)
(False, [9, 4, 0, 1, 6, 8, 5, 7, 2, 3])
sage: fh(G,find_path=True)
(True, [7, 2, 1, 0, 5, 8, 6, 9, 4, 3])

We now show the algorithm working on another known hypohamiltonian graph, the generalized Petersen graph with parameters 11 and 2:

sage: G=graphs.GeneralizedPetersenGraph(11,2)
sage: fh(G)
(False, [7, 8, 9, 10, 0, 1, 2, 3, 14, 12, 21, 19, 17, 6, 5, 4, 15, 13, 11, 20, 18, 16])
sage: fh(G,find_path=True)
(True, [2, 1, 12, 21, 10, 0, 11, 13, 15, 17, 19, 8, 7, 6, 5, 4, 3, 14, 16, 18, 20, 9])

Finally, an example on a graph which does not have a Hamiltonian path:

sage: G=graphs.HyperStarGraph(5,2)
sage: fh(G,find_path=False)
(False, ['00110', '10100', '01100', '11000', '01010', '10010', '00011', '10001', '00101'])
sage: fh(G,find_path=True)
(False, ['01001', '10001', '00101', '10100', '00110', '10010', '01010', '11000', '01100'])
sage.graphs.generic_graph_pyx.int_to_binary_string(n)

A quick python int to binary string conversion.

INPUT:

  • n (integer)

EXAMPLES:

sage: sage.graphs.generic_graph_pyx.int_to_binary_string(389)
'110000101'
sage: Integer(389).binary()
'110000101'
sage: sage.graphs.generic_graph_pyx.int_to_binary_string(2007)
'11111010111'
sage.graphs.generic_graph_pyx.length_and_string_from_graph6(s)

Returns a pair (length,graph6_string) from a graph6 string of unknown length.

This helper function is the inverse of \(N\) from [McK].

INPUT:

  • s – a graph6 string describing an binary vector (and encoding its length).

EXAMPLES:

sage: from sage.graphs.generic_graph_pyx import length_and_string_from_graph6
sage: length_and_string_from_graph6('~??~?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?')
(63, '?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?')
sage: length_and_string_from_graph6('_???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????')
(32, '???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????')
sage.graphs.generic_graph_pyx.small_integer_to_graph6(n)

Encodes a small integer (i.e. a number of vertices) as a graph6 string.

This helper function is named \(N\) [McK].

INPUT:

  • n (integer)

EXAMPLES:

sage: from sage.graphs.generic_graph_pyx import small_integer_to_graph6
sage: small_integer_to_graph6(13)
'L'
sage: small_integer_to_graph6(136)
'~?AG'
sage.graphs.generic_graph_pyx.spring_layout_fast(G, iterations=50, dim=2, vpos=None, rescale=True, height=False, by_component=False, **options)

Spring force model layout

This function primarily acts as a wrapper around run_spring(), converting to and from raw C types.

This kind of speed cannot be achieved by naive Cythonification of the function alone, especially if we require a function call (let alone an object creation) every time we want to add a pair of doubles.

INPUT:

  • by_component – a boolean

EXAMPLES:

sage: G = graphs.DodecahedralGraph()
sage: for i in range(10): G.add_cycle(list(range(100*i, 100*i+3)))
sage: from sage.graphs.generic_graph_pyx import spring_layout_fast
sage: pos = spring_layout_fast(G)
sage: pos[0]  # random
[0.00..., 0.03...]
sage: sorted(pos.keys()) == sorted(G)
True

With split=True, each component of G is layed out separately, placing them adjacent to each other. This is done because on a disconnected graph, the spring layout will push components further and further from each other without bound, resulting in very tight clumps for each component.

If the axis are scaled to fit the plot in a square, the horizontal distance may end up being “squished” due to the several adjacent components.

sage: G = graphs.DodecahedralGraph()
sage: for i in range(10): G.add_cycle(list(range(100*i, 100*i+3)))
sage: from sage.graphs.generic_graph_pyx import spring_layout_fast
sage: pos = spring_layout_fast(G, by_component = True)
sage: pos[0]  # random
[2.21..., -0.00...]
sage: len(pos) == G.order()
True
sage.graphs.generic_graph_pyx.spring_layout_fast_split(G, **options)

Graph each component of G separately, placing them adjacent to each other.

This is done because on a disconnected graph, the spring layout will push components further and further from each other without bound, resulting in very tight clumps for each component.

Note

If the axis are scaled to fit the plot in a square, the horizontal distance may end up being “squished” due to the several adjacent components.

EXAMPLES:

sage: G = graphs.DodecahedralGraph()
sage: for i in range(10): G.add_cycle(list(range(100*i, 100*i+3)))
sage: from sage.graphs.generic_graph_pyx import spring_layout_fast_split
sage: D = spring_layout_fast_split(G); D  # random
{0: [0.77..., 0.06...],
 ...
 902: [3.13..., 0.22...]}

AUTHOR:

Robert Bradshaw

sage.graphs.generic_graph_pyx.transitive_reduction_acyclic(G)

Return the transitive reduction of an acyclic digraph.

INPUT:

  • G – an acyclic digraph.

EXAMPLES:

sage: from sage.graphs.generic_graph_pyx import transitive_reduction_acyclic
sage: G = posets.BooleanLattice(4).hasse_diagram()
sage: G == transitive_reduction_acyclic(G.transitive_closure())
True