/usr/lib/python2.7/dist-packages/altgraph/GraphUtil.py is in python-altgraph 0.15~repack0-1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 140 141 142 143 144 | '''
altgraph.GraphUtil - Utility classes and functions
==================================================
'''
import random
from collections import deque
from altgraph import Graph
from altgraph import 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.
'''
# FIXME: 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 = set([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
|