Generators for common digraphs.
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
- RandomDirectedGNR
Families of Graphs:
- DeBruijn
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 the De Bruijn diraph 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.
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 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 digraph on nodes. Each edge is
inserted independently with probability
.
REFERENCES:
PLOTTING: When plotting, this graph will use the default spring-layout algorithm, unless a position dictionary is specified.
EXAMPLE:
sage: D = digraphs.RandomDirectedGNP(10, .2)
sage: D.num_verts()
10
sage: D.edges(labels=False)
[(0, 1), (0, 3), (0, 6), (0, 8), (1, 4), (3, 7), (4, 1), (4, 8), (5, 2), (5, 6), (5, 8), (6, 4), (7, 6), (8, 4), (8, 5), (8, 7), (8, 9), (9, 3), (9, 4), (9, 6)]
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: