lib/Transforms/Instrumentation/MaximumSpanningTree.h

   1 //===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This module privides means for calculating a maximum spanning tree for a
  11 // given set of weighted edges. The type parameter T is the type of a node.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
  16 #define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
  17
  18 #include "llvm/ADT/EquivalenceClasses.h"
  19 #include <vector>
  20 #include <algorithm>
  21
  22 namespace llvm {
  23
  24   /// MaximumSpanningTree - A MST implementation.
  25   /// The type parameter T determines the type of the nodes of the graph.
  26   template <typename T>
  27   class MaximumSpanningTree {
  28
  29     // A comparing class for comparing weighted edges.
  30     template <typename CT>
  31     struct EdgeWeightCompare {
  32       bool operator()(typename MaximumSpanningTree<CT>::EdgeWeight X,
  33                       typename MaximumSpanningTree<CT>::EdgeWeight Y) const {
  34         if (X.second > Y.second) return true;
  35         if (X.second < Y.second) return false;
  36         return false;
  37       }
  38     };
  39
  40   public:
  41     typedef std::pair<const T*, const T*> Edge;
  42     typedef std::pair<Edge, double> EdgeWeight;
  43     typedef std::vector<EdgeWeight> EdgeWeights;
  44   protected:
  45     typedef std::vector<Edge> MaxSpanTree;
  46
  47     MaxSpanTree MST;
  48
  49   public:
  50     static char ID; // Class identification, replacement for typeinfo
  51
  52     /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a
  53     /// spanning tree.
  54     MaximumSpanningTree(EdgeWeights &EdgeVector) {
  55
  56       std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare<T>());
  57
  58       // Create spanning tree, Forest contains a special data structure
  59       // that makes checking if two nodes are already in a common (sub-)tree
  60       // fast and cheap.
  61       EquivalenceClasses<const T*> Forest;
  62       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
  63            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
  64         Edge e = (*EWi).first;
  65
  66         Forest.insert(e.first);
  67         Forest.insert(e.second);
  68       }
  69
  70       // Iterate over the sorted edges, biggest first.
  71       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
  72            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
  73         Edge e = (*EWi).first;
  74
  75         if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) {
  76           Forest.unionSets(e.first, e.second);
  77           // So we know now that the edge is not already in a subtree, so we push
  78           // the edge to the MST.
  79           MST.push_back(e);
  80         }
  81       }
  82     }
  83
  84     typename MaxSpanTree::iterator begin() {
  85       return MST.begin();
  86     }
  87
  88     typename MaxSpanTree::iterator end() {
  89       return MST.end();
  90     }
  91   };
  92
  93 } // End llvm namespace
  94
  95 #endif