MLIR
20.0.0git

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 minimumweight 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...  
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 worstcase computational complexity of this algorithm is O(N^3), for a single root. The PDLtoPDLInterp 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.
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.
OptimalBranching::OptimalBranching  (  RootOrderingGraph  graph, 
Value  root  
) 
Constructs the solver for the given graph and root value.
Definition at line 120 of file RootOrdering.cpp.

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.
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().
unsigned OptimalBranching::solve  (  ) 
Runs the Edmonds' algorithm for the current graph
, returning the total cost of the minimumweight 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().
Referenced by buildPredicateList().