The optimal branching algorithm solver. More...

#include "Conversion/PDLToPDLInterp/RootOrdering.h"

Public Types
using	EdgeList = std::vector< std::pair< Value, Value > >
	A list of edges (child, parent). More...

Public Member Functions
	OptimalBranching (RootOrderingGraph graph, Value root)
	Constructs the solver for the given graph and root value. More...

unsigned	solve ()
	Runs the Edmonds' algorithm for the current `graph`, returning the total cost of the minimum-weight spanning arborescence (sum of the edge costs). More...

const DenseMap< Value, Value > &	getRootOrderingParents () const
	Returns the computed parent map. More...

EdgeList	preOrderTraversal (ArrayRef< Value > nodes) const
	Returns the computed edges as visited in the preorder traversal. More...

Detailed Description

The optimal branching algorithm solver.

This solver accepts a graph and the root in its constructor, and is invoked via the solve() member function. This is a direct implementation of the Edmonds' algorithm, see https://en.wikipedia.org/wiki/Edmonds%27_algorithm. The worst-case computational complexity of this algorithm is O(N^3), for a single root. The PDL-to-PDLInterp lowering calls this N times (once for each candidate root), so the overall complexity root ordering is O(N^4). If needed, this could be reduced to O(N^3) with a more efficient algorithm. However, note that the underlying implementation is very efficient, and N in our instances tends to be very small (<10).

Definition at line 90 of file RootOrdering.h.

Member Typedef Documentation

◆ EdgeList

using mlir::pdl_to_pdl_interp::OptimalBranching::EdgeList = std::vector<std::pair<Value, Value> >

A list of edges (child, parent).

Definition at line 93 of file RootOrdering.h.

Constructor & Destructor Documentation

◆ OptimalBranching()

OptimalBranching::OptimalBranching	(	RootOrderingGraph	graph,
		Value	root
	)

Constructs the solver for the given graph and root value.

Definition at line 120 of file RootOrdering.cpp.

Member Function Documentation

◆ getRootOrderingParents()

const DenseMap<Value, Value>& mlir::pdl_to_pdl_interp::OptimalBranching::getRootOrderingParents ( ) const

inline

Returns the computed parent map.

This is the unique predecessor for each node (root) in the optimal branching.

Definition at line 111 of file RootOrdering.h.

◆ preOrderTraversal()

OptimalBranching::EdgeList OptimalBranching::preOrderTraversal ( ArrayRef< Value > nodes ) const

Returns the computed edges as visited in the preorder traversal.

The specified array determines the order for breaking any ties.

Definition at line 208 of file RootOrdering.cpp.

Referenced by buildPredicateList().

◆ solve()

unsigned OptimalBranching::solve ( )

Runs the Edmonds' algorithm for the current graph, returning the total cost of the minimum-weight spanning arborescence (sum of the edge costs).

This function first determines the optimal local choice of the parents and stores this choice in the parents mapping. If this choice results in an acyclic graph, the function returns immediately. Otherwise, it takes an arbitrary cycle, contracts it, and recurses on the new graph (which is guaranteed to have fewer nodes than we began with). After we return from recursion, we redirect the edges to/from the contracted node, so the parents map contains a valid solution for the current graph.

Definition at line 123 of file RootOrdering.cpp.

References contract(), mlir::pdl_to_pdl_interp::RootOrderingEntry::cost, and getCycle().