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
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
- sage.graphs.generic_graph_pyx.binary_string_from_dig6(s, n)[source]¶
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'
>>> 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'
- 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 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'
>>> 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'
- 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'
- 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. 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 the procedurebacktrack_bound
– number of iterations to elapse before discarding the last 5 vertices of the pathfind_path
– boolean (default:False
); if set toTrue
, will search a Hamiltonian path. IfFalse
, 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)
>>> from sage.all import * >>> set_random_seed(Integer(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])
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])
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])
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])
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)
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)
- 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.layout_split(layout_function, G, **options)[source]¶
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...]}
>>> 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...]}
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?_@@??@??????')
- 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'
- 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
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
- 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