LLVM  mainline
MaximumSpanningTree.h
Go to the documentation of this file.
00001 //===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This module provides means for calculating a maximum spanning tree for a
00011 // given set of weighted edges. The type parameter T is the type of a node.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
00016 #define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
00017 
00018 #include "llvm/ADT/EquivalenceClasses.h"
00019 #include "llvm/IR/BasicBlock.h"
00020 #include <algorithm>
00021 #include <vector>
00022 
00023 namespace llvm {
00024 
00025   /// MaximumSpanningTree - A MST implementation.
00026   /// The type parameter T determines the type of the nodes of the graph.
00027   template <typename T>
00028   class MaximumSpanningTree {
00029   public:
00030     typedef std::pair<const T*, const T*> Edge;
00031     typedef std::pair<Edge, double> EdgeWeight;
00032     typedef std::vector<EdgeWeight> EdgeWeights;
00033   protected:
00034     typedef std::vector<Edge> MaxSpanTree;
00035 
00036     MaxSpanTree MST;
00037 
00038   private:
00039     // A comparing class for comparing weighted edges.
00040     struct EdgeWeightCompare {
00041       static bool getBlockSize(const T *X) {
00042         const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X);
00043         return BB ? BB->size() : 0;
00044       }
00045 
00046       bool operator()(EdgeWeight X, EdgeWeight Y) const {
00047         if (X.second > Y.second) return true;
00048         if (X.second < Y.second) return false;
00049 
00050         // Equal edge weights: break ties by comparing block sizes.
00051         size_t XSizeA = getBlockSize(X.first.first);
00052         size_t YSizeA = getBlockSize(Y.first.first);
00053         if (XSizeA > YSizeA) return true;
00054         if (XSizeA < YSizeA) return false;
00055 
00056         size_t XSizeB = getBlockSize(X.first.second);
00057         size_t YSizeB = getBlockSize(Y.first.second);
00058         if (XSizeB > YSizeB) return true;
00059         if (XSizeB < YSizeB) return false;
00060 
00061         return false;
00062       }
00063     };
00064 
00065   public:
00066     static char ID; // Class identification, replacement for typeinfo
00067 
00068     /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a
00069     /// spanning tree.
00070     MaximumSpanningTree(EdgeWeights &EdgeVector) {
00071 
00072       std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare());
00073 
00074       // Create spanning tree, Forest contains a special data structure
00075       // that makes checking if two nodes are already in a common (sub-)tree
00076       // fast and cheap.
00077       EquivalenceClasses<const T*> Forest;
00078       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
00079            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
00080         Edge e = (*EWi).first;
00081 
00082         Forest.insert(e.first);
00083         Forest.insert(e.second);
00084       }
00085 
00086       // Iterate over the sorted edges, biggest first.
00087       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
00088            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
00089         Edge e = (*EWi).first;
00090 
00091         if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) {
00092           Forest.unionSets(e.first, e.second);
00093           // So we know now that the edge is not already in a subtree, so we push
00094           // the edge to the MST.
00095           MST.push_back(e);
00096         }
00097       }
00098     }
00099 
00100     typename MaxSpanTree::iterator begin() {
00101       return MST.begin();
00102     }
00103 
00104     typename MaxSpanTree::iterator end() {
00105       return MST.end();
00106     }
00107   };
00108 
00109 } // End llvm namespace
00110 
00111 #endif