Coverage for local/lib/python2.7/site-packages/sage/graphs/digraph

[('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

:trac:`22355`::

sage: K = digraphs.Kautz(2, 2, vertices='strings')

sage: K.vertices()

['01', '02', '10', '12', '20', '21']

sage: h = digraphs.Kautz(2, 2, vertices='integers')

sage: h.vertices()

[0, 1, 2, 3, 4, 5]

sage: h.is_isomorphic(K)

True

sage: h = digraphs.Kautz([1,'aA','BB'], 2, vertices='integers')

sage: h.is_isomorphic(K)

True

sage: h.vertices()

[0, 1, 2, 3, 4, 5]

sage: digraphs.Kautz(2, 2, vertices='circles')

Traceback (most recent call last):

...

ValueError: unknown type for vertices

REFERENCE:

.. [Kautz68] \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.

"""

if D < 1:

raise ValueError("Kautz digraphs are defined for diameter at least one")

from sage.combinat.words.words import Words

from sage.rings.integer import Integer

if vertices == 'strings':

my_alphabet = Words([str(i) for i in range(k+1)] if isinstance(k, Integer) else k, 1)

if my_alphabet.alphabet().cardinality() < 2:

raise ValueError("Kautz digraphs are defined for degree at least one")

# We start building the set of vertices

V = [i for i in my_alphabet]

for i in range(D-1):

VV = []

for w in V:

VV += [w*a for a in my_alphabet if not w.has_suffix(a) ]

V = VV

# We now build the set of arcs

G = DiGraph()

for u in V:

for a in my_alphabet:

if not u.has_suffix(a):

G.add_edge(u.string_rep(), (u[1:]*a).string_rep(), a.string_rep())

elif vertices == 'integers':

d = k if isinstance(k, Integer) else (len(list(k))-1)

if d < 1:

raise ValueError("Kautz digraphs are defined for degree at least one")

G = digraphs.ImaseItoh( (d+1)*(d**(D-1)), d)

else:

raise ValueError('unknown type for vertices')

G.name( "Kautz digraph (k={}, D={})".format(k, D) )

return G

def RandomDirectedGN(self, n, kernel=lambda x:x, 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`` - 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.

"""

if seed is None:

seed = current_randstate().long_seed()

import networkx

return DiGraph(networkx.gn_graph(n, kernel, seed=seed))

def RandomDirectedGNC(self, 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.

"""

if seed is None:

seed = current_randstate().long_seed()

import networkx

return DiGraph(networkx.gnc_graph(n, seed=seed))

def RandomDirectedGNP(self, n, p, loops = False, seed = None):

r"""

Returns a random digraph on `n` nodes. Each edge is inserted

independently with probability `p`.

INPUT:

- ``n`` -- number of nodes of the digraph

- ``p`` -- probability of an edge

- ``loops`` -- 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()

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)]

"""

from sage.graphs.graph_generators_pyx import RandomGNP

if 0.0 > p or 1.0 < p:

raise ValueError("The probability p must be in [0..1].")

if seed is None:

seed = current_randstate().long_seed()

return RandomGNP(n, p, directed = True, loops = loops)

def RandomDirectedGNM(self, n, m, loops = False):

r"""

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 to ``False`` 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()

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()

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.

"""

n, m = int(n), int(m)

# The random graph is built by drawing randomly and uniformly two

# integers u,v, and adding the corresponding edge if it does not exist,

# as many times as necessary.

# When the graph is dense, we actually compute its complement. This will

# prevent us from drawing the same pair u,v too many times.

from sage.misc.prandom import _pyrand

rand = _pyrand()

D = DiGraph(n, loops = loops)

# Ensuring the parameters n,m make sense.

# If the graph is dense, we actually want to build its complement. We

# update m accordingly.

good_input = True

is_dense = False

if m < 0:

good_input = False

if loops:

if m > n*n:

good_input = False

elif 2*m > n*n:

is_dense = True

m = n*n - m

else:

if m > n*(n-1):

good_input = False

elif m > (n * (n - 1)) // 2:

is_dense = True

m = n*(n-1) - m

if not good_input:

raise ValueError("The number of edges must satisfy 0<= m <= n(n-1) when no loops are allowed, and 0<= m <= n^2 otherwise.")

# When the given number of edges defines a density larger than 1/2, it

# should be faster to compute the complement of the graph (less edges to

# generate), then to return its complement. This being said, the

# .complement() method for sparse graphs is very slow at the moment.

# Similarly, it is faster to test whether a pair belongs to a dictionary

# than to test the adjacency of two vertices in a graph. For these

# reasons, the following code mainly works on dictionaries.

adj = dict( (i, dict()) for i in range(n) )

# We fill the dictionary structure, but add the corresponding edge in

# the graph only if is_dense is False. If it is true, we will add the

# edges in a second phase.

while m > 0:

# It is better to obtain random numbers this way than by calling the

# randint or randrange method. This, because they are very expensive

# when trying to compute MANY random integers, and because the

# following lines is precisely what they do anyway, after checking

# their parameters are correct.

u=int(rand.random()*n)

v=int(rand.random()*n)

if (u != v or loops) and (not v in adj[u]):

adj[u][v] = 1

m -= 1

if not is_dense:

D.add_edge(u,v)

# If is_dense is True, it means the graph has not been built. We fill D

# with the complement of the edges stored in the adj dictionary

if is_dense:

for u in range(n):

for v in range(n):

if ((u != v) or loops) and (not (v in adj[u])):

D.add_edge(u,v)

return D

def RandomDirectedGNR(self, 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`` - for the random number generator.

EXAMPLES::

sage: D = digraphs.RandomDirectedGNR(25, .2)

sage: D.edges(labels=False)

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.

"""

if seed is None:

seed = current_randstate().long_seed()

import networkx

return DiGraph(networkx.gnc_graph(n, seed=seed))

def RandomSemiComplete(self, n):

r"""

Return a random semi-complete digraph on `n` vertices.

A directed graph `G=(V,E)` is *semi-complete* if for any pair of

vertices `u` and `v`, 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 `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

.. SEEALSO::

- :meth:`~sage.graphs.digraph_generators.DiGraphGenerators.Complete`

- :meth:`~sage.graphs.digraph_generators.DiGraphGenerators.RandomTournament`

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!

"""

G = DiGraph(n, name="Random Semi-Complete digraph")

# For each pair u,v we choose a randon number ``coin`` in [1,3].

# We select edge `(u,v)` if `coin==1` or `coin==2`.

# We select edge `(v,u)` if `coin==2` or `coin==3`.

import itertools

from sage.misc.prandom import randint

for u,v in itertools.combinations(range(n), 2):

coin = randint(1,3)

if coin<=2:

G.add_edge(u,v)

if coin>=2:

G.add_edge(v,u)

if n:

from sage.graphs.graph_plot import _circle_embedding

_circle_embedding(G, list(range(n)))

return G

################################################################################

# DiGraph Iterators

################################################################################

def __call__(self, vertices=None, property=lambda x: True, augment='edges',

size=None, implementation='c_graph', sparse=True, copy=True):

"""

Accesses the generator of isomorphism class representatives.

Iterates over distinct, exhaustive representatives.

INPUT:

- ``vertices`` - natural number or ``None`` to generate all 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 not ``c_graph``

- ``copy`` (boolean) -- If set to ``True`` (default)

this method makes copies of the digraphs before returning

them. If set to ``False`` the method returns the digraph it

is working on. The second alternative is faster, but modifying

any of the digraph instances returned by the method may break

the function's behaviour, as it is using these digraphs to

compute the next ones: only use ``copy = False`` when

you stick to *reading* the digraphs returned.

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

Print digraphs on 3 vertices.

sage: for D in digraphs(3):

....: print(D)

Digraph on 3 vertices

...

Digraph on 3 vertices

For more examples, see the class level documentation, or type

sage: digraphs? # not tested

REFERENCE:

- Brendan D. McKay, Isomorph-Free Exhaustive generation.

Journal of Algorithms Volume 26, Issue 2, February 1998,

pages 306-324.

"""

from copy import copy as copyfun

if size is not None:

extra_property = lambda x: x.size() == size

else:

extra_property = lambda x: True

if augment == 'vertices':

if vertices is None:

raise NotImplementedError

from sage.graphs.graph_generators import canaug_traverse_vert

g = DiGraph(implementation=implementation, sparse=sparse)

for gg in canaug_traverse_vert(g, [], vertices, property, dig=True, implementation=implementation, sparse=sparse):

if extra_property(gg):

yield copyfun(gg) if copy else gg

elif augment == 'edges':

if vertices is None:

vertices = 0

while True:

for g in self(vertices, implementation=implementation, sparse=sparse, copy=copy):

yield g

vertices += 1

from sage.graphs.graph_generators import canaug_traverse_edge

g = DiGraph(vertices, implementation=implementation, sparse=sparse)

gens = []

for i in range(vertices-1):

gen = list(range(i))

gen.append(i+1); gen.append(i)

gen += list(range(i + 2, vertices))

gens.append(gen)

for gg in canaug_traverse_edge(g, gens, property, dig=True, implementation=implementation, sparse=sparse):

if extra_property(gg):

yield copyfun(gg) if copy else gg

else:

raise NotImplementedError()

# Easy access to the graph generators from the command line:

digraphs = DiGraphGenerators()

Coverage for local/lib/python2.7/site-packages/sage/graphs/digraph_generators.py : 87%

323 statements 281 run 42 missing 0 excluded