MaximumSpanningTree.h revision 221345
1198090Srdivacky//===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===// 2198090Srdivacky// 3198090Srdivacky// The LLVM Compiler Infrastructure 4198090Srdivacky// 5198090Srdivacky// This file is distributed under the University of Illinois Open Source 6198090Srdivacky// License. See LICENSE.TXT for details. 7198090Srdivacky// 8198090Srdivacky//===----------------------------------------------------------------------===// 9198090Srdivacky// 10221345Sdim// This module provides means for calculating a maximum spanning tree for a 11198090Srdivacky// given set of weighted edges. The type parameter T is the type of a node. 12198090Srdivacky// 13198090Srdivacky//===----------------------------------------------------------------------===// 14198090Srdivacky 15198090Srdivacky#ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 16198090Srdivacky#define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 17198090Srdivacky 18200581Srdivacky#include "llvm/BasicBlock.h" 19198090Srdivacky#include "llvm/ADT/EquivalenceClasses.h" 20198090Srdivacky#include <vector> 21198090Srdivacky#include <algorithm> 22198090Srdivacky 23198090Srdivackynamespace llvm { 24198090Srdivacky 25198090Srdivacky /// MaximumSpanningTree - A MST implementation. 26198090Srdivacky /// The type parameter T determines the type of the nodes of the graph. 27198090Srdivacky template <typename T> 28198090Srdivacky class MaximumSpanningTree { 29198090Srdivacky 30198090Srdivacky // A comparing class for comparing weighted edges. 31198090Srdivacky template <typename CT> 32198090Srdivacky struct EdgeWeightCompare { 33198090Srdivacky bool operator()(typename MaximumSpanningTree<CT>::EdgeWeight X, 34198090Srdivacky typename MaximumSpanningTree<CT>::EdgeWeight Y) const { 35198090Srdivacky if (X.second > Y.second) return true; 36198090Srdivacky if (X.second < Y.second) return false; 37200581Srdivacky if (const BasicBlock *BBX = dyn_cast<BasicBlock>(X.first.first)) { 38200581Srdivacky if (const BasicBlock *BBY = dyn_cast<BasicBlock>(Y.first.first)) { 39200581Srdivacky if (BBX->size() > BBY->size()) return true; 40200581Srdivacky if (BBX->size() < BBY->size()) return false; 41200581Srdivacky } 42200581Srdivacky } 43200581Srdivacky if (const BasicBlock *BBX = dyn_cast<BasicBlock>(X.first.second)) { 44200581Srdivacky if (const BasicBlock *BBY = dyn_cast<BasicBlock>(Y.first.second)) { 45200581Srdivacky if (BBX->size() > BBY->size()) return true; 46200581Srdivacky if (BBX->size() < BBY->size()) return false; 47200581Srdivacky } 48200581Srdivacky } 49198090Srdivacky return false; 50198090Srdivacky } 51198090Srdivacky }; 52198090Srdivacky 53198090Srdivacky public: 54198090Srdivacky typedef std::pair<const T*, const T*> Edge; 55198090Srdivacky typedef std::pair<Edge, double> EdgeWeight; 56198090Srdivacky typedef std::vector<EdgeWeight> EdgeWeights; 57198090Srdivacky protected: 58198090Srdivacky typedef std::vector<Edge> MaxSpanTree; 59198090Srdivacky 60198090Srdivacky MaxSpanTree MST; 61198090Srdivacky 62198090Srdivacky public: 63198090Srdivacky static char ID; // Class identification, replacement for typeinfo 64198090Srdivacky 65198090Srdivacky /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a 66198090Srdivacky /// spanning tree. 67198090Srdivacky MaximumSpanningTree(EdgeWeights &EdgeVector) { 68198090Srdivacky 69198090Srdivacky std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare<T>()); 70198090Srdivacky 71198090Srdivacky // Create spanning tree, Forest contains a special data structure 72198090Srdivacky // that makes checking if two nodes are already in a common (sub-)tree 73198090Srdivacky // fast and cheap. 74198090Srdivacky EquivalenceClasses<const T*> Forest; 75198090Srdivacky for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 76198090Srdivacky EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 77198090Srdivacky Edge e = (*EWi).first; 78198090Srdivacky 79198090Srdivacky Forest.insert(e.first); 80198090Srdivacky Forest.insert(e.second); 81198090Srdivacky } 82198090Srdivacky 83198090Srdivacky // Iterate over the sorted edges, biggest first. 84198090Srdivacky for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 85198090Srdivacky EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 86198090Srdivacky Edge e = (*EWi).first; 87198090Srdivacky 88198090Srdivacky if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { 89198090Srdivacky Forest.unionSets(e.first, e.second); 90198090Srdivacky // So we know now that the edge is not already in a subtree, so we push 91198090Srdivacky // the edge to the MST. 92198090Srdivacky MST.push_back(e); 93198090Srdivacky } 94198090Srdivacky } 95198090Srdivacky } 96198090Srdivacky 97198090Srdivacky typename MaxSpanTree::iterator begin() { 98198090Srdivacky return MST.begin(); 99198090Srdivacky } 100198090Srdivacky 101198090Srdivacky typename MaxSpanTree::iterator end() { 102198090Srdivacky return MST.end(); 103198090Srdivacky } 104198090Srdivacky }; 105198090Srdivacky 106198090Srdivacky} // End llvm namespace 107198090Srdivacky 108198090Srdivacky#endif 109