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 18198090Srdivacky#include "llvm/ADT/EquivalenceClasses.h" 19249423Sdim#include "llvm/IR/BasicBlock.h" 20249423Sdim#include <algorithm> 21198090Srdivacky#include <vector> 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 { 29243830Sdim public: 30243830Sdim typedef std::pair<const T*, const T*> Edge; 31243830Sdim typedef std::pair<Edge, double> EdgeWeight; 32243830Sdim typedef std::vector<EdgeWeight> EdgeWeights; 33243830Sdim protected: 34243830Sdim typedef std::vector<Edge> MaxSpanTree; 35198090Srdivacky 36243830Sdim MaxSpanTree MST; 37243830Sdim 38243830Sdim private: 39198090Srdivacky // A comparing class for comparing weighted edges. 40198090Srdivacky struct EdgeWeightCompare { 41243830Sdim static bool getBlockSize(const T *X) { 42243830Sdim const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X); 43243830Sdim return BB ? BB->size() : 0; 44243830Sdim } 45243830Sdim 46243830Sdim bool operator()(EdgeWeight X, EdgeWeight Y) const { 47198090Srdivacky if (X.second > Y.second) return true; 48198090Srdivacky if (X.second < Y.second) return false; 49243830Sdim 50243830Sdim // Equal edge weights: break ties by comparing block sizes. 51243830Sdim size_t XSizeA = getBlockSize(X.first.first); 52243830Sdim size_t YSizeA = getBlockSize(Y.first.first); 53243830Sdim if (XSizeA > YSizeA) return true; 54243830Sdim if (XSizeA < YSizeA) return false; 55243830Sdim 56243830Sdim size_t XSizeB = getBlockSize(X.first.second); 57243830Sdim size_t YSizeB = getBlockSize(Y.first.second); 58243830Sdim if (XSizeB > YSizeB) return true; 59243830Sdim if (XSizeB < YSizeB) return false; 60243830Sdim 61198090Srdivacky return false; 62198090Srdivacky } 63198090Srdivacky }; 64198090Srdivacky 65198090Srdivacky public: 66198090Srdivacky static char ID; // Class identification, replacement for typeinfo 67198090Srdivacky 68198090Srdivacky /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a 69198090Srdivacky /// spanning tree. 70198090Srdivacky MaximumSpanningTree(EdgeWeights &EdgeVector) { 71198090Srdivacky 72243830Sdim std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare()); 73198090Srdivacky 74198090Srdivacky // Create spanning tree, Forest contains a special data structure 75198090Srdivacky // that makes checking if two nodes are already in a common (sub-)tree 76198090Srdivacky // fast and cheap. 77198090Srdivacky EquivalenceClasses<const T*> Forest; 78198090Srdivacky for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 79198090Srdivacky EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 80198090Srdivacky Edge e = (*EWi).first; 81198090Srdivacky 82198090Srdivacky Forest.insert(e.first); 83198090Srdivacky Forest.insert(e.second); 84198090Srdivacky } 85198090Srdivacky 86198090Srdivacky // Iterate over the sorted edges, biggest first. 87198090Srdivacky for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 88198090Srdivacky EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 89198090Srdivacky Edge e = (*EWi).first; 90198090Srdivacky 91198090Srdivacky if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { 92198090Srdivacky Forest.unionSets(e.first, e.second); 93198090Srdivacky // So we know now that the edge is not already in a subtree, so we push 94198090Srdivacky // the edge to the MST. 95198090Srdivacky MST.push_back(e); 96198090Srdivacky } 97198090Srdivacky } 98198090Srdivacky } 99198090Srdivacky 100198090Srdivacky typename MaxSpanTree::iterator begin() { 101198090Srdivacky return MST.begin(); 102198090Srdivacky } 103198090Srdivacky 104198090Srdivacky typename MaxSpanTree::iterator end() { 105198090Srdivacky return MST.end(); 106198090Srdivacky } 107198090Srdivacky }; 108198090Srdivacky 109198090Srdivacky} // End llvm namespace 110198090Srdivacky 111198090Srdivacky#endif 112