# Source code for openmdao.utils.graph_utils

"""
Various graph related utilities.
"""
import networkx as nx
[docs]def get_sccs_topo(graph):
"""
Return strongly connected subsystems of the given Group in topological order.
Parameters
----------
graph : networkx.DiGraph
Directed graph of Systems.
Returns
-------
list of sets of str
A list of strongly connected components in topological order.
"""
# Tarjan's algorithm returns SCCs in reverse topological order, so
# the list returned here is reversed.
sccs = list(nx.strongly_connected_components(graph))
sccs.reverse()
return sccs
[docs]def get_out_of_order_nodes(graph, orders):
"""
Return a list of nodes that are out of order.
Parameters
----------
graph : networkx.DiGraph
Directed graph of Systems.
orders : dict
A dict of order values keyed by node name.
Returns
-------
list of sets of str
A list of strongly connected components in topological order.
list of str
A list of nodes that are out of order.
"""
strongcomps = get_sccs_topo(graph)
out_of_order = []
for strongcomp in strongcomps:
for u, v in graph.edges(strongcomp):
# for any connection between a system in this strongcomp and a system
# outside of it, the target must be ordered after the source.
if u in strongcomp and v not in strongcomp and orders[u] > orders[v]:
out_of_order.append((u, v))
return strongcomps, out_of_order