summaryrefslogtreecommitdiff
path: root/lib/spack/external/altgraph/GraphUtil.py
diff options
context:
space:
mode:
Diffstat (limited to 'lib/spack/external/altgraph/GraphUtil.py')
-rw-r--r--lib/spack/external/altgraph/GraphUtil.py37
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