MaximumSpanningTree.h revision 221345
174009Sjhb//===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===// 267480Smarkm// 367480Smarkm// The LLVM Compiler Infrastructure 467480Smarkm// 567480Smarkm// This file is distributed under the University of Illinois Open Source 667480Smarkm// License. See LICENSE.TXT for details. 767480Smarkm// 867480Smarkm//===----------------------------------------------------------------------===// 967480Smarkm// 1067480Smarkm// This module provides means for calculating a maximum spanning tree for a 1167480Smarkm// given set of weighted edges. The type parameter T is the type of a node. 1267480Smarkm// 1367480Smarkm//===----------------------------------------------------------------------===// 1467480Smarkm 1567480Smarkm#ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 1667480Smarkm#define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 1767480Smarkm 1867480Smarkm#include "llvm/BasicBlock.h" 1967480Smarkm#include "llvm/ADT/EquivalenceClasses.h" 2067480Smarkm#include <vector> 2167480Smarkm#include <algorithm> 2267480Smarkm 2367480Smarkmnamespace llvm { 2467480Smarkm 2567480Smarkm /// MaximumSpanningTree - A MST implementation. 2667480Smarkm /// The type parameter T determines the type of the nodes of the graph. 2767480Smarkm template <typename T> 28269935Sgavin class MaximumSpanningTree { 2967480Smarkm 3068687Sjhb // A comparing class for comparing weighted edges. 3167480Smarkm template <typename CT> 32173007Sjulian struct EdgeWeightCompare { 33173007Sjulian bool operator()(typename MaximumSpanningTree<CT>::EdgeWeight X, 34173007Sjulian typename MaximumSpanningTree<CT>::EdgeWeight Y) const { 3567480Smarkm if (X.second > Y.second) return true; 3670067Sjhb if (X.second < Y.second) return false; 3770067Sjhb if (const BasicBlock *BBX = dyn_cast<BasicBlock>(X.first.first)) { 3870067Sjhb if (const BasicBlock *BBY = dyn_cast<BasicBlock>(Y.first.first)) { 39173030Sjulian if (BBX->size() > BBY->size()) return true; 4067480Smarkm if (BBX->size() < BBY->size()) return false; 4184306Sru } 4267480Smarkm } 43173007Sjulian if (const BasicBlock *BBX = dyn_cast<BasicBlock>(X.first.second)) { 4468687Sjhb if (const BasicBlock *BBY = dyn_cast<BasicBlock>(Y.first.second)) { 45173007Sjulian if (BBX->size() > BBY->size()) return true; 4667480Smarkm if (BBX->size() < BBY->size()) return false; 47173007Sjulian } 4867480Smarkm } 49173007Sjulian return false; 5070067Sjhb } 51173007Sjulian }; 5268687Sjhb 53202933Sattilio public: 54187746Strhodes typedef std::pair<const T*, const T*> Edge; 55178682Sjulian typedef std::pair<Edge, double> EdgeWeight; 56187746Strhodes typedef std::vector<EdgeWeight> EdgeWeights; 57187746Strhodes protected: 58187746Strhodes typedef std::vector<Edge> MaxSpanTree; 59187746Strhodes 60187746Strhodes MaxSpanTree MST; 61187746Strhodes 62178682Sjulian public: 63178682Sjulian static char ID; // Class identification, replacement for typeinfo 64178682Sjulian 65178682Sjulian /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a 66178682Sjulian /// spanning tree. 6767480Smarkm MaximumSpanningTree(EdgeWeights &EdgeVector) { 68196450Sjulian 69196450Sjulian std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare<T>()); 70196450Sjulian 71196450Sjulian // Create spanning tree, Forest contains a special data structure 72196450Sjulian // that makes checking if two nodes are already in a common (sub-)tree 73196450Sjulian // fast and cheap. 74196450Sjulian EquivalenceClasses<const T*> Forest; 75196450Sjulian for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 76196450Sjulian EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 77196450Sjulian Edge e = (*EWi).first; 78196450Sjulian 79196450Sjulian Forest.insert(e.first); 80196450Sjulian Forest.insert(e.second); 81196450Sjulian } 82196450Sjulian 83196450Sjulian // Iterate over the sorted edges, biggest first. 84196450Sjulian for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 85233648Seadler EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 86196450Sjulian Edge e = (*EWi).first; 87196450Sjulian 88196450Sjulian if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { 8967480Smarkm Forest.unionSets(e.first, e.second); 90173007Sjulian // So we know now that the edge is not already in a subtree, so we push 9168687Sjhb // the edge to the MST. 9268687Sjhb MST.push_back(e); 93173030Sjulian } 94173030Sjulian } 95173030Sjulian } 96173030Sjulian 97173030Sjulian typename MaxSpanTree::iterator begin() { 9868687Sjhb return MST.begin(); 9968687Sjhb } 10068687Sjhb 10168687Sjhb typename MaxSpanTree::iterator end() { 10268687Sjhb return MST.end(); 103173030Sjulian } 10468687Sjhb }; 10568687Sjhb 106173007Sjulian} // End llvm namespace 107173030Sjulian 108173030Sjulian#endif 109173030Sjulian