• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- llvm/Analysis/MaximumSpanningTree.h - Interface ----------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This module provides means for calculating a maximum spanning tree for a
11 // given set of weighted edges. The type parameter T is the type of a node.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
16 #define LLVM_ANALYSIS_MAXIMUMSPANNINGTREE_H
17 
18 #include "llvm/ADT/EquivalenceClasses.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include <algorithm>
21 #include <vector>
22 
23 namespace llvm {
24 
25   /// MaximumSpanningTree - A MST implementation.
26   /// The type parameter T determines the type of the nodes of the graph.
27   template <typename T>
28   class MaximumSpanningTree {
29   public:
30     typedef std::pair<const T*, const T*> Edge;
31     typedef std::pair<Edge, double> EdgeWeight;
32     typedef std::vector<EdgeWeight> EdgeWeights;
33   protected:
34     typedef std::vector<Edge> MaxSpanTree;
35 
36     MaxSpanTree MST;
37 
38   private:
39     // A comparing class for comparing weighted edges.
40     struct EdgeWeightCompare {
getBlockSizeEdgeWeightCompare41       static bool getBlockSize(const T *X) {
42         const BasicBlock *BB = dyn_cast_or_null<BasicBlock>(X);
43         return BB ? BB->size() : 0;
44       }
45 
operatorEdgeWeightCompare46       bool operator()(EdgeWeight X, EdgeWeight Y) const {
47         if (X.second > Y.second) return true;
48         if (X.second < Y.second) return false;
49 
50         // Equal edge weights: break ties by comparing block sizes.
51         size_t XSizeA = getBlockSize(X.first.first);
52         size_t YSizeA = getBlockSize(Y.first.first);
53         if (XSizeA > YSizeA) return true;
54         if (XSizeA < YSizeA) return false;
55 
56         size_t XSizeB = getBlockSize(X.first.second);
57         size_t YSizeB = getBlockSize(Y.first.second);
58         if (XSizeB > YSizeB) return true;
59         if (XSizeB < YSizeB) return false;
60 
61         return false;
62       }
63     };
64 
65   public:
66     static char ID; // Class identification, replacement for typeinfo
67 
68     /// MaximumSpanningTree() - Takes a vector of weighted edges and returns a
69     /// spanning tree.
MaximumSpanningTree(EdgeWeights & EdgeVector)70     MaximumSpanningTree(EdgeWeights &EdgeVector) {
71 
72       std::stable_sort(EdgeVector.begin(), EdgeVector.end(), EdgeWeightCompare());
73 
74       // Create spanning tree, Forest contains a special data structure
75       // that makes checking if two nodes are already in a common (sub-)tree
76       // fast and cheap.
77       EquivalenceClasses<const T*> Forest;
78       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
79            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
80         Edge e = (*EWi).first;
81 
82         Forest.insert(e.first);
83         Forest.insert(e.second);
84       }
85 
86       // Iterate over the sorted edges, biggest first.
87       for (typename EdgeWeights::iterator EWi = EdgeVector.begin(),
88            EWe = EdgeVector.end(); EWi != EWe; ++EWi) {
89         Edge e = (*EWi).first;
90 
91         if (Forest.findLeader(e.first) != Forest.findLeader(e.second)) {
92           Forest.unionSets(e.first, e.second);
93           // So we know now that the edge is not already in a subtree, so we push
94           // the edge to the MST.
95           MST.push_back(e);
96         }
97       }
98     }
99 
begin()100     typename MaxSpanTree::iterator begin() {
101       return MST.begin();
102     }
103 
end()104     typename MaxSpanTree::iterator end() {
105       return MST.end();
106     }
107   };
108 
109 } // End llvm namespace
110 
111 #endif
112