OpenASIP 2.2
Loading...
Searching...
No Matches
BoostGraph.icc
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.icc
26 *
27 * Boost-based templated implementation of graph base class.
28 * In-line implementation of templated methods.
29 *
30 * @author Andrea Cilio 2005 (cilio-no.spam-cs.tut.fi)
31 * @author Vladimir Guzma 2006 (vladimir.guzma-no.spam-tut.fi)
32 * @author Heikki Kultala 2007-2010
33 * @author Pekka Jääskeläinen 2009-2010
34 * @note rating: red
35 */
36
37#include <queue>
38#include <map>
39#include <algorithm>
40#include <climits>
41#include <boost/version.hpp>
42#include <boost/format.hpp>
43
44#include "CompilerWarnings.hh"
45IGNORE_COMPILER_WARNING("-Wunused-parameter")
46IGNORE_CLANG_WARNING("-Wunused-local-typedef")
47#include <boost/graph/topological_sort.hpp>
48
49#if BOOST_VERSION < 104000
50#include <boost/property_map.hpp>
51#else
52#include <boost/property_map/property_map.hpp>
53#endif
54
55#include <boost/graph/adjacency_list.hpp>
56#include <boost/graph/graphviz.hpp>
57#include <boost/graph/johnson_all_pairs_shortest.hpp>
58POP_CLANG_DIAGS
59POP_COMPILER_DIAGS
60
61#include "Conversion.hh"
62#include "AssocTools.hh"
63#include "Application.hh"
64#include "SetTools.hh"
65#include "hash_map.hh"
66
67/**
68 * Constructor
69 *
70 */
71template <typename GraphNode, typename GraphEdge>
72BoostGraph<GraphNode, GraphEdge>::BoostGraph(bool allowLoopEdges) :
73 height_(-1), parentGraph_(NULL), sgCounter_(0),
74 allowLoopEdges_(allowLoopEdges), pathCache_(NULL) {}
75
76/**
77 * Constructor
78 *
79 */
80template <typename GraphNode, typename GraphEdge>
81BoostGraph<GraphNode, GraphEdge>::BoostGraph(
82 const TCEString& name, bool allowLoopEdges) :
83 height_(-1), parentGraph_(NULL), name_(name), sgCounter_(0),
84 allowLoopEdges_(allowLoopEdges), pathCache_(NULL) {}
85
86/**
87 * Copy constructor
88 *
89 */
90template <typename GraphNode, typename GraphEdge>
91BoostGraph<GraphNode, GraphEdge>::BoostGraph(
92 const BoostGraph<GraphNode, GraphEdge>& other, bool allowLoopEdges) :
93 GraphBase<GraphNode, GraphEdge>(), height_(other.height_),
94 parentGraph_(NULL) , name_(other.name()), sgCounter_(0),
95 allowLoopEdges_(allowLoopEdges), pathCache_(NULL) {
96
97 // table which node of other
98 std::map<GraphNode*, GraphNode*> nodeMap;
99
100 for (int i = 0; i < other.nodeCount(); i++) {
101 GraphNode& currNode = other.node(i);
102 if (nodeMap.find(&currNode) == nodeMap.end()){
103 nodeMap[&currNode] =
104 dynamic_cast<GraphNode*>(currNode.clone());
105 addNode(*nodeMap[&currNode]);
106 }
107
108 GraphNode* ourTail = nodeMap[&currNode];
109
110 // copy all out edges of the node
111 EdgeSet outs = other.outEdges(currNode);
112 typename EdgeSet::iterator iter;
113 for (iter = outs.begin(); iter != outs.end(); iter++) {
114 GraphEdge* outEdge = *iter;
115 GraphNode& headNode = other.headNode(*outEdge);
116
117 if (nodeMap.find(&headNode) == nodeMap.end()){
118 nodeMap[&headNode] =
119 dynamic_cast<GraphNode*>(headNode.clone());
120 addNode(*nodeMap[&headNode]);
121 }
122
123 GraphNode* ourHead = nodeMap[&headNode];
124 GraphEdge* ourEdge = dynamic_cast<GraphEdge*>(outEdge->clone());
125
126 connectNodes(*ourTail, *ourHead, *ourEdge);
127 }
128 }
129}
130
131/**
132 * Destructor
133 *
134 * This automatically deletes all edges that have been in the graph.
135 * Those should not be deleted by destructors of deleted graphs.
136 */
137template <typename GraphNode, typename GraphEdge>
138BoostGraph<GraphNode, GraphEdge>::~BoostGraph() {
139 if (parentGraph_ != NULL) {
140 parentGraph_->detachSubgraph(*this);
141 }
142 for (typename std::set<GraphEdge*>::iterator i = ownedEdges_.begin();
143 i != ownedEdges_.end(); i++) {
144 delete *i;
145 }
146 delete pathCache_;
147 pathCache_ = NULL;
148}
149
150/**
151 * Adds a node to the graph.
152 *
153 * Once added, a node is owned and managed by the graph.
154 *
155 * Adding a node does not add it to the subgraphs of a graph,
156 * but does add into the parent graph.
157 *
158 * @param node Node to be added.
159 */
160template <typename GraphNode, typename GraphEdge>
161void
162BoostGraph<GraphNode, GraphEdge>::addNode(GraphNode& node) {
163 NodeDescriptor nd = boost::add_vertex(&node, graph_);
164 nodeDescriptors_[&node] = nd;
165
166 if (height_ != -1) {
167 sourceDistances_[&node] = 0;
168 sinkDistances_[&node] = 0;
169
170 loopingSourceDistances_[&node] = 0;
171 loopingSinkDistances_[&node] = 0;
172 }
173
174 // add node also to parent graph
175 if (parentGraph_ != NULL) {
176 parentGraph_->addNode(node);
177 }
178}
179
180/**
181 * Returns the number of nodes contained in this graph.
182 *
183 * @returns The number of nodes.
184 */
185template <typename GraphNode, typename GraphEdge>
186int
187BoostGraph<GraphNode, GraphEdge>::nodeCount() const {
188 return boost::num_vertices(graph_);
189}
190
191/**
192 * Returns the number of edges contained in this graph.
193 *
194 * @returns The number of edges.
195 */
196template <typename GraphNode, typename GraphEdge>
197int
198BoostGraph<GraphNode, GraphEdge>::edgeCount() const {
199 return boost::num_edges(graph_);
200}
201
202/**
203 * Returns the node of the graph identified by the given index.
204 *
205 * Notice that the index is not constant. If nodes are added or removed from
206 * the graph, the index of an untouched node may change.
207 *
208 * @param index Index of a node of the graph.
209 * @returns The node currently identified by the given index.
210 * @exception OutOfRange If the given index is negative, or is not smaller
211 * than the number of nodes of the graph.
212 */
213template <typename GraphNode, typename GraphEdge>
214GraphNode&
215BoostGraph<GraphNode, GraphEdge>::node(const int index) const {
216 return node(index, true);
217}
218
219/**
220 * Returns the node of the graph identified by the given index.
221 *
222 * Notice that the index is not constant. If nodes are added or removed from
223 * the graph, the index of an untouched node may change.
224 *
225 * @param index Index of a node of the graph.
226 * @returns The node currently identified by the given index.
227 * @exception OutOfRange If the given index is negative, or is not smaller
228 * than the number of nodes of the graph.
229 */
230template <typename GraphNode, typename GraphEdge>
231GraphNode&
232BoostGraph<GraphNode, GraphEdge>::node(
233 const int index, bool cacheResult) const {
234 if (index < 0 || index >= nodeCount()) {
235 TCEString procName("BoostGraph::node");
236 boost::format errorMsg("Node index %1% out of range [0, %2%).");
237 errorMsg % index % nodeCount();
238 throw OutOfRange(__FILE__, __LINE__, procName, errorMsg.str());
239 }
240 NodeDescriptor nd = boost::vertex(index, graph_);
241 Node* n = graph_[nd];
242 if (cacheResult) {
243 nodeDescriptors_[n] = nd;
244 }
245 return *n;
246}
247
248/**
249 * Returns the edge of the graph identified by the given index.
250 *
251 * Notice that the index is not constant. If edges are added or removed from
252 * the graph, the index of an untouched edge may change.
253 *
254 * Running time of this function is O(n) where n is the number of edges.
255 *
256 * @param index Index of an edge of the graph.
257 * @returns The edge currently identified by the given index.
258 * @exception OutOfRange If the given index is negative, or is not smaller
259 * than the number of edges of the graph.
260 */
261template <typename GraphNode, typename GraphEdge>
262GraphEdge&
263BoostGraph<GraphNode, GraphEdge>::edge(const int index) const {
264 if (index < 0 || index >= edgeCount()) {
265 TCEString procName("BoostGraph::edge");
266 boost::format errorMsg("Edge index %1% out of range [0, %2%).");
267 errorMsg % index % edgeCount();
268 throw OutOfRange(__FILE__, __LINE__, procName, errorMsg.str());
269 }
270
271 typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
272 EdgeIterPair edges = boost::edges(graph_);
273 int counter = 0;
274 for (EdgeIter i = edges.first; i != edges.second; i++) {
275 if (counter == index) {
276 GraphEdge* theEdge = graph_[*i];
277 return *theEdge;
278 }
279 counter++;
280 }
281 assert(false);
282 // keep pedantic compilers quiet
283 return *graph_[*edges.second];
284}
285
286/**
287 * Returns the n:th outgoing edge from a given node.
288 *
289 * Warning: this function is slow. When iterating over all outgoing edges
290 * of a node, use outEdges instead.
291 *
292 * @param node Node whose outgoing edges we are searching
293 * @param index index of outgoing edge being asked
294 * @return The edge.
295 */
296template <typename GraphNode, typename GraphEdge>
297GraphEdge&
298BoostGraph<GraphNode, GraphEdge>::outEdge(
299 const GraphNode& node, const int index) const {
300 const TCEString procName("BoostGraph::outEdge");
301
302 if (outDegree(node) <= index) {
303 boost::format errorMsg(
304 "Outgoing edge at index %1% is out of range. The node "
305 "out-degree is %2%.");
306 errorMsg % index % outDegree(node);
307 throw OutOfRange(__FILE__, __LINE__, procName, errorMsg.str());
308 }
309
310 std::pair<OutEdgeIter, OutEdgeIter> edges =
311 boost::out_edges(descriptor(node), graph_);
312 if (edges.first == edges.second) {
313 TCEString errorMsg("Node does not belong to this graph.");
314 throw InstanceNotFound(__FILE__, __LINE__, procName, errorMsg);
315 }
316
317 GraphEdge* result = NULL;
318 int n = 0;
319 for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
320 if (n == index) {
321 result = graph_[(*ei)];
322 break;
323 } else {
324 n++;
325 }
326 }
327 assert(result != NULL);
328
329 return *result;
330}
331
332/**
333 * Returns the n:th incoming edge to a given node.
334 *
335 * Warning: this function is slow. When iterating over all incoming edges
336 * of a node, use inEdges instead.
337 *
338 * @param node Node whose incoming edges we are searching
339 * @param index index of incoming edge being asked
340 * @return The edge.
341 */
342template <typename GraphNode, typename GraphEdge>
343GraphEdge&
344BoostGraph<GraphNode, GraphEdge>::inEdge(
345 const GraphNode& node, const int index) const {
346 std::pair<InEdgeIter, InEdgeIter> edges =
347 boost::in_edges(descriptor(node), graph_);
348 if (edges.first == edges.second) {
349 const TCEString procName("BoostGraph::inEdge");
350 TCEString errorMsg("Node does not belong to this graph.");
351 throw InstanceNotFound(__FILE__, __LINE__, __func__, errorMsg);
352 }
353
354 GraphEdge* result = NULL;
355 int n = 0;
356 for (InEdgeIter ei = edges.first; ei != edges.second; ei++) {
357 if (n == index) {
358 result = graph_[(*ei)];
359 break;
360 } else {
361 n++;
362 }
363 }
364 if (result == NULL) {
365 boost::format errorMsg(
366 "Incoming edge at index %1% is out of range. The node "
367 "in-degree is %2%.");
368 errorMsg % index % inDegree(node);
369 throw OutOfRange(__FILE__, __LINE__, __func__, errorMsg.str());
370 }
371
372 return *result;
373}
374
375/**
376 * Returns the outgoing edges of a node.
377 *
378 * @param node A node of the graph.
379 * @returns A set of edges.
380 */
381template <typename GraphNode, typename GraphEdge>
382typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
383BoostGraph<GraphNode, GraphEdge>::outEdges(const GraphNode& node) const {
384 typedef typename GraphTraits::out_edge_iterator outEdgeIter;
385 std::pair<outEdgeIter, outEdgeIter> edges = boost::out_edges(
386 descriptor(node), graph_);
387 EdgeSet result;
388 for (outEdgeIter ei = edges.first; ei != edges.second; ei++) {
389 GraphEdge* edge = graph_[(*ei)];
390 // add to descriptor cache.
391 edgeDescriptors_[edge] = *ei;
392 result.insert(edge);
393 }
394 return result;
395}
396
397/**
398 * Returns the outgoing edges of a node in the root graph of the
399 * subgraph tree.
400 *
401 * @param node A node of the graph.
402 * @returns A set of edges.
403 */
404template <typename GraphNode, typename GraphEdge>
405typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
406BoostGraph<GraphNode, GraphEdge>::rootGraphOutEdges(
407 const GraphNode& node) const {
408 if (parentGraph_ == NULL) {
409 return outEdges(node);
410 } else {
411 return parentGraph_->rootGraphOutEdges(node);
412 }
413}
414
415/**
416 * Returns the ingoing edges of a node.
417 *
418 * @param node A node of the graph.
419 * @returns A set of edges.
420 */
421template <typename GraphNode, typename GraphEdge>
422typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
423BoostGraph<GraphNode, GraphEdge>::inEdges(const GraphNode& node) const {
424 typedef typename GraphTraits::in_edge_iterator InEdgeIter;
425 std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
426 descriptor(node), graph_);
427 EdgeSet result;
428 for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
429 GraphEdge* edge = graph_[(*ei)];
430 edgeDescriptors_[edge] = *ei;
431 result.insert(edge);
432 }
433 return result;
434}
435
436/**
437 * Returns the ingoing edges of a node in the root graph of the subgraph tree.
438 *
439 * @param node A node of the graph.
440 * @returns A set of edges.
441 */
442template <typename GraphNode, typename GraphEdge>
443typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
444BoostGraph<GraphNode, GraphEdge>::rootGraphInEdges(
445 const GraphNode& node) const {
446 if (parentGraph_ == NULL) {
447 return inEdges(node);
448 } else {
449 return parentGraph_->rootGraphInEdges(node);
450 }
451}
452
453/**
454 * Returns the ingoing edge of a node in the root graph of the subgraph tree.
455 *
456 * @param node A node of the graph.
457 * @param index index of edge.
458 * @return the edge edges.
459 */
460template <typename GraphNode, typename GraphEdge>
461typename BoostGraph<GraphNode, GraphEdge>::Edge&
462BoostGraph<GraphNode, GraphEdge>::rootGraphInEdge(
463 const GraphNode& node, const int index) const {
464 if (parentGraph_ == NULL) {
465 return inEdge(node, index);
466 } else {
467 return parentGraph_->rootGraphInEdge(node, index);
468 }
469}
470
471/**
472 * Returns the outgoing edge of a node in the root graph of the subgraph tree.
473 *
474 * @param node A node of the graph.
475 * @param index index of edge.
476 * @return the edge.
477 */
478template <typename GraphNode, typename GraphEdge>
479typename BoostGraph<GraphNode, GraphEdge>::Edge&
480BoostGraph<GraphNode, GraphEdge>::rootGraphOutEdge(
481 const GraphNode& node, const int index) const {
482 if (parentGraph_ == NULL) {
483 return outEdge(node, index);
484 } else {
485 return parentGraph_->rootGraphOutEdge(node, index);
486 }
487}
488
489/**
490 * Returns the output degree of a node, that is, the number of outgoing edges
491 * of a node.
492 *
493 * @param node A node of the graph.
494 * @returns A set of edges.
495 * @exception InstanceNotFound if the node does not belong to this graph.
496 */
497template <typename GraphNode, typename GraphEdge>
498int
499BoostGraph<GraphNode, GraphEdge>::outDegree(const GraphNode& node) const {
500 return boost::out_degree(descriptor(node), graph_);
501}
502
503/**
504 * Returns the input degree of a node, that is, the number of incoming edges
505 * of a node.
506 *
507 * @param node A node of the graph.
508 * @returns A set of edges.
509 * @exception InstanceNotFound if the node does not belong to this graph.
510 */
511template <typename GraphNode, typename GraphEdge>
512int
513BoostGraph<GraphNode, GraphEdge>::inDegree(const GraphNode& node) const {
514 return boost::in_degree(descriptor(node), graph_);
515}
516
517/**
518 * Returns the output degree of a node, that is, the number of outgoing edges
519 * of a node in the root graph of the subgraph tree
520 *
521 * @param node A node of the graph.
522 * @returns A set of edges.
523 * @exception InstanceNotFound if the node does not belong to this graph.
524 */
525template <typename GraphNode, typename GraphEdge>
526int
527BoostGraph<GraphNode, GraphEdge>::rootGraphOutDegree(
528 const GraphNode& node) const {
529 return parentGraph_ == NULL ?
530 boost::out_degree(descriptor(node), graph_) :
531 parentGraph_->rootGraphOutDegree(node);
532}
533
534/**
535 * Returns the input degree of a node, that is, the number of incoming edges
536 * of a node in the root graph of the subgraph tree
537 *
538 * @param node A node of the graph.
539 * @returns A set of edges.
540 * @exception InstanceNotFound if the node does not belong to this graph.
541 */
542template <typename GraphNode, typename GraphEdge>
543int
544BoostGraph<GraphNode, GraphEdge>::rootGraphInDegree(
545 const GraphNode& node) const {
546 return parentGraph_ == NULL ?
547 boost::in_degree(descriptor(node), graph_) :
548 parentGraph_->rootGraphInDegree(node);
549}
550
551/**
552 * Returns the tail node of a edge.
553 *
554 * Warning: this function is slow, O(n) to number of edges in the graph.
555 *
556 * @param edge Edge whose tail node we are asking
557 * @return The tail node of the given edge
558 */
559template <typename GraphNode, typename GraphEdge>
560GraphNode&
561BoostGraph<GraphNode, GraphEdge>::tailNode(const GraphEdge& edge) const {
562 EdgeDescriptor ed = descriptor(edge);
563 NodeDescriptor nd = boost::source(ed, graph_);
564 GraphNode* nn = graph_[nd];
565 nodeDescriptors_[nn] = nd;
566 return *nn;
567}
568
569/**
570 * Returns the tail node of a edge.
571 *
572 * This is faster but uglier version of the function.
573 *
574 * @param edge Edge whose tail node we are asking
575 * @return The tail node of the given edge
576 */
577template <typename GraphNode, typename GraphEdge>
578GraphNode&
579BoostGraph<GraphNode, GraphEdge>::tailNode(
580 const GraphEdge& edge, const NodeDescriptor& headNode) const {
581 EdgeDescriptor ed = edgeDescriptor(edge, headNode);
582 NodeDescriptor nd = boost::source(ed, graph_);
583 GraphNode* nn = graph_[nd];
584 nodeDescriptors_[nn] = nd;
585 return *nn;
586}
587
588/**
589 * Returns the head node of a edge.
590 *
591 * Warning: this function is slow, O(n) to number of edges in the graph.
592 *
593 * @param edge Edge whose head node we are asking
594 * @return The head node of the given edge
595 */
596template <typename GraphNode, typename GraphEdge>
597GraphNode&
598BoostGraph<GraphNode, GraphEdge>::headNode(const GraphEdge& edge) const {
599 EdgeDescriptor ed = descriptor(edge);
600 NodeDescriptor nd = boost::target(ed, graph_);
601 GraphNode* node = graph_[nd];
602 nodeDescriptors_[node] = nd;
603 return *node;
604}
605
606/**
607 * Returns the head node of a edge.
608 *
609 * This is faster but uglier version of the function.
610 *
611 * @param edge Edge whose head node we are asking
612 * @return The head node of the given edge
613 */
614template <typename GraphNode, typename GraphEdge>
615GraphNode&
616BoostGraph<GraphNode, GraphEdge>::headNode(
617 const GraphEdge& edge, const NodeDescriptor& tailNode) const {
618 EdgeDescriptor ed = edgeDescriptor(tailNode,edge);
619 NodeDescriptor nd = boost::target(ed, graph_);
620 GraphNode* node = graph_[nd];
621 nodeDescriptors_[node] = nd;
622 return *node;
623}
624
625/**
626 * Connects two nodes and attaches the given properties to the new graph
627 * edge connecting the nodes.
628 *
629 * Once registered into a graph connection, the edge properties are owned
630 * and managed by the graph. This method can be invoked repeatedly on the
631 * same pair of nodes; each time it will create a new (parallel) edge.
632 *
633 * @param nTail Tail node of the connection.
634 * @param nHead Head node of the connection.
635 * @param e Properties of the connecting edge.
636 */
637template <typename GraphNode, typename GraphEdge>
638void
639BoostGraph<GraphNode, GraphEdge>::connectNodes(
640 const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e) {
641 connectNodes(nTail, nHead, e, NULL);
642}
643
644template <typename GraphNode, typename GraphEdge>
645void
646BoostGraph<GraphNode, GraphEdge>::calculatePathLengthsOnConnect(
647 const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e) {
648
649 if (height_ == -1) {
650 return;
651 }
652 int eWeight = edgeWeight(e, nHead);
653 auto loopingHeadIter = loopingSinkDistances_.find(&nHead);
654 auto loopingTailIter = loopingSourceDistances_.find(&nTail);
655 auto headIter = sinkDistances_.find(&nHead);
656 auto tailIter = sourceDistances_.find(&nTail);
657
658 if (loopingHeadIter != loopingSinkDistances_.end() &&
659 !e.isBackEdge()) {
660 calculateSinkDistance(
661 nTail, loopingHeadIter->second + eWeight, true);
662 }
663
664 if (headIter == sinkDistances_.end()) {
665 sinkDistances_[&nHead] = 0;
666 calculateSinkDistance(nTail, eWeight, e.isBackEdge());
667 } else {
668 calculateSinkDistance(
669 nTail, headIter->second + eWeight, e.isBackEdge());
670 }
671
672 if (loopingTailIter != loopingSourceDistances_.end() &&
673 !e.isBackEdge()) {
674 calculateSourceDistances(
675 &nHead, loopingTailIter->second + eWeight, true);
676 }
677
678 if (tailIter == sourceDistances_.end()) {
679 sourceDistances_[&nTail] = 0;
680 calculateSourceDistances(&nHead, eWeight, e.isBackEdge());
681 } else {
682 calculateSourceDistances(
683 &nHead, tailIter->second + eWeight, e.isBackEdge());
684 }
685}
686
687/**
688 * Connects two nodes and attaches the given properties to the new graph
689 * edge connecting the nodes.
690 *
691 * Once registered into a graph connection, the edge properties are owned
692 * and managed by the graph. This method can be invoked repeatedly on the
693 * same pair of nodes; each time it will create a new (parallel) edge.
694 *
695 * @param nTail Tail node of the connection.
696 * @param nHead Head node of the connection.
697 * @param e Properties of the connecting edge.
698 * @param modifier sub-or parent Graph which caused this procedure to be called
699 */
700template <typename GraphNode, typename GraphEdge>
701void
702BoostGraph<GraphNode, GraphEdge>::connectNodes(
703 const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e,
704 GraphBase<GraphNode, GraphEdge>* modifier, bool creatingSG) {
705 // not add if invalid params
706 if (!hasNode(nTail) || !hasNode(nHead)) {
707 // for sub graphs silently skip it
708 if (parentGraph_ != NULL) {
709 return;
710 } else {
711 assert(hasNode(nTail)
712 && "Trying to connect tail node not on the graph");
713 assert(hasNode(nHead)
714 && "Trying to connect head node not on the graph");
715 }
716 }
717
718 if (hasEdge(nTail, nHead, e)) {
719 TCEString procName("BoostGraph::addEdge");
720 TCEString errorMsg("Edge already belongs to this graph.");
721 throw ObjectAlreadyExists(__FILE__, __LINE__, procName, errorMsg);
722 }
723
724 if (parentGraph_ == NULL && !creatingSG) {
725 ownedEdges_.insert(&e);
726 }
727
728 if (allowLoopEdges_ || !e.isBackEdge()) {
729 NodeDescriptor td = descriptor(nTail);
730 NodeDescriptor hd = descriptor(nHead);
731 if (!e.isBackEdge() && td == hd && creatingSG) {
732 std::cerr << "node: " << nTail.toString() << " edge: " << e.toString() << std::endl;
733 assert(0 && "non-loop-edge going from node to itsefl!");
734 }
735 edgeDescriptors_[&e] =
736 boost::add_edge(td, hd, &e, graph_).
737 first;
738
739 // If we have calculated path lenght data, keep it in sync.
740 if (height_ != -1) {
741 calculatePathLengthsOnConnect(nTail, nHead, e);
742 }
743 }
744
745 if (parentGraph_ != NULL && parentGraph_ != modifier) {
746 parentGraph_->connectNodes(nTail, nHead, e, this);
747 }
748
749 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
750 if ( childGraphs_[i] != modifier ) {
751 childGraphs_[i]->connectNodes(nTail, nHead, e, this);
752 }
753 }
754}
755
756template<typename GraphNode, typename GraphEdge>
757void
758BoostGraph<GraphNode, GraphEdge>::sinkDistDecreased(
759const GraphNode& n) const {
760
761 if (height_ == -1) {
762 return;
763 }
764
765 auto lsdIter = loopingSinkDistances_.find(&n);
766 int oldSD = sinkDistances_[&n];
767 int oldLSD = lsdIter != loopingSinkDistances_.end() ?
768 lsdIter->second : 0;
769 int sd = 0;
770 int loopingSD = 0;
771 int nd = descriptor(n);
772 auto edges = boost::out_edges(nd, graph_);
773 for (auto j = edges.first; j != edges.second; j++) {
774 EdgeDescriptor ed = *j;
775 NodeDescriptor hd = boost::target(ed, graph_);
776 GraphNode* head = graph_[hd];
777 GraphEdge* edge = graph_[ed];
778 int eWeight = edgeWeight(*edge, *head);
779 int headSD = sinkDistances_[head] + eWeight;
780 if (edge->isBackEdge()) {
781 loopingSD = std::max(loopingSD, headSD);
782 } else {
783 sd = std::max(sd, headSD);
784 auto headLSDIter = loopingSinkDistances_.find(head);
785 if (headLSDIter != loopingSinkDistances_.end()) {
786 loopingSD = std::max(
787 loopingSD, headLSDIter->second + eWeight);
788 }
789 }
790 }
791 if (sd < oldSD || loopingSD < oldLSD) {
792 sinkDistances_[&n] = sd;
793 if (loopingSD < oldLSD) {
794 loopingSinkDistances_[&n] = loopingSD;
795 }
796
797 // propagate to predecessors
798 auto edges = boost::in_edges(nd, graph_);
799 for (auto j = edges.first; j != edges.second; j++) {
800 EdgeDescriptor ed = *j;
801 GraphEdge* edge = graph_[ed];
802 if (!edge->isBackEdge() || sd < oldSD) {
803 NodeDescriptor td = boost::source(ed, graph_);
804 GraphNode* tail = graph_[td];
805 sinkDistDecreased(*tail);
806 }
807 }
808 }
809}
810
811template<typename GraphNode, typename GraphEdge>
812void
813BoostGraph<GraphNode, GraphEdge>::sourceDistDecreased(
814 const GraphNode& n) const {
815
816 if (height_ == -1) {
817 return;
818 }
819
820 auto lsdIter = loopingSourceDistances_.find(&n);
821 int oldSD = sourceDistances_[&n];
822 int oldLSD = lsdIter != loopingSourceDistances_.end() ?
823 lsdIter->second : 0;
824
825 int sd = 0;
826 int loopingSD = 0;
827 int nd = descriptor(n);
828 auto edges = boost::in_edges(nd, graph_);
829 for (auto j = edges.first; j != edges.second; j++) {
830 EdgeDescriptor ed = *j;
831 NodeDescriptor td = boost::source(ed, graph_);
832 GraphNode* tail = graph_[td];
833 GraphEdge* edge = graph_[ed];
834 int eWeight = edgeWeight(*edge, n);
835 int tailSD = sourceDistances_[tail] + eWeight;
836 if (edge->isBackEdge()) {
837 loopingSD = std::max(loopingSD, tailSD);
838 } else {
839 sd = std::max(sd, tailSD);
840 auto tailLSDIter = loopingSourceDistances_.find(tail);
841 if (tailLSDIter != loopingSourceDistances_.end()) {
842 loopingSD = std::max(
843 loopingSD, tailLSDIter->second + eWeight);
844 }
845 }
846 }
847
848 if (sd < oldSD || loopingSD < oldLSD) {
849 sourceDistances_[&n] = sd;
850 if (loopingSD < oldLSD) {
851 loopingSourceDistances_[&n] = loopingSD;
852 }
853
854 // propagate to successors
855 auto edges = boost::out_edges(nd, graph_);
856 for (auto j = edges.first; j != edges.second; j++) {
857 EdgeDescriptor ed = *j;
858 GraphEdge* edge = graph_[ed];
859 if (!edge->isBackEdge() || sd < oldSD) {
860 NodeDescriptor hd = boost::target(ed, graph_);
861 GraphNode* head = graph_[hd];
862 sourceDistDecreased(*head);
863 }
864 }
865 }
866}
867
868/**
869 * Disconnects two nodes.
870 *
871 * All edges between the given nodes are deleted. It is not an error to
872 * invoke this method on a pair of nodes that are not connected.
873 *
874 * @param nTail Tail node of the connection.
875 * @param nHead Head node of the connection.
876 */
877template <typename GraphNode, typename GraphEdge>
878void
879BoostGraph<GraphNode, GraphEdge>::disconnectNodes(
880 const GraphNode& nTail,
881 const GraphNode& nHead) {
882
883 int maxW = 0;
884 int maxwLoop = 0;
885 while (hasEdge(nTail, nHead)) {
886 EdgeDescriptor ed = connectingEdge(nTail, nHead);
887 GraphEdge* e = graph_[ed];
888 if (height_ != -1) {
889 int eWeight = edgeWeight(*e, nHead);
890 if (e->isBackEdge()) {
891 maxwLoop = std::max(eWeight, maxW);
892 } else {
893 maxW = std::max(eWeight, maxW);
894 }
895 }
896 removeEdge(*e, &nTail, &nHead);
897 }
898
899 if (height_ != -1) {
900 bool recalc = false;
901 if (sourceDistances_[&nTail] + maxW ==
902 sourceDistances_[&nHead] ||
903 (!loopingSourceDistances_.empty() &&
904 (loopingSourceDistances_[&nTail] + maxW ==
905 loopingSourceDistances_[&nHead] ||
906 sourceDistances_[&nTail] + maxwLoop ==
907 loopingSourceDistances_[&nHead]))) {
908 recalc = true;
909 sourceDistDecreased(nTail);
910 }
911
912 if (!sinkDistances_.empty() &&
913 (sinkDistances_[&nHead] + maxW ==
914 sinkDistances_[&nTail] ||
915 (!loopingSinkDistances_.empty() &&
916 (loopingSinkDistances_[&nHead] + maxW ==
917 loopingSinkDistances_[&nTail] ||
918 sinkDistances_[&nHead] +maxwLoop ==
919 loopingSinkDistances_[&nTail])))) {
920 recalc = true;
921 sinkDistDecreased(nHead);
922 }
923
924 if (recalc) {
925 delete pathCache_;
926 pathCache_ = NULL;
927 }
928 }
929}
930
931/**
932 * Moves all incoming edges from a node to another node.
933 *
934 * This reuses the origial Edge objects, thus should retain the original
935 * properties (even if defined in a derived class).
936 *
937 * @param source The node to move the incoming edges from.
938 * @param destination The node to move the incoming edges to.
939 */
940template <typename GraphNode, typename GraphEdge>
941void
942BoostGraph<GraphNode, GraphEdge>::moveInEdges(
943 const GraphNode& source, const GraphNode& destination) {
944 moveInEdges(source, destination, NULL);
945}
946
947/**
948 * Moves all incoming edges from a node to another node.
949 *
950 * This reuses the origial Edge objects, thus should retain the original
951 * properties (even if defined in a derived class).
952 *
953 * @param source The node to move the incoming edges from.
954 * @param destination The node to move the incoming edges to.
955 */
956template <typename GraphNode, typename GraphEdge>
957void
958BoostGraph<GraphNode, GraphEdge>::moveInEdges(
959 const GraphNode& source, const GraphNode& destination,
960 BoostGraph* modifierGraph) {
961 if (!hasNode(source)) {
962 if (hasNode(destination)) {
963 TCEString msg = "Illegal Graph update: "
964 "copying edges from outside of the graph";
965 throw NotAvailable(__FILE__,__LINE__,__func__, msg);
966 } else {
967 return; // no need to do anything
968 }
969
970 } else {
971 EdgeSet edges = inEdges(source);
972 for (typename EdgeSet::iterator i = edges.begin();
973 i != edges.end(); ++i) {
974 Edge& e = **i;
975 const GraphNode& tail = tailNode(e);
976 const GraphNode& head = destination;
977 boost::remove_edge(descriptor(e), graph_);
978
979 typename EdgeDescMap::iterator
980 edIter = edgeDescriptors_.find(&e);
981 if (edIter != edgeDescriptors_.end()) {
982 edgeDescriptors_.erase(edIter);
983 }
984
985 sourceDistDecreased(source);
986 sinkDistDecreased(tail);
987
988 // if dest not in this graph, just remove
989 if (hasNode(destination)) {
990 std::pair<EdgeDescriptor,bool> tmpPair =
991 boost::add_edge(
992 descriptor(tail), descriptor(head), &e, graph_);
993 edgeDescriptors_[&e] = tmpPair.first;
994
995 if (height_ != -1) {
996 calculatePathLengthsOnConnect(tail, head, e);
997 }
998
999 }
1000 }
1001
1002 // update parent- and childgraphs
1003 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1004 parentGraph_->moveInEdges(
1005 source, destination, this);
1006 }
1007
1008 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1009 if (childGraphs_.at(i) != modifierGraph ) {
1010 childGraphs_.at(i)->moveInEdges(
1011 source, destination, this);
1012 }
1013 }
1014 }
1015}
1016
1017template <typename GraphNode, typename GraphEdge>
1018void
1019BoostGraph<GraphNode, GraphEdge>::copyInEdge(
1020 const GraphNode& destination,
1021 GraphEdge& edge,
1022 const GraphNode* tail) {
1023 // start from the root tree.
1024 BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
1025 if (tail == NULL) {
1026 tail = &rg->tailNode(edge);
1027 }
1028 Edge* newEdge = new Edge(edge);
1029 rg->connectNodes(*tail, destination, *newEdge);
1030}
1031
1032template <typename GraphNode, typename GraphEdge>
1033void
1034BoostGraph<GraphNode, GraphEdge>::copyOutEdge(
1035// const GraphNode& source,
1036 const GraphNode& destination,
1037 GraphEdge& edge,
1038 const GraphNode* head) {
1039 // start from the root tree.
1040 BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
1041 if (head == NULL) {
1042 head = &rg->headNode(edge);
1043 }
1044 Edge* newEdge = new Edge(edge);
1045 rg->connectNodes(destination, *head, *newEdge);
1046}
1047
1048/**
1049 * Moves an edge which comes into source node to point into another node.
1050 */
1051template <typename GraphNode, typename GraphEdge>
1052void
1053BoostGraph<GraphNode, GraphEdge>::moveInEdge(
1054 const GraphNode& originalHeadNode,
1055 const GraphNode& newHeadNode,
1056 GraphEdge& edge,
1057 const GraphNode* tail,
1058 bool childs) {
1059
1060 // start from the root tree.
1061 if (!childs) {
1062 BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
1063 if (tail == NULL) {
1064 tail = &rg->tailNode(edge);
1065 }
1066 rg->moveInEdge(originalHeadNode, newHeadNode, edge, tail, true);
1067 return;
1068 }
1069
1070 if (hasNode(*tail) && hasEdge(edge)) {
1071 bool hasSource = hasNode(originalHeadNode);
1072 bool hasDestination = hasNode(newHeadNode);
1073 const GraphNode& head = newHeadNode;
1074
1075 if (hasSource) {
1076 boost::remove_edge(descriptor(edge), graph_);
1077
1078 sourceDistDecreased(originalHeadNode);
1079 sinkDistDecreased(*tail);
1080 }
1081
1082 if (hasDestination) {
1083 std::pair<EdgeDescriptor,bool> tmpPair =
1084 boost::add_edge(
1085 descriptor(*tail), descriptor(head), &edge, graph_);
1086 edgeDescriptors_[&edge] = tmpPair.first;
1087
1088 if (height_ != -1) {
1089 calculatePathLengthsOnConnect(*tail, head, edge);
1090 }
1091
1092 }
1093 // need to process child graphs?
1094 if (hasSource | hasDestination) {
1095 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1096 childGraphs_.at(i)->moveInEdge(
1097 originalHeadNode, newHeadNode, edge, tail, true);
1098 }
1099 }
1100 }
1101}
1102
1103/*
1104 * Moves edge which originally points
1105 */
1106template <typename GraphNode, typename GraphEdge>
1107void
1108BoostGraph<GraphNode, GraphEdge>::moveOutEdge(
1109 const GraphNode& originalTailNode,
1110 const GraphNode& newTailNode,
1111 GraphEdge& edge,
1112 const GraphNode* head,
1113 bool childs) {
1114
1115 if (!childs) {
1116 BoostGraph* rg = rootGraph();
1117 if (head == NULL) {
1118 head = &rg->headNode(edge);
1119 }
1120 rg->moveOutEdge(originalTailNode, newTailNode, edge, head, true);
1121 return;
1122 }
1123
1124 if (hasNode(*head) && hasEdge(edge)) {
1125 bool hasSource = hasNode(originalTailNode);
1126 bool hasDestination = hasNode(newTailNode);
1127
1128 const GraphNode& tail = newTailNode;
1129 if (hasSource) {
1130 boost::remove_edge(descriptor(edge), graph_);
1131
1132 sourceDistDecreased(*head);
1133 sinkDistDecreased(originalTailNode);
1134
1135 }
1136
1137 if (hasDestination) {
1138 std::pair<EdgeDescriptor,bool> tmpPair =
1139 boost::add_edge(
1140 descriptor(tail), descriptor(*head), &edge, graph_);
1141 edgeDescriptors_[&edge] = tmpPair.first;
1142
1143 if (height_ != -1) {
1144 calculatePathLengthsOnConnect(tail, *head, edge);
1145 }
1146
1147 }
1148
1149 // need to process child graphs?
1150 if (hasSource | hasDestination) {
1151 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1152 childGraphs_.at(i)->moveOutEdge(
1153 originalTailNode, newTailNode, edge, head, true);
1154 }
1155 }
1156 }
1157}
1158
1159/**
1160 * Moves all outgoing edges from a node to another node.
1161 *
1162 * This reuses the origial Edge objects, thus should retain the original
1163 * properties (even if defined in a derived class).
1164 *
1165 * @param source The node to move the outgoing edges from.
1166 * @param destination The node to move the outgoing edges to.
1167 */
1168template <typename GraphNode, typename GraphEdge>
1169void
1170BoostGraph<GraphNode, GraphEdge>::moveOutEdges(
1171 const GraphNode& source, const GraphNode& destination) {
1172 moveOutEdges(source, destination, this);
1173}
1174
1175/**
1176 * Moves all outgoing edges from a node to another node.
1177 *
1178 * This reuses the origial Edge objects, thus should retain the original
1179 * properties (even if defined in a derived class).
1180 *
1181 * @param source The node to move the outgoing edges from.
1182 * @param destination The node to move the outgoing edges to.
1183 */
1184template <typename GraphNode, typename GraphEdge>
1185void
1186BoostGraph<GraphNode, GraphEdge>::moveOutEdges(
1187 const GraphNode& source, const GraphNode& destination,
1188 BoostGraph* modifierGraph) {
1189 if (!hasNode(source)) {
1190 if (hasNode(destination)) {
1191 TCEString msg = "Illegal Graph update: "
1192 "copying edges from outside of the graph";
1193 throw NotAvailable(__FILE__,__LINE__,__func__, msg);
1194 } else {
1195 return; // no need to do anything
1196 }
1197
1198 } else {
1199 EdgeSet edges = outEdges(source);
1200 for (typename EdgeSet::iterator i = edges.begin();
1201 i != edges.end(); ++i) {
1202 Edge& e = **i;
1203 const GraphNode& tail = destination;
1204 const GraphNode& head = headNode(e);
1205 boost::remove_edge(descriptor(e), graph_);
1206
1207 sourceDistDecreased(head);
1208 sinkDistDecreased(source);
1209
1210 typename EdgeDescMap::iterator
1211 edIter = edgeDescriptors_.find(&e);
1212 if (edIter != edgeDescriptors_.end()) {
1213 edgeDescriptors_.erase(edIter);
1214 }
1215
1216 if (hasNode(destination)) {
1217 std::pair<EdgeDescriptor,bool> tmpPair =
1218 boost::add_edge(
1219 descriptor(tail), descriptor(head), &e, graph_);
1220 edgeDescriptors_[&e] = tmpPair.first;
1221
1222 if (height_ != -1) {
1223 calculatePathLengthsOnConnect(tail, head, e);
1224 }
1225
1226 }
1227 }
1228
1229
1230 // update parent- and childgraphs
1231 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1232 parentGraph_->moveOutEdges(source, destination, this);
1233 }
1234
1235 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1236 if (childGraphs_.at(i) != modifierGraph ) {
1237 childGraphs_.at(i)->moveOutEdges(source, destination, this);
1238 }
1239 }
1240
1241 }
1242}
1243
1244template <typename GraphNode, typename GraphEdge>
1245void
1246BoostGraph<GraphNode, GraphEdge>::clearDescriptorCache(EdgeSet edges) {
1247 for (typename EdgeSet::iterator i = edges.begin();
1248 i != edges.end(); ++i) {
1249 typename EdgeDescMap::iterator iedi = edgeDescriptors_.find(*i);
1250 if (iedi != edgeDescriptors_.end()) {
1251 edgeDescriptors_.erase(iedi);
1252 }
1253 }
1254}
1255
1256/**
1257 * Removes a node of the graph, without deleting the associated properties.
1258 *
1259 * The connection between the given nodes and other nodes are removed from
1260 * the graph. The property object is not managed by the graph anymore.
1261 *
1262 * @param node Properties of the node to be removed.
1263 * @exception InstanceNotFound If the node propertes are not registered to a
1264 * node of the graph.
1265 */
1266template <typename GraphNode, typename GraphEdge>
1267void
1268BoostGraph<GraphNode, GraphEdge>::removeNode(
1269 GraphNode& nodeToRemove, BoostGraph* modifierGraph) {
1270 if (hasNode(nodeToRemove)) {
1271
1272 replaceNodeWithLastNode(nodeToRemove);
1273
1274 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1275 parentGraph_->removeNode(nodeToRemove, this);
1276 }
1277
1278 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1279 if (childGraphs_.at(i) != modifierGraph ) {
1280 childGraphs_.at(i)->removeNode(nodeToRemove, this);
1281 }
1282 }
1283 } else {
1284 if (parentGraph_ == NULL) {
1285 TCEString msg = "Node not found in graph, cannot remove";
1286 throw InstanceNotFound(__FILE__,__LINE__,__func__, msg);
1287 }
1288 }
1289}
1290
1291/**
1292 * Removes a node of the graph, without deleting the associated properties.
1293 *
1294 * The connection between the given nodes and other nodes are removed from
1295 * the graph. The property object is not managed by the graph anymore.
1296 *
1297 * @param node Properties of the node to be removed.
1298 * @exception InstanceNotFound If the node propertes are not registered to a
1299 * node of the graph.
1300 */
1301template <typename GraphNode, typename GraphEdge>
1302void
1303BoostGraph<GraphNode, GraphEdge>::removeNode(GraphNode& node) {
1304 removeNode(node, NULL);
1305}
1306
1307/**
1308 * Removes a node of the subgraph, leaving it to the parent graph.
1309 *
1310 * Drops node also from all child graphs.
1311 *
1312 * @param node Properties of the node to be removed.
1313 * @exception InstanceNotFound If the node propertes are not registered to a
1314 * node of the graph.
1315 */
1316template <typename GraphNode, typename GraphEdge>
1317void
1318BoostGraph<GraphNode, GraphEdge>::dropNode(GraphNode& nodeToDrop) {
1319 if (!hasNode(nodeToDrop)) {
1320 return;
1321 }
1322
1323 replaceNodeWithLastNode(nodeToDrop);
1324
1325 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1326 childGraphs_.at(i)->dropNode(nodeToDrop);
1327 }
1328}
1329
1330/**
1331 * Replaces a node with properties of the last node and then removes the
1332 * last node from the graph. This is semantically equal to removing
1333 * a node from the graph but runs much faster.
1334 * Does not remove anything from subgraphs.
1335 *
1336 * @param dest node to be removed/replaced with last one.
1337 */
1338template <typename GraphNode, typename GraphEdge>
1339void
1340BoostGraph<GraphNode, GraphEdge>::replaceNodeWithLastNode(GraphNode& dest) {
1341
1342 NodeDescriptor nd = descriptor(dest);
1343 typename BoostGraph<GraphNode, GraphEdge>::NodeSet preds;
1344 typename BoostGraph<GraphNode, GraphEdge>::NodeSet succs;
1345
1346 succs = successors(dest);
1347 preds = predecessors(dest);
1348
1349 // remove edge cache
1350 clearDescriptorCache(inEdges(dest));
1351 clearDescriptorCache(outEdges(dest));
1352
1353 // clear all edges. from to node to remove/drop.
1354 boost::clear_vertex(nd, graph_);
1355
1356 // Move last node to place of deleted node, then delete last node.
1357 GraphNode& lastNode = node(nodeCount()-1);
1358
1359 NodeDescriptor lnd = descriptor(lastNode);
1360 if (&dest != &lastNode) {
1361 // move in edges from last node to place of deleted node.
1362 EdgeSet iEdges = inEdges(lastNode);
1363 for (typename EdgeSet::iterator i = iEdges.begin();
1364 i != iEdges.end(); ++i) {
1365 Edge& e = **i;
1366 const GraphNode& tail = tailNode(e);
1367 // remove the edge pointing to old place of last node
1368 boost::remove_edge(descriptor(e), graph_);
1369
1370 // clear descriptor cache for that edge
1371 typename EdgeDescMap::iterator
1372 edIter = edgeDescriptors_.find(&e);
1373 if (edIter != edgeDescriptors_.end()) {
1374 edgeDescriptors_.erase(edIter);
1375 }
1376
1377 // add the edge back, pointing to the new place
1378 // of the last node.
1379 std::pair<EdgeDescriptor,bool> tmpPair =
1380 boost::add_edge(
1381 descriptor(tail), nd, &e, graph_);
1382 edgeDescriptors_[&e] = tmpPair.first;
1383 }
1384
1385 // move out edges. from last node to place of deleted node.
1386 EdgeSet oEdges = outEdges(lastNode);
1387 for (typename EdgeSet::iterator i = oEdges.begin();
1388 i != oEdges.end(); ++i) {
1389 Edge& e = **i;
1390 const GraphNode& head = headNode(e);
1391 // remove the edge pointing to old place of last node
1392 boost::remove_edge(descriptor(e), graph_);
1393
1394 // clear descriptor cache for that edge
1395 typename EdgeDescMap::iterator
1396 edIter = edgeDescriptors_.find(&e);
1397 if (edIter != edgeDescriptors_.end()) {
1398 edgeDescriptors_.erase(edIter);
1399 }
1400
1401 // add the edge back, originating from the new place
1402 // of the last node.
1403 std::pair<EdgeDescriptor,bool> tmpPair =
1404 boost::add_edge(
1405 nd, descriptor(head), &e, graph_);
1406 edgeDescriptors_[&e] = tmpPair.first;
1407 }
1408
1409 // then move the Node class.
1410 graph_[nd] = &lastNode;
1411
1412 // update descriptor map.
1413 nodeDescriptors_[&lastNode] = nd;
1414 }
1415
1416 if (height_ != -1) {
1417 sinkDistances_.erase(&dest);
1418 sourceDistances_.erase(&dest);
1419 loopingSinkDistances_.erase(&dest);
1420 loopingSourceDistances_.erase(&dest);
1421 }
1422
1423 for (auto n: succs) sourceDistDecreased(*n);
1424 for (auto n: preds) sinkDistDecreased(*n);
1425
1426 nodeDescriptors_[&lastNode] = nd;
1427
1428 // remove just the last node.
1429 boost::remove_vertex(lnd, graph_);
1430
1431 // remove node from descriptor cache
1432 typename NodeDescMap::iterator ndi =
1433 nodeDescriptors_.find(&dest);
1434 if (ndi != nodeDescriptors_.end()) {
1435 nodeDescriptors_.erase(ndi);
1436 }
1437}
1438
1439/**
1440 * Removes the edge connecting two nodes of the graph.
1441 * The associated properties are deleted automatically when
1442 * the graph is deleted, should not be deleted by the used.
1443 *
1444 * The connection between the head and tail nodes corresponding to the given
1445 * property object is removed from the graph.
1446 *
1447 * @param e Properties of the connecting edge to be removed.
1448 * @exception InstanceNotFound If the edge propertes are not registered to a
1449 * connection of the graph.
1450 */
1451template <typename GraphNode, typename GraphEdge>
1452void
1453BoostGraph<GraphNode, GraphEdge>::removeEdge(GraphEdge& e) {
1454 removeEdge(e, NULL, NULL, NULL);
1455}
1456
1457/**
1458 * Removes the edge connecting two nodes of the graph from a subgraph,
1459 * but leaves it into the original graph
1460 *
1461 * @param e Properties of the connecting edge to be removed.
1462 * @exception InstanceNotFound If the edge propertes are not registered to a
1463 * connection of the graph.
1464
1465 */
1466template <typename GraphNode, typename GraphEdge>
1467void
1468BoostGraph<GraphNode, GraphEdge>::dropEdge(GraphEdge& e) {
1469 boost::remove_edge(descriptor(e), graph_);
1470
1471 typename EdgeDescMap::iterator
1472 edIter = edgeDescriptors_.find(&e);
1473 if (edIter != edgeDescriptors_.end()) {
1474 edgeDescriptors_.erase(edIter);
1475 }
1476
1477 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1478 childGraphs_.at(i)->dropEdge(e);
1479 }
1480}
1481
1482/**
1483 * Removes the edge connecting two nodes of the graph, without deleting the
1484 * associated properties.
1485 *
1486 * The connection between the head and tail nodes corresponding to the given
1487 * property object is removed from the graph. The property object is not
1488 * managed by the graph anymore.
1489 *
1490 * @param e Properties of the connecting edge to be removed.
1491 * @exception InstanceNotFound If the edge propertes are not registered to a
1492 * connection of the graph.
1493 */
1494template <typename GraphNode, typename GraphEdge>
1495void
1496BoostGraph<GraphNode, GraphEdge>::removeEdge(
1497 GraphEdge& e, const GraphNode* tailNode, const GraphNode* headNode,
1498 BoostGraph* modifierGraph) {
1499 if (hasEdge(e, tailNode, headNode)) {
1500 boost::remove_edge(descriptor(e), graph_);
1501
1502 typename EdgeDescMap::iterator
1503 edIter = edgeDescriptors_.find(&e);
1504 if (edIter != edgeDescriptors_.end()) {
1505 edgeDescriptors_.erase(edIter);
1506 }
1507
1508 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1509 parentGraph_->removeEdge(e, tailNode, headNode, this);
1510 }
1511
1512 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1513 if (childGraphs_.at(i) != modifierGraph ) {
1514 childGraphs_.at(i)->removeEdge(e, tailNode, headNode, this);
1515 }
1516 }
1517 delete pathCache_;
1518 pathCache_ = NULL;
1519 }
1520}
1521
1522//////////////////////////////////////////////////////////////////////////////
1523// Subgraph related public methods
1524//////////////////////////////////////////////////////////////////////////////
1525
1526/**
1527 * Returns the parent graph of this subgraph.
1528 * If the graph has no parent, returns NULL.
1529 *
1530 * @return parent graph of this subgraph or NULL if is not subgraph.
1531 */
1532template <typename GraphNode, typename GraphEdge>
1533BoostGraph<GraphNode, GraphEdge>*
1534BoostGraph<GraphNode, GraphEdge>::parentGraph() {
1535 return parentGraph_;
1536}
1537
1538/**
1539 * Returns the root graph of this subgraph.
1540 * If this has no parent, return this.
1541 *
1542 * @return parent graph of this subgraph.
1543 */
1544template <typename GraphNode, typename GraphEdge>
1545BoostGraph<GraphNode, GraphEdge>*
1546BoostGraph<GraphNode, GraphEdge>::rootGraph() {
1547 if (parentGraph_ == NULL) {
1548 return this;
1549 }
1550 return parentGraph_;
1551}
1552
1553/**
1554 * Returns the root graph of this subgraph.
1555 * If this has no parent, return this.
1556 *
1557 * @return parent graph of this subgraph.
1558 */
1559template <typename GraphNode, typename GraphEdge>
1560const BoostGraph<GraphNode, GraphEdge>*
1561BoostGraph<GraphNode, GraphEdge>::rootGraph() const {
1562 if (parentGraph_ == NULL) {
1563 return this;
1564 }
1565 return parentGraph_;
1566}
1567
1568/**
1569 * Creates a subgraph from this graph.
1570 *
1571 * This procedure is suposed to be called from derived class's
1572 * createSubGraph method which also wold create the new object.
1573 */
1574template <typename GraphNode, typename GraphEdge>
1575void
1576BoostGraph<GraphNode, GraphEdge>::constructSubGraph(
1577 BoostGraph& subGraph, NodeSet& nodes) {
1578 // first add nodes
1579 for( typename NodeSet::iterator i = nodes.begin();
1580 i != nodes.end(); i++ ) {
1581 GraphNode& gn = *(*i);
1582 subGraph.addNode(gn);
1583 }
1584 // then edges
1585 for( typename NodeSet::iterator i = nodes.begin();
1586 i != nodes.end(); i++ ) {
1587 GraphNode& gn = *(*i);
1588 NodeDescriptor nd = descriptor(gn);
1589
1590 std::pair<OutEdgeIter, OutEdgeIter> edges =
1591 boost::out_edges(nd, graph_);
1592 for (OutEdgeIter j = edges.first; j != edges.second; j++) {
1593 EdgeDescriptor ed = *j;
1594 NodeDescriptor hd = boost::target(ed, graph_);
1595 GraphNode* head = graph_[hd];
1596 if (nodes.find(head) != nodes.end()) {
1597 subGraph.connectNodes(gn, *head, *graph_[ed], NULL, true);
1598 }
1599 }
1600 }
1601 subGraph.parentGraph_ = this;
1602 childGraphs_.push_back(&subGraph);
1603 subGraph.name_ = name() + "_" + Conversion::toString(++sgCounter_);
1604}
1605
1606/**
1607 * When a node has been dropped from a subgraph, this restores it,
1608 * based on the edges on the parent graph
1609 */
1610template <typename GraphNode, typename GraphEdge>
1611void
1612BoostGraph<GraphNode, GraphEdge>::restoreNodeFromParent(
1613 GraphNode& n) {
1614 assert(parentGraph_ != NULL);
1615
1616 BoostGraph<GraphNode, GraphEdge>* parent = parentGraph_;
1617 parentGraph_ = NULL;
1618
1619 addNode(n);
1620 NodeDescriptor ndp = parent->descriptor(n);
1621
1622 std::pair<OutEdgeIter, OutEdgeIter> oEdges =
1623 boost::out_edges(ndp, parent->graph_);
1624
1625 for (OutEdgeIter j = oEdges.first; j != oEdges.second; j++) {
1626 NodeDescriptor hd = boost::target(*j, parent->graph_);
1627 GraphNode* head = parent->graph_[hd];
1628 if (hasNode(*head)) {
1629 Edge& e = *graph_[*j];
1630 connectNodes(n, *head, e, NULL, true);
1631 calculatePathLengthsOnConnect(n, *head, e);
1632 }
1633 }
1634
1635 std::pair<InEdgeIter, InEdgeIter> iEdges =
1636 boost::in_edges(ndp, parent->graph_);
1637
1638 for (InEdgeIter j = iEdges.first; j != iEdges.second; j++) {
1639 NodeDescriptor tl = boost::source(*j, parent->graph_);
1640 GraphNode* tail = parent->graph_[tl];
1641 if (hasNode(*tail) && tail != &n) {
1642 Edge& e = *graph_[*j];
1643 connectNodes(*tail, n, e, NULL, true);
1644 calculatePathLengthsOnConnect(*tail, n, e);
1645 }
1646 }
1647 parentGraph_ = parent;
1648}
1649
1650/*
1651 * Detach a subgraph from this graph.
1652 *
1653 * After this the subgraph is no longer updated when the graph is changed.
1654 * Does NOT remove parent_ of the subgraph, ie. leaves the subgraph in
1655 * non-functional stage. Should be used only just before deleting subgraph.
1656 *
1657 * @param subGraph subgraph to remove from the graph
1658 */
1659template <typename GraphNode, typename GraphEdge>
1660void
1661BoostGraph<GraphNode, GraphEdge>::detachSubgraph(BoostGraph& subGraph) {
1662 for (typename std::vector<BoostGraph<GraphNode, GraphEdge>*>::iterator
1663 iter = childGraphs_.begin(); iter != childGraphs_.end();iter++) {
1664 if ( *iter == &subGraph ) {
1665 childGraphs_.erase(iter);
1666 return;
1667 }
1668 }
1669}
1670
1671
1672/////////////////////////////////////////////////////////////////////////////
1673// Private helper methods
1674/////////////////////////////////////////////////////////////////////////////
1675
1676/**
1677 *
1678 * Checks whether the given node belongs to the graph
1679 *
1680 * @param node node being tested
1681 * @return whether the ndoe belongs to the graph
1682 */
1683template <typename GraphNode, typename GraphEdge>
1684bool
1685BoostGraph<GraphNode, GraphEdge>::hasNode(const GraphNode& node) const {
1686
1687 if (AssocTools::containsKey(nodeDescriptors_,&node)) {
1688 return true;
1689 }
1690
1691 typedef std::pair<NodeIter, NodeIter> NodeIterPair;
1692 NodeIterPair nodes = boost::vertices(graph_);
1693 for (NodeIter i = nodes.first; i != nodes.second; i++) {
1694 if (graph_[*i] == &node) {
1695 nodeDescriptors_[&node] = *i;
1696 return true;
1697 }
1698 }
1699 return false;
1700}
1701
1702/**
1703 *
1704 * Checks whether there exists and edge between the given nodes
1705 *
1706 * @param nTail tail node of the edge
1707 * @param nHead head node of the edge
1708 * @return whether there is an edge from nTail to nHead
1709 */
1710template <typename GraphNode, typename GraphEdge>
1711bool
1712BoostGraph<GraphNode, GraphEdge>::hasEdge(
1713 const GraphNode& nTail,
1714 const GraphNode& nHead) const {
1715
1716 typedef std::pair<EdgeDescriptor, bool> EdgeReturned;
1717 EdgeReturned er = boost::edge(
1718 descriptor(nTail), descriptor(nHead), graph_);
1719 if (er.second == true) {
1720 return true;
1721 }
1722 return false;
1723}
1724
1725/**
1726 *
1727 * Checks whether the given edge connects the given nodes
1728 *
1729 * @param nTail tail node of the edge
1730 * @param nHead head node of the edge
1731 * @param edge edge which may connect the nodes
1732 * @return whether the given edge does from nTail to nHead
1733 */
1734template <typename GraphNode, typename GraphEdge>
1735bool
1736BoostGraph<GraphNode, GraphEdge>::hasEdge(
1737 const GraphNode& nTail,
1738 const GraphNode& nHead,
1739 const GraphEdge& edge) const {
1740
1741 typedef std::pair<OutEdgeIter, OutEdgeIter> OutEdgeIterPair;
1742
1743 unsigned int hd = descriptor(nHead);
1744 OutEdgeIterPair edges = boost::out_edges(descriptor(nTail), graph_);
1745
1746 for (OutEdgeIter i = edges.first; i != edges.second; i++) {
1747 if (graph_[*i] == &edge && target(*i, graph_) == hd) {
1748 return true;
1749 }
1750 }
1751 return false;
1752}
1753
1754/**
1755 *
1756 * Checks whether the given edge belongs to the graph.
1757 *
1758 * @param edge edge being tested
1759 * @param tailnode, if known. makes this routine faster.
1760 * @param headnode, if known. makes this routine faster.
1761 * @return whether the edge belongs to the graph
1762 */
1763template <typename GraphNode, typename GraphEdge>
1764bool
1765BoostGraph<GraphNode, GraphEdge>::hasEdge(
1766 const GraphEdge& e,
1767 const GraphNode* nTail,
1768 const GraphNode* nHead) const {
1769
1770 if (AssocTools::containsKey(edgeDescriptors_,&e)) {
1771 return true;
1772 }
1773
1774 // if we have tails, check if's out edges
1775 if (nTail != NULL && hasNode(*nTail)) {
1776 typedef std::pair<OutEdgeIter, OutEdgeIter> OutEdgeIterPair;
1777
1778 OutEdgeIterPair edges = boost::out_edges(descriptor(*nTail), graph_);
1779
1780 for (OutEdgeIter i = edges.first; i != edges.second; i++) {
1781 if (graph_[*i] == &e) {
1782 edgeDescriptors_[&e] = *i;
1783 return true;
1784 }
1785 }
1786 return false;
1787 } else { // if we have head, check it's in edges.
1788 if (nHead != NULL && hasNode(*nHead)) {
1789 typedef std::pair<InEdgeIter, InEdgeIter> InEdgeIterPair;
1790
1791 InEdgeIterPair edges = boost::in_edges(descriptor(*nHead), graph_);
1792
1793 for (InEdgeIter i = edges.first; i != edges.second; i++) {
1794 if (graph_[*i] == &e) {
1795 edgeDescriptors_[&e] = *i;
1796 return true;
1797 }
1798 }
1799 return false;
1800 }
1801 }
1802
1803 // we don't have head or tail, slowly go thru all edges.
1804 typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
1805 EdgeIterPair edges = boost::edges(graph_);
1806
1807 for (EdgeIter i = edges.first; i != edges.second; i++) {
1808 if (graph_[*i] == &e) {
1809 edgeDescriptors_[&e] = *i;
1810 return true;
1811 }
1812 }
1813 return false;
1814}
1815
1816template <typename GraphNode, typename GraphEdge>
1817typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1818BoostGraph<GraphNode, GraphEdge>::descriptor(const GraphEdge& e) const {
1819
1820 typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
1821 if (cacheIter != edgeDescriptors_.end()) {
1822 return cacheIter->second;
1823 }
1824
1825 typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
1826 EdgeIterPair edges = boost::edges(graph_);
1827
1828 for (EdgeIter i = edges.first; i != edges.second; i++) {
1829 if (graph_[*i] == &e) {
1830 edgeDescriptors_[&e] = *i;
1831 return *i;
1832 }
1833 }
1834 assert(false && "Descriptor for edge not found!");
1835 return *edges.second;
1836}
1837
1838template <typename GraphNode, typename GraphEdge>
1839typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1840BoostGraph<GraphNode, GraphEdge>::edgeDescriptor(
1841 const GraphEdge& e, const NodeDescriptor& headNode) const {
1842
1843 typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
1844 if (cacheIter != edgeDescriptors_.end()) {
1845 return cacheIter->second;
1846 }
1847
1848 typedef std::pair<InEdgeIter, InEdgeIter> EdgeIterPair;
1849 EdgeIterPair edges = boost::in_edges(headNode,graph_);
1850
1851 for (InEdgeIter i = edges.first; i != edges.second; i++) {
1852 if (graph_[*i] == &e) {
1853 edgeDescriptors_[&e] = *i;
1854 return *i;
1855 }
1856 }
1857 assert(false);
1858 return *edges.second;
1859}
1860
1861template <typename GraphNode, typename GraphEdge>
1862typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1863BoostGraph<GraphNode, GraphEdge>::edgeDescriptor(
1864 const NodeDescriptor& tailNode, const GraphEdge& e) const {
1865
1866 typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
1867 if (cacheIter != edgeDescriptors_.end()) {
1868 return cacheIter->second;
1869 }
1870
1871 typedef std::pair<OutEdgeIter, OutEdgeIter> EdgeIterPair;
1872 EdgeIterPair edges = boost::out_edges(tailNode,graph_);
1873
1874 for (OutEdgeIter i = edges.first; i != edges.second; i++) {
1875 if (graph_[*i] == &e) {
1876 edgeDescriptors_[&e] = *i;
1877 return *i;
1878 }
1879 }
1880 assert(false);
1881 return *edges.second;
1882}
1883
1884template <typename GraphNode, typename GraphEdge>
1885typename BoostGraph<GraphNode, GraphEdge>::NodeDescriptor
1886BoostGraph<GraphNode, GraphEdge>::descriptor(const GraphNode& n) const {
1887
1888 typename NodeDescMap::iterator cacheIter = nodeDescriptors_.find(&n);
1889 if (cacheIter != nodeDescriptors_.end()) {
1890 return cacheIter->second;
1891 }
1892
1893 typedef std::pair<NodeIter, NodeIter> NodeIterPair;
1894 NodeIterPair nodes = boost::vertices(graph_);
1895
1896 for (NodeIter i = nodes.first; i != nodes.second; i++) {
1897 if (graph_[*i] == &n) {
1898 nodeDescriptors_[&n] = *i;
1899 return *i;
1900 }
1901 }
1902 Application::logStream()
1903 << "Node " << n.toString() << "not in graph!" << std::endl;
1904 BoostGraph<GraphNode, GraphEdge>::writeToDotFile("missing_node.dot");
1905
1906 assert(false);
1907 return *nodes.second;
1908}
1909
1910
1911template <typename GraphNode, typename GraphEdge>
1912typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1913BoostGraph<GraphNode, GraphEdge>::connectingEdge(
1914 const GraphNode& nTail,
1915 const GraphNode& nHead) const {
1916
1917 typedef std::pair<EdgeDescriptor, bool> EdgeReturned;
1918
1919 EdgeReturned edges = boost::edge(
1920 descriptor(nTail), descriptor(nHead), graph_);
1921 if (edges.second == false) {
1922 abortWithError("Connecting edge not found!");
1923 }
1924 return edges.first;
1925}
1926
1927/**
1928 * Returns all the root nodes of the graph.
1929 *
1930 * Root nodes are nodes of which input degree is 0 (no edges entering, only
1931 * leaving). Also known as 'source nodes'.
1932 *
1933 * @return Set of root nodes, can be empty.
1934 */
1935template<typename GraphNode, typename GraphEdge>
1936typename BoostGraph<GraphNode, GraphEdge>::NodeSet
1937BoostGraph<GraphNode, GraphEdge>::rootNodes() const {
1938
1939 NodeSet rootNodes;
1940 for (int nodeIndex = 0; nodeIndex < nodeCount(); ++nodeIndex) {
1941 GraphNode& nod = node(nodeIndex);
1942 if (inDegree(nod) == 0)
1943 rootNodes.insert(&nod);
1944 }
1945 return rootNodes;
1946}
1947
1948
1949/**
1950 * Returns all the sink nodes of the graph.
1951 *
1952 * Sink nodes are nodes of which output degree is 0 (no edges exiting, only
1953 * incoming).
1954 *
1955 * @return Set of sink nodes, can be empty.
1956 */
1957template<typename GraphNode, typename GraphEdge>
1958typename BoostGraph<GraphNode, GraphEdge>::NodeSet
1959BoostGraph<GraphNode, GraphEdge>::sinkNodes() const {
1960
1961 NodeSet sinkNodes;
1962 for (int nodeIndex = 0; nodeIndex < nodeCount(); ++nodeIndex) {
1963 GraphNode& nod = node(nodeIndex);
1964 if (outDegree(nod) == 0)
1965 sinkNodes.insert(&nod);
1966 }
1967 return sinkNodes;
1968}
1969
1970/**
1971 * Returns all the successors of the given node.
1972 *
1973 * If node has no successors, an empty set is returned. Note: the node can
1974 * also be a successor of itself.
1975 *
1976 * @param node The node of which successors to find.
1977 * @return Set of root nodes, can be empty.
1978 */
1979template<typename GraphNode, typename GraphEdge>
1980typename BoostGraph<GraphNode, GraphEdge>::NodeSet
1981BoostGraph<GraphNode, GraphEdge>::successors(
1982 const Node& node, bool ignoreBackEdges, bool ignoreForwardEdges) const {
1983
1984 NodeSet succ;
1985
1986 NodeDescriptor nd = descriptor(node);
1987 typedef typename GraphTraits::out_edge_iterator outEdgeIter;
1988 std::pair<outEdgeIter, outEdgeIter> edges = boost::out_edges(nd, graph_);
1989
1990 for (outEdgeIter ei = edges.first; ei != edges.second; ei++) {
1991 EdgeDescriptor ed = *ei;
1992 GraphEdge* edge = graph_[ed];
1993 bool backEdge = edge->isBackEdge();
1994 if (!((ignoreBackEdges && backEdge) ||
1995 (ignoreForwardEdges && !backEdge))) {
1996 NodeDescriptor ndHead = boost::target(ed, graph_);
1997 GraphNode* head = graph_[ndHead];
1998 succ.insert(head);
1999 }
2000 }
2001
2002 return succ;
2003}
2004
2005/**
2006 * Returns all the predecessors of the given node.
2007 *
2008 * If node has no predecessors, an empty set is returned. Note: the node can
2009 * also be a predecessor of itself.
2010 *
2011 * @param node The node of which predecessors to find.
2012 * @return Set of root nodes, can be empty.
2013 */
2014template<typename GraphNode, typename GraphEdge>
2015typename BoostGraph<GraphNode, GraphEdge>::NodeSet
2016BoostGraph<GraphNode, GraphEdge>::predecessors(
2017 const Node& node, bool ignoreBackEdges, bool ignoreForwardEdges) const {
2018
2019 NodeSet pred;
2020
2021 typedef typename GraphTraits::in_edge_iterator InEdgeIter;
2022 std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
2023 descriptor(node), graph_);
2024
2025 for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
2026 EdgeDescriptor ed = *ei;
2027 GraphEdge* edge = graph_[ed];
2028 bool backEdge = edge->isBackEdge();
2029 if (!((ignoreBackEdges && backEdge) ||
2030 (ignoreForwardEdges && !backEdge))) {
2031 NodeDescriptor nTail = boost::source(ed, graph_);
2032 GraphNode* tail = graph_[nTail];
2033 pred.insert(tail);
2034 }
2035 }
2036 return pred;
2037}
2038
2039/**
2040 * Calculates maximum path lengths from sinks and sources to all nodes.
2041 *
2042 * This procedure is called internally when this information is needed
2043 */
2044template<typename GraphNode, typename GraphEdge>
2045void
2046BoostGraph<GraphNode, GraphEdge>::calculatePathLengthsFast() const {
2047 std::vector<NodeDescriptor> sortedNodes;
2048 sortedNodes.reserve(nodeCount());
2049 // inserts first elements into end?
2050 topological_sort(graph_, std::back_inserter(sortedNodes));
2051 for (unsigned int i = 0 ; i < sortedNodes.size(); i++) {
2052 NodeDescriptor& nd = sortedNodes[i];
2053 const Node* node = graph_[nd];
2054 int len = sinkDistances_[node];
2055
2056 // loop over all in edges.
2057 std::pair <InEdgeIter, InEdgeIter> edges = boost::in_edges(nd, graph_);
2058 for (InEdgeIter ii = edges.first; ii != edges.second; ii++) {
2059 EdgeDescriptor ed = *ii;
2060 Edge* edge = graph_[ed];
2061 NodeDescriptor td = boost::source(*ii, graph_);
2062 const Node* tailNode = graph_[td];
2063 int eWeight = edgeWeight(*edge, *node);
2064 int sdLen = len + eWeight;
2065
2066 // find the place in the sourcedistances table
2067 auto sdIter = sinkDistances_.find(tailNode);
2068 // update if this path is longer.
2069 if (sdIter == sinkDistances_.end()) {
2070 sinkDistances_[tailNode] = sdLen;
2071 if (sdLen > height_) {
2072 height_ = sdLen;
2073 }
2074 } else if(sdIter->second < sdLen) {
2075 sdIter->second = sdLen;
2076 if (sdLen > height_) {
2077 height_ = sdLen;
2078 }
2079 }
2080 }
2081 }
2082}
2083
2084/**
2085 * Calculates maximum path lengths from sinks and sources to all nodes.
2086 *
2087 * This procedure is called internally when this information is needed
2088 */
2089template<typename GraphNode, typename GraphEdge>
2090void
2091BoostGraph<GraphNode, GraphEdge>::calculatePathLengths() const {
2092
2093 calculateSourceDistances();
2094
2095 if (!allowLoopEdges_) {
2096 calculatePathLengthsFast();
2097 return;
2098 }
2099
2100 // priority queue of all sink nodes.
2101 std::priority_queue<PathLengthHelper> sinkDistanceQueue;
2102
2103 // insert all sink nodes to the pqueue
2104 for (int i = nodeCount() -1 ; i >= 0 ; i--) {
2105
2106 NodeDescriptor nd = descriptor(node(i));
2107 std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
2108 nd, graph_);
2109
2110 bool outEdgeFound = false;
2111 for (OutEdgeIter ii = edges.first; ii != edges.second;
2112 ii++) {
2113 EdgeDescriptor ed = *ii;
2114 if (!graph_[ed]->isBackEdge()) {
2115 outEdgeFound = true;
2116 }
2117 }
2118 if (!outEdgeFound) {
2119 sinkDistanceQueue.push(
2120 PathLengthHelper(nd, 0, sourceDistances_[&node(i)]));
2121 }
2122 }
2123
2124 // and then start sink calculation from each of them.
2125 while (!sinkDistanceQueue.empty()) {
2126 calculateSinkDistance(*graph_[sinkDistanceQueue.top().nd_],0);
2127 sinkDistanceQueue.pop();
2128 }
2129}
2130
2131/**
2132 * Calculates source distances of nodes.
2133 *
2134 * Iterative algorithm, starts from given node or all source nodes.
2135 *
2136 * Does a breadth-first search, prioritizating first nodes in the graph.
2137 *
2138 * @param startingNode node whose successors's source dist to calculate,
2139 * or NULL if start from all sources.
2140 *
2141 * @param startingLength source distance of the startingnode.
2142 */
2143template<typename GraphNode, typename GraphEdge>
2144void
2145BoostGraph<GraphNode, GraphEdge>::calculateSourceDistances(
2146 const GraphNode* startingNode, int startingLength, bool looping) const {
2147
2148 if (startingLength > height_) {
2149 height_ = startingLength;
2150 }
2151
2152 // priority queue of nodes to be processed
2153 typename std::map <NodeDescriptor, int> sourceDistanceQueue;
2154
2155 // priority queue of nodes to be processed
2156 typename std::map <NodeDescriptor, int> loopingSourceDistanceQueue;
2157
2158 // first initialize starting nodes to the queue
2159
2160 // one starting node?
2161 if (startingNode != NULL) {
2162 if (!looping) {
2163 sourceDistances_[startingNode] = startingLength;
2164 sourceDistanceQueue[descriptor(*startingNode)] = startingLength;
2165 } else {
2166 loopingSourceDistances_[startingNode] = startingLength;
2167 loopingSourceDistanceQueue[descriptor(*startingNode)] =
2168 startingLength;
2169 }
2170
2171 } else {
2172 // insert all source nodes to the pqueue
2173 for (int i = 0; i < nodeCount(); i++) {
2174 NodeDescriptor nd = boost::vertex(i, graph_);
2175 std::pair <InEdgeIter, InEdgeIter> edges = boost::in_edges(
2176 nd, graph_);
2177
2178 bool inEdgeFound = false;
2179 for (InEdgeIter ii = edges.first; ii != edges.second;
2180 ii++) {
2181 EdgeDescriptor ed = *ii;
2182 if (!graph_[ed]->isBackEdge()) {
2183 inEdgeFound = true;
2184 }
2185 }
2186 if (!inEdgeFound) {
2187 sourceDistances_[graph_[nd]] = startingLength;
2188 sourceDistanceQueue[nd] = startingLength;
2189 }
2190 }
2191 }
2192
2193 // and then start sink calculation from each of them.
2194 while (!sourceDistanceQueue.empty()) {
2195 typename std::map <NodeDescriptor, int>::iterator sdBegin =
2196 sourceDistanceQueue.begin();
2197
2198 NodeDescriptor nd = sdBegin->first;
2199 int len = sdBegin->second;
2200 sourceDistanceQueue.erase(sdBegin);
2201
2202 // then test all successors..
2203 std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
2204 nd, graph_);
2205 for (OutEdgeIter oi = edges.first; oi != edges.second; oi++) {
2206 EdgeDescriptor ed = *oi;
2207 GraphEdge *edge = graph_[ed];
2208 NodeDescriptor headDesc = boost::target(ed, graph_);
2209 Node* headNode = graph_[headDesc];
2210 int eWeight = edgeWeight(*edge, *headNode);
2211 int destLen = len + eWeight;
2212
2213 if (destLen > height_) {
2214 height_ = destLen;
2215 }
2216
2217 // normal or loop-containing length?
2218 auto & sourceDistances =
2219 edge->isBackEdge() ? loopingSourceDistances_:sourceDistances_;
2220
2221 // find the place in the sourcedistances table
2222 auto sdIter = sourceDistances.find(headNode);
2223
2224 // if not yet there, add
2225 if (sdIter == sourceDistances.end()) {
2226 sourceDistances[headNode] = destLen;
2227 } else {
2228 // this is longer? replace with this
2229 if (sdIter->second < destLen ) {
2230 sdIter->second = destLen;
2231 } else {
2232 // we have already been here, with bigger path.
2233 // no need to check successors.
2234 continue;
2235 }
2236 }
2237
2238 // add to normal or loop-containing queue?
2239 typename std::map<
2240 NodeDescriptor,int> &
2241 mySourceDistanceQueue =
2242 edge->isBackEdge() ?
2243 loopingSourceDistanceQueue : sourceDistanceQueue;
2244
2245 // then may enqueue the successor for processing it.
2246 typename std::map <NodeDescriptor, int>::iterator qiter =
2247 mySourceDistanceQueue.find(headDesc);
2248 if (qiter == mySourceDistanceQueue.end()) {
2249 // not found from queue, add it there.
2250 mySourceDistanceQueue[headDesc] = destLen;
2251 } else {
2252 // already is in queue.
2253 if (qiter->second < destLen) {
2254 // if this one has longer path, replace the queued
2255 // ath lenght with this path length.
2256 qiter->second = destLen;
2257 }
2258 }
2259 }
2260 }
2261
2262 // then iterate over nodes that have one loop node pointing to them.
2263 // do not follow any other loop edges.
2264
2265 while (!loopingSourceDistanceQueue.empty()) {
2266 typename std::map <NodeDescriptor, int>::iterator sdBegin =
2267 loopingSourceDistanceQueue.begin();
2268
2269 NodeDescriptor nd = sdBegin->first;
2270 int len = sdBegin->second;
2271 loopingSourceDistanceQueue.erase(sdBegin);
2272
2273 // then test all successors..
2274 std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
2275 nd, graph_);
2276 for (OutEdgeIter oi = edges.first; oi != edges.second; oi++) {
2277 EdgeDescriptor ed = *oi;
2278 GraphEdge *edge = graph_[ed];
2279 // do not follow no more loop edges.
2280 if (edge->isBackEdge()) {
2281 continue;
2282 }
2283 NodeDescriptor headDesc = boost::target(ed, graph_);
2284 Node* headNode = graph_[headDesc];
2285 int eWeight = edgeWeight(*edge, *headNode);
2286 int destLen = len + eWeight;
2287
2288 // find the place in the sourcedistances table
2289 auto sdIter = loopingSourceDistances_.find(headNode);
2290
2291 // if not yet there, add
2292 if (sdIter == loopingSourceDistances_.end()) {
2293 loopingSourceDistances_[headNode] = destLen;
2294 } else {
2295 // this is longer? replace with this
2296 if (sdIter->second < destLen ) {
2297 sdIter->second = destLen;
2298 } else {
2299 // we have already been here, with bigger path.
2300 // no need to check successors.
2301 continue;
2302 }
2303 }
2304
2305 // then may enqueue the successor for processing it.
2306 typename std::map <NodeDescriptor, int>::iterator qiter =
2307 loopingSourceDistanceQueue.find(headDesc);
2308 if (qiter == loopingSourceDistanceQueue.end()) {
2309 // not found from queue, add it there.
2310 loopingSourceDistanceQueue[headDesc] = destLen;
2311 } else {
2312 // already is in queue.
2313 if (qiter->second < destLen) {
2314 // if this one has longer path, replace the queued
2315 // ath lenght with this path length.
2316 qiter->second = destLen;
2317 }
2318 }
2319 }
2320 }
2321}
2322
2323/**
2324 * Recursively calculates path lenght from sinks to sources.
2325 *
2326 * @param node Node curently being processed
2327 * @param len Current lenght from sink.
2328 */
2329template<typename GraphNode, typename GraphEdge>
2330void
2331BoostGraph<GraphNode, GraphEdge>::calculateSinkDistance(
2332 const Node& node, int len, bool looping ) const {
2333 if (len > 26000) {
2334 GraphBase<GraphNode,GraphEdge>::writeToDotFile("not_dag.dot");
2335 assert(false&&"cannot calc sink distance for graph which is not dag");
2336 }
2337
2338 auto &sinkDistances = looping ? loopingSinkDistances_ : sinkDistances_;
2339
2340 // find the place in the sourcedistances table
2341 auto sdIter = sinkDistances.find(&node);
2342
2343 // if not yet there, add
2344 if (sdIter == sinkDistances.end()) {
2345 sinkDistances[&node] = len;
2346 } else {
2347 // this is longer? replace with this
2348 if (sdIter->second <= len ) {
2349 sdIter->second = len;
2350 } else {
2351 // we have already been here, with bigger path.
2352 // no need to check successors.
2353 return;
2354 }
2355 }
2356
2357 if (len > height_) {
2358 height_ = len;
2359 }
2360
2361 // priority queue of predecessor nodes. recurse always
2362 // to one with highest source distance
2363 std::priority_queue<PathLengthHelper> predecessorQueue;
2364 NodeDescriptor nd = descriptor(node);
2365 std::pair <InEdgeIter, InEdgeIter> edges = boost::in_edges(nd, graph_);
2366 for (InEdgeIter ii = edges.first; ii != edges.second; ii++) {
2367 EdgeDescriptor ed = *ii;
2368 Edge* edge = graph_[ed];
2369 // if already looping, may not be backedge.
2370 if (!looping || !edge->isBackEdge()) {
2371 NodeDescriptor td = boost::source(*ii, graph_);
2372 Node* tailNode = graph_[td];
2373 int eWeight = edgeWeight(*edge, node);
2374 int sdLen = len + eWeight;
2375 if (sdLen > height_) {
2376 height_ = sdLen;
2377 }
2378
2379 // the predecessor is thru one loop?
2380 if (looping || edge->isBackEdge()) {
2381 sdIter = loopingSinkDistances_.find(tailNode);
2382 // if not yet there, add
2383 if (sdIter == loopingSinkDistances_.end()) {
2384 loopingSinkDistances_[tailNode] = sdLen;
2385 } else {
2386 // this is longer? replace with this
2387 if (sdIter->second < sdLen) {
2388 sdIter->second = sdLen;
2389 } else {
2390 // we have already been here, with bigger path.
2391 // no need to check successors.
2392 continue;
2393 }
2394 }
2395 predecessorQueue.push(
2396 PathLengthHelper(
2397 td, sdLen, sourceDistances_[tailNode], true));
2398 } else {
2399 sdIter = sinkDistances_.find(tailNode);
2400 // if not yet there, add
2401 if (sdIter == sinkDistances_.end()) {
2402 sinkDistances_[tailNode] = sdLen;
2403 } else {
2404 // this is longer? replace with this
2405 if (sdIter->second < sdLen ) {
2406 sdIter->second = sdLen;
2407 } else {
2408 // we have already been here, with bigger path.
2409 // no need to check successors.
2410 continue;
2411 }
2412 }
2413 predecessorQueue.push(
2414 PathLengthHelper(
2415 td, sdLen, sourceDistances_[tailNode], false));
2416 }
2417 }
2418 }
2419
2420 // all predecessors are in the queue, loop it thru in
2421 // correct order.
2422 while (!predecessorQueue.empty()) {
2423
2424 PathLengthHelper plh = predecessorQueue.top();
2425 calculateSinkDistance(
2426 *graph_[plh.nd_], plh.len_, plh.looping_);
2427 predecessorQueue.pop();
2428 }
2429}
2430
2431/**
2432 * Gives the lenght of a longest path a node belongs in a graph.
2433 *
2434 * If the path lenghts are not calculated calculates them.
2435 * If the graph is a cyclic graph, the function may never return.
2436 *
2437 * @param node Node belonging to a path.
2438 *
2439 * @return length of the longest path where given node belongs to
2440 */
2441template<typename GraphNode, typename GraphEdge>
2442int
2443BoostGraph<GraphNode, GraphEdge>::maxPathLength(const GraphNode& node) const {
2444 return maxSinkDistance(node) + maxSourceDistance(node);
2445}
2446
2447/**
2448 * Gives the lenght of a longest path from any source node to given node.
2449 *
2450 * If the path lenghts are not calculated calculates them.
2451 * If the graph is a cyclic graph without back edges correctly set,
2452 * the function may never return. If all cycles contain at least one
2453 * backedge, this should work, and it will then return longest path where
2454 * maximum of one loop is looped.
2455 *
2456 * @param node Node belonging to a path.
2457 *
2458 * @return length of the longest path where given node belongs to
2459 */
2460template<typename GraphNode, typename GraphEdge>
2461int
2462BoostGraph<GraphNode, GraphEdge>::maxSourceDistance(const GraphNode& node)
2463 const {
2464
2465 if (!hasNode(node)) {
2466 return -1;
2467 }
2468
2469
2470 for (int i = 0; i < 2; i++) {
2471 auto iter = loopingSourceDistances_.find(&node);
2472 if (iter != loopingSourceDistances_.end()) {
2473 return iter->second;
2474 }
2475
2476 auto iter2 = sourceDistances_.find(&node);
2477
2478 if (iter2 == sourceDistances_.end()) {
2479 if (i == 0) {
2480 calculateSourceDistances();
2481 }
2482 } else {
2483 return iter2->second;
2484 }
2485 }
2486 if (!hasNode(node)) {
2487 return -1;
2488 }
2489 std::cerr << "Node lacks source distance! " << node.nodeID() << " " << node.nodeID() << " "
2490 << node.toString() << std::endl;
2491 BoostGraph<GraphNode, GraphEdge>::writeToDotFile("lacking_sourced.dot");
2492 assert(0 && "source distance should have been found.");
2493 return -1;
2494}
2495
2496/**
2497 * Gives the lenght of a longest path from the given node to any sink node.
2498 *
2499 * If the path lenghts are not calculated calculates them.
2500 * If the graph is a cyclic graph without back edges correctly set,
2501 * the function may never return. If all cycles contain at least one
2502 * backedge, this should work, and it will then return longest path where
2503 * maximum of one loop is looped.
2504 *
2505 * @param node Node belonging to a path.
2506 *
2507 * @return length of the longest path where given node belongs to
2508 */
2509template<typename GraphNode, typename GraphEdge>
2510int
2511BoostGraph<GraphNode, GraphEdge>::maxSinkDistance(const GraphNode& node)
2512 const {
2513
2514 if (!hasNode(node)) {
2515 return -1;
2516 }
2517
2518 for (int i = 0; i < 2; i++) {
2519 auto iter = loopingSinkDistances_.find(&node);
2520 if (iter != loopingSinkDistances_.end()) {
2521 if (sinkDistances_.find(&node) == sinkDistances_.end() ||
2522 iter->second > sinkDistances_[&node]) {
2523 return iter->second;
2524 }
2525 }
2526
2527 auto iter2 = sinkDistances_.find(&node);
2528
2529 if (iter2 == sinkDistances_.end()) {
2530 calculatePathLengths();
2531 } else {
2532 return iter2->second;
2533 }
2534 }
2535 if (!hasNode(node)) {
2536 return -1;
2537 }
2538 std::cerr << "Node lacks sink distance! " << node.nodeID() << " "
2539 << node.toString() << std::endl;
2540 BoostGraph<GraphNode, GraphEdge>::writeToDotFile("lacking_sinkd.dot");
2541
2542 assert(0 && "sink distance should have been found.");
2543 return -1;
2544}
2545
2546/**
2547 * Gives the longest path in acyclic graph.
2548 *
2549 * If the path lenghts are not calculated calculates them.
2550 * If the graph is a cyclic graph, the function may never return.
2551 *
2552 * @return Longst path in acyclic graph.
2553 */
2554template<typename GraphNode, typename GraphEdge>
2555int
2556BoostGraph<GraphNode, GraphEdge>::height() const {
2557
2558 if (height_ == -1) {
2559 calculatePathLengths();
2560 }
2561
2562 return height_;
2563}
2564
2565/**
2566 * Gives weight of a one edge in a graph.
2567 *
2568 * Derived class should overrider this with real implementation
2569 * which does the actual node weight calculation.
2570 *
2571 * This base class implementation always returns 1.
2572 *
2573 * @return The weight of an edge.
2574 */
2575template <typename GraphNode, typename GraphEdge>
2576int
2577BoostGraph<GraphNode, GraphEdge>::edgeWeight(
2578 GraphEdge&,const GraphNode&) const {
2579 return 1;
2580}
2581
2582/**
2583 * Returns all edges that connect two nodes.
2584 *
2585 * @param nTail source node
2586 * @param nHead destination node
2587 * @return a set containing all edges from nTail to nHead
2588 */
2589template <typename GraphNode, typename GraphEdge>
2590typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
2591BoostGraph<GraphNode, GraphEdge>::connectingEdges(
2592 const GraphNode& nTail, const GraphNode& nHead) const {
2593
2594 EdgeSet headIn = inEdges(nHead);
2595 EdgeSet tailOut = outEdges(nTail);
2596 EdgeSet intersection;
2597 SetTools::intersection(headIn, tailOut, intersection);
2598 return intersection;
2599}
2600
2601template <typename GraphNode, typename GraphEdge>
2602const TCEString&
2603BoostGraph<GraphNode, GraphEdge>::name() const {
2604 return name_;
2605}
2606
2607/**
2608 * Finds all paths between nodes and updates the internal path cache.
2609 *
2610 * This data is used internally to speed up hasPath().
2611 */
2612template <typename GraphNode, typename GraphEdge>
2613void
2614BoostGraph<GraphNode, GraphEdge>::findAllPaths() const {
2615
2616 using namespace boost;
2617
2618 typedef std::map<EdgeDescriptor, int> WeightMap;
2619 WeightMap weightsMap;
2620 associative_property_map<WeightMap> weights(weightsMap);
2621
2622 typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
2623 EdgeIterPair edges = boost::edges(graph_);
2624 for (EdgeIter i = edges.first; i != edges.second; i++) {
2625 weightsMap[*i] = 0;
2626 }
2627
2628 const int nodes = nodeCount();
2629 delete pathCache_;
2630 pathCache_ = new PathCache;
2631 for (int i = 0; i < nodes; ++i) {
2632 pathCache_->push_back(std::vector<int>(nodes));
2633 }
2634 johnson_all_pairs_shortest_paths(graph_, *pathCache_, weight_map(weights));
2635}
2636
2637template <typename GraphNode, typename GraphEdge>
2638bool
2639BoostGraph<GraphNode, GraphEdge>::hasPath(
2640 GraphNode& src, const GraphNode& dest) const {
2641
2642 if (&src == &dest) {
2643 return true;
2644 }
2645
2646 if (pathCache_ != NULL) {
2647 return (*pathCache_)[descriptor(src)][descriptor(dest)] !=
2648 (std::numeric_limits<int>::max)();
2649 }
2650 NodeSet foundNodes;
2651 NodeSet queue;
2652 queue.insert(&src);
2653 int dstSinkDist = -1;
2654 if (height_ != -1) {
2655 dstSinkDist = maxSinkDistance(dest);
2656 }
2657 while (!queue.empty()) {
2658 GraphNode* current = *queue.begin();
2659 queue.erase(current);
2660
2661 int sd = INT_MAX;
2662 if (height_ != -1) {
2663 sd = maxSinkDistance(*current);
2664 }
2665 if (sd >= dstSinkDist) {
2666 NodeDescriptor nd = descriptor(*current);
2667 std::pair<OutEdgeIter, OutEdgeIter> edges =
2668 boost::out_edges(nd, graph_);
2669 for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
2670 EdgeDescriptor ed = *ei;
2671 const Edge& edge = *graph_[ed];
2672 if (edge.isBackEdge()) {
2673 continue;
2674 }
2675 NodeDescriptor hd = boost::target(ed, graph_);
2676 Node* const head = graph_[hd];
2677
2678 if (head == &dest) {
2679 return true;
2680 }
2681 if (foundNodes.find(head) == foundNodes.end()) {
2682 queue.insert(head);
2683 foundNodes.insert(head);
2684 // make sure found from the descriptor cache.
2685 nodeDescriptors_[head] = hd;
2686 }
2687 }
2688 }
2689 }
2690 return false;
2691}
2692
2693/**
2694 * Detects cycles that happen without proper backedge properties
2695 * This routine is currently quite slow , there is room for
2696 * optimization. This is to be used for debugging.
2697 */
2698template <typename GraphNode, typename GraphEdge>
2699bool
2700BoostGraph<GraphNode, GraphEdge>::detectIllegalCycles() const {
2701 for (int i = 0; i < nodeCount(); i++) {
2702 GraphNode* originalNode = &node(i);
2703 NodeSet queuedNodes;
2704 NodeSet foundNodes;
2705 queuedNodes.insert(originalNode);
2706 foundNodes.insert(originalNode);
2707 while (!queuedNodes.empty()) {
2708 const GraphNode* n = *queuedNodes.begin();
2709 queuedNodes.erase(queuedNodes.begin());
2710 EdgeSet es = outEdges(*n);
2711 for (typename EdgeSet::iterator ei = es.begin(); ei != es.end(); ei++) {
2712 const GraphEdge* e = *ei;
2713 if (!e->isBackEdge()) {
2714 GraphNode& head = headNode(*e);
2715 if (&head == originalNode) {
2716 std::cerr << "Detected illegal cycle between nodes: "
2717 << originalNode->toString() << " and "
2718 << n->toString() << " edge: " <<
2719 e->toString() << std::endl;
2720 return true;
2721 }
2722 if (!AssocTools::containsKey(foundNodes,&head)) {
2723 foundNodes.insert(&head);
2724 queuedNodes.insert(&head);
2725 }
2726 }
2727 }
2728 }
2729 }
2730 return false;
2731}
2732
2733template <typename GraphNode, typename GraphEdge>
2734bool
2735BoostGraph<GraphNode, GraphEdge>::PathLengthHelper::operator<(
2736 const BoostGraph<GraphNode, GraphEdge>::PathLengthHelper& other) const {
2737 return sd_ < other.sd_;
2738}
2739
2740template <typename GraphNode, typename GraphEdge>
2741BoostGraph<GraphNode, GraphEdge>::PathLengthHelper::PathLengthHelper(
2742 typename BoostGraph<GraphNode,GraphEdge>::NodeDescriptor nd,
2743 int len, int sd, bool looping) :
2744 nd_(nd), len_(len), sd_(sd), looping_(looping) {}