MaximumSpanningTree.h revision 198090
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 22namespace 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 96