Function opensn::RemoveCyclicDependencies

• Defined in File feedback_arc_set.h

Function Documentation

std::vector<std::pair<Vertex, Vertex>> opensn::RemoveCyclicDependencies(Graph &g)

Removes cyclic dependencies from the given graph.

Each strongly connected component with at most MAX_EXACT_FAS_SCC_SIZE vertices is broken by a feedback arc set (FAS) of minimum total edge weight. Larger components use a greedy approximation.

Parameters:

g – The graph from which cyclic dependencies are to be removed. The FAS edges are removed from it, leaving it acyclic.

Returns:

FAS as a vector of graph edges. Each removed (source, target) pair appears once.