MaximumSpanningTree.h revision 198090
1166124Srafan//===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===// 2174993Srafan// 3166124Srafan// The LLVM Compiler Infrastructure 4166124Srafan// 5166124Srafan// This file is distributed under the University of Illinois Open Source 6166124Srafan// License. See LICENSE.TXT for details. 7166124Srafan// 8166124Srafan//===----------------------------------------------------------------------===// 9166124Srafan// 10166124Srafan// This module privides means for calculating a maximum spanning tree for a 11166124Srafan// given set of weighted edges. The type parameter T is the type of a node. 12166124Srafan// 13166124Srafan//===----------------------------------------------------------------------===// 14166124Srafan 15166124Srafan#ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 16166124Srafan#define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 17166124Srafan 18166124Srafan#include "llvm/ADT/EquivalenceClasses.h" 19166124Srafan#include <vector> 20166124Srafan#include <algorithm> 21166124Srafan 22166124Srafannamespace llvm { 23166124Srafan 24166124Srafan /// MaximumSpanningTree - A MST implementation. 25166124Srafan /// The type parameter T determines the type of the nodes of the graph. 26166124Srafan template <typename T> 27166124Srafan class MaximumSpanningTree { 2850276Speter 2950276Speter // A comparing class for comparing weighted edges. 3050276Speter template <typename CT> 31166124Srafan struct EdgeWeightCompare { 3250276Speter bool operator()(typename MaximumSpanningTree<CT>::EdgeWeight X, 3350276Speter typename MaximumSpanningTree<CT>::EdgeWeight Y) const { 3450276Speter if (X.second > Y.second) return true; 3550276Speter if (X.second < Y.second) return false; 3650276Speter return false; 37174993Srafan } 3850276Speter }; 3950276Speter 4050276Speter public: 4150276Speter typedef std::pair<const T*, const T*> Edge; 4250276Speter typedef std::pair<Edge, double> EdgeWeight; 43166124Srafan typedef std::vector<EdgeWeight> EdgeWeights; 44166124Srafan protected: 45166124Srafan typedef std::vector<Edge> MaxSpanTree; 46166124Srafan 47166124Srafan MaxSpanTree MST; 4850276Speter 49166124Srafan public: 50166124Srafan static char ID; // Class identification, replacement for typeinfo 51166124Srafan 52166124Srafan /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a 53166124Srafan /// spanning tree. 54166124Srafan MaximumSpanningTree(EdgeWeights &EdgeVector) { 55166124Srafan 56166124Srafan std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare<T>()); 57166124Srafan 58166124Srafan // Create spanning tree, Forest contains a special data structure 59166124Srafan // that makes checking if two nodes are already in a common (sub-)tree 60166124Srafan // fast and cheap. 61166124Srafan EquivalenceClasses<const T*> Forest; 62166124Srafan for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 63166124Srafan EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 64166124Srafan Edge e = (*EWi).first; 65166124Srafan 6650276Speter Forest.insert(e.first); 67166124Srafan Forest.insert(e.second); 68166124Srafan } 69166124Srafan 7050276Speter // Iterate over the sorted edges, biggest first. 7150276Speter for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 7250276Speter EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 7350276Speter Edge e = (*EWi).first; 74166124Srafan 75166124Srafan if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { 7650276Speter Forest.unionSets(e.first, e.second); 77174993Srafan // So we know now that the edge is not already in a subtree, so we push 7850276Speter // the edge to the MST. 7950276Speter MST.push_back(e); 8050276Speter } 81174993Srafan } 82166124Srafan } 83166124Srafan 84166124Srafan typename MaxSpanTree::iterator begin() { 85166124Srafan return MST.begin(); 8650276Speter } 87166124Srafan 8850276Speter typename MaxSpanTree::iterator end() { 89166124Srafan return MST.end(); 9050276Speter } 9150276Speter }; 9250276Speter 9350276Speter} // End llvm namespace 9450276Speter 9550276Speter#endif 96166124Srafan