diff options
Diffstat (limited to 'lib/spack/external/altgraph/GraphUtil.py')
-rw-r--r-- | lib/spack/external/altgraph/GraphUtil.py | 37 |
1 files changed, 16 insertions, 21 deletions
diff --git a/lib/spack/external/altgraph/GraphUtil.py b/lib/spack/external/altgraph/GraphUtil.py index 500a74b9f7..cfd6a34f3c 100644 --- a/lib/spack/external/altgraph/GraphUtil.py +++ b/lib/spack/external/altgraph/GraphUtil.py @@ -1,31 +1,29 @@ -''' +""" altgraph.GraphUtil - Utility classes and functions ================================================== -''' +""" import random from collections import deque -from altgraph import Graph -from altgraph import GraphError +from altgraph import Graph, GraphError -def generate_random_graph( - node_num, edge_num, self_loops=False, multi_edges=False): - ''' + +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) + max_edges = node_num * (node_num - 1) if edge_num > max_edges: - raise GraphError( - "inconsistent arguments to 'generate_random_graph'") + raise GraphError("inconsistent arguments to 'generate_random_graph'") nodes = range(node_num) @@ -52,17 +50,16 @@ def generate_random_graph( return g -def generate_scale_free_graph( - steps, growth_num, self_loops=False, multi_edges=False): - ''' +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) + 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. + """ + # The code doesn't seem to do what the documentation claims. graph = Graph.Graph() # initialize the graph @@ -113,7 +110,7 @@ def filter_stack(graph, head, filters): in *removes*. """ - visited, removes, orphans = set([head]), set(), set() + visited, removes, orphans = {head}, set(), set() stack = deque([(head, head)]) get_data = graph.node_data get_edges = graph.out_edges @@ -137,8 +134,6 @@ def filter_stack(graph, head, filters): visited.add(tail) stack.append((last_good, tail)) - orphans = [ - (lg, tl) - for (lg, tl) in orphans if tl not in removes] + orphans = [(lg, tl) for (lg, tl) in orphans if tl not in removes] return visited, removes, orphans |