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:
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) # needs sage.modules sage: S.cardinality() # needs sage.modules 6
Check that the method is working even when vertices or edges are of incomparable types (see github 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
- sage.graphs.generic_graph_pyx.binary_string_from_dig6(s, n)#
A helper function for the dig6 format.
INPUT:
s
– a graph6 stringn
– the length of the binary string encoded bys
.
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'
- sage.graphs.generic_graph_pyx.binary_string_from_graph6(s, n)#
Decode a binary string from its graph6 representation
This helper function is the inverse of \(R\) from [McK2015].
INPUT:
s
– a graph6 stringn
– the length of the binary string encoded bys
.
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'
- sage.graphs.generic_graph_pyx.binary_string_to_graph6(x)#
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'
- 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. Everyreset_bound
iterations the path will be cleared and the procedure is restarted. Everybacktrack_bound
steps we discard the last five vertices and continue with the procedure. The total number of steps in the algorithm is controlled bymax_iter
. If a Hamiltonian cycle or Hamiltonian path is found it is returned. If the number of steps reachesmax_iter
then a longest path is returned. See OUTPUT for more details.INPUT:
G
– graphmax_iter
– maximum number of iterationsreset_bound
– number of iterations before restarting theprocedure
backtrack_bound
– number of iterations to elapse beforediscarding the last 5 vertices of the path.
find_path
– (default:False
) if set toTrue
, willsearch a Hamiltonian path; if
False
, will search for a Hamiltonian cycle
OUTPUT:
A pair
(B, P)
, whereB
is a Boolean andP
is a list of vertices.If
B
isTrue
andfind_path
isFalse
,P
represents a Hamiltonian cycle.If
B
isTrue
andfind_path
isTrue
,P
represents a Hamiltonian path.If
B
isFalse
, thenP
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)
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: 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)
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)
- 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.layout_split(layout_function, G, **options)#
Graph each component of
G
separately withlayout_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...]}
AUTHOR:
Robert Bradshaw
- sage.graphs.generic_graph_pyx.length_and_string_from_graph6(s)#
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?_@@??@??????')
- sage.graphs.generic_graph_pyx.small_integer_to_graph6(n)#
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'
- 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 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
- 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