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[source]

Bases: SageObject

class sage.graphs.generic_graph_pyx.SubgraphSearch[source]

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()[source]

Return 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)                                              # needs sage.modules
sage: S.cardinality()                                                       # needs sage.modules
6

>>> from sage.all import *
>>> from sage.graphs.generic_graph_pyx import SubgraphSearch
>>> g = graphs.PathGraph(Integer(5))
>>> h = graphs.PathGraph(Integer(3))
>>> S = SubgraphSearch(g, h)                                              # needs sage.modules
>>> S.cardinality()                                                       # needs sage.modules
6

from sage.graphs.generic_graph_pyx import SubgraphSearch
g = graphs.PathGraph(5)
h = graphs.PathGraph(3)
S = SubgraphSearch(g, h)                                              # needs sage.modules
S.cardinality()                                                       # needs sage.modules

Check that the method is working even when vertices or edges are of incomparable types (see Issue #35904):

sage: from sage.graphs.generic_graph_pyx import SubgraphSearch
sage: G = Graph()
sage: G.add_cycle(['A', 1, 2, 3, ('a', 1)])
sage: H = Graph()
sage: H.add_path("xyz")
sage: S = SubgraphSearch(G, H)                                              # needs sage.modules
sage: S.cardinality()                                                       # needs sage.modules
10

>>> from sage.all import *
>>> from sage.graphs.generic_graph_pyx import SubgraphSearch
>>> G = Graph()
>>> G.add_cycle(['A', Integer(1), Integer(2), Integer(3), ('a', Integer(1))])
>>> H = Graph()
>>> H.add_path("xyz")
>>> S = SubgraphSearch(G, H)                                              # needs sage.modules
>>> S.cardinality()                                                       # needs sage.modules
10

from sage.graphs.generic_graph_pyx import SubgraphSearch
G = Graph()
G.add_cycle(['A', 1, 2, 3, ('a', 1)])
H = Graph()
H.add_path("xyz")
S = SubgraphSearch(G, H)                                              # needs sage.modules
S.cardinality()                                                       # needs sage.modules
sage.graphs.generic_graph_pyx.binary_string_from_dig6(s, n)[source]

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: d6 = '?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O?????'
sage: d6 += '?G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?'
sage: d6 += 'CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???'
sage: d6 += 'O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_'
sage: d6 += 'C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G'
sage: d6 += '@A??O??_?A?????O@Z?_@M????GQ@_G@?C?'
sage: binary_string_from_dig6(d6, 63)
'0000000000000000000000000000001000000000010000000001000010000000000000000000110000000000000000010100000010000000000001000000000010000000000...10000000000000000000000000000000010000000001011011000000100000000001001110000000000000000000000000001000010010000001100000001000000001000000000100000000'
sage: d6 = '???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG??'
sage: d6 += '??I?J??Q??O?_@@??@??????'
sage: binary_string_from_dig6(d6, 32)
'0000000000000000000001000000000000010000100000100000001000000000000000100000000100000...010000000000000100010000001000000000000000000000000000001010000000001011000000000000010010000000000000010000000000100000000001000001000000000000000001000000000000000000000000000000000000'

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

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

Decode a binary string from its graph6 representation.

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

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: g6 = '?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O?????'
sage: g6 += '?G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?'
sage: g6 += 'CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???'
sage: g6 += 'O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_'
sage: g6 += 'C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G'
sage: g6 += '@A??O??_?A?????O@Z?_@M????GQ@_G@?C?'
sage: binary_string_from_graph6(g6, 63)
'0000000000000000000000000000001000000000010000000001000010000000000000000000110000000000000000010100000010000000000001000000000010000000000...10000000000000000000000000000000010000000001011011000000100000000001001110000000000000000000000000001000010010000001100000001000000001000000000100000000'
sage: g6 = '???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG??'
sage: g6 += '??I?J??Q??O?_@@??@??????'
sage: binary_string_from_graph6(g6, 32)
'0000000000000000000001000000000000010000100000100000001000000000000000100000000100000...010000000000000100010000001000000000000000000000000000001010000000001011000000000000010010000000000000010000000000100000000001000001000000000000000001000000000000000000000000000000000000'

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

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

Transform a binary string into its graph6 representation.

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

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'

>>> from sage.all import *
>>> from sage.graphs.generic_graph_pyx import binary_string_to_graph6
>>> binary_string_to_graph6('110111010110110010111000001100000001000000001')
'vUqwK@?G'

from sage.graphs.generic_graph_pyx import binary_string_to_graph6
binary_string_to_graph6('110111010110110010111000001100000001000000001')
sage.graphs.generic_graph_pyx.find_hamiltonian(G, max_iter=100000, reset_bound=30000, backtrack_bound=1000, find_path=False)[source]

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 – boolean (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:

For demonstration purposes we fix a random seed:

sage: set_random_seed(0)

>>> from sage.all import *
>>> set_random_seed(Integer(0))

set_random_seed(0)

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

>>> from sage.all import *
>>> from sage.graphs.generic_graph_pyx import find_hamiltonian as fh
>>> G=graphs.DodecahedralGraph()
>>> fh(G)
(True, [12, 11, 10, 9, 13, 14, 15, 5, 4, 3, 2, 6, 7, 8, 1, 0, 19, 18, 17, 16])
>>> 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])

from sage.graphs.generic_graph_pyx import find_hamiltonian as fh
G=graphs.DodecahedralGraph()
fh(G)
fh(G,find_path=True)

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

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

G=graphs.MoebiusKantorGraph()
fh(G)
fh(G,find_path=True)

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

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

G=graphs.PetersenGraph()
fh(G)
fh(G,find_path=True)

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

>>> from sage.all import *
>>> G=graphs.GeneralizedPetersenGraph(Integer(11),Integer(2))
>>> 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])
>>> 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])

G=graphs.GeneralizedPetersenGraph(11,2)
fh(G)
fh(G,find_path=True)

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

sage: G = graphs.HyperStarGraph(5, 2)
sage: G.order()
10
sage: b, P = fh(G,find_path=False)
sage: b, len(P)
(False, 9)
sage: b, P = fh(G,find_path=True)
sage: b, len(P)
(False, 9)

>>> from sage.all import *
>>> G = graphs.HyperStarGraph(Integer(5), Integer(2))
>>> G.order()
10
>>> b, P = fh(G,find_path=False)
>>> b, len(P)
(False, 9)
>>> b, P = fh(G,find_path=True)
>>> b, len(P)
(False, 9)

G = graphs.HyperStarGraph(5, 2)
G.order()
b, P = fh(G,find_path=False)
b, len(P)
b, P = fh(G,find_path=True)
b, len(P)

The method can also be used for directed graphs:

sage: G = DiGraph([(0, 1), (1, 2), (2, 3)])
sage: fh(G)
(False, [0, 1, 2, 3])
sage: G = G.reverse()
sage: fh(G)
(False, [3, 2, 1, 0])
sage: G = DiGraph()
sage: G.add_cycle([0, 1, 2, 3, 4, 5])
sage: b, P = fh(G)
sage: b, len(P)
(True, 6)

>>> from sage.all import *
>>> G = DiGraph([(Integer(0), Integer(1)), (Integer(1), Integer(2)), (Integer(2), Integer(3))])
>>> fh(G)
(False, [0, 1, 2, 3])
>>> G = G.reverse()
>>> fh(G)
(False, [3, 2, 1, 0])
>>> G = DiGraph()
>>> G.add_cycle([Integer(0), Integer(1), Integer(2), Integer(3), Integer(4), Integer(5)])
>>> b, P = fh(G)
>>> b, len(P)
(True, 6)

G = DiGraph([(0, 1), (1, 2), (2, 3)])
fh(G)
G = G.reverse()
fh(G)
G = DiGraph()
G.add_cycle([0, 1, 2, 3, 4, 5])
b, P = fh(G)
b, len(P)
sage.graphs.generic_graph_pyx.int_to_binary_string(n)[source]

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'

>>> from sage.all import *
>>> sage.graphs.generic_graph_pyx.int_to_binary_string(Integer(389))
'110000101'
>>> Integer(Integer(389)).binary()
'110000101'
>>> sage.graphs.generic_graph_pyx.int_to_binary_string(Integer(2007))
'11111010111'

sage.graphs.generic_graph_pyx.int_to_binary_string(389)
Integer(389).binary()
sage.graphs.generic_graph_pyx.int_to_binary_string(2007)
sage.graphs.generic_graph_pyx.layout_split(layout_function, G, **options)[source]

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

This is done because several layout methods need the input graph to be connected. For instance, 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 layout_split, spring_layout_fast
sage: D = layout_split(spring_layout_fast, G); D  # random
{0: [0.77..., 0.06...],
 ...
 902: [3.13..., 0.22...]}

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

G = graphs.DodecahedralGraph()
for i in range(10): G.add_cycle(list(range(100*i, 100*i+3)))
from sage.graphs.generic_graph_pyx import layout_split, spring_layout_fast
D = layout_split(spring_layout_fast, G); D  # random

AUTHOR:

Robert Bradshaw

sage.graphs.generic_graph_pyx.length_and_string_from_graph6(s)[source]

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

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

INPUT:

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

EXAMPLES:

sage: from sage.graphs.generic_graph_pyx import length_and_string_from_graph6
sage: g6 = '~??~?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O?'
sage: g6 += '?????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?C'
sage: g6 += 'C?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@E'
sage: g6 += 'G???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAA'
sage: g6 += 'Cd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?'
sage: g6 += 'aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?'
sage: length_and_string_from_graph6(g6)
(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: g6 = '_???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG?'
sage: g6 += '???I?J??Q??O?_@@??@??????'
sage: length_and_string_from_graph6(g6)
(32, '???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????')

>>> from sage.all import *
>>> from sage.graphs.generic_graph_pyx import length_and_string_from_graph6
>>> g6 = '~??~?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O?'
>>> g6 += '?????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?C'
>>> g6 += 'C?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@E'
>>> g6 += 'G???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAA'
>>> g6 += 'Cd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?'
>>> g6 += 'aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?'
>>> length_and_string_from_graph6(g6)
(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?')
>>> g6 = '_???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG?'
>>> g6 += '???I?J??Q??O?_@@??@??????'
>>> length_and_string_from_graph6(g6)
(32, '???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????')

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

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

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

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'

>>> from sage.all import *
>>> from sage.graphs.generic_graph_pyx import small_integer_to_graph6
>>> small_integer_to_graph6(Integer(13))
'L'
>>> small_integer_to_graph6(Integer(136))
'~?AG'

from sage.graphs.generic_graph_pyx import small_integer_to_graph6
small_integer_to_graph6(13)
small_integer_to_graph6(136)
sage.graphs.generic_graph_pyx.spring_layout_fast(G, iterations=50, dim=2, vpos=None, rescale=True, height=False, by_component=False, **options)[source]

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

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

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

With split=True, each component of G is laid 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

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

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

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

>>> from sage.all import *
>>> from sage.graphs.generic_graph_pyx import transitive_reduction_acyclic
>>> G = posets.BooleanLattice(Integer(4)).hasse_diagram()
>>> G == transitive_reduction_acyclic(G.transitive_closure())
True

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