1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
"""
altgraph.GraphUtil - Utility classes and functions
==================================================
"""
import random
from collections import deque
from altgraph import Graph, GraphError
def generate_random_graph(node_num, edge_num, self_loops=False, multi_edges=False):
"""
Generates and returns a :py:class:`~altgraph.Graph.Graph` instance with
*node_num* nodes randomly connected by *edge_num* edges.
"""
g = Graph.Graph()
if not multi_edges:
if self_loops:
max_edges = node_num * node_num
else:
max_edges = node_num * (node_num - 1)
if edge_num > max_edges:
raise GraphError("inconsistent arguments to 'generate_random_graph'")
nodes = range(node_num)
for node in nodes:
g.add_node(node)
while 1:
head = random.choice(nodes)
tail = random.choice(nodes)
# loop defense
if head == tail and not self_loops:
continue
# multiple edge defense
if g.edge_by_node(head, tail) is not None and not multi_edges:
continue
# add the edge
g.add_edge(head, tail)
if g.number_of_edges() >= edge_num:
break
return g
def generate_scale_free_graph(steps, growth_num, self_loops=False, multi_edges=False):
"""
Generates and returns a :py:class:`~altgraph.Graph.Graph` instance that
will have *steps* \\* *growth_num* nodes and a scale free (powerlaw)
connectivity. Starting with a fully connected graph with *growth_num*
nodes at every step *growth_num* nodes are added to the graph and are
connected to existing nodes with a probability proportional to the degree
of these existing nodes.
"""
# The code doesn't seem to do what the documentation claims.
graph = Graph.Graph()
# initialize the graph
store = []
for i in range(growth_num):
for j in range(i + 1, growth_num):
store.append(i)
store.append(j)
graph.add_edge(i, j)
# generate
for node in range(growth_num, steps * growth_num):
graph.add_node(node)
while graph.out_degree(node) < growth_num:
nbr = random.choice(store)
# loop defense
if node == nbr and not self_loops:
continue
# multi edge defense
if graph.edge_by_node(node, nbr) and not multi_edges:
continue
graph.add_edge(node, nbr)
for nbr in graph.out_nbrs(node):
store.append(node)
store.append(nbr)
return graph
def filter_stack(graph, head, filters):
"""
Perform a walk in a depth-first order starting
at *head*.
Returns (visited, removes, orphans).
* visited: the set of visited nodes
* removes: the list of nodes where the node
data does not all *filters*
* orphans: tuples of (last_good, node),
where node is not in removes, is directly
reachable from a node in *removes* and
*last_good* is the closest upstream node that is not
in *removes*.
"""
visited, removes, orphans = {head}, set(), set()
stack = deque([(head, head)])
get_data = graph.node_data
get_edges = graph.out_edges
get_tail = graph.tail
while stack:
last_good, node = stack.pop()
data = get_data(node)
if data is not None:
for filtfunc in filters:
if not filtfunc(data):
removes.add(node)
break
else:
last_good = node
for edge in get_edges(node):
tail = get_tail(edge)
if last_good is not node:
orphans.add((last_good, tail))
if tail not in visited:
visited.add(tail)
stack.append((last_good, tail))
orphans = [(lg, tl) for (lg, tl) in orphans if tl not in removes]
return visited, removes, orphans
|
