drepr.planning.topological_sorting#

Functions

dfs_breaking_cycle(sm, node, visited_path, ...)

Try to break cycles using invert DFS.

dfs_reverse_topo_sort(sm, topo_order, node, ...)

Generate a topological order of class nodes in the semantic model.

reverse_dfs(sm, node, visited_nodes, ...)

Reverse DFS to visit all ancestors of a node

topological_sorting(sm)

suppose we have a semantic model, that may contains circle, our task is to generate a topological order from the directed cyclic graph, and a set of edges involved in the cycles that are removed in order to generate the topo-order

Classes

ReversedTopoSortResult(topo_order, ...)

class ReversedTopoSortResult(topo_order: 'list[str]', removed_outgoing_edges: 'dict[int, bool]')[source]#

Bases: object

Parameters:
topo_order: list[str]#
removed_outgoing_edges: dict[int, bool]#
topological_sorting(sm: SemanticModel) → ReversedTopoSortResult[source]#

suppose we have a semantic model, that may contains circle, our task is to generate a topological order from the directed cyclic graph, and a set of edges involved in the cycles that are removed in order to generate the topo-order

Parameters:

sm (SemanticModel) –

Return type:

ReversedTopoSortResult

dfs_reverse_topo_sort(sm: SemanticModel, topo_order: list[str], node: str, visited_nodes: dict[str, bool], tmp_visited_nodes: dict[str, bool], removed_outgoing_edges: dict[int, bool])[source]#

Generate a topological order of class nodes in the semantic model. The graph must be acyclic before using this function

Based on DFS algorithm in here: https://en.wikipedia.org/wiki/Topological_sorting

Parameters:
dfs_breaking_cycle(sm: SemanticModel, node: str, visited_path: list[str], removed_outgoing_edges: dict[int, bool]) → bool[source]#

Try to break cycles using invert DFS. It returns true when break one cycle, and it terminates immediately. Thus, requires you to run this function many times until it return false

Parameters:
Return type:

bool

reverse_dfs(sm: SemanticModel, node: str, visited_nodes: dict[str, bool], removed_outgoing_edges: dict[int, bool]) → bool[source]#

Reverse DFS to visit all ancestors of a node

Parameters:
Return type:

bool