Generators for common digraphs.
ButterflyGraph() | Returns a n-dimensional butterfly graph. |
Circuit() | Returns the circuit on ![]() |
Circulant() | Returns a circulant 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. |
RandomTournament() | Returns a random tournament on ![]() |
TransitiveTournament() | Returns a transitive tournament on ![]() |
tournaments_nauty() | Returns all tournaments on ![]() |
AUTHORS:
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
Families of Graphs:
- 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:
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(0, 5):
... print len(list(digraphs(i)))
1
1
3
16
218
REFERENCE:
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:
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))]
Returns the circuit on vertices
The circuit is an oriented CycleGraph
EXAMPLE:
A circuit is the smallest strongly connected digraph:
sage: circuit = digraphs.Circuit(15)
sage: len(circuit.strongly_connected_components()) == 1
True
Returns a circulant digraph on vertices from a set of integers.
INPUT:
EXAMPLE:
sage: digraphs.Circulant(13,[3,5,7])
Circulant graph ([3, 5, 7]): Digraph on 13 vertices
TESTS:
sage: digraphs.Circulant(13,[3,5,7,"hey"])
Traceback (most recent call last):
...
ValueError: The list must contain only relative integers.
sage: digraphs.Circulant(3,[3,5,7,3.4])
Traceback (most recent call last):
...
ValueError: The list must contain only relative integers.
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:
n – An integer equal to the length of words in the De Bruijn digraph when vertices == '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:
sage: db=digraphs.DeBruijn(2,2); db
De Bruijn digraph (k=2, n=2): Looped digraph on 4 vertices
sage: db.order()
4
sage: db.size()
8
TESTS:
sage: digraphs.DeBruijn(5,0)
De Bruijn digraph (k=5, n=0): Looped multi-digraph on 1 vertex
sage: digraphs.DeBruijn(0,0)
De Bruijn digraph (k=0, n=0): Looped multi-digraph on 0 vertices
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
.
INPUTS:
See also
EXAMPLE:
sage: GB = digraphs.GeneralizedDeBruijn(8, 2)
sage: GB.is_isomorphic(digraphs.DeBruijn(2, 3), certify = True)
(True, {0: '000', 1: '001', 2: '010', 3: '011', 4: '100', 5: '101', 6: '110', 7: '111'})
TESTS:
An exception is raised when the degree is less than one:
sage: G = digraphs.GeneralizedDeBruijn(2, 0)
Traceback (most recent call last):
...
ValueError: The generalized de Bruijn digraph is defined for degree at least one.
An exception is raised when the order of the graph is less than one:
sage: G = digraphs.GeneralizedDeBruijn(0, 2)
Traceback (most recent call last):
...
ValueError: The generalized de Bruijn digraph is defined for at least one vertex.
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. |
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
.
INPUTS:
EXAMPLES:
sage: II = digraphs.ImaseItoh(8, 2)
sage: II.is_isomorphic(digraphs.DeBruijn(2, 3), certify = 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), certify = 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'})
TESTS:
An exception is raised when the degree is less than one:
sage: G = digraphs.ImaseItoh(2, 0)
Traceback (most recent call last):
...
ValueError: The digraph of Imase and Itoh is defined for degree at least one.
An exception is raised when the order of the graph is less than two:
sage: G = digraphs.ImaseItoh(1, 2)
Traceback (most recent call last):
...
ValueError: The digraph of Imase and Itoh is defined for at least two vertices.
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. |
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.
INPUTS:
the length of a vertex label when vertices == 'strings'.
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), certify = True)
(True, {'201': 5, '120': 9, '202': 4, '212': 7, '210': 6, '010': 0, '121': 8, '012': 1, '021': 2, '020': 3, '102': 10, '101': 11})
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')]
TESTS:
An exception is raised when the degree is less than one:
sage: G = digraphs.Kautz(0, 2)
Traceback (most recent call last):
...
ValueError: Kautz digraphs are defined for degree at least one.
sage: G = digraphs.Kautz(['a'], 2)
Traceback (most recent call last):
...
ValueError: Kautz digraphs are defined for degree at least one.
An exception is raised when the diameter of the graph is less than one:
sage: G = digraphs.Kautz(2, 0)
Traceback (most recent call last):
...
ValueError: Kautz digraphs are defined for diameter at least one.
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. |
Returns a directed path on vertices.
INPUT:
EXAMPLES:
sage: g = digraphs.Path(5)
sage: g.vertices()
[0, 1, 2, 3, 4]
sage: g.size()
4
sage: g.automorphism_group().cardinality()
1
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:
EXAMPLE:
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:
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:
EXAMPLE:
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:
Returns a random labelled digraph on nodes and
arcs.
INPUT:
PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.
EXAMPLE:
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)]
TESTS:
sage: digraphs.RandomDirectedGNM(10,-3)
Traceback (most recent call last):
...
ValueError: The number of edges must satisfy 0<= m <= n(n-1) when no loops are allowed, and 0<= m <= n^2 otherwise.
sage: digraphs.RandomDirectedGNM(10,100)
Traceback (most recent call last):
...
ValueError: The number of edges must satisfy 0<= m <= n(n-1) when no loops are allowed, and 0<= m <= n^2 otherwise.
Returns a random digraph on nodes. Each edge is inserted
independently with probability
.
INPUTS:
REFERENCES:
[1] | P. Erdos and A. Renyi, On Random Graphs, Publ. Math. 6, 290 (1959). |
[2] |
|
PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.
EXAMPLE:
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)]
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:
EXAMPLE:
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:
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:
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!
Returns a transitive tournament on vertices.
In this tournament there is an edge from to
if
.
See Wikipedia article Tournament_(graph_theory)
INPUT:
EXAMPLES:
sage: g = digraphs.TransitiveTournament(5)
sage: g.vertices()
[0, 1, 2, 3, 4]
sage: g.size()
10
sage: g.automorphism_group().cardinality()
1
TESTS:
sage: digraphs.TransitiveTournament(-1)
Traceback (most recent call last):
...
ValueError: The number of vertices cannot be strictly negative!
Returns all tournaments on vertices using Nauty.
INPUT:
Note
To use this method you must first install the Nauty spkg.
EXAMPLES:
sage: for g in digraphs.tournaments_nauty(4): # optional - nauty
....: print g.edges(labels = False) # optional - nauty
[(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)] # optional - nauty
[1, 1, 2, 4, 12, 56, 456]
sage: [len(list(tournaments(x, strongly_connected = True))) for x in range(1,9)] # optional - nauty
[1, 0, 1, 1, 6, 35, 353, 6008]