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 \(i\) has \(i+2\) and \(i+3\) 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() 
Return a \(n\)dimensional butterfly graph. 
Circuit() 
Return the circuit on \(n\) vertices. 
Circulant() 
Return a circulant digraph on \(n\) vertices from a set of integers. 
Complete() 
Return a complete digraph on \(n\) vertices. 
DeBruijn() 
Return the De Bruijn digraph with parameters \(k,n\). 
GeneralizedDeBruijn() 
Return the generalized de Bruijn digraph of order \(n\) and degree \(d\). 
ImaseItoh() 
Return the digraph of Imase and Itoh of order \(n\) and degree \(d\). 
Kautz() 
Return the Kautz digraph of degree \(d\) and diameter \(D\). 
nauty_directg() 
Return an iterator yielding digraphs using nauty’s directg program. 
Paley() 
Return a Paley digraph on \(q\) vertices. 
Path() 
Return a directed path on \(n\) vertices. 
RandomDirectedGNC() 
Returns a random GNC (growing network with copying) digraph with \(n\) vertices. 
RandomDirectedGNM() 
Returns a random labelled digraph on \(n\) nodes and \(m\) arcs. 
RandomDirectedGNP() 
Returns a random digraph on \(n\) nodes. 
RandomDirectedGN() 
Returns a random GN (growing network) digraph with \(n\) vertices. 
RandomDirectedGNR() 
Returns a random GNR (growing network with redirection) digraph. 
RandomSemiComplete() 
Return a random semicomplete digraph of order \(n\). 
RandomTournament() 
Return a random tournament on \(n\) vertices. 
TransitiveTournament() 
Return a transitive tournament on \(n\) vertices. 
tournaments_nauty() 
Iterator over all tournaments on \(n\) vertices using Nauty. 
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 number orNone
to infinitely generate bigger and bigger digraphs.property
 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, IsomorphFree Exhaustive generation. Journal of Algorithms Volume 26, Issue 2, February 1998, pages 306324.

ButterflyGraph
(n, vertices='strings')¶ Return 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 when \(v[i] \neq w[i]\).
A butterfly graph has \((2^n)(n+1)\) vertices and \(n2^{n+1}\) edges.
INPUT:
n
– integer;vertices
– string (default:'strings'
); specifies whether the vertices are zeroone strings (default) or tuples over GF(2) (vertices='vectors'
)
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)¶ Return the circuit on \(n\) 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)¶ Return a circulant digraph on \(n\) vertices from a set of integers.
INPUT:
n
– integer; number of verticesintegers
– iterable container (list, set, etc.) of integers such that there is an edge from \(i\) to \(j\) if and only if(ji)%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 \(n\) vertices.
INPUT:
n
– integer; number of verticesloops
– boolean (default:False
); whether to add loops or not, i.e., edges from \(u\) to itself
See also
EXAMPLES:
sage: n = 10 sage: G = digraphs.Complete(n); G Complete digraph: Digraph on 10 vertices sage: G.size() == n*(n1) 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')¶ Return the De Bruijn digraph with parameters \(k,n\).
The De Bruijn digraph with parameters \(k,n\) is built upon a set of vertices equal to the set of words of length \(n\) from a dictionary of \(k\) letters.
In this digraph, there is an arc \(w_1w_2\) if \(w_2\) can be obtained from \(w_1\) by removing the leftmost letter and adding a new letter at its right end. For more information, see the Wikipedia article 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
– integer; length of words in the De Bruijn digraph whenvertices == 'strings'
, and also the diameter of the digraph.vertices
– string (default:'strings'
); whether the vertices are words over an alphabet (default) or integers (vertices='string'
)
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)¶ Return the generalized de Bruijn digraph of order \(n\) and degree \(d\).
The generalized de Bruijn digraph was defined in [RPK1980] [RPK1983]. It has vertex set \(V=\{0, 1,..., n1\}\) and there is an arc from vertex \(u \in V\) to all vertices \(v \in V\) such that \(v \equiv (u*d + a) \mod{n}\) with \(0 \leq a < d\).
When \(n = d^{D}\), the generalized de Bruijn digraph is isomorphic to the de Bruijn digraph of degree \(d\) and diameter \(D\).
INPUT:
n
– integer; number of vertices of the digraph (must be at least one)d
– integer; degree of the digraph (must be at least one)
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'})

ImaseItoh
(n, d)¶ Return the ImaseItoh digraph of order \(n\) and degree \(d\).
The ImaseItoh digraph was defined in [II1983]. It has vertex set \(V=\{0, 1,..., n1\}\) and there is an arc from vertex \(u \in V\) to all vertices \(v \in V\) such that \(v \equiv (u*da1) \mod{n}\) with \(0 \leq a < d\).
When \(n = d^{D}\), the ImaseItoh digraph is isomorphic to the de Bruijn digraph of degree \(d\) and diameter \(D\). When \(n = d^{D1}(d+1)\), the ImaseItoh digraph is isomorphic to the Kautz digraph [Kau1968] of degree \(d\) and diameter \(D\).
INPUT:
n
– integer; number of vertices of the digraph (must be greater than or equal to two)d
– integer; degree of the digraph (must be greater than or equal to one)
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: b,D = II.is_isomorphic(digraphs.Kautz(2, 3), certificate=True) sage: b True sage: D # random isomorphism {0: '202', 1: '201', 2: '210', 3: '212', 4: '121', 5: '120', 6: '102', 7: '101', 8: '010', 9: '012', 10: '021', 11: '020'}

Kautz
(k, D, vertices='strings')¶ Return the Kautz digraph of degree \(d\) and diameter \(D\).
The Kautz digraph has been defined in [Kau1968]. The Kautz digraph of degree \(d\) and diameter \(D\) has \(d^{D1}(d+1)\) vertices. This digraph is built from a set of vertices equal to the set of words of length \(D\) over an alphabet of \(d+1\) letters such that consecutive letters are different. There is an arc from vertex \(u\) to vertex \(v\) if \(v\) can be obtained from \(u\) by removing the leftmost letter and adding a new letter, distinct from the rightmost letter of \(u\), at the right end.
The Kautz digraph of degree \(d\) and diameter \(D\) is isomorphic to the ImaseItoh digraph [II1983] of degree \(d\) and order \(d^{D1}(d+1)\).
See the Wikipedia article Kautz_graph for more information.
INPUT:
k
– two possibilities for this parameter. In either case the degree must be at least one: An integer equal to the degree of the digraph to be produced, that is, the cardinality of the alphabet to be used minus one.
 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
– integer; diameter of the digraph, and length of a vertex label whenvertices == 'strings'
(must be at least one)vertices
– string (default:'strings'
); whether the vertices are words over an alphabet (default) or integers (vertices='strings'
)
EXAMPLES:
sage: K = digraphs.Kautz(2, 3) sage: b,D = K.is_isomorphic(digraphs.ImaseItoh(12, 2), certificate=True) sage: b True sage: D # random isomorphism {'010': 8, '012': 9, '020': 11, '021': 10, '101': 7, '102': 6, '120': 5, '121': 4, '201': 1, '202': 0, '210': 2, '212': 3} 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')]

Paley
(q)¶ Return a Paley digraph on \(q\) vertices.
Parameter \(q\) must be the power of a prime number and congruent to 3 mod 4.
EXAMPLES:
A Paley digraph has \(n * (n1) / 2\) edges, its underlying graph is a clique, and so it is a tournament:
sage: g = digraphs.Paley(7); g Paley digraph with parameter 7: Digraph on 7 vertices sage: g.size() == g.order() * (g.order()  1) / 2 True sage: g.to_undirected().is_clique() True
A Paley digraph is always selfcomplementary:
sage: g.complement().is_isomorphic(g) True

Path
(n)¶ Return a directed path on \(n\) 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 kernel.seed
 arandom.Random
seed or a Pythonint
for the random number generator (default:None
).
EXAMPLES:
sage: D = digraphs.RandomDirectedGN(25) sage: D.edges(labels=False) [(1, 0), (2, 0), (3, 2), (4, 2), (5, 4), (6, 3), (7, 0), (8, 4), (9, 4), (10, 3), (11, 4), (12, 4), (13, 3), (14, 4), (15, 4), (16, 0), (17, 2), (18, 4), (19, 6), (20, 14), (21, 4), (22, 0), (23, 22), (24, 14)] # 32bit [(1, 0), (2, 1), (3, 0), (4, 2), (5, 0), (6, 2), (7, 3), (8, 2), (9, 3), (10, 4), (11, 5), (12, 9), (13, 2), (14, 2), (15, 5), (16, 2), (17, 15), (18, 1), (19, 5), (20, 2), (21, 5), (22, 1), (23, 5), (24, 14)] # 64bit 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
 arandom.Random
seed or a Pythonint
for the random number generator (default:None
).
EXAMPLES:
sage: D = digraphs.RandomDirectedGNC(25) sage: D.is_directed_acyclic() True sage: D.topological_sort() [24, 23, ..., 1, 0] 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 \(n\) nodes and \(m\) 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 springlayout 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 \(n\) nodes. Each edge is inserted independently with probability \(p\).
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 springlayout 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 probability.seed
 arandom.Random
seed or a Pythonint
for the random number generator (default:None
).
EXAMPLES:
sage: D = digraphs.RandomDirectedGNR(25, .2) sage: D.is_directed_acyclic() True sage: D.to_undirected().is_tree() True 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 semicomplete digraph on \(n\) vertices.
A directed graph \(G=(V,E)\) is semicomplete if for any pair of vertices \(u\) and \(v\), there is at least one arc between them.
To generate randomly a semicomplete digraph, we have to ensure, for any pair of distinct vertices \(u\) and \(v\), that with probability \(1/3\) we have only arc \(uv\), with probability \(1/3\) we have only arc \(vu\), and with probability \(1/3\) we have both arc \(uv\) and arc \(vu\). We do so by selecting a random integer \(coin\) in \([1,3]\). When \(coin==1\) we select only arc \(uv\), when \(coin==3\) we select only arc \(vu\), and when \(coin==2\) we select both arcs. In other words, we select arc \(uv\) when \(coin\leq 2\) and arc \(vu\) when \(coin\geq 2\).
INPUT:
n
(integer) – the number of nodes
See also
EXAMPLES:
sage: SC = digraphs.RandomSemiComplete(10); SC Random SemiComplete 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)¶ Return a random tournament on \(n\) vertices.
For every pair of vertices, the tournament has an edge from \(i\) to \(j\) with probability \(1/2\), otherwise it has an edge from \(j\) to \(i\).
INPUT:
n
– integer; number of vertices
EXAMPLES:
sage: T = digraphs.RandomTournament(10); T Random Tournament: Digraph on 10 vertices sage: T.size() == binomial(10, 2) True sage: T.is_tournament() True sage: digraphs.RandomTournament(1) Traceback (most recent call last): ... ValueError: the number of vertices cannot be strictly negative

TransitiveTournament
(n)¶ Return a transitive tournament on \(n\) vertices.
In this tournament there is an edge from \(i\) to \(j\) if \(i<j\).
See the Wikipedia article Tournament_(graph_theory) for more information.
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

nauty_directg
(graphs, options='', debug=False)¶ Return an iterator yielding digraphs using nauty’s
directg
program.Description from directg –help: Read undirected graphs and orient their edges in all possible ways. Edges can be oriented in either or both directions (3 possibilities). Isomorphic directed graphs derived from the same input are suppressed. If the input graphs are nonisomorphic then the output graphs are also.
INPUT:
graphs
– aGraph
or an iterable containingGraph
the graph6 string of these graphs is used as an input fordirectg
.options
(str) – a string passed to directg as if it was run at a system command line. Available options from directg –help:e#  e#:# specify a value or range of the total number of arcs o orient each edge in only one direction, never both f# Use only the subgroup that fixes the first # vertices setwise V only output graphs with nontrivial groups (including exchange of isolated vertices). The f option is respected. s#/# Make only a fraction of the orientations: The first integer is the part number (first is 0) and the second is the number of parts. Splitting is done per input graph independently.
debug
(boolean) – default:False
 ifTrue
directg standard error and standard output are displayed.
EXAMPLES:
sage: gen = graphs.nauty_geng("c 3") sage: dgs = list(digraphs.nauty_directg(gen)) sage: len(dgs) 13 sage: dgs[0] Digraph on 3 vertices sage: dgs[0]._bit_vector() '001001000' sage: len(list(digraphs.nauty_directg(graphs.PetersenGraph(), options="o"))) 324
See also

tournaments_nauty
(n, min_out_degree=None, max_out_degree=None, strongly_connected=False, debug=False, options='')¶ Iterator over all tournaments on \(n\) vertices using Nauty.
INPUT:
n
– integer; number of verticesmin_out_degree
,max_out_degree
– integers; if set toNone
(default), then the min/max outdegree is not constraineddebug
– boolean (default:False
); 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/.
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]