OpenASIP 2.2
Loading...
Searching...
No Matches
BoostGraph.hh
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2010 Tampere University.
3
4 This file is part of TTA-Based Codesign Environment (TCE).
5
6 Permission is hereby granted, free of charge, to any person obtaining a
7 copy of this software and associated documentation files (the "Software"),
8 to deal in the Software without restriction, including without limitation
9 the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 and/or sell copies of the Software, and to permit persons to whom the
11 Software is furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in
14 all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 DEALINGS IN THE SOFTWARE.
23 */
24/**
25 * @file BoostGraph.hh
26 *
27 * Declaration of boost-based templated implementation of graph base class.
28 *
29 * @author Andrea Cilio 2005 (cilio-no.spam-cs.tut.fi)
30 * @author Vladimir Guzma 2006 (vladimir.guzma-no.spam-tut.fi)
31 * @author Heikki Kultala 2007-2010
32 * @author Pekka Jääskeläinen 2009-2010
33 * @note rating: red
34 */
35
36
37#ifndef TTA_BOOST_GRAPH_HH
38#define TTA_BOOST_GRAPH_HH
39
40#include <boost/version.hpp>
41
42#if BOOST_VERSION < 103500
43// from boost v1.35 (missing from 1.34 making findAllPaths() fail)
44#include <boost/graph/detail/edge.hpp>
45
46namespace boost {
47 namespace detail {
48 template <class D, class V>
49 inline bool
50 operator<(const detail::edge_desc_impl<D,V>& a,
51 const detail::edge_desc_impl<D,V>& b) {
52 return a.get_property() < b.get_property();
53 }
54 }
55}
56
57#endif
58
59#include <map>
60#include <set>
61
62// these need to be included before Boost so we include a working
63// and warning-free hash_map
64#include "hash_set.hh"
65#include "hash_map.hh"
66
67#include "CompilerWarnings.hh"
68IGNORE_CLANG_WARNING("-Wunused-local-typedef")
69#include <boost/config.hpp>
70#include <boost/graph/adjacency_list.hpp>
71#include <boost/graph/subgraph.hpp>
73
74#include "Exception.hh"
75#include "Graph.hh"
76
77/**
78 * Graph-based program representation.
79 *
80 * Boost::graph based implementation.
81 */
82template <typename GraphNode, typename GraphEdge>
83class BoostGraph : public GraphBase<GraphNode, GraphEdge> {
84public:
85
86 typedef std::set<GraphNode*, typename GraphNode::Comparator > NodeSet;
87 typedef std::set<GraphEdge*, typename GraphEdge::Comparator > EdgeSet;
88 /// The (base) node type managed by this graph.
89 /// @todo What's the point of these typedefs?
90 typedef GraphNode Node;
91 /// The (base) edge type managed by this graph.
92 typedef GraphEdge Edge;
93
94 BoostGraph(bool allowLoopEdges = true);
95 BoostGraph(const TCEString& name, bool allowLoopEdges = true);
96 BoostGraph(const BoostGraph& other, bool allowLoopEdges = true);
98
99 int nodeCount() const;
100 int edgeCount() const;
101 Node& node(const int index) const;
102 Node& node(const int index, bool cacheResult) const;
103 virtual Edge& edge(const int index) const;
104
105 virtual void addNode(Node& node);
106
107 virtual Edge& outEdge(const Node& node, const int index) const;
108
109 virtual Edge& inEdge(const Node& node, const int index) const;
110
111 virtual EdgeSet outEdges(const Node& node) const;
112 virtual EdgeSet inEdges(const Node& node) const;
113
114 virtual EdgeSet rootGraphOutEdges(const Node& node) const;
115
116 virtual EdgeSet rootGraphInEdges(const Node& node) const;
117
118 virtual Edge& rootGraphInEdge(const Node& node, const int index) const;
119
120 virtual Edge& rootGraphOutEdge(const Node& node, const int index) const;
121
122 virtual int rootGraphInDegree(const Node& node) const;
123
124 virtual int rootGraphOutDegree(const Node& node) const;
125
126 virtual int outDegree(const Node& node) const;
127 virtual int inDegree(const Node& node) const;
128
129 virtual Node& tailNode(const Edge& edge) const;
130 virtual Node& headNode(const Edge& edge) const;
131
132 virtual void connectNodes(const Node& nTail, const Node& nHead, Edge& e);
133
134 virtual void disconnectNodes(const Node& nTail, const Node& nHead);
135
136 virtual void moveInEdges(const Node& source, const Node& destination);
137 virtual void moveOutEdges(const Node& source, const Node& destination);
138
139 virtual void moveInEdge(const Node& source, const Node& destination,
140 Edge& edge,
141 const Node* tail = NULL, bool childs = false);
142
143 virtual void moveOutEdge(const Node& source, const Node& destination,
144 Edge& edge,
145 const Node* head = NULL, bool childs = false);
146
147 virtual void copyInEdge(const Node& destination, Edge& edge,
148 const Node* tail = NULL);
149
150 virtual void copyOutEdge(const Node& destination, Edge& edge,
151 const Node* head = NULL);
152
153 virtual void removeNode(Node& node);
154 virtual void removeEdge(Edge& e);
155
156 virtual void dropNode(Node& node);
157
158 virtual void dropEdge(Edge& edge);
159
160 virtual bool hasEdge(
161 const Node& nTail,
162 const Node& nHead) const;
163
164 /// useful utility functions
165 virtual NodeSet rootNodes() const;
166 virtual NodeSet sinkNodes() const;
167
169 const Node& node, bool ignoreBackEdges=false,
170 bool ignoreForwardEdges=false) const;
172 const Node& node, bool ignoreBackEdges=false,
173 bool ignoreForwardEdges=false) const;
174
175 // critical path-related functions
176 int maxPathLength(const GraphNode& node) const;
177 int maxSinkDistance(const GraphNode& node) const;
179 bool isInCriticalPath(const GraphNode& node) const {
181 }
182 int height() const;
183 void findAllPaths() const;
184
185 void detachSubgraph(BoostGraph& subGraph);
186
189
190 const BoostGraph* rootGraph() const;
191
192 bool hasNode(const Node&) const;
193
194 virtual const TCEString& name() const;
195 void setName(const TCEString& newName) { name_ = newName; }
196
197 bool hasPath(GraphNode& src, const GraphNode& dest) const;
198
201
203 const Node& nTail, const Node& nHead) const;
204
205private:
206 /// Assignment forbidden.
208
209protected:
210
212 public:
213 size_t operator()(const GraphNode* node) const {
214 int tmp = reinterpret_cast<size_t>(node);
215 return tmp ^ (tmp >> 16);
216 }
217 size_t operator()(const GraphEdge* edge) const {
218 int tmp = reinterpret_cast<size_t>(edge);
219 return tmp ^ (tmp >> 16);
220 }
221 };
222
227
229 nTail(tail), nHead(head), edge(e) {}
230
231 bool operator< (const RemovedEdgeDatum& other) const {
232 return edge.edgeID() < other.edge.edgeID();
233 }
234 };
235
236 typedef std::set<RemovedEdgeDatum> RemovedEdgeMap;
237
239
240 /// Internal graph type, providing actual graph-like operations.
241 /// This type definition relies on bundled properties of boost library,
242 /// which need the host compiler to support partial template
243 /// specialisation.
244
245 typedef typename boost::adjacency_list<
246 boost::listS, boost::vecS,
247 boost::bidirectionalS, Node*, Edge*> Graph;
248
249 /// Traits characterising the internal graph type.
250 typedef typename boost::graph_traits<Graph> GraphTraits;
251
252 /// Output edge iterator type.
253 typedef typename GraphTraits::out_edge_iterator OutEdgeIter;
254 /// Input edge iterator type.
255 typedef typename GraphTraits::in_edge_iterator InEdgeIter;
256 /// Iterator type for the list of all edges in the graph.
257 typedef typename GraphTraits::edge_iterator EdgeIter;
258 /// Iterator type for the list of all nodes in the graph.
259 typedef typename GraphTraits::vertex_iterator NodeIter;
260
261 /// Type with which edges of the graph are seen internally.
262 typedef typename GraphTraits::edge_descriptor EdgeDescriptor;
263 /// Type with which nodes of the graph are seen internally.
264 typedef typename GraphTraits::vertex_descriptor NodeDescriptor;
265
266 // private helper methods
267
268 // this is a slow(linear to size of the graph) operation
270 // these two are much faster operations
272 const NodeDescriptor& tailNode, const Edge& e) const;
274 const Edge& e, const NodeDescriptor& headNode) const;
277 const Node& nTail,
278 const Node& nHead,
279 const Edge& edge) const;
281 const Edge& edge, const Node* nTail = NULL, const Node* nHead = NULL)
282 const;
283
285 const Node& nTail,
286 const Node& nHead) const;
287
288 // optimized but uglier versions
291
292 // fast node removal
294
295 // internal implementation of path-length-related things.
297
299
301 const GraphNode& node, int len, bool looping = false) const;
302
304 const GraphNode* startNode = NULL, int startingLength = 0,
305 bool looping = false) const;
306
308 const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e);
309
310 void sinkDistDecreased(const GraphNode& n) const;
311
312 void sourceDistDecreased(const GraphNode& n) const;
313
314 virtual int edgeWeight( GraphEdge& e, const GraphNode& n) const;
315
316 // Calculated path lengths
317 mutable std::unordered_map<const GraphNode*,int>
319 mutable std::unordered_map<const GraphNode*,int>
321
322 // Calculated path lengths
323 mutable std::unordered_map<const GraphNode*,int>
325 mutable std::unordered_map<const GraphNode*,int>
327
328 mutable int height_;
329
330 /// The internal graph structure.
332
333 // these cache data that may get cached even on ro operations,
334 // so they are mutable.
335 typedef hash_map<const Edge*, EdgeDescriptor, GraphHashFunctions>
337 typedef hash_map<const Node*, NodeDescriptor, GraphHashFunctions>
339
342
344
345 // graph editing functions which tell the changes to parents and childs
346
347 virtual void removeNode(Node& node, BoostGraph* modifierGraph);
348 virtual void removeEdge(
349 Edge& e, const GraphNode* tailNode, const GraphNode* headNode,
350 BoostGraph* modifierGraph = NULL);
351
352 virtual void connectNodes(
353 const Node& nTail, const Node& nHead, Edge& e,
354 GraphBase<GraphNode, GraphEdge>* modifier, bool creatingSG = false);
355
357 const Node& source, const Node& destination, BoostGraph* modifierGraph);
358
359 virtual void moveOutEdges(
360 const Node& source, const Node& destination, BoostGraph* modifierGraph);
361 void constructSubGraph(BoostGraph& subGraph, NodeSet& nodes);
362
363 /**
364 * This class is used in the pririty queue, to select which node to
365 * start sink distance calculations */
368 NodeDescriptor nd, int len, int sd, bool looping = false);
370 int len_;
371 int sd_;
373 inline bool operator< (const PathLengthHelper& other) const;
374 };
375
376 // for subgraphs
378 std::vector<BoostGraph<GraphNode,GraphEdge>*> childGraphs_;
379
382
383 std::set<Edge*> ownedEdges_;
385
386 // cache to speed up hasPath(), call findAllPaths() to initialize
387 typedef std::vector<std::vector<int> > PathCache;
389};
390
391#include "BoostGraph.icc"
392
393#endif
#define POP_CLANG_DIAGS
#define IGNORE_CLANG_WARNING(X)
size_t operator()(const GraphNode *node) const
size_t operator()(const GraphEdge *edge) const
void restoreRemovedEdges(RemovedEdgeMap removedEdges)
int maxSourceDistance(const GraphNode &node) const
BoostGraph * rootGraph()
virtual EdgeSet rootGraphOutEdges(const Node &node) const
void sinkDistDecreased(const GraphNode &n) const
virtual void removeEdge(Edge &e)
BoostGraph(bool allowLoopEdges=true)
std::set< RemovedEdgeDatum > RemovedEdgeMap
virtual void disconnectNodes(const Node &nTail, const Node &nHead)
bool hasEdge(const Edge &edge, const Node *nTail=NULL, const Node *nHead=NULL) const
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e, GraphBase< GraphNode, GraphEdge > *modifier, bool creatingSG=false)
virtual void moveOutEdges(const Node &source, const Node &destination, BoostGraph *modifierGraph)
EdgeDescriptor descriptor(const Edge &e) const
GraphTraits::vertex_descriptor NodeDescriptor
Type with which nodes of the graph are seen internally.
GraphTraits::out_edge_iterator OutEdgeIter
Output edge iterator type.
virtual void moveOutEdges(const Node &source, const Node &destination)
virtual Node & headNode(const Edge &edge) const
int nodeCount() const
Node & tailNode(const Edge &edge, const NodeDescriptor &headNode) const
int edgeCount() const
virtual int edgeWeight(GraphEdge &e, const GraphNode &n) const
void calculateSourceDistances(const GraphNode *startNode=NULL, int startingLength=0, bool looping=false) const
boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, Node *, Edge * > Graph
Internal graph type, providing actual graph-like operations. This type definition relies on bundled p...
virtual NodeSet rootNodes() const
useful utility functions
NodeDescriptor descriptor(const Node &n) const
void detachSubgraph(BoostGraph &subGraph)
void sourceDistDecreased(const GraphNode &n) const
virtual void copyOutEdge(const Node &destination, Edge &edge, const Node *head=NULL)
int maxSinkDistance(const GraphNode &node) const
int maxPathLength(const GraphNode &node) const
Node & headNode(const Edge &edge, const NodeDescriptor &tailNode) const
std::set< GraphEdge *, typename GraphEdge::Comparator > EdgeSet
Definition BoostGraph.hh:87
virtual int rootGraphInDegree(const Node &node) const
void calculatePathLengths() const
virtual Edge & outEdge(const Node &node, const int index) const
BoostGraph * parentGraph()
void setName(const TCEString &newName)
hash_map< const Node *, NodeDescriptor, GraphHashFunctions > NodeDescMap
virtual void removeNode(Node &node)
EdgeDescMap edgeDescriptors_
virtual void dropEdge(Edge &edge)
virtual Edge & inEdge(const Node &node, const int index) const
void restoreNodeFromParent(GraphNode &node)
BoostGraph(const TCEString &name, bool allowLoopEdges=true)
virtual bool hasEdge(const Node &nTail, const Node &nHead) const
virtual void copyInEdge(const Node &destination, Edge &edge, const Node *tail=NULL)
virtual int rootGraphOutDegree(const Node &node) const
virtual Edge & rootGraphInEdge(const Node &node, const int index) const
void calculatePathLengthsOnConnect(const GraphNode &nTail, const GraphNode &nHead, GraphEdge &e)
virtual void addNode(Node &node)
GraphTraits::in_edge_iterator InEdgeIter
Input edge iterator type.
virtual void moveOutEdge(const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false)
EdgeDescriptor edgeDescriptor(const NodeDescriptor &tailNode, const Edge &e) const
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
Node & node(const int index) const
bool hasNode(const Node &) const
BoostGraph(const BoostGraph &other, bool allowLoopEdges=true)
EdgeDescriptor connectingEdge(const Node &nTail, const Node &nHead) const
virtual void dropNode(Node &node)
virtual const TCEString & name() const
bool hasPath(GraphNode &src, const GraphNode &dest) const
TCEString name_
GraphTraits::edge_descriptor EdgeDescriptor
Type with which edges of the graph are seen internally.
void replaceNodeWithLastNode(GraphNode &dest)
virtual Edge & rootGraphOutEdge(const Node &node, const int index) const
boost::graph_traits< Graph > GraphTraits
Traits characterising the internal graph type.
virtual int inDegree(const Node &node) const
std::unordered_map< const GraphNode *, int > loopingSinkDistances_
std::vector< BoostGraph< GraphNode, GraphEdge > * > childGraphs_
void calculatePathLengthsFast() const
std::unordered_map< const GraphNode *, int > loopingSourceDistances_
std::set< GraphNode *, typename GraphNode::Comparator > NodeSet
Definition BoostGraph.hh:86
bool detectIllegalCycles() const
virtual void moveInEdge(const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
void findAllPaths() const
virtual NodeSet predecessors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
virtual int outDegree(const Node &node) const
GraphNode Node
The (base) node type managed by this graph.
Definition BoostGraph.hh:90
EdgeSet connectingEdges(const Node &nTail, const Node &nHead) const
virtual EdgeSet outEdges(const Node &node) const
virtual void removeEdge(Edge &e, const GraphNode *tailNode, const GraphNode *headNode, BoostGraph *modifierGraph=NULL)
std::set< Edge * > ownedEdges_
GraphTraits::vertex_iterator NodeIter
Iterator type for the list of all nodes in the graph.
bool isInCriticalPath(const GraphNode &node) const
hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions > EdgeDescMap
virtual Node & tailNode(const Edge &edge) const
PathCache * pathCache_
bool hasEdge(const Node &nTail, const Node &nHead, const Edge &edge) const
EdgeDescriptor edgeDescriptor(const Edge &e, const NodeDescriptor &headNode) const
bool allowLoopEdges_
void clearDescriptorCache(EdgeSet edges)
std::unordered_map< const GraphNode *, int > sourceDistances_
virtual void moveInEdges(const Node &source, const Node &destination)
Node & node(const int index, bool cacheResult) const
virtual void removeNode(Node &node, BoostGraph *modifierGraph)
virtual Edge & edge(const int index) const
GraphEdge Edge
The (base) edge type managed by this graph.
Definition BoostGraph.hh:92
NodeDescMap nodeDescriptors_
Graph graph_
The internal graph structure.
std::vector< std::vector< int > > PathCache
const BoostGraph * rootGraph() const
int height() const
std::unordered_map< const GraphNode *, int > sinkDistances_
void constructSubGraph(BoostGraph &subGraph, NodeSet &nodes)
virtual NodeSet sinkNodes() const
void moveInEdges(const Node &source, const Node &destination, BoostGraph *modifierGraph)
BoostGraph< GraphNode, GraphEdge > * parentGraph_
virtual EdgeSet inEdges(const Node &node) const
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
BoostGraph & operator=(const BoostGraph &)
Assignment forbidden.
virtual EdgeSet rootGraphInEdges(const Node &node) const
GraphTraits::edge_iterator EdgeIter
Iterator type for the list of all edges in the graph.
void calculateSinkDistance(const GraphNode &node, int len, bool looping=false) const
virtual int edgeID() const
Definition GraphEdge.cc:92
bool operator<(const detail::edge_desc_impl< D, V > &a, const detail::edge_desc_impl< D, V > &b)
Definition BoostGraph.hh:50
bool operator<(const PathLengthHelper &other) const
PathLengthHelper(NodeDescriptor nd, int len, int sd, bool looping=false)
RemovedEdgeDatum(GraphNode &tail, GraphNode &head, GraphEdge &e)
bool operator<(const RemovedEdgeDatum &other) const