Common Digraphs¶
All digraphs in Sage can be built through the digraphs
object. In order to
build a circuit on 15 elements, one can do:
sage: g = digraphs.Circuit(15)
To get a circulant graph on 10 vertices in which a vertex has
and
as outneighbors:
sage: p = digraphs.Circulant(10,[2,3])
More interestingly, one can get the list of all digraphs that Sage knows how to
build by typing digraphs.
in Sage and then hitting tab.
ButterflyGraph() |
Returns a n-dimensional butterfly graph. |
Circuit() |
Returns the circuit on ![]() |
Circulant() |
Returns a circulant digraph on ![]() |
Complete() |
Return a complete digraph on ![]() |
DeBruijn() |
Returns the De Bruijn digraph with parameters ![]() |
GeneralizedDeBruijn() |
Returns the generalized de Bruijn digraph of order ![]() ![]() |
ImaseItoh() |
Returns the digraph of Imase and Itoh of order ![]() ![]() |
Kautz() |
Returns the Kautz digraph of degree ![]() ![]() |
Path() |
Returns a directed path on ![]() |
RandomDirectedGNC() |
Returns a random GNC (growing network with copying) digraph with ![]() |
RandomDirectedGNM() |
Returns a random labelled digraph on ![]() ![]() |
RandomDirectedGNP() |
Returns a random digraph on ![]() |
RandomDirectedGN() |
Returns a random GN (growing network) digraph with ![]() |
RandomDirectedGNR() |
Returns a random GNR (growing network with redirection) digraph. |
RandomSemiComplete() |
Return a random semi-complete digraph of order ![]() |
RandomTournament() |
Returns a random tournament on ![]() |
TransitiveTournament() |
Returns a transitive tournament on ![]() |
tournaments_nauty() |
Returns all tournaments on ![]() |
AUTHORS:
- Robert L. Miller (2006)
- Emily A. Kirkman (2006)
- Michael C. Yurko (2009)
- David Coudert (2012)
Functions and methods¶
-
class
sage.graphs.digraph_generators.
DiGraphGenerators
¶ A class consisting of constructors for several common digraphs, including orderly generation of isomorphism class representatives.
A list of all graphs and graph structures in this database is available via tab completion. Type “digraphs.” and then hit tab to see which graphs are available.
The docstrings include educational information about each named digraph with the hopes that this class can be used as a reference.
The constructors currently in this class include:
Random Directed Graphs: - RandomDirectedGN - RandomDirectedGNC - RandomDirectedGNP - RandomDirectedGNM - RandomDirectedGNR - RandomTournament - RandomSemiComplete Families of Graphs: - Complete - DeBruijn - GeneralizedDeBruijn - Kautz - Path - ImaseItoh - RandomTournament - TransitiveTournament - tournaments_nauty
ORDERLY GENERATION: digraphs(vertices, property=lambda x: True, augment=’edges’, size=None)
Accesses the generator of isomorphism class representatives. Iterates over distinct, exhaustive representatives.
INPUT:
vertices
- natural numberproperty
- any property to be tested on digraphs before generation.augment
- choices:'vertices'
- augments by adding a vertex, and edges incident to that vertex. In this case, all digraphs on up to n=vertices are generated. If for any digraph G satisfying the property, every subgraph, obtained from G by deleting one vertex and only edges incident to that vertex, satisfies the property, then this will generate all digraphs with that property. If this does not hold, then all the digraphs generated will satisfy the property, but there will be some missing.'edges'
- augments a fixed number of vertices by adding one edge In this case, all digraphs on exactly n=vertices are generated. If for any graph G satisfying the property, every subgraph, obtained from G by deleting one edge but not the vertices incident to that edge, satisfies the property, then this will generate all digraphs with that property. If this does not hold, then all the digraphs generated will satisfy the property, but there will be some missing.implementation
- which underlying implementation to use (see DiGraph?)sparse
- ignored if implementation is notc_graph
EXAMPLES: Print digraphs on 2 or less vertices.
sage: for D in digraphs(2, augment='vertices'): ....: print(D) Digraph on 0 vertices Digraph on 1 vertex Digraph on 2 vertices Digraph on 2 vertices Digraph on 2 vertices
Note that we can also get digraphs with underlying Cython implementation:
sage: for D in digraphs(2, augment='vertices', implementation='c_graph'): ....: print(D) Digraph on 0 vertices Digraph on 1 vertex Digraph on 2 vertices Digraph on 2 vertices Digraph on 2 vertices
Print digraphs on 3 vertices.
sage: for D in digraphs(3): ....: print(D) Digraph on 3 vertices Digraph on 3 vertices ... Digraph on 3 vertices Digraph on 3 vertices
Generate all digraphs with 4 vertices and 3 edges.
sage: L = digraphs(4, size=3) sage: len(list(L)) 13
Generate all digraphs with 4 vertices and up to 3 edges.
sage: L = list(digraphs(4, lambda G: G.size() <= 3)) sage: len(L) 20 sage: graphs_list.show_graphs(L) # long time
Generate all digraphs with degree at most 2, up to 5 vertices.
sage: property = lambda G: ( max([G.degree(v) for v in G] + [0]) <= 2 ) sage: L = list(digraphs(5, property, augment='vertices')) sage: len(L) 75
Generate digraphs on the fly: (see http://oeis.org/classic/A000273)
sage: for i in range(5): ....: print(len(list(digraphs(i)))) 1 1 3 16 218
REFERENCE:
- Brendan D. McKay, Isomorph-Free Exhaustive generation. Journal of Algorithms Volume 26, Issue 2, February 1998, pages 306-324.
-
ButterflyGraph
(n, vertices='strings')¶ Returns a n-dimensional butterfly graph. The vertices consist of pairs (v,i), where v is an n-dimensional tuple (vector) with binary entries (or a string representation of such) and i is an integer in [0..n]. A directed edge goes from (v,i) to (w,i+1) if v and w are identical except for possibly v[i] != w[i].
A butterfly graph has
vertices and
edges.
INPUT:
vertices
- ‘strings’ (default) or ‘vectors’, specifying whether the vertices are zero-one strings or actually tuples over GF(2).
EXAMPLES:
sage: digraphs.ButterflyGraph(2).edges(labels=False) [(('00', 0), ('00', 1)), (('00', 0), ('10', 1)), (('00', 1), ('00', 2)), (('00', 1), ('01', 2)), (('01', 0), ('01', 1)), (('01', 0), ('11', 1)), (('01', 1), ('00', 2)), (('01', 1), ('01', 2)), (('10', 0), ('00', 1)), (('10', 0), ('10', 1)), (('10', 1), ('10', 2)), (('10', 1), ('11', 2)), (('11', 0), ('01', 1)), (('11', 0), ('11', 1)), (('11', 1), ('10', 2)), (('11', 1), ('11', 2))] sage: digraphs.ButterflyGraph(2,vertices='vectors').edges(labels=False) [(((0, 0), 0), ((0, 0), 1)), (((0, 0), 0), ((1, 0), 1)), (((0, 0), 1), ((0, 0), 2)), (((0, 0), 1), ((0, 1), 2)), (((0, 1), 0), ((0, 1), 1)), (((0, 1), 0), ((1, 1), 1)), (((0, 1), 1), ((0, 0), 2)), (((0, 1), 1), ((0, 1), 2)), (((1, 0), 0), ((0, 0), 1)), (((1, 0), 0), ((1, 0), 1)), (((1, 0), 1), ((1, 0), 2)), (((1, 0), 1), ((1, 1), 2)), (((1, 1), 0), ((0, 1), 1)), (((1, 1), 0), ((1, 1), 1)), (((1, 1), 1), ((1, 0), 2)), (((1, 1), 1), ((1, 1), 2))]
-
Circuit
(n)¶ Returns the circuit on
vertices
The circuit is an oriented
CycleGraph
EXAMPLES:
A circuit is the smallest strongly connected digraph:
sage: circuit = digraphs.Circuit(15) sage: len(circuit.strongly_connected_components()) == 1 True
-
Circulant
(n, integers)¶ Returns a circulant digraph on
vertices from a set of integers.
INPUT:
n
(integer) – number of vertices.integers
– the list of integers such that there is an edge fromto
if and only if
(j-i)%n in integers
.
EXAMPLES:
sage: digraphs.Circulant(13,[3,5,7]) Circulant graph ([3, 5, 7]): Digraph on 13 vertices
-
Complete
(n, loops=False)¶ Return the complete digraph on
vertices.
INPUT:
n
(integer) – number of vertices.loops
(boolean) – whether to add loops or not, i.e., edges fromto itself.
See also
EXAMPLES:
sage: n = 10 sage: G = digraphs.Complete(n); G Complete digraph: Digraph on 10 vertices sage: G.size() == n*(n-1) True sage: G = digraphs.Complete(n, loops=True); G Complete digraph with loops: Looped digraph on 10 vertices sage: G.size() == n*n True sage: digraphs.Complete(-1) Traceback (most recent call last): ... ValueError: The number of vertices cannot be strictly negative!
-
DeBruijn
(k, n, vertices='strings')¶ Returns the De Bruijn digraph with parameters
.
The De Bruijn digraph with parameters
is built upon a set of vertices equal to the set of words of length
from a dictionary of
letters.
In this digraph, there is an arc
if
can be obtained from
by removing the leftmost letter and adding a new letter at its right end. For more information, see the Wikipedia article on De Bruijn graph.
INPUT:
k
– Two possibilities for this parameter :- An integer equal to the cardinality of the alphabet to use, that is the degree of the digraph to be produced.
- An iterable object to be used as the set of letters. The degree of the resulting digraph is the cardinality of the set of letters.
n
– An integer equal to the length of words in the De Bruijn digraph whenvertices == 'strings'
, and also to the diameter of the digraph.vertices
– ‘strings’ (default) or ‘integers’, specifying whether the vertices are words build upon an alphabet or integers.
EXAMPLES:
de Bruijn digraph of degree 2 and diameter 2:
sage: db = digraphs.DeBruijn(2, 2); db De Bruijn digraph (k=2, n=2): Looped digraph on 4 vertices sage: db.order(), db.size() (4, 8) sage: db.diameter() 2
Building a de Bruijn digraph on a different alphabet:
sage: g = digraphs.DeBruijn(['a', 'b'], 2) sage: g.vertices() ['aa', 'ab', 'ba', 'bb'] sage: g.is_isomorphic(db) True sage: g = digraphs.DeBruijn(['AA', 'BB'], 2) sage: g.vertices() ['AA,AA', 'AA,BB', 'BB,AA', 'BB,BB'] sage: g.is_isomorphic(db) True
-
GeneralizedDeBruijn
(n, d)¶ Returns the generalized de Bruijn digraph of order
and degree
.
The generalized de Bruijn digraph has been defined in [RPK80] [RPK83]. It has vertex set
and there is an arc from vertex
to all vertices
such that
with
.
When
, the generalized de Bruijn digraph is isomorphic to the de Bruijn digraph of degree
and diameter
.
INPUT:
n
– is the number of vertices of the digraphd
– is the degree of the digraph
See also
sage.graphs.generic_graph.GenericGraph.is_circulant()
– checks whether a (di)graph is circulant, and/or returns all possible sets of parameters.
EXAMPLES:
sage: GB = digraphs.GeneralizedDeBruijn(8, 2) sage: GB.is_isomorphic(digraphs.DeBruijn(2, 3), certificate = True) (True, {0: '000', 1: '001', 2: '010', 3: '011', 4: '100', 5: '101', 6: '110', 7: '111'})
REFERENCES:
[RPK80] S. M. Reddy, D. K. Pradhan, and J. Kuhl. Directed graphs with minimal diameter and maximal connectivity, School Eng., Oakland Univ., Rochester MI, Tech. Rep., July 1980. [RPK83] S. Reddy, P. Raghavan, and J. Kuhl. A Class of Graphs for Processor Interconnection. IEEE International Conference on Parallel Processing, pages 154-157, Los Alamitos, Ca., USA, August 1983.
-
ImaseItoh
(n, d)¶ Returns the digraph of Imase and Itoh of order
and degree
.
The digraph of Imase and Itoh has been defined in [II83]. It has vertex set
and there is an arc from vertex
to all vertices
such that
with
.
When
, the digraph of Imase and Itoh is isomorphic to the de Bruijn digraph of degree
and diameter
. When
, the digraph of Imase and Itoh is isomorphic to the Kautz digraph [Kautz68] of degree
and diameter
.
INPUT:
n
– is the number of vertices of the digraphd
– is the degree of the digraph
EXAMPLES:
sage: II = digraphs.ImaseItoh(8, 2) sage: II.is_isomorphic(digraphs.DeBruijn(2, 3), certificate = True) (True, {0: '010', 1: '011', 2: '000', 3: '001', 4: '110', 5: '111', 6: '100', 7: '101'}) sage: II = digraphs.ImaseItoh(12, 2) sage: II.is_isomorphic(digraphs.Kautz(2, 3), certificate = True) (True, {0: '010', 1: '012', 2: '021', 3: '020', 4: '202', 5: '201', 6: '210', 7: '212', 8: '121', 9: '120', 10: '102', 11: '101'})
REFERENCE:
[II83] (1, 2) M. Imase and M. Itoh. A design for directed graphs with minimum diameter, IEEE Trans. Comput., vol. C-32, pp. 782-784, 1983.
-
Kautz
(k, D, vertices='strings')¶ Returns the Kautz digraph of degree
and diameter
.
The Kautz digraph has been defined in [Kautz68]. The Kautz digraph of degree
and diameter
has
vertices. This digraph is build upon a set of vertices equal to the set of words of length
from an alphabet of
letters such that consecutive letters are differents. There is an arc from vertex
to vertex
if
can be obtained from
by removing the leftmost letter and adding a new letter, distinct from the rightmost letter of
, at the right end.
The Kautz digraph of degree
and diameter
is isomorphic to the digraph of Imase and Itoh [II83] of degree
and order
.
See also the Wikipedia article on Kautz Graphs.
INPUT:
k
– Two possibilities for this parameter :- An integer equal to the degree of the digraph to be produced, that is the cardinality minus one of the alphabet to use.
- An iterable object to be used as the set of letters. The degree of the resulting digraph is the cardinality of the set of letters minus one.
D
– An integer equal to the diameter of the digraph, and also to- the length of a vertex label when
vertices == 'strings'
.
vertices
– ‘strings’ (default) or ‘integers’, specifying whether- the vertices are words build upon an alphabet or integers.
EXAMPLES:
sage: K = digraphs.Kautz(2, 3) sage: K.is_isomorphic(digraphs.ImaseItoh(12, 2), certificate = True) (True, {'010': 0, '012': 1, '020': 3, '021': 2, '101': 11, '102': 10, '120': 9, '121': 8, '201': 5, '202': 4, '210': 6, '212': 7}) sage: K = digraphs.Kautz([1,'a','B'], 2) sage: K.edges() [('1B', 'B1', '1'), ('1B', 'Ba', 'a'), ('1a', 'a1', '1'), ('1a', 'aB', 'B'), ('B1', '1B', 'B'), ('B1', '1a', 'a'), ('Ba', 'a1', '1'), ('Ba', 'aB', 'B'), ('a1', '1B', 'B'), ('a1', '1a', 'a'), ('aB', 'B1', '1'), ('aB', 'Ba', 'a')] sage: K = digraphs.Kautz([1,'aA','BB'], 2) sage: K.edges() [('1,BB', 'BB,1', '1'), ('1,BB', 'BB,aA', 'aA'), ('1,aA', 'aA,1', '1'), ('1,aA', 'aA,BB', 'BB'), ('BB,1', '1,BB', 'BB'), ('BB,1', '1,aA', 'aA'), ('BB,aA', 'aA,1', '1'), ('BB,aA', 'aA,BB', 'BB'), ('aA,1', '1,BB', 'BB'), ('aA,1', '1,aA', 'aA'), ('aA,BB', 'BB,1', '1'), ('aA,BB', 'BB,aA', 'aA')]
REFERENCE:
[Kautz68] (1, 2) W. H. Kautz. Bounds on directed (d, k) graphs. Theory of cellular logic networks and machines, AFCRL-68-0668, SRI Project 7258, Final Rep., pp. 20-28, 1968.
-
Path
(n)¶ Returns a directed path on
vertices.
INPUT:
n
(integer) – number of vertices in the path.
EXAMPLES:
sage: g = digraphs.Path(5) sage: g.vertices() [0, 1, 2, 3, 4] sage: g.size() 4 sage: g.automorphism_group().cardinality() 1
-
RandomDirectedGN
(n, kernel=<function <lambda>>, seed=None)¶ Returns a random GN (growing network) digraph with n vertices.
The digraph is constructed by adding vertices with a link to one previously added vertex. The vertex to link to is chosen with a preferential attachment model, i.e. probability is proportional to degree. The default attachment kernel is a linear function of degree. The digraph is always a tree, so in particular it is a directed acyclic graph.
INPUT:
n
- number of vertices.kernel
- the attachment kernelseed
- for the random number generator
EXAMPLES:
sage: D = digraphs.RandomDirectedGN(25) sage: D.edges(labels=False) [(1, 0), (2, 0), (3, 1), (4, 0), (5, 0), (6, 1), (7, 0), (8, 3), (9, 0), (10, 8), (11, 3), (12, 9), (13, 8), (14, 0), (15, 11), (16, 11), (17, 5), (18, 11), (19, 6), (20, 5), (21, 14), (22, 5), (23, 18), (24, 11)] sage: D.show() # long time
REFERENCE:
- [1] Krapivsky, P.L. and Redner, S. Organization of Growing Random Networks, Phys. Rev. E vol. 63 (2001), p. 066123.
-
RandomDirectedGNC
(n, seed=None)¶ Returns a random GNC (growing network with copying) digraph with n vertices.
The digraph is constructed by adding vertices with a link to one previously added vertex. The vertex to link to is chosen with a preferential attachment model, i.e. probability is proportional to degree. The new vertex is also linked to all of the previously added vertex’s successors.
INPUT:
n
- number of vertices.seed
- for the random number generator
EXAMPLES:
sage: D = digraphs.RandomDirectedGNC(25) sage: D.edges(labels=False) [(1, 0), (2, 0), (2, 1), (3, 0), (4, 0), (4, 1), (5, 0), (5, 1), (5, 2), (6, 0), (6, 1), (7, 0), (7, 1), (7, 4), (8, 0), (9, 0), (9, 8), (10, 0), (10, 1), (10, 2), (10, 5), (11, 0), (11, 8), (11, 9), (12, 0), (12, 8), (12, 9), (13, 0), (13, 1), (14, 0), (14, 8), (14, 9), (14, 12), (15, 0), (15, 8), (15, 9), (15, 12), (16, 0), (16, 1), (16, 4), (16, 7), (17, 0), (17, 8), (17, 9), (17, 12), (18, 0), (18, 8), (19, 0), (19, 1), (19, 4), (19, 7), (20, 0), (20, 1), (20, 4), (20, 7), (20, 16), (21, 0), (21, 8), (22, 0), (22, 1), (22, 4), (22, 7), (22, 19), (23, 0), (23, 8), (23, 9), (23, 12), (23, 14), (24, 0), (24, 8), (24, 9), (24, 12), (24, 15)] sage: D.show() # long time
REFERENCE:
- [1] Krapivsky, P.L. and Redner, S. Network Growth by Copying, Phys. Rev. E vol. 71 (2005), p. 036118.
-
RandomDirectedGNM
(n, m, loops=False)¶ Returns a random labelled digraph on
nodes and
arcs.
INPUT:
n
(integer) – number of vertices.m
(integer) – number of edges.loops
(boolean) – whether to allow loops (set toFalse
by default).
PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.
EXAMPLES:
sage: D = digraphs.RandomDirectedGNM(10, 5) sage: D.num_verts() 10 sage: D.edges(labels=False) [(0, 3), (1, 5), (5, 1), (7, 0), (8, 5)]
With loops:
sage: D = digraphs.RandomDirectedGNM(10, 100, loops = True) sage: D.num_verts() 10 sage: D.loops() [(0, 0, None), (1, 1, None), (2, 2, None), (3, 3, None), (4, 4, None), (5, 5, None), (6, 6, None), (7, 7, None), (8, 8, None), (9, 9, None)]
-
RandomDirectedGNP
(n, p, loops=False, seed=None)¶ Returns a random digraph on
nodes. Each edge is inserted independently with probability
.
INPUT:
n
– number of nodes of the digraphp
– probability of an edgeloops
– is a boolean set to True if the random digraph may have loops, and False (default) otherwise.seed
– integer seed for random number generator (default=None).
REFERENCES:
[1] P. Erdos and A. Renyi, On Random Graphs, Publ. Math. 6, 290 (1959). [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959). PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.
EXAMPLES:
sage: set_random_seed(0) sage: D = digraphs.RandomDirectedGNP(10, .2) sage: D.num_verts() 10 sage: D.edges(labels=False) [(1, 0), (1, 2), (3, 6), (3, 7), (4, 5), (4, 7), (4, 8), (5, 2), (6, 0), (7, 2), (8, 1), (8, 9), (9, 4)]
-
RandomDirectedGNR
(n, p, seed=None)¶ Returns a random GNR (growing network with redirection) digraph with n vertices and redirection probability p.
The digraph is constructed by adding vertices with a link to one previously added vertex. The vertex to link to is chosen uniformly. With probability p, the arc is instead redirected to the successor vertex. The digraph is always a tree.
INPUT:
n
- number of vertices.p
- redirection probabilityseed
- for the random number generator.
EXAMPLES:
sage: D = digraphs.RandomDirectedGNR(25, .2) sage: D.edges(labels=False) [(1, 0), (2, 0), (2, 1), (3, 0), (4, 0), (4, 1), (5, 0), (5, 1), (5, 2), (6, 0), (6, 1), (7, 0), (7, 1), (7, 4), (8, 0), (9, 0), (9, 8), (10, 0), (10, 1), (10, 2), (10, 5), (11, 0), (11, 8), (11, 9), (12, 0), (12, 8), (12, 9), (13, 0), (13, 1), (14, 0), (14, 8), (14, 9), (14, 12), (15, 0), (15, 8), (15, 9), (15, 12), (16, 0), (16, 1), (16, 4), (16, 7), (17, 0), (17, 8), (17, 9), (17, 12), (18, 0), (18, 8), (19, 0), (19, 1), (19, 4), (19, 7), (20, 0), (20, 1), (20, 4), (20, 7), (20, 16), (21, 0), (21, 8), (22, 0), (22, 1), (22, 4), (22, 7), (22, 19), (23, 0), (23, 8), (23, 9), (23, 12), (23, 14), (24, 0), (24, 8), (24, 9), (24, 12), (24, 15)] sage: D.show() # long time
REFERENCE:
- [1] Krapivsky, P.L. and Redner, S. Organization of Growing Random Networks, Phys. Rev. E vol. 63 (2001), p. 066123.
-
RandomSemiComplete
(n)¶ Return a random semi-complete digraph on
vertices.
A directed graph
is semi-complete if for any pair of vertices
and
, there is at least one arc between them.
To generate randomly a semi-complete digraph, we have to ensure, for any pair of distinct vertices
and
, that with probability
we have only arc
, with probability
we have only arc
, and with probability
we have both arc
and arc
. We do so by selecting a random integer
in
. When
we select only arc
, when
we select only arc
, and when
we select both arcs. In other words, we select arc
when
and arc
when
.
INPUT:
n
(integer) – the number of nodes
See also
EXAMPLES:
sage: SC = digraphs.RandomSemiComplete(10); SC Random Semi-Complete digraph: Digraph on 10 vertices sage: SC.size() >= binomial(10, 2) True sage: digraphs.RandomSemiComplete(-1) Traceback (most recent call last): ... ValueError: The number of vertices cannot be strictly negative!
-
RandomTournament
(n)¶ Returns a random tournament on
vertices.
For every pair of vertices, the tournament has an edge from
to
with probability
, otherwise it has an edge from
to
.
See Wikipedia article Tournament_(graph_theory)
INPUT:
n
(integer) – number of vertices.
See also
EXAMPLES:
sage: T = digraphs.RandomTournament(10); T Random Tournament: Digraph on 10 vertices sage: T.size() == binomial(10, 2) True sage: digraphs.RandomTournament(-1) Traceback (most recent call last): ... ValueError: The number of vertices cannot be strictly negative!
-
TransitiveTournament
(n)¶ Returns a transitive tournament on
vertices.
In this tournament there is an edge from
to
if
.
See Wikipedia article Tournament_(graph_theory)
INPUT:
n
(integer) – number of vertices in the tournament.
EXAMPLES:
sage: g = digraphs.TransitiveTournament(5) sage: g.vertices() [0, 1, 2, 3, 4] sage: g.size() 10 sage: g.automorphism_group().cardinality() 1
-
tournaments_nauty
(n, min_out_degree=None, max_out_degree=None, strongly_connected=False, debug=False, options='')¶ Returns all tournaments on
vertices using Nauty.
INPUT:
n
(integer) – number of vertices.min_out_degree
,max_out_degree
(integers) – if set toNone
(default), then the min/max out-degree is not constrained.debug
(boolean) – ifTrue
the first line of genbg’s output to standard error is captured and the first call to the generator’snext()
function will return this line as a string. A line leading with “>A” indicates a successful initiation of the program with some information on the arguments, while a line beginning with “>E” indicates an error with the input.options
(string) – anything else that should be forwarded as input to Nauty’s genbg. See its documentation for more information : http://cs.anu.edu.au/~bdm/nauty/.
Note
To use this method you must first install the Nauty spkg.
EXAMPLES:
sage: for g in digraphs.tournaments_nauty(4): ....: print(g.edges(labels = False)) [(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2)] [(1, 0), (1, 3), (2, 0), (2, 1), (3, 0), (3, 2)] [(0, 2), (1, 0), (2, 1), (3, 0), (3, 1), (3, 2)] [(0, 2), (0, 3), (1, 0), (2, 1), (3, 1), (3, 2)] sage: tournaments = digraphs.tournaments_nauty sage: [len(list(tournaments(x))) for x in range(1,8)] [1, 1, 2, 4, 12, 56, 456] sage: [len(list(tournaments(x, strongly_connected = True))) for x in range(1,9)] [1, 0, 1, 1, 6, 35, 353, 6008]