MaximumSpanningTree.h revision 249423
161981Sbrian//===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===// 261981Sbrian// 361981Sbrian// The LLVM Compiler Infrastructure 461981Sbrian// 561981Sbrian// This file is distributed under the University of Illinois Open Source 661981Sbrian// License. See LICENSE.TXT for details. 761981Sbrian// 861981Sbrian//===----------------------------------------------------------------------===// 961981Sbrian// 1061981Sbrian// This module provides means for calculating a maximum spanning tree for a 1161981Sbrian// given set of weighted edges. The type parameter T is the type of a node. 1261981Sbrian// 13140771Skeramida//===----------------------------------------------------------------------===// 14140771Skeramida 15140771Skeramida#ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 1661981Sbrian#define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H 1761981Sbrian 1861981Sbrian#include "llvm/ADT/EquivalenceClasses.h" 1961981Sbrian#include "llvm/IR/BasicBlock.h" 2061981Sbrian#include <algorithm> 2161981Sbrian#include <vector> 2261981Sbrian 2361981Sbriannamespace llvm { 2461981Sbrian 2561981Sbrian /// MaximumSpanningTree - A MST implementation. 2661981Sbrian /// The type parameter T determines the type of the nodes of the graph. 2761981Sbrian template <typename T> 2865843Sbrian class MaximumSpanningTree { 2965843Sbrian public: 3065843Sbrian typedef std::pair<const T*, const T*> Edge; 3165843Sbrian typedef std::pair<Edge, double> EdgeWeight; 3265843Sbrian typedef std::vector<EdgeWeight> EdgeWeights; 3365843Sbrian protected: 3465843Sbrian typedef std::vector<Edge> MaxSpanTree; 3565843Sbrian 3665843Sbrian MaxSpanTree MST; 3765843Sbrian 3861981Sbrian private: 3961981Sbrian // A comparing class for comparing weighted edges. 4061981Sbrian struct EdgeWeightCompare { 4161981Sbrian static bool getBlockSize(const T *X) { 4261981Sbrian const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X); 4361981Sbrian return BB ? BB->size() : 0; 4461981Sbrian } 4561981Sbrian 4661981Sbrian bool operator()(EdgeWeight X, EdgeWeight Y) const { 4761981Sbrian if (X.second > Y.second) return true; 4861981Sbrian if (X.second < Y.second) return false; 4961981Sbrian 5061981Sbrian // Equal edge weights: break ties by comparing block sizes. 5161981Sbrian size_t XSizeA = getBlockSize(X.first.first); 5261981Sbrian size_t YSizeA = getBlockSize(Y.first.first); 5361981Sbrian if (XSizeA > YSizeA) return true; 5461981Sbrian if (XSizeA < YSizeA) return false; 5561981Sbrian 5661981Sbrian size_t XSizeB = getBlockSize(X.first.second); 5761981Sbrian size_t YSizeB = getBlockSize(Y.first.second); 5861981Sbrian if (XSizeB > YSizeB) return true; 5961981Sbrian if (XSizeB < YSizeB) return false; 6061981Sbrian 6161981Sbrian return false; 6261981Sbrian } 6361981Sbrian }; 6461981Sbrian 6561981Sbrian public: 66108959Swollman static char ID; // Class identification, replacement for typeinfo 67108959Swollman 6861981Sbrian /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a 6961981Sbrian /// spanning tree. 7061981Sbrian MaximumSpanningTree(EdgeWeights &EdgeVector) { 7161981Sbrian 7261981Sbrian std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare()); 7361981Sbrian 7461981Sbrian // Create spanning tree, Forest contains a special data structure 7561981Sbrian // that makes checking if two nodes are already in a common (sub-)tree 7661981Sbrian // fast and cheap. 7761981Sbrian EquivalenceClasses<const T*> Forest; 7861981Sbrian for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 7961981Sbrian EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 8062054Sbrian Edge e = (*EWi).first; 8177496Sbrian 8277492Sbrian Forest.insert(e.first); 8361981Sbrian Forest.insert(e.second); 8461981Sbrian } 8561981Sbrian 8661981Sbrian // Iterate over the sorted edges, biggest first. 8761981Sbrian for (typename EdgeWeights::iterator EWi = EdgeVector.begin(), 8861981Sbrian EWe = EdgeVector.end(); EWi != EWe; ++EWi) { 89155060Smatteo Edge e = (*EWi).first; 9061981Sbrian 91121620Sjesper if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) { 92123498Sjesper Forest.unionSets(e.first, e.second); 93121620Sjesper // So we know now that the edge is not already in a subtree, so we push 94154304Swollman // the edge to the MST. 95154304Swollman MST.push_back(e); 96154304Swollman } 9761981Sbrian } 9861981Sbrian } 9961981Sbrian 10061981Sbrian typename MaxSpanTree::iterator begin() { 10161981Sbrian return MST.begin(); 10261981Sbrian } 10361981Sbrian 10461981Sbrian typename MaxSpanTree::iterator end() { 10561981Sbrian return MST.end(); 10661981Sbrian } 10794342Sgshapiro }; 10861981Sbrian 10961981Sbrian} // End llvm namespace 11061981Sbrian 11187514Scjc#endif 11261981Sbrian