test_graph_utils.py:97:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
..\..\..\golem\core\dag\graph.py:223: in show
GraphVisualizer(graph=self)\
..\..\..\golem\visualisation\graph_viz.py:67: in visualise
self.__draw_with_networkx(save_path=save_path, node_color=node_color, dpi=dpi,
..\..\..\golem\visualisation\graph_viz.py:183: in __draw_with_networkx
self.draw_nx_dag(ax, node_color, node_size_scale, font_size_scale, edge_curvature_scale,
..\..\..\golem\visualisation\graph_viz.py:232: in draw_nx_dag
pos, longest_sequence = get_hierarchy_pos(nx_graph)
..\..\..\golem\visualisation\graph_viz.py:407: in get_hierarchy_pos
longest_path = nx.dag_longest_path(graph, weight=None)
C:\Users\hades\miniconda3\envs\golem\lib\site-packages\networkx\utils\decorators.py:795: in func
return argmap._lazy_compile(__wrapper)(*args, **kwargs)
<class 'networkx.utils.decorators.argmap'> compilation 4:4: in argmap_dag_longest_path_1
???
C:\Users\hades\miniconda3\envs\golem\lib\site-packages\networkx\algorithms\dag.py:803: in dag_longest_path
for v in topo_order:
C:\Users\hades\miniconda3\envs\golem\lib\site-packages\networkx\algorithms\dag.py:246: in topological_sort
for generation in nx.topological_generations(G):
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
G = <networkx.classes.digraph.DiGraph object at 0x00000205FE33CCD0>
def topological_generations(G):
"""Stratifies a DAG into generations.
A topological generation is node collection in which ancestors of a node in each
generation are guaranteed to be in a previous generation, and any descendants of
a node are guaranteed to be in a following generation. Nodes are guaranteed to
be in the earliest possible generation that they can belong to.
Parameters
----------
G : NetworkX digraph
A directed acyclic graph (DAG)
Yields
------
sets of nodes
Yields sets of nodes representing each generation.
Raises
------
NetworkXError
Generations are defined for directed graphs only. If the graph
`G` is undirected, a :exc:`NetworkXError` is raised.
NetworkXUnfeasible
If `G` is not a directed acyclic graph (DAG) no topological generations
exist and a :exc:`NetworkXUnfeasible` exception is raised. This can also
be raised if `G` is changed while the returned iterator is being processed
RuntimeError
If `G` is changed while the returned iterator is being processed.
Examples
--------
>>> DG = nx.DiGraph([(2, 1), (3, 1)])
>>> [sorted(generation) for generation in nx.topological_generations(DG)]
[[2, 3], [1]]
Notes
-----
The generation in which a node resides can also be determined by taking the
max-path-distance from the node to the farthest leaf node. That value can
be obtained with this function using `enumerate(topological_generations(G))`.
See also
--------
topological_sort
"""
if not G.is_directed():
raise nx.NetworkXError("Topological sort not defined on undirected graphs.")
multigraph = G.is_multigraph()
indegree_map = {v: d for v, d in G.in_degree() if d > 0}
zero_indegree = [v for v, d in G.in_degree() if d == 0]
while zero_indegree:
this_generation = zero_indegree
zero_indegree = []
for node in this_generation:
if node not in G:
raise RuntimeError("Graph changed during iteration")
for child in G.neighbors(node):
try:
indegree_map[child] -= len(G[node][child]) if multigraph else 1
except KeyError as e:
raise RuntimeError("Graph changed during iteration") from e
if indegree_map[child] == 0:
zero_indegree.append(child)
del indegree_map[child]
yield this_generation
if indegree_map:
> raise nx.NetworkXUnfeasible(
"Graph contains a cycle or graph changed during iteration"
)
E networkx.exception.NetworkXUnfeasible: Graph contains a cycle or graph changed during iteration
gkirgizov
commented
1 year ago