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 provides 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 "llvm/IR/BasicBlock.h" 20 #include <algorithm> 21 #include <vector> 22 23 namespace llvm { 24 25 /// MaximumSpanningTree - A MST implementation. 26 /// The type parameter T determines the type of the nodes of the graph. 27 template <typename T> 28 class MaximumSpanningTree { 29 public: 30 typedef std::pair<const T*, const T*> Edge; 31 typedef std::pair<Edge, double> EdgeWeight; 32 typedef std::vector<EdgeWeight> EdgeWeights; 33 protected: 34 typedef std::vector<Edge> MaxSpanTree; 35 36 MaxSpanTree MST; 37 38 private: 39 // A comparing class for comparing weighted edges. 40 struct EdgeWeightCompare { 41 static bool getBlockSize(const T *X) { 42 const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X); 43 return BB ? BB->size() : 0; 44 } 45 46 bool operator()(EdgeWeight X, EdgeWeight Y) const { 47 if (X.second > Y.second) return true; 48 if (X.second < Y.second) return false; 49 50 // Equal edge weights: break ties by comparing block sizes. 51 size_t XSizeA = getBlockSize(X.first.first); 52 size_t YSizeA = getBlockSize(Y.first.first); 53 if (XSizeA > YSizeA) return true; 54 if (XSizeA < YSizeA) return false; 55 56 size_t XSizeB = getBlockSize(X.first.second); 57 size_t YSizeB = getBlockSize(Y.first.second); 58 if (XSizeB > YSizeB) return true; 59 if (XSizeB < YSizeB) return false; 60 61 return false; 62 } 63 }; 64 65 public: 66 static char ID; // Class identification, replacement for typeinfo 67 68 /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a 69 /// spanning tree. 70 MaximumSpanningTree(EdgeWeights &EdgeVector) { 71 72 std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare()); 73 74 // Create spanning tree, Forest contains a special data structure 75 // that makes checking if two nodes are already in a common (sub-)tree 76 // fast and cheap. 77 EquivalenceClasses<const T*> Forest; 78 for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 79 EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 80 Edge e = (*EWi).first; 81 82 Forest.insert(e.first); 83 Forest.insert(e.second); 84 } 85 86 // Iterate over the sorted edges, biggest first. 87 for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 88 EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 89 Edge e = (*EWi).first; 90 91 if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { 92 Forest.unionSets(e.first, e.second); 93 // So we know now that the edge is not already in a subtree, so we push 94 // the edge to the MST. 95 MST.push_back(e); 96 } 97 } 98 } 99 100 typename MaxSpanTree::iterator begin() { 101 return MST.begin(); 102 } 103 104 typename MaxSpanTree::iterator end() { 105 return MST.end(); 106 } 107 }; 108 109 } // End llvm namespace 110 111 #endif 112
