2 Copyright (c) 2002-2010 Tampere University.
4 This file is part of TTA-Based Codesign Environment (TCE).
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:
13 The above copyright notice and this permission notice shall be included in
14 all copies or substantial portions of the Software.
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.
25 * @file BoostGraph.icc
27 * Boost-based templated implementation of graph base class.
28 * In-line implementation of templated methods.
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
41#include <boost/version.hpp>
42#include <boost/format.hpp>
44#include "CompilerWarnings.hh"
45IGNORE_COMPILER_WARNING("-Wunused-parameter")
46IGNORE_CLANG_WARNING("-Wunused-local-typedef")
47#include <boost/graph/topological_sort.hpp>
49#if BOOST_VERSION < 104000
50#include <boost/property_map.hpp>
52#include <boost/property_map/property_map.hpp>
55#include <boost/graph/adjacency_list.hpp>
56#include <boost/graph/graphviz.hpp>
57#include <boost/graph/johnson_all_pairs_shortest.hpp>
61#include "Conversion.hh"
62#include "AssocTools.hh"
63#include "Application.hh"
71template <typename GraphNode, typename GraphEdge>
72BoostGraph<GraphNode, GraphEdge>::BoostGraph(bool allowLoopEdges) :
73 height_(-1), parentGraph_(NULL), sgCounter_(0),
74 allowLoopEdges_(allowLoopEdges), pathCache_(NULL) {}
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) {}
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) {
97 // table which node of other
98 std::map<GraphNode*, GraphNode*> nodeMap;
100 for (int i = 0; i < other.nodeCount(); i++) {
101 GraphNode& currNode = other.node(i);
102 if (nodeMap.find(&currNode) == nodeMap.end()){
104 dynamic_cast<GraphNode*>(currNode.clone());
105 addNode(*nodeMap[&currNode]);
108 GraphNode* ourTail = nodeMap[&currNode];
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);
117 if (nodeMap.find(&headNode) == nodeMap.end()){
119 dynamic_cast<GraphNode*>(headNode.clone());
120 addNode(*nodeMap[&headNode]);
123 GraphNode* ourHead = nodeMap[&headNode];
124 GraphEdge* ourEdge = dynamic_cast<GraphEdge*>(outEdge->clone());
126 connectNodes(*ourTail, *ourHead, *ourEdge);
134 * This automatically deletes all edges that have been in the graph.
135 * Those should not be deleted by destructors of deleted graphs.
137template <typename GraphNode, typename GraphEdge>
138BoostGraph<GraphNode, GraphEdge>::~BoostGraph() {
139 if (parentGraph_ != NULL) {
140 parentGraph_->detachSubgraph(*this);
142 for (typename std::set<GraphEdge*>::iterator i = ownedEdges_.begin();
143 i != ownedEdges_.end(); i++) {
151 * Adds a node to the graph.
153 * Once added, a node is owned and managed by the graph.
155 * Adding a node does not add it to the subgraphs of a graph,
156 * but does add into the parent graph.
158 * @param node Node to be added.
160template <typename GraphNode, typename GraphEdge>
162BoostGraph<GraphNode, GraphEdge>::addNode(GraphNode& node) {
163 NodeDescriptor nd = boost::add_vertex(&node, graph_);
164 nodeDescriptors_[&node] = nd;
167 sourceDistances_[&node] = 0;
168 sinkDistances_[&node] = 0;
170 loopingSourceDistances_[&node] = 0;
171 loopingSinkDistances_[&node] = 0;
174 // add node also to parent graph
175 if (parentGraph_ != NULL) {
176 parentGraph_->addNode(node);
181 * Returns the number of nodes contained in this graph.
183 * @returns The number of nodes.
185template <typename GraphNode, typename GraphEdge>
187BoostGraph<GraphNode, GraphEdge>::nodeCount() const {
188 return boost::num_vertices(graph_);
192 * Returns the number of edges contained in this graph.
194 * @returns The number of edges.
196template <typename GraphNode, typename GraphEdge>
198BoostGraph<GraphNode, GraphEdge>::edgeCount() const {
199 return boost::num_edges(graph_);
203 * Returns the node of the graph identified by the given index.
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.
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.
213template <typename GraphNode, typename GraphEdge>
215BoostGraph<GraphNode, GraphEdge>::node(const int index) const {
216 return node(index, true);
220 * Returns the node of the graph identified by the given index.
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.
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.
230template <typename GraphNode, typename GraphEdge>
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());
240 NodeDescriptor nd = boost::vertex(index, graph_);
241 Node* n = graph_[nd];
243 nodeDescriptors_[n] = nd;
249 * Returns the edge of the graph identified by the given index.
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.
254 * Running time of this function is O(n) where n is the number of edges.
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.
261template <typename GraphNode, typename GraphEdge>
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());
271 typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
272 EdgeIterPair edges = boost::edges(graph_);
274 for (EdgeIter i = edges.first; i != edges.second; i++) {
275 if (counter == index) {
276 GraphEdge* theEdge = graph_[*i];
282 // keep pedantic compilers quiet
283 return *graph_[*edges.second];
287 * Returns the n:th outgoing edge from a given node.
289 * Warning: this function is slow. When iterating over all outgoing edges
290 * of a node, use outEdges instead.
292 * @param node Node whose outgoing edges we are searching
293 * @param index index of outgoing edge being asked
296template <typename GraphNode, typename GraphEdge>
298BoostGraph<GraphNode, GraphEdge>::outEdge(
299 const GraphNode& node, const int index) const {
300 const TCEString procName("BoostGraph::outEdge");
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());
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);
317 GraphEdge* result = NULL;
319 for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
321 result = graph_[(*ei)];
327 assert(result != NULL);
333 * Returns the n:th incoming edge to a given node.
335 * Warning: this function is slow. When iterating over all incoming edges
336 * of a node, use inEdges instead.
338 * @param node Node whose incoming edges we are searching
339 * @param index index of incoming edge being asked
342template <typename GraphNode, typename GraphEdge>
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);
354 GraphEdge* result = NULL;
356 for (InEdgeIter ei = edges.first; ei != edges.second; ei++) {
358 result = graph_[(*ei)];
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());
376 * Returns the outgoing edges of a node.
378 * @param node A node of the graph.
379 * @returns A set of edges.
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_);
388 for (outEdgeIter ei = edges.first; ei != edges.second; ei++) {
389 GraphEdge* edge = graph_[(*ei)];
390 // add to descriptor cache.
391 edgeDescriptors_[edge] = *ei;
398 * Returns the outgoing edges of a node in the root graph of the
401 * @param node A node of the graph.
402 * @returns A set of edges.
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);
411 return parentGraph_->rootGraphOutEdges(node);
416 * Returns the ingoing edges of a node.
418 * @param node A node of the graph.
419 * @returns A set of edges.
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_);
428 for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
429 GraphEdge* edge = graph_[(*ei)];
430 edgeDescriptors_[edge] = *ei;
437 * Returns the ingoing edges of a node in the root graph of the subgraph tree.
439 * @param node A node of the graph.
440 * @returns A set of edges.
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);
449 return parentGraph_->rootGraphInEdges(node);
454 * Returns the ingoing edge of a node in the root graph of the subgraph tree.
456 * @param node A node of the graph.
457 * @param index index of edge.
458 * @return the edge edges.
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);
467 return parentGraph_->rootGraphInEdge(node, index);
472 * Returns the outgoing edge of a node in the root graph of the subgraph tree.
474 * @param node A node of the graph.
475 * @param index index of edge.
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);
485 return parentGraph_->rootGraphOutEdge(node, index);
490 * Returns the output degree of a node, that is, the number of outgoing edges
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.
497template <typename GraphNode, typename GraphEdge>
499BoostGraph<GraphNode, GraphEdge>::outDegree(const GraphNode& node) const {
500 return boost::out_degree(descriptor(node), graph_);
504 * Returns the input degree of a node, that is, the number of incoming edges
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.
511template <typename GraphNode, typename GraphEdge>
513BoostGraph<GraphNode, GraphEdge>::inDegree(const GraphNode& node) const {
514 return boost::in_degree(descriptor(node), graph_);
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
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.
525template <typename GraphNode, typename GraphEdge>
527BoostGraph<GraphNode, GraphEdge>::rootGraphOutDegree(
528 const GraphNode& node) const {
529 return parentGraph_ == NULL ?
530 boost::out_degree(descriptor(node), graph_) :
531 parentGraph_->rootGraphOutDegree(node);
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
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.
542template <typename GraphNode, typename GraphEdge>
544BoostGraph<GraphNode, GraphEdge>::rootGraphInDegree(
545 const GraphNode& node) const {
546 return parentGraph_ == NULL ?
547 boost::in_degree(descriptor(node), graph_) :
548 parentGraph_->rootGraphInDegree(node);
552 * Returns the tail node of a edge.
554 * Warning: this function is slow, O(n) to number of edges in the graph.
556 * @param edge Edge whose tail node we are asking
557 * @return The tail node of the given edge
559template <typename GraphNode, typename GraphEdge>
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;
570 * Returns the tail node of a edge.
572 * This is faster but uglier version of the function.
574 * @param edge Edge whose tail node we are asking
575 * @return The tail node of the given edge
577template <typename GraphNode, typename GraphEdge>
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;
589 * Returns the head node of a edge.
591 * Warning: this function is slow, O(n) to number of edges in the graph.
593 * @param edge Edge whose head node we are asking
594 * @return The head node of the given edge
596template <typename GraphNode, typename GraphEdge>
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;
607 * Returns the head node of a edge.
609 * This is faster but uglier version of the function.
611 * @param edge Edge whose head node we are asking
612 * @return The head node of the given edge
614template <typename GraphNode, typename GraphEdge>
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;
626 * Connects two nodes and attaches the given properties to the new graph
627 * edge connecting the nodes.
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.
633 * @param nTail Tail node of the connection.
634 * @param nHead Head node of the connection.
635 * @param e Properties of the connecting edge.
637template <typename GraphNode, typename GraphEdge>
639BoostGraph<GraphNode, GraphEdge>::connectNodes(
640 const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e) {
641 connectNodes(nTail, nHead, e, NULL);
644template <typename GraphNode, typename GraphEdge>
646BoostGraph<GraphNode, GraphEdge>::calculatePathLengthsOnConnect(
647 const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e) {
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);
658 if (loopingHeadIter != loopingSinkDistances_.end() &&
660 calculateSinkDistance(
661 nTail, loopingHeadIter->second + eWeight, true);
664 if (headIter == sinkDistances_.end()) {
665 sinkDistances_[&nHead] = 0;
666 calculateSinkDistance(nTail, eWeight, e.isBackEdge());
668 calculateSinkDistance(
669 nTail, headIter->second + eWeight, e.isBackEdge());
672 if (loopingTailIter != loopingSourceDistances_.end() &&
674 calculateSourceDistances(
675 &nHead, loopingTailIter->second + eWeight, true);
678 if (tailIter == sourceDistances_.end()) {
679 sourceDistances_[&nTail] = 0;
680 calculateSourceDistances(&nHead, eWeight, e.isBackEdge());
682 calculateSourceDistances(
683 &nHead, tailIter->second + eWeight, e.isBackEdge());
688 * Connects two nodes and attaches the given properties to the new graph
689 * edge connecting the nodes.
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.
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
700template <typename GraphNode, typename GraphEdge>
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) {
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");
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);
724 if (parentGraph_ == NULL && !creatingSG) {
725 ownedEdges_.insert(&e);
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!");
735 edgeDescriptors_[&e] =
736 boost::add_edge(td, hd, &e, graph_).
739 // If we have calculated path lenght data, keep it in sync.
741 calculatePathLengthsOnConnect(nTail, nHead, e);
745 if (parentGraph_ != NULL && parentGraph_ != modifier) {
746 parentGraph_->connectNodes(nTail, nHead, e, this);
749 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
750 if ( childGraphs_[i] != modifier ) {
751 childGraphs_[i]->connectNodes(nTail, nHead, e, this);
756template<typename GraphNode, typename GraphEdge>
758BoostGraph<GraphNode, GraphEdge>::sinkDistDecreased(
759const GraphNode& n) const {
765 auto lsdIter = loopingSinkDistances_.find(&n);
766 int oldSD = sinkDistances_[&n];
767 int oldLSD = lsdIter != loopingSinkDistances_.end() ?
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);
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);
791 if (sd < oldSD || loopingSD < oldLSD) {
792 sinkDistances_[&n] = sd;
793 if (loopingSD < oldLSD) {
794 loopingSinkDistances_[&n] = loopingSD;
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);
811template<typename GraphNode, typename GraphEdge>
813BoostGraph<GraphNode, GraphEdge>::sourceDistDecreased(
814 const GraphNode& n) const {
820 auto lsdIter = loopingSourceDistances_.find(&n);
821 int oldSD = sourceDistances_[&n];
822 int oldLSD = lsdIter != loopingSourceDistances_.end() ?
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);
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);
848 if (sd < oldSD || loopingSD < oldLSD) {
849 sourceDistances_[&n] = sd;
850 if (loopingSD < oldLSD) {
851 loopingSourceDistances_[&n] = loopingSD;
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);
869 * Disconnects two nodes.
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.
874 * @param nTail Tail node of the connection.
875 * @param nHead Head node of the connection.
877template <typename GraphNode, typename GraphEdge>
879BoostGraph<GraphNode, GraphEdge>::disconnectNodes(
880 const GraphNode& nTail,
881 const GraphNode& nHead) {
885 while (hasEdge(nTail, nHead)) {
886 EdgeDescriptor ed = connectingEdge(nTail, nHead);
887 GraphEdge* e = graph_[ed];
889 int eWeight = edgeWeight(*e, nHead);
890 if (e->isBackEdge()) {
891 maxwLoop = std::max(eWeight, maxW);
893 maxW = std::max(eWeight, maxW);
896 removeEdge(*e, &nTail, &nHead);
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]))) {
909 sourceDistDecreased(nTail);
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])))) {
921 sinkDistDecreased(nHead);
932 * Moves all incoming edges from a node to another node.
934 * This reuses the origial Edge objects, thus should retain the original
935 * properties (even if defined in a derived class).
937 * @param source The node to move the incoming edges from.
938 * @param destination The node to move the incoming edges to.
940template <typename GraphNode, typename GraphEdge>
942BoostGraph<GraphNode, GraphEdge>::moveInEdges(
943 const GraphNode& source, const GraphNode& destination) {
944 moveInEdges(source, destination, NULL);
948 * Moves all incoming edges from a node to another node.
950 * This reuses the origial Edge objects, thus should retain the original
951 * properties (even if defined in a derived class).
953 * @param source The node to move the incoming edges from.
954 * @param destination The node to move the incoming edges to.
956template <typename GraphNode, typename GraphEdge>
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);
967 return; // no need to do anything
971 EdgeSet edges = inEdges(source);
972 for (typename EdgeSet::iterator i = edges.begin();
973 i != edges.end(); ++i) {
975 const GraphNode& tail = tailNode(e);
976 const GraphNode& head = destination;
977 boost::remove_edge(descriptor(e), graph_);
979 typename EdgeDescMap::iterator
980 edIter = edgeDescriptors_.find(&e);
981 if (edIter != edgeDescriptors_.end()) {
982 edgeDescriptors_.erase(edIter);
985 sourceDistDecreased(source);
986 sinkDistDecreased(tail);
988 // if dest not in this graph, just remove
989 if (hasNode(destination)) {
990 std::pair<EdgeDescriptor,bool> tmpPair =
992 descriptor(tail), descriptor(head), &e, graph_);
993 edgeDescriptors_[&e] = tmpPair.first;
996 calculatePathLengthsOnConnect(tail, head, e);
1002 // update parent- and childgraphs
1003 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1004 parentGraph_->moveInEdges(
1005 source, destination, this);
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);
1017template <typename GraphNode, typename GraphEdge>
1019BoostGraph<GraphNode, GraphEdge>::copyInEdge(
1020 const GraphNode& destination,
1022 const GraphNode* tail) {
1023 // start from the root tree.
1024 BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
1026 tail = &rg->tailNode(edge);
1028 Edge* newEdge = new Edge(edge);
1029 rg->connectNodes(*tail, destination, *newEdge);
1032template <typename GraphNode, typename GraphEdge>
1034BoostGraph<GraphNode, GraphEdge>::copyOutEdge(
1035// const GraphNode& source,
1036 const GraphNode& destination,
1038 const GraphNode* head) {
1039 // start from the root tree.
1040 BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
1042 head = &rg->headNode(edge);
1044 Edge* newEdge = new Edge(edge);
1045 rg->connectNodes(destination, *head, *newEdge);
1049 * Moves an edge which comes into source node to point into another node.
1051template <typename GraphNode, typename GraphEdge>
1053BoostGraph<GraphNode, GraphEdge>::moveInEdge(
1054 const GraphNode& originalHeadNode,
1055 const GraphNode& newHeadNode,
1057 const GraphNode* tail,
1060 // start from the root tree.
1062 BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
1064 tail = &rg->tailNode(edge);
1066 rg->moveInEdge(originalHeadNode, newHeadNode, edge, tail, true);
1070 if (hasNode(*tail) && hasEdge(edge)) {
1071 bool hasSource = hasNode(originalHeadNode);
1072 bool hasDestination = hasNode(newHeadNode);
1073 const GraphNode& head = newHeadNode;
1076 boost::remove_edge(descriptor(edge), graph_);
1078 sourceDistDecreased(originalHeadNode);
1079 sinkDistDecreased(*tail);
1082 if (hasDestination) {
1083 std::pair<EdgeDescriptor,bool> tmpPair =
1085 descriptor(*tail), descriptor(head), &edge, graph_);
1086 edgeDescriptors_[&edge] = tmpPair.first;
1088 if (height_ != -1) {
1089 calculatePathLengthsOnConnect(*tail, head, edge);
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);
1104 * Moves edge which originally points
1106template <typename GraphNode, typename GraphEdge>
1108BoostGraph<GraphNode, GraphEdge>::moveOutEdge(
1109 const GraphNode& originalTailNode,
1110 const GraphNode& newTailNode,
1112 const GraphNode* head,
1116 BoostGraph* rg = rootGraph();
1118 head = &rg->headNode(edge);
1120 rg->moveOutEdge(originalTailNode, newTailNode, edge, head, true);
1124 if (hasNode(*head) && hasEdge(edge)) {
1125 bool hasSource = hasNode(originalTailNode);
1126 bool hasDestination = hasNode(newTailNode);
1128 const GraphNode& tail = newTailNode;
1130 boost::remove_edge(descriptor(edge), graph_);
1132 sourceDistDecreased(*head);
1133 sinkDistDecreased(originalTailNode);
1137 if (hasDestination) {
1138 std::pair<EdgeDescriptor,bool> tmpPair =
1140 descriptor(tail), descriptor(*head), &edge, graph_);
1141 edgeDescriptors_[&edge] = tmpPair.first;
1143 if (height_ != -1) {
1144 calculatePathLengthsOnConnect(tail, *head, edge);
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);
1160 * Moves all outgoing edges from a node to another node.
1162 * This reuses the origial Edge objects, thus should retain the original
1163 * properties (even if defined in a derived class).
1165 * @param source The node to move the outgoing edges from.
1166 * @param destination The node to move the outgoing edges to.
1168template <typename GraphNode, typename GraphEdge>
1170BoostGraph<GraphNode, GraphEdge>::moveOutEdges(
1171 const GraphNode& source, const GraphNode& destination) {
1172 moveOutEdges(source, destination, this);
1176 * Moves all outgoing edges from a node to another node.
1178 * This reuses the origial Edge objects, thus should retain the original
1179 * properties (even if defined in a derived class).
1181 * @param source The node to move the outgoing edges from.
1182 * @param destination The node to move the outgoing edges to.
1184template <typename GraphNode, typename GraphEdge>
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);
1195 return; // no need to do anything
1199 EdgeSet edges = outEdges(source);
1200 for (typename EdgeSet::iterator i = edges.begin();
1201 i != edges.end(); ++i) {
1203 const GraphNode& tail = destination;
1204 const GraphNode& head = headNode(e);
1205 boost::remove_edge(descriptor(e), graph_);
1207 sourceDistDecreased(head);
1208 sinkDistDecreased(source);
1210 typename EdgeDescMap::iterator
1211 edIter = edgeDescriptors_.find(&e);
1212 if (edIter != edgeDescriptors_.end()) {
1213 edgeDescriptors_.erase(edIter);
1216 if (hasNode(destination)) {
1217 std::pair<EdgeDescriptor,bool> tmpPair =
1219 descriptor(tail), descriptor(head), &e, graph_);
1220 edgeDescriptors_[&e] = tmpPair.first;
1222 if (height_ != -1) {
1223 calculatePathLengthsOnConnect(tail, head, e);
1230 // update parent- and childgraphs
1231 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1232 parentGraph_->moveOutEdges(source, destination, this);
1235 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1236 if (childGraphs_.at(i) != modifierGraph ) {
1237 childGraphs_.at(i)->moveOutEdges(source, destination, this);
1244template <typename GraphNode, typename GraphEdge>
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);
1257 * Removes a node of the graph, without deleting the associated properties.
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.
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.
1266template <typename GraphNode, typename GraphEdge>
1268BoostGraph<GraphNode, GraphEdge>::removeNode(
1269 GraphNode& nodeToRemove, BoostGraph* modifierGraph) {
1270 if (hasNode(nodeToRemove)) {
1272 replaceNodeWithLastNode(nodeToRemove);
1274 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1275 parentGraph_->removeNode(nodeToRemove, this);
1278 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1279 if (childGraphs_.at(i) != modifierGraph ) {
1280 childGraphs_.at(i)->removeNode(nodeToRemove, this);
1284 if (parentGraph_ == NULL) {
1285 TCEString msg = "Node not found in graph, cannot remove";
1286 throw InstanceNotFound(__FILE__,__LINE__,__func__, msg);
1292 * Removes a node of the graph, without deleting the associated properties.
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.
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.
1301template <typename GraphNode, typename GraphEdge>
1303BoostGraph<GraphNode, GraphEdge>::removeNode(GraphNode& node) {
1304 removeNode(node, NULL);
1308 * Removes a node of the subgraph, leaving it to the parent graph.
1310 * Drops node also from all child graphs.
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.
1316template <typename GraphNode, typename GraphEdge>
1318BoostGraph<GraphNode, GraphEdge>::dropNode(GraphNode& nodeToDrop) {
1319 if (!hasNode(nodeToDrop)) {
1323 replaceNodeWithLastNode(nodeToDrop);
1325 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1326 childGraphs_.at(i)->dropNode(nodeToDrop);
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.
1336 * @param dest node to be removed/replaced with last one.
1338template <typename GraphNode, typename GraphEdge>
1340BoostGraph<GraphNode, GraphEdge>::replaceNodeWithLastNode(GraphNode& dest) {
1342 NodeDescriptor nd = descriptor(dest);
1343 typename BoostGraph<GraphNode, GraphEdge>::NodeSet preds;
1344 typename BoostGraph<GraphNode, GraphEdge>::NodeSet succs;
1346 succs = successors(dest);
1347 preds = predecessors(dest);
1349 // remove edge cache
1350 clearDescriptorCache(inEdges(dest));
1351 clearDescriptorCache(outEdges(dest));
1353 // clear all edges. from to node to remove/drop.
1354 boost::clear_vertex(nd, graph_);
1356 // Move last node to place of deleted node, then delete last node.
1357 GraphNode& lastNode = node(nodeCount()-1);
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) {
1366 const GraphNode& tail = tailNode(e);
1367 // remove the edge pointing to old place of last node
1368 boost::remove_edge(descriptor(e), graph_);
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);
1377 // add the edge back, pointing to the new place
1378 // of the last node.
1379 std::pair<EdgeDescriptor,bool> tmpPair =
1381 descriptor(tail), nd, &e, graph_);
1382 edgeDescriptors_[&e] = tmpPair.first;
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) {
1390 const GraphNode& head = headNode(e);
1391 // remove the edge pointing to old place of last node
1392 boost::remove_edge(descriptor(e), graph_);
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);
1401 // add the edge back, originating from the new place
1402 // of the last node.
1403 std::pair<EdgeDescriptor,bool> tmpPair =
1405 nd, descriptor(head), &e, graph_);
1406 edgeDescriptors_[&e] = tmpPair.first;
1409 // then move the Node class.
1410 graph_[nd] = &lastNode;
1412 // update descriptor map.
1413 nodeDescriptors_[&lastNode] = nd;
1416 if (height_ != -1) {
1417 sinkDistances_.erase(&dest);
1418 sourceDistances_.erase(&dest);
1419 loopingSinkDistances_.erase(&dest);
1420 loopingSourceDistances_.erase(&dest);
1423 for (auto n: succs) sourceDistDecreased(*n);
1424 for (auto n: preds) sinkDistDecreased(*n);
1426 nodeDescriptors_[&lastNode] = nd;
1428 // remove just the last node.
1429 boost::remove_vertex(lnd, graph_);
1431 // remove node from descriptor cache
1432 typename NodeDescMap::iterator ndi =
1433 nodeDescriptors_.find(&dest);
1434 if (ndi != nodeDescriptors_.end()) {
1435 nodeDescriptors_.erase(ndi);
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.
1444 * The connection between the head and tail nodes corresponding to the given
1445 * property object is removed from the graph.
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.
1451template <typename GraphNode, typename GraphEdge>
1453BoostGraph<GraphNode, GraphEdge>::removeEdge(GraphEdge& e) {
1454 removeEdge(e, NULL, NULL, NULL);
1458 * Removes the edge connecting two nodes of the graph from a subgraph,
1459 * but leaves it into the original graph
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.
1466template <typename GraphNode, typename GraphEdge>
1468BoostGraph<GraphNode, GraphEdge>::dropEdge(GraphEdge& e) {
1469 boost::remove_edge(descriptor(e), graph_);
1471 typename EdgeDescMap::iterator
1472 edIter = edgeDescriptors_.find(&e);
1473 if (edIter != edgeDescriptors_.end()) {
1474 edgeDescriptors_.erase(edIter);
1477 for (unsigned int i = 0; i < childGraphs_.size(); i++) {
1478 childGraphs_.at(i)->dropEdge(e);
1483 * Removes the edge connecting two nodes of the graph, without deleting the
1484 * associated properties.
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.
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.
1494template <typename GraphNode, typename GraphEdge>
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_);
1502 typename EdgeDescMap::iterator
1503 edIter = edgeDescriptors_.find(&e);
1504 if (edIter != edgeDescriptors_.end()) {
1505 edgeDescriptors_.erase(edIter);
1508 if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
1509 parentGraph_->removeEdge(e, tailNode, headNode, this);
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);
1522//////////////////////////////////////////////////////////////////////////////
1523// Subgraph related public methods
1524//////////////////////////////////////////////////////////////////////////////
1527 * Returns the parent graph of this subgraph.
1528 * If the graph has no parent, returns NULL.
1530 * @return parent graph of this subgraph or NULL if is not subgraph.
1532template <typename GraphNode, typename GraphEdge>
1533BoostGraph<GraphNode, GraphEdge>*
1534BoostGraph<GraphNode, GraphEdge>::parentGraph() {
1535 return parentGraph_;
1539 * Returns the root graph of this subgraph.
1540 * If this has no parent, return this.
1542 * @return parent graph of this subgraph.
1544template <typename GraphNode, typename GraphEdge>
1545BoostGraph<GraphNode, GraphEdge>*
1546BoostGraph<GraphNode, GraphEdge>::rootGraph() {
1547 if (parentGraph_ == NULL) {
1550 return parentGraph_;
1554 * Returns the root graph of this subgraph.
1555 * If this has no parent, return this.
1557 * @return parent graph of this subgraph.
1559template <typename GraphNode, typename GraphEdge>
1560const BoostGraph<GraphNode, GraphEdge>*
1561BoostGraph<GraphNode, GraphEdge>::rootGraph() const {
1562 if (parentGraph_ == NULL) {
1565 return parentGraph_;
1569 * Creates a subgraph from this graph.
1571 * This procedure is suposed to be called from derived class's
1572 * createSubGraph method which also wold create the new object.
1574template <typename GraphNode, typename GraphEdge>
1576BoostGraph<GraphNode, GraphEdge>::constructSubGraph(
1577 BoostGraph& subGraph, NodeSet& nodes) {
1579 for( typename NodeSet::iterator i = nodes.begin();
1580 i != nodes.end(); i++ ) {
1581 GraphNode& gn = *(*i);
1582 subGraph.addNode(gn);
1585 for( typename NodeSet::iterator i = nodes.begin();
1586 i != nodes.end(); i++ ) {
1587 GraphNode& gn = *(*i);
1588 NodeDescriptor nd = descriptor(gn);
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);
1601 subGraph.parentGraph_ = this;
1602 childGraphs_.push_back(&subGraph);
1603 subGraph.name_ = name() + "_" + Conversion::toString(++sgCounter_);
1607 * When a node has been dropped from a subgraph, this restores it,
1608 * based on the edges on the parent graph
1610template <typename GraphNode, typename GraphEdge>
1612BoostGraph<GraphNode, GraphEdge>::restoreNodeFromParent(
1614 assert(parentGraph_ != NULL);
1616 BoostGraph<GraphNode, GraphEdge>* parent = parentGraph_;
1617 parentGraph_ = NULL;
1620 NodeDescriptor ndp = parent->descriptor(n);
1622 std::pair<OutEdgeIter, OutEdgeIter> oEdges =
1623 boost::out_edges(ndp, parent->graph_);
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);
1635 std::pair<InEdgeIter, InEdgeIter> iEdges =
1636 boost::in_edges(ndp, parent->graph_);
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);
1647 parentGraph_ = parent;
1651 * Detach a subgraph from this graph.
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.
1657 * @param subGraph subgraph to remove from the graph
1659template <typename GraphNode, typename GraphEdge>
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);
1672/////////////////////////////////////////////////////////////////////////////
1673// Private helper methods
1674/////////////////////////////////////////////////////////////////////////////
1678 * Checks whether the given node belongs to the graph
1680 * @param node node being tested
1681 * @return whether the ndoe belongs to the graph
1683template <typename GraphNode, typename GraphEdge>
1685BoostGraph<GraphNode, GraphEdge>::hasNode(const GraphNode& node) const {
1687 if (AssocTools::containsKey(nodeDescriptors_,&node)) {
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;
1704 * Checks whether there exists and edge between the given nodes
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
1710template <typename GraphNode, typename GraphEdge>
1712BoostGraph<GraphNode, GraphEdge>::hasEdge(
1713 const GraphNode& nTail,
1714 const GraphNode& nHead) const {
1716 typedef std::pair<EdgeDescriptor, bool> EdgeReturned;
1717 EdgeReturned er = boost::edge(
1718 descriptor(nTail), descriptor(nHead), graph_);
1719 if (er.second == true) {
1727 * Checks whether the given edge connects the given nodes
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
1734template <typename GraphNode, typename GraphEdge>
1736BoostGraph<GraphNode, GraphEdge>::hasEdge(
1737 const GraphNode& nTail,
1738 const GraphNode& nHead,
1739 const GraphEdge& edge) const {
1741 typedef std::pair<OutEdgeIter, OutEdgeIter> OutEdgeIterPair;
1743 unsigned int hd = descriptor(nHead);
1744 OutEdgeIterPair edges = boost::out_edges(descriptor(nTail), graph_);
1746 for (OutEdgeIter i = edges.first; i != edges.second; i++) {
1747 if (graph_[*i] == &edge && target(*i, graph_) == hd) {
1756 * Checks whether the given edge belongs to the graph.
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
1763template <typename GraphNode, typename GraphEdge>
1765BoostGraph<GraphNode, GraphEdge>::hasEdge(
1767 const GraphNode* nTail,
1768 const GraphNode* nHead) const {
1770 if (AssocTools::containsKey(edgeDescriptors_,&e)) {
1774 // if we have tails, check if's out edges
1775 if (nTail != NULL && hasNode(*nTail)) {
1776 typedef std::pair<OutEdgeIter, OutEdgeIter> OutEdgeIterPair;
1778 OutEdgeIterPair edges = boost::out_edges(descriptor(*nTail), graph_);
1780 for (OutEdgeIter i = edges.first; i != edges.second; i++) {
1781 if (graph_[*i] == &e) {
1782 edgeDescriptors_[&e] = *i;
1787 } else { // if we have head, check it's in edges.
1788 if (nHead != NULL && hasNode(*nHead)) {
1789 typedef std::pair<InEdgeIter, InEdgeIter> InEdgeIterPair;
1791 InEdgeIterPair edges = boost::in_edges(descriptor(*nHead), graph_);
1793 for (InEdgeIter i = edges.first; i != edges.second; i++) {
1794 if (graph_[*i] == &e) {
1795 edgeDescriptors_[&e] = *i;
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_);
1807 for (EdgeIter i = edges.first; i != edges.second; i++) {
1808 if (graph_[*i] == &e) {
1809 edgeDescriptors_[&e] = *i;
1816template <typename GraphNode, typename GraphEdge>
1817typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1818BoostGraph<GraphNode, GraphEdge>::descriptor(const GraphEdge& e) const {
1820 typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
1821 if (cacheIter != edgeDescriptors_.end()) {
1822 return cacheIter->second;
1825 typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
1826 EdgeIterPair edges = boost::edges(graph_);
1828 for (EdgeIter i = edges.first; i != edges.second; i++) {
1829 if (graph_[*i] == &e) {
1830 edgeDescriptors_[&e] = *i;
1834 assert(false && "Descriptor for edge not found!");
1835 return *edges.second;
1838template <typename GraphNode, typename GraphEdge>
1839typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1840BoostGraph<GraphNode, GraphEdge>::edgeDescriptor(
1841 const GraphEdge& e, const NodeDescriptor& headNode) const {
1843 typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
1844 if (cacheIter != edgeDescriptors_.end()) {
1845 return cacheIter->second;
1848 typedef std::pair<InEdgeIter, InEdgeIter> EdgeIterPair;
1849 EdgeIterPair edges = boost::in_edges(headNode,graph_);
1851 for (InEdgeIter i = edges.first; i != edges.second; i++) {
1852 if (graph_[*i] == &e) {
1853 edgeDescriptors_[&e] = *i;
1858 return *edges.second;
1861template <typename GraphNode, typename GraphEdge>
1862typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1863BoostGraph<GraphNode, GraphEdge>::edgeDescriptor(
1864 const NodeDescriptor& tailNode, const GraphEdge& e) const {
1866 typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
1867 if (cacheIter != edgeDescriptors_.end()) {
1868 return cacheIter->second;
1871 typedef std::pair<OutEdgeIter, OutEdgeIter> EdgeIterPair;
1872 EdgeIterPair edges = boost::out_edges(tailNode,graph_);
1874 for (OutEdgeIter i = edges.first; i != edges.second; i++) {
1875 if (graph_[*i] == &e) {
1876 edgeDescriptors_[&e] = *i;
1881 return *edges.second;
1884template <typename GraphNode, typename GraphEdge>
1885typename BoostGraph<GraphNode, GraphEdge>::NodeDescriptor
1886BoostGraph<GraphNode, GraphEdge>::descriptor(const GraphNode& n) const {
1888 typename NodeDescMap::iterator cacheIter = nodeDescriptors_.find(&n);
1889 if (cacheIter != nodeDescriptors_.end()) {
1890 return cacheIter->second;
1893 typedef std::pair<NodeIter, NodeIter> NodeIterPair;
1894 NodeIterPair nodes = boost::vertices(graph_);
1896 for (NodeIter i = nodes.first; i != nodes.second; i++) {
1897 if (graph_[*i] == &n) {
1898 nodeDescriptors_[&n] = *i;
1902 Application::logStream()
1903 << "Node " << n.toString() << "not in graph!" << std::endl;
1904 BoostGraph<GraphNode, GraphEdge>::writeToDotFile("missing_node.dot");
1907 return *nodes.second;
1911template <typename GraphNode, typename GraphEdge>
1912typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
1913BoostGraph<GraphNode, GraphEdge>::connectingEdge(
1914 const GraphNode& nTail,
1915 const GraphNode& nHead) const {
1917 typedef std::pair<EdgeDescriptor, bool> EdgeReturned;
1919 EdgeReturned edges = boost::edge(
1920 descriptor(nTail), descriptor(nHead), graph_);
1921 if (edges.second == false) {
1922 abortWithError("Connecting edge not found!");
1928 * Returns all the root nodes of the graph.
1930 * Root nodes are nodes of which input degree is 0 (no edges entering, only
1931 * leaving). Also known as 'source nodes'.
1933 * @return Set of root nodes, can be empty.
1935template<typename GraphNode, typename GraphEdge>
1936typename BoostGraph<GraphNode, GraphEdge>::NodeSet
1937BoostGraph<GraphNode, GraphEdge>::rootNodes() const {
1940 for (int nodeIndex = 0; nodeIndex < nodeCount(); ++nodeIndex) {
1941 GraphNode& nod = node(nodeIndex);
1942 if (inDegree(nod) == 0)
1943 rootNodes.insert(&nod);
1950 * Returns all the sink nodes of the graph.
1952 * Sink nodes are nodes of which output degree is 0 (no edges exiting, only
1955 * @return Set of sink nodes, can be empty.
1957template<typename GraphNode, typename GraphEdge>
1958typename BoostGraph<GraphNode, GraphEdge>::NodeSet
1959BoostGraph<GraphNode, GraphEdge>::sinkNodes() const {
1962 for (int nodeIndex = 0; nodeIndex < nodeCount(); ++nodeIndex) {
1963 GraphNode& nod = node(nodeIndex);
1964 if (outDegree(nod) == 0)
1965 sinkNodes.insert(&nod);
1971 * Returns all the successors of the given node.
1973 * If node has no successors, an empty set is returned. Note: the node can
1974 * also be a successor of itself.
1976 * @param node The node of which successors to find.
1977 * @return Set of root nodes, can be empty.
1979template<typename GraphNode, typename GraphEdge>
1980typename BoostGraph<GraphNode, GraphEdge>::NodeSet
1981BoostGraph<GraphNode, GraphEdge>::successors(
1982 const Node& node, bool ignoreBackEdges, bool ignoreForwardEdges) const {
1986 NodeDescriptor nd = descriptor(node);
1987 typedef typename GraphTraits::out_edge_iterator outEdgeIter;
1988 std::pair<outEdgeIter, outEdgeIter> edges = boost::out_edges(nd, graph_);
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];
2006 * Returns all the predecessors of the given node.
2008 * If node has no predecessors, an empty set is returned. Note: the node can
2009 * also be a predecessor of itself.
2011 * @param node The node of which predecessors to find.
2012 * @return Set of root nodes, can be empty.
2014template<typename GraphNode, typename GraphEdge>
2015typename BoostGraph<GraphNode, GraphEdge>::NodeSet
2016BoostGraph<GraphNode, GraphEdge>::predecessors(
2017 const Node& node, bool ignoreBackEdges, bool ignoreForwardEdges) const {
2021 typedef typename GraphTraits::in_edge_iterator InEdgeIter;
2022 std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
2023 descriptor(node), graph_);
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];
2040 * Calculates maximum path lengths from sinks and sources to all nodes.
2042 * This procedure is called internally when this information is needed
2044template<typename GraphNode, typename GraphEdge>
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];
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;
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_) {
2074 } else if(sdIter->second < sdLen) {
2075 sdIter->second = sdLen;
2076 if (sdLen > height_) {
2085 * Calculates maximum path lengths from sinks and sources to all nodes.
2087 * This procedure is called internally when this information is needed
2089template<typename GraphNode, typename GraphEdge>
2091BoostGraph<GraphNode, GraphEdge>::calculatePathLengths() const {
2093 calculateSourceDistances();
2095 if (!allowLoopEdges_) {
2096 calculatePathLengthsFast();
2100 // priority queue of all sink nodes.
2101 std::priority_queue<PathLengthHelper> sinkDistanceQueue;
2103 // insert all sink nodes to the pqueue
2104 for (int i = nodeCount() -1 ; i >= 0 ; i--) {
2106 NodeDescriptor nd = descriptor(node(i));
2107 std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
2110 bool outEdgeFound = false;
2111 for (OutEdgeIter ii = edges.first; ii != edges.second;
2113 EdgeDescriptor ed = *ii;
2114 if (!graph_[ed]->isBackEdge()) {
2115 outEdgeFound = true;
2118 if (!outEdgeFound) {
2119 sinkDistanceQueue.push(
2120 PathLengthHelper(nd, 0, sourceDistances_[&node(i)]));
2124 // and then start sink calculation from each of them.
2125 while (!sinkDistanceQueue.empty()) {
2126 calculateSinkDistance(*graph_[sinkDistanceQueue.top().nd_],0);
2127 sinkDistanceQueue.pop();
2132 * Calculates source distances of nodes.
2134 * Iterative algorithm, starts from given node or all source nodes.
2136 * Does a breadth-first search, prioritizating first nodes in the graph.
2138 * @param startingNode node whose successors's source dist to calculate,
2139 * or NULL if start from all sources.
2141 * @param startingLength source distance of the startingnode.
2143template<typename GraphNode, typename GraphEdge>
2145BoostGraph<GraphNode, GraphEdge>::calculateSourceDistances(
2146 const GraphNode* startingNode, int startingLength, bool looping) const {
2148 if (startingLength > height_) {
2149 height_ = startingLength;
2152 // priority queue of nodes to be processed
2153 typename std::map <NodeDescriptor, int> sourceDistanceQueue;
2155 // priority queue of nodes to be processed
2156 typename std::map <NodeDescriptor, int> loopingSourceDistanceQueue;
2158 // first initialize starting nodes to the queue
2160 // one starting node?
2161 if (startingNode != NULL) {
2163 sourceDistances_[startingNode] = startingLength;
2164 sourceDistanceQueue[descriptor(*startingNode)] = startingLength;
2166 loopingSourceDistances_[startingNode] = startingLength;
2167 loopingSourceDistanceQueue[descriptor(*startingNode)] =
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(
2178 bool inEdgeFound = false;
2179 for (InEdgeIter ii = edges.first; ii != edges.second;
2181 EdgeDescriptor ed = *ii;
2182 if (!graph_[ed]->isBackEdge()) {
2187 sourceDistances_[graph_[nd]] = startingLength;
2188 sourceDistanceQueue[nd] = startingLength;
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();
2198 NodeDescriptor nd = sdBegin->first;
2199 int len = sdBegin->second;
2200 sourceDistanceQueue.erase(sdBegin);
2202 // then test all successors..
2203 std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
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;
2213 if (destLen > height_) {
2217 // normal or loop-containing length?
2218 auto & sourceDistances =
2219 edge->isBackEdge() ? loopingSourceDistances_:sourceDistances_;
2221 // find the place in the sourcedistances table
2222 auto sdIter = sourceDistances.find(headNode);
2224 // if not yet there, add
2225 if (sdIter == sourceDistances.end()) {
2226 sourceDistances[headNode] = destLen;
2228 // this is longer? replace with this
2229 if (sdIter->second < destLen ) {
2230 sdIter->second = destLen;
2232 // we have already been here, with bigger path.
2233 // no need to check successors.
2238 // add to normal or loop-containing queue?
2240 NodeDescriptor,int> &
2241 mySourceDistanceQueue =
2242 edge->isBackEdge() ?
2243 loopingSourceDistanceQueue : sourceDistanceQueue;
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;
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;
2262 // then iterate over nodes that have one loop node pointing to them.
2263 // do not follow any other loop edges.
2265 while (!loopingSourceDistanceQueue.empty()) {
2266 typename std::map <NodeDescriptor, int>::iterator sdBegin =
2267 loopingSourceDistanceQueue.begin();
2269 NodeDescriptor nd = sdBegin->first;
2270 int len = sdBegin->second;
2271 loopingSourceDistanceQueue.erase(sdBegin);
2273 // then test all successors..
2274 std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
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()) {
2283 NodeDescriptor headDesc = boost::target(ed, graph_);
2284 Node* headNode = graph_[headDesc];
2285 int eWeight = edgeWeight(*edge, *headNode);
2286 int destLen = len + eWeight;
2288 // find the place in the sourcedistances table
2289 auto sdIter = loopingSourceDistances_.find(headNode);
2291 // if not yet there, add
2292 if (sdIter == loopingSourceDistances_.end()) {
2293 loopingSourceDistances_[headNode] = destLen;
2295 // this is longer? replace with this
2296 if (sdIter->second < destLen ) {
2297 sdIter->second = destLen;
2299 // we have already been here, with bigger path.
2300 // no need to check successors.
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;
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;
2324 * Recursively calculates path lenght from sinks to sources.
2326 * @param node Node curently being processed
2327 * @param len Current lenght from sink.
2329template<typename GraphNode, typename GraphEdge>
2331BoostGraph<GraphNode, GraphEdge>::calculateSinkDistance(
2332 const Node& node, int len, bool looping ) const {
2334 GraphBase<GraphNode,GraphEdge>::writeToDotFile("not_dag.dot");
2335 assert(false&&"cannot calc sink distance for graph which is not dag");
2338 auto &sinkDistances = looping ? loopingSinkDistances_ : sinkDistances_;
2340 // find the place in the sourcedistances table
2341 auto sdIter = sinkDistances.find(&node);
2343 // if not yet there, add
2344 if (sdIter == sinkDistances.end()) {
2345 sinkDistances[&node] = len;
2347 // this is longer? replace with this
2348 if (sdIter->second <= len ) {
2349 sdIter->second = len;
2351 // we have already been here, with bigger path.
2352 // no need to check successors.
2357 if (len > height_) {
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_) {
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;
2386 // this is longer? replace with this
2387 if (sdIter->second < sdLen) {
2388 sdIter->second = sdLen;
2390 // we have already been here, with bigger path.
2391 // no need to check successors.
2395 predecessorQueue.push(
2397 td, sdLen, sourceDistances_[tailNode], true));
2399 sdIter = sinkDistances_.find(tailNode);
2400 // if not yet there, add
2401 if (sdIter == sinkDistances_.end()) {
2402 sinkDistances_[tailNode] = sdLen;
2404 // this is longer? replace with this
2405 if (sdIter->second < sdLen ) {
2406 sdIter->second = sdLen;
2408 // we have already been here, with bigger path.
2409 // no need to check successors.
2413 predecessorQueue.push(
2415 td, sdLen, sourceDistances_[tailNode], false));
2420 // all predecessors are in the queue, loop it thru in
2422 while (!predecessorQueue.empty()) {
2424 PathLengthHelper plh = predecessorQueue.top();
2425 calculateSinkDistance(
2426 *graph_[plh.nd_], plh.len_, plh.looping_);
2427 predecessorQueue.pop();
2432 * Gives the lenght of a longest path a node belongs in a graph.
2434 * If the path lenghts are not calculated calculates them.
2435 * If the graph is a cyclic graph, the function may never return.
2437 * @param node Node belonging to a path.
2439 * @return length of the longest path where given node belongs to
2441template<typename GraphNode, typename GraphEdge>
2443BoostGraph<GraphNode, GraphEdge>::maxPathLength(const GraphNode& node) const {
2444 return maxSinkDistance(node) + maxSourceDistance(node);
2448 * Gives the lenght of a longest path from any source node to given node.
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.
2456 * @param node Node belonging to a path.
2458 * @return length of the longest path where given node belongs to
2460template<typename GraphNode, typename GraphEdge>
2462BoostGraph<GraphNode, GraphEdge>::maxSourceDistance(const GraphNode& node)
2465 if (!hasNode(node)) {
2470 for (int i = 0; i < 2; i++) {
2471 auto iter = loopingSourceDistances_.find(&node);
2472 if (iter != loopingSourceDistances_.end()) {
2473 return iter->second;
2476 auto iter2 = sourceDistances_.find(&node);
2478 if (iter2 == sourceDistances_.end()) {
2480 calculateSourceDistances();
2483 return iter2->second;
2486 if (!hasNode(node)) {
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.");
2497 * Gives the lenght of a longest path from the given node to any sink node.
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.
2505 * @param node Node belonging to a path.
2507 * @return length of the longest path where given node belongs to
2509template<typename GraphNode, typename GraphEdge>
2511BoostGraph<GraphNode, GraphEdge>::maxSinkDistance(const GraphNode& node)
2514 if (!hasNode(node)) {
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;
2527 auto iter2 = sinkDistances_.find(&node);
2529 if (iter2 == sinkDistances_.end()) {
2530 calculatePathLengths();
2532 return iter2->second;
2535 if (!hasNode(node)) {
2538 std::cerr << "Node lacks sink distance! " << node.nodeID() << " "
2539 << node.toString() << std::endl;
2540 BoostGraph<GraphNode, GraphEdge>::writeToDotFile("lacking_sinkd.dot");
2542 assert(0 && "sink distance should have been found.");
2547 * Gives the longest path in acyclic graph.
2549 * If the path lenghts are not calculated calculates them.
2550 * If the graph is a cyclic graph, the function may never return.
2552 * @return Longst path in acyclic graph.
2554template<typename GraphNode, typename GraphEdge>
2556BoostGraph<GraphNode, GraphEdge>::height() const {
2558 if (height_ == -1) {
2559 calculatePathLengths();
2566 * Gives weight of a one edge in a graph.
2568 * Derived class should overrider this with real implementation
2569 * which does the actual node weight calculation.
2571 * This base class implementation always returns 1.
2573 * @return The weight of an edge.
2575template <typename GraphNode, typename GraphEdge>
2577BoostGraph<GraphNode, GraphEdge>::edgeWeight(
2578 GraphEdge&,const GraphNode&) const {
2583 * Returns all edges that connect two nodes.
2585 * @param nTail source node
2586 * @param nHead destination node
2587 * @return a set containing all edges from nTail to nHead
2589template <typename GraphNode, typename GraphEdge>
2590typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
2591BoostGraph<GraphNode, GraphEdge>::connectingEdges(
2592 const GraphNode& nTail, const GraphNode& nHead) const {
2594 EdgeSet headIn = inEdges(nHead);
2595 EdgeSet tailOut = outEdges(nTail);
2596 EdgeSet intersection;
2597 SetTools::intersection(headIn, tailOut, intersection);
2598 return intersection;
2601template <typename GraphNode, typename GraphEdge>
2603BoostGraph<GraphNode, GraphEdge>::name() const {
2608 * Finds all paths between nodes and updates the internal path cache.
2610 * This data is used internally to speed up hasPath().
2612template <typename GraphNode, typename GraphEdge>
2614BoostGraph<GraphNode, GraphEdge>::findAllPaths() const {
2616 using namespace boost;
2618 typedef std::map<EdgeDescriptor, int> WeightMap;
2619 WeightMap weightsMap;
2620 associative_property_map<WeightMap> weights(weightsMap);
2622 typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
2623 EdgeIterPair edges = boost::edges(graph_);
2624 for (EdgeIter i = edges.first; i != edges.second; i++) {
2628 const int nodes = nodeCount();
2630 pathCache_ = new PathCache;
2631 for (int i = 0; i < nodes; ++i) {
2632 pathCache_->push_back(std::vector<int>(nodes));
2634 johnson_all_pairs_shortest_paths(graph_, *pathCache_, weight_map(weights));
2637template <typename GraphNode, typename GraphEdge>
2639BoostGraph<GraphNode, GraphEdge>::hasPath(
2640 GraphNode& src, const GraphNode& dest) const {
2642 if (&src == &dest) {
2646 if (pathCache_ != NULL) {
2647 return (*pathCache_)[descriptor(src)][descriptor(dest)] !=
2648 (std::numeric_limits<int>::max)();
2653 int dstSinkDist = -1;
2654 if (height_ != -1) {
2655 dstSinkDist = maxSinkDistance(dest);
2657 while (!queue.empty()) {
2658 GraphNode* current = *queue.begin();
2659 queue.erase(current);
2662 if (height_ != -1) {
2663 sd = maxSinkDistance(*current);
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()) {
2675 NodeDescriptor hd = boost::target(ed, graph_);
2676 Node* const head = graph_[hd];
2678 if (head == &dest) {
2681 if (foundNodes.find(head) == foundNodes.end()) {
2683 foundNodes.insert(head);
2684 // make sure found from the descriptor cache.
2685 nodeDescriptors_[head] = hd;
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.
2698template <typename GraphNode, typename GraphEdge>
2700BoostGraph<GraphNode, GraphEdge>::detectIllegalCycles() const {
2701 for (int i = 0; i < nodeCount(); i++) {
2702 GraphNode* originalNode = &node(i);
2703 NodeSet queuedNodes;
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;
2722 if (!AssocTools::containsKey(foundNodes,&head)) {
2723 foundNodes.insert(&head);
2724 queuedNodes.insert(&head);
2733template <typename GraphNode, typename GraphEdge>
2735BoostGraph<GraphNode, GraphEdge>::PathLengthHelper::operator<(
2736 const BoostGraph<GraphNode, GraphEdge>::PathLengthHelper& other) const {
2737 return sd_ < other.sd_;
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) {}