MLIR  20.0.0git
Public Types | Public Member Functions | List of all members
mlir::pdl_to_pdl_interp::OptimalBranching Class Reference

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

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().

Referenced by buildPredicateList().


The documentation for this class was generated from the following files: