BoostGraph.icc

Go to the documentation of this file.

/*
    Copyright (c) 2002-2010 Tampere University.
 
    This file is part of TTA-Based Codesign Environment (TCE).
 
    Permission is hereby granted, free of charge, to any person obtaining a
    copy of this software and associated documentation files (the "Software"),
    to deal in the Software without restriction, including without limitation
    the rights to use, copy, modify, merge, publish, distribute, sublicense,
    and/or sell copies of the Software, and to permit persons to whom the
    Software is furnished to do so, subject to the following conditions:
 
    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.
 
    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
    THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.
 */
/**
 * @file BoostGraph.icc
 *
 * Boost-based templated implementation of graph base class.
 * In-line implementation of templated methods.
 *
 * @author Andrea Cilio 2005 (cilio-no.spam-cs.tut.fi)
 * @author Vladimir Guzma 2006 (vladimir.guzma-no.spam-tut.fi)
 * @author Heikki Kultala 2007-2010
 * @author Pekka Jääskeläinen 2009-2010
 * @note rating: red
 */
 
#include <queue>
#include <map>
#include <algorithm>
#include <climits>
#include <boost/version.hpp>
#include <boost/format.hpp>
 
#include "CompilerWarnings.hh"
IGNORE_COMPILER_WARNING("-Wunused-parameter")
IGNORE_CLANG_WARNING("-Wunused-local-typedef")
#include <boost/graph/topological_sort.hpp>
 
#if BOOST_VERSION < 104000
#include <boost/property_map.hpp>
#else
#include <boost/property_map/property_map.hpp>
#endif
 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>
POP_CLANG_DIAGS
POP_COMPILER_DIAGS
 
#include "Conversion.hh"
#include "AssocTools.hh"
#include "Application.hh"
#include "SetTools.hh"
#include "hash_map.hh"
 
/**
 * Constructor
 *
 */
template <typename GraphNode, typename GraphEdge>
BoostGraph<GraphNode, GraphEdge>::BoostGraph(bool allowLoopEdges) :
    height_(-1), parentGraph_(NULL), sgCounter_(0), 
    allowLoopEdges_(allowLoopEdges), pathCache_(NULL) {}
 
/**
 * Constructor
 *
 */
template <typename GraphNode, typename GraphEdge>
BoostGraph<GraphNode, GraphEdge>::BoostGraph(
    const TCEString& name, bool allowLoopEdges) :
    height_(-1), parentGraph_(NULL), name_(name), sgCounter_(0),
    allowLoopEdges_(allowLoopEdges), pathCache_(NULL) {}
 
/**
 * Copy constructor
 *
 */
template <typename GraphNode, typename GraphEdge>
BoostGraph<GraphNode, GraphEdge>::BoostGraph(
    const BoostGraph<GraphNode, GraphEdge>& other, bool allowLoopEdges) :
    GraphBase<GraphNode, GraphEdge>(), height_(other.height_),
    parentGraph_(NULL) , name_(other.name()), sgCounter_(0),
    allowLoopEdges_(allowLoopEdges), pathCache_(NULL) {
 
    // table which node of other
    std::map<GraphNode*, GraphNode*> nodeMap;
 
    for (int i = 0; i < other.nodeCount(); i++) {
        GraphNode& currNode = other.node(i);
        if (nodeMap.find(&currNode) == nodeMap.end()){
            nodeMap[&currNode] =
                dynamic_cast<GraphNode*>(currNode.clone());
            addNode(*nodeMap[&currNode]);
        }
 
        GraphNode* ourTail = nodeMap[&currNode];
 
        // copy all out edges of the node
        EdgeSet outs = other.outEdges(currNode);
        typename EdgeSet::iterator iter;
        for (iter = outs.begin(); iter != outs.end(); iter++) {
            GraphEdge* outEdge = *iter;
            GraphNode& headNode = other.headNode(*outEdge);
 
            if (nodeMap.find(&headNode) == nodeMap.end()){
                nodeMap[&headNode] =
                    dynamic_cast<GraphNode*>(headNode.clone());
                addNode(*nodeMap[&headNode]);
            }
 
            GraphNode* ourHead = nodeMap[&headNode];
            GraphEdge* ourEdge = dynamic_cast<GraphEdge*>(outEdge->clone());
 
            connectNodes(*ourTail, *ourHead, *ourEdge);
        }
    }
}
 
/**
 * Destructor
 *
 * This automatically deletes all edges that have been in the graph.
 * Those should not be deleted by destructors of deleted graphs.
 */
template <typename GraphNode, typename GraphEdge>
BoostGraph<GraphNode, GraphEdge>::~BoostGraph() {
    if (parentGraph_ != NULL) {
        parentGraph_->detachSubgraph(*this);
    }
    for (typename std::set<GraphEdge*>::iterator i = ownedEdges_.begin();
         i != ownedEdges_.end(); i++) {
        delete *i;
    }
    delete pathCache_;
    pathCache_ = NULL;
}
 
/**
 * Adds a node to the graph.
 *
 * Once added, a node is owned and managed by the graph.
 *
 * Adding a node does not add it to the subgraphs of a graph,
 * but does add into the parent graph.
 *
 * @param node Node to be added.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::addNode(GraphNode& node) {
    NodeDescriptor nd = boost::add_vertex(&node, graph_);
    nodeDescriptors_[&node] = nd;
 
    if (height_ != -1) {
        sourceDistances_[&node] = 0;
        sinkDistances_[&node] = 0;
 
        loopingSourceDistances_[&node] = 0;
        loopingSinkDistances_[&node] = 0;
    }
 
    // add node also to parent graph
    if (parentGraph_ != NULL) {
        parentGraph_->addNode(node);
    }
}
 
/**
 * Returns the number of nodes contained in this graph.
 *
 * @returns The number of nodes.
 */
template <typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::nodeCount() const {
    return boost::num_vertices(graph_);
}
 
/**
 * Returns the number of edges contained in this graph.
 *
 * @returns The number of edges.
 */
template <typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::edgeCount() const {
    return boost::num_edges(graph_);
}
 
/**
 * Returns the node of the graph identified by the given index.
 *
 * Notice that the index is not constant. If nodes are added or removed from
 * the graph, the index of an untouched node may change.
 *
 * @param index Index of a node of the graph.
 * @returns The node currently identified by the given index.
 * @exception OutOfRange If the given index is negative, or is not smaller
 *     than the number of nodes of the graph.
 */
template <typename GraphNode, typename GraphEdge>
GraphNode&
BoostGraph<GraphNode, GraphEdge>::node(const int index) const {
    return node(index, true);
}
 
/**
 * Returns the node of the graph identified by the given index.
 *
 * Notice that the index is not constant. If nodes are added or removed from
 * the graph, the index of an untouched node may change.
 *
 * @param index Index of a node of the graph.
 * @returns The node currently identified by the given index.
 * @exception OutOfRange If the given index is negative, or is not smaller
 *     than the number of nodes of the graph.
 */
template <typename GraphNode, typename GraphEdge>
GraphNode&
BoostGraph<GraphNode, GraphEdge>::node(
    const int index, bool cacheResult) const {
    if (index < 0 || index >=  nodeCount()) {
        TCEString procName("BoostGraph::node");
        boost::format errorMsg("Node index %1% out of range [0, %2%).");
        errorMsg % index % nodeCount();
        throw OutOfRange(__FILE__, __LINE__, procName, errorMsg.str());
    }
    NodeDescriptor nd = boost::vertex(index, graph_);
    Node* n = graph_[nd];
    if (cacheResult) {
        nodeDescriptors_[n] = nd;
    }
    return *n;
}
 
/**
 * Returns the edge of the graph identified by the given index.
 *
 * Notice that the index is not constant. If edges are added or removed from
 * the graph, the index of an untouched edge may change.
 *
 * Running time of this function is O(n) where n is the number of edges.
 *
 * @param index Index of an edge of the graph.
 * @returns The edge currently identified by the given index.
 * @exception OutOfRange If the given index is negative, or is not smaller
 *     than the number of edges of the graph.
 */
template <typename GraphNode, typename GraphEdge>
GraphEdge&
BoostGraph<GraphNode, GraphEdge>::edge(const int index) const {
    if (index < 0 || index >=  edgeCount()) {
        TCEString procName("BoostGraph::edge");
        boost::format errorMsg("Edge index %1% out of range [0, %2%).");
        errorMsg % index % edgeCount();
        throw OutOfRange(__FILE__, __LINE__, procName, errorMsg.str());
    }
 
    typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::edges(graph_);
    int counter = 0;
    for (EdgeIter i = edges.first; i != edges.second; i++) {
        if (counter == index) {
            GraphEdge* theEdge = graph_[*i];
            return *theEdge;
        }
        counter++;
    }
    assert(false);
    // keep pedantic compilers quiet
    return *graph_[*edges.second];
}
 
/**
 * Returns the n:th outgoing edge from a given node.
 *
 * Warning: this function is slow. When iterating over all outgoing edges
 * of a node, use outEdges instead.
 *
 * @param node Node whose outgoing edges we are searching
 * @param index index of outgoing edge being asked
 * @return The edge.
 */
template <typename GraphNode, typename GraphEdge>
GraphEdge&
BoostGraph<GraphNode, GraphEdge>::outEdge(
    const GraphNode& node, const int index) const {
    const TCEString procName("BoostGraph::outEdge");
 
    if (outDegree(node) <= index) {
        boost::format errorMsg(
            "Outgoing edge at index %1% is out of range. The node "
            "out-degree is %2%.");
        errorMsg % index % outDegree(node);
        throw OutOfRange(__FILE__, __LINE__, procName, errorMsg.str());
    }
 
    std::pair<OutEdgeIter, OutEdgeIter> edges =
        boost::out_edges(descriptor(node), graph_);
    if (edges.first == edges.second) {
        TCEString errorMsg("Node does not belong to this graph.");
        throw InstanceNotFound(__FILE__, __LINE__, procName, errorMsg);
    }
 
    GraphEdge* result = NULL;
    int n = 0;
    for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
        if (n == index) {
            result = graph_[(*ei)];
            break;
        } else {
            n++;
        }
    }
    assert(result != NULL);
 
    return *result;
}
 
/**
 * Returns the n:th incoming edge to a given node.
 *
 * Warning: this function is slow. When iterating over all incoming edges
 * of a node, use inEdges instead.
 *
 * @param node Node whose incoming edges we are searching
 * @param index index of incoming edge being asked
 * @return The edge.
 */
template <typename GraphNode, typename GraphEdge>
GraphEdge&
BoostGraph<GraphNode, GraphEdge>::inEdge(
    const GraphNode& node, const int index) const {
    std::pair<InEdgeIter, InEdgeIter> edges =
        boost::in_edges(descriptor(node), graph_);
    if (edges.first == edges.second) {
        const TCEString procName("BoostGraph::inEdge");
        TCEString errorMsg("Node does not belong to this graph.");
        throw InstanceNotFound(__FILE__, __LINE__, __func__, errorMsg);
    }
 
    GraphEdge* result = NULL;
    int n = 0;
    for (InEdgeIter ei = edges.first; ei != edges.second; ei++) {
        if (n == index) {
            result = graph_[(*ei)];
            break;
        } else {
            n++;
        }
    }
    if (result == NULL) {
        boost::format errorMsg(
            "Incoming edge at index %1% is out of range. The node "
            "in-degree is %2%.");
        errorMsg % index % inDegree(node);
        throw OutOfRange(__FILE__, __LINE__, __func__, errorMsg.str());
    }
 
    return *result;
}
 
/**
 * Returns the outgoing edges of a node.
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 */
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
BoostGraph<GraphNode, GraphEdge>::outEdges(const GraphNode& node) const {
    typedef typename GraphTraits::out_edge_iterator outEdgeIter;
    std::pair<outEdgeIter, outEdgeIter> edges = boost::out_edges(
        descriptor(node), graph_);
    EdgeSet result;
    for (outEdgeIter ei = edges.first; ei != edges.second; ei++) {
        GraphEdge* edge = graph_[(*ei)];
        // add to descriptor cache.
        edgeDescriptors_[edge] = *ei;
        result.insert(edge);
    }
    return result;
}
 
/**
 * Returns the outgoing edges of a node in the root graph of the
 * subgraph tree.
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 */
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
BoostGraph<GraphNode, GraphEdge>::rootGraphOutEdges(
    const GraphNode& node) const {
    if (parentGraph_ == NULL) {
        return outEdges(node);
    } else {
        return parentGraph_->rootGraphOutEdges(node);
    }
}
 
/**
 * Returns the ingoing edges of a node.
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 */
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
BoostGraph<GraphNode, GraphEdge>::inEdges(const GraphNode& node) const {
    typedef typename GraphTraits::in_edge_iterator InEdgeIter;
    std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
        descriptor(node), graph_);
    EdgeSet result;
    for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
        GraphEdge* edge = graph_[(*ei)];
        edgeDescriptors_[edge] = *ei;
        result.insert(edge);
    }
    return result;
}
 
/**
 * Returns the ingoing edges of a node in the root graph of the subgraph tree.
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 */
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
BoostGraph<GraphNode, GraphEdge>::rootGraphInEdges(
    const GraphNode& node) const {
    if (parentGraph_ == NULL) {
        return inEdges(node);
    } else {
        return parentGraph_->rootGraphInEdges(node);
    }
}
 
/**
 * Returns the ingoing edge of a node in the root graph of the subgraph tree.
 *
 * @param node A node of the graph.
 * @param index index of edge.
 * @return the edge edges.
 */
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::Edge&
BoostGraph<GraphNode, GraphEdge>::rootGraphInEdge(
    const GraphNode& node, const int index) const {
    if (parentGraph_ == NULL) {
        return inEdge(node, index);
    } else {
        return parentGraph_->rootGraphInEdge(node, index);
    }
}
 
/**
 * Returns the outgoing edge of a node in the root graph of the subgraph tree.
 *
 * @param node A node of the graph.
 * @param index index of edge.
 * @return the edge.
 */
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::Edge&
BoostGraph<GraphNode, GraphEdge>::rootGraphOutEdge(
    const GraphNode& node, const int index) const {
    if (parentGraph_ == NULL) {
        return outEdge(node, index);
    } else {
        return parentGraph_->rootGraphOutEdge(node, index);
    }
}
 
/**
 * Returns the output degree of a node, that is, the number of outgoing edges
 * of a node.
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 * @exception InstanceNotFound if the node does not belong to this graph.
 */
template <typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::outDegree(const GraphNode& node) const {
    return boost::out_degree(descriptor(node), graph_);
}
 
/**
 * Returns the input degree of a node, that is, the number of incoming edges
 * of a node.
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 * @exception InstanceNotFound if the node does not belong to this graph.
 */
template <typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::inDegree(const GraphNode& node) const {
    return boost::in_degree(descriptor(node), graph_);
}
 
/**
 * Returns the output degree of a node, that is, the number of outgoing edges
 * of a node in the root graph of the subgraph tree
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 * @exception InstanceNotFound if the node does not belong to this graph.
 */
template <typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::rootGraphOutDegree(
    const GraphNode& node) const {
    return parentGraph_ == NULL ?
        boost::out_degree(descriptor(node), graph_) :
        parentGraph_->rootGraphOutDegree(node);
}
 
/**
 * Returns the input degree of a node, that is, the number of incoming edges
 * of a node in the root graph of the subgraph tree
 *
 * @param node A node of the graph.
 * @returns A set of edges.
 * @exception InstanceNotFound if the node does not belong to this graph.
 */
template <typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::rootGraphInDegree(
    const GraphNode& node) const {
    return parentGraph_ == NULL ?
        boost::in_degree(descriptor(node), graph_) :
        parentGraph_->rootGraphInDegree(node);
}
 
/**
 * Returns the tail node of a edge.
 *
 * Warning: this function is slow, O(n) to number of edges in the graph.
 *
 * @param edge Edge whose tail node we are asking
 * @return The tail node of the given edge
 */
template <typename GraphNode, typename GraphEdge>
GraphNode&
BoostGraph<GraphNode, GraphEdge>::tailNode(const GraphEdge& edge) const {
    EdgeDescriptor ed = descriptor(edge);
    NodeDescriptor nd = boost::source(ed, graph_);
    GraphNode* nn = graph_[nd];
    nodeDescriptors_[nn] = nd;
    return *nn;
}
 
/**
 * Returns the tail node of a edge.
 *
 * This is faster but uglier version of the function.
 *
 * @param edge Edge whose tail node we are asking
 * @return The tail node of the given edge
 */
template <typename GraphNode, typename GraphEdge>
GraphNode&
BoostGraph<GraphNode, GraphEdge>::tailNode(
    const GraphEdge& edge, const NodeDescriptor& headNode) const {
    EdgeDescriptor ed = edgeDescriptor(edge, headNode);
    NodeDescriptor nd = boost::source(ed, graph_);
    GraphNode* nn = graph_[nd];
    nodeDescriptors_[nn] = nd;
    return *nn;
}
 
/**
 * Returns the head node of a edge.
 *
 * Warning: this function is slow, O(n) to number of edges in the graph.
 *
 * @param edge Edge whose head node we are asking
 * @return The head node of the given edge
 */
template <typename GraphNode, typename GraphEdge>
GraphNode&
BoostGraph<GraphNode, GraphEdge>::headNode(const GraphEdge& edge) const {
    EdgeDescriptor ed = descriptor(edge);
    NodeDescriptor nd = boost::target(ed, graph_);
    GraphNode* node = graph_[nd];
    nodeDescriptors_[node] = nd;
    return *node;
}
 
/**
 * Returns the head node of a edge.
 *
 * This is faster but uglier version of the function.
 *
 * @param edge Edge whose head node we are asking
 * @return The head node of the given edge
 */
template <typename GraphNode, typename GraphEdge>
GraphNode&
BoostGraph<GraphNode, GraphEdge>::headNode(
    const GraphEdge& edge, const NodeDescriptor& tailNode) const {
    EdgeDescriptor ed = edgeDescriptor(tailNode,edge);
    NodeDescriptor nd = boost::target(ed, graph_);
    GraphNode* node = graph_[nd];
    nodeDescriptors_[node] = nd;
    return *node;
}
 
/**
 * Connects two nodes and attaches the given properties to the new graph
 * edge connecting the nodes.
 *
 * Once registered into a graph connection, the edge properties are owned
 * and managed by the graph. This method can be invoked repeatedly on the
 * same pair of nodes; each time it will create a new (parallel) edge.
 *
 * @param nTail Tail node of the connection.
 * @param nHead Head node of the connection.
 * @param e Properties of the connecting edge.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::connectNodes(
    const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e) {
    connectNodes(nTail, nHead, e, NULL);
}
 
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::calculatePathLengthsOnConnect(
    const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e) {
 
    if (height_ == -1) {
        return;
    }
    int eWeight = edgeWeight(e, nHead);
    auto loopingHeadIter = loopingSinkDistances_.find(&nHead);
    auto loopingTailIter = loopingSourceDistances_.find(&nTail);
    auto headIter = sinkDistances_.find(&nHead);
    auto tailIter = sourceDistances_.find(&nTail);
 
    if (loopingHeadIter != loopingSinkDistances_.end() &&
        !e.isBackEdge()) {
        calculateSinkDistance(
            nTail, loopingHeadIter->second + eWeight, true);
    }
 
    if (headIter == sinkDistances_.end()) {
        sinkDistances_[&nHead] = 0;
        calculateSinkDistance(nTail, eWeight, e.isBackEdge());
    } else {
        calculateSinkDistance(
            nTail, headIter->second + eWeight, e.isBackEdge());
    }
 
    if (loopingTailIter != loopingSourceDistances_.end() &&
        !e.isBackEdge()) {
        calculateSourceDistances(
            &nHead, loopingTailIter->second + eWeight, true);
    }
 
    if (tailIter == sourceDistances_.end()) {
        sourceDistances_[&nTail] = 0;
        calculateSourceDistances(&nHead, eWeight, e.isBackEdge());
    } else {
        calculateSourceDistances(
                    &nHead, tailIter->second + eWeight, e.isBackEdge());
    }
}
 
/**
 * Connects two nodes and attaches the given properties to the new graph
 * edge connecting the nodes.
 *
 * Once registered into a graph connection, the edge properties are owned
 * and managed by the graph. This method can be invoked repeatedly on the
 * same pair of nodes; each time it will create a new (parallel) edge.
 *
 * @param nTail Tail node of the connection.
 * @param nHead Head node of the connection.
 * @param e Properties of the connecting edge.
 * @param modifier sub-or parent Graph which caused this procedure to be called
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::connectNodes(
    const GraphNode& nTail, const GraphNode& nHead, GraphEdge& e,
    GraphBase<GraphNode, GraphEdge>* modifier, bool creatingSG) {
    // not add if invalid params
    if (!hasNode(nTail) || !hasNode(nHead)) {
        // for sub graphs silently skip it
        if (parentGraph_ != NULL) {
            return;
        } else {
            assert(hasNode(nTail)
                && "Trying to connect tail node not on the graph");
            assert(hasNode(nHead)
                && "Trying to connect head node not on the graph");
        }
    }
 
    if (hasEdge(nTail, nHead, e)) {
        TCEString procName("BoostGraph::addEdge");
        TCEString errorMsg("Edge already belongs to this graph.");
        throw ObjectAlreadyExists(__FILE__, __LINE__, procName, errorMsg);
    }
 
    if (parentGraph_ == NULL && !creatingSG) {
        ownedEdges_.insert(&e);
    }
 
    if (allowLoopEdges_ || !e.isBackEdge()) {
        NodeDescriptor td = descriptor(nTail);
        NodeDescriptor hd = descriptor(nHead);
        if (!e.isBackEdge() && td == hd && creatingSG) {
            std::cerr << "node: " << nTail.toString() << " edge: " << e.toString() << std::endl;
            assert(0 && "non-loop-edge going from node to itsefl!");
        }
        edgeDescriptors_[&e] =
            boost::add_edge(td, hd, &e, graph_).
            first;
 
        // If we have calculated path lenght data, keep it in sync.
        if (height_ != -1) {
            calculatePathLengthsOnConnect(nTail, nHead, e);
        }
    }
 
    if (parentGraph_ != NULL && parentGraph_ != modifier) {
        parentGraph_->connectNodes(nTail, nHead, e, this);
    }
 
    for (unsigned int i = 0; i < childGraphs_.size(); i++) {
        if ( childGraphs_[i] != modifier ) {
            childGraphs_[i]->connectNodes(nTail, nHead, e, this);
        }
    }
}
 
template<typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::sinkDistDecreased(
const GraphNode& n) const {
 
    if (height_ == -1) {
        return;
    }
 
    auto lsdIter = loopingSinkDistances_.find(&n);
    int oldSD = sinkDistances_[&n];
    int oldLSD = lsdIter != loopingSinkDistances_.end() ?
        lsdIter->second : 0;
    int sd = 0;
    int loopingSD = 0;
    int nd = descriptor(n);
    auto edges = boost::out_edges(nd, graph_);
    for (auto j = edges.first; j != edges.second; j++) {
        EdgeDescriptor ed = *j;
        NodeDescriptor hd = boost::target(ed, graph_);
        GraphNode* head = graph_[hd];
        GraphEdge* edge = graph_[ed];
        int eWeight = edgeWeight(*edge, *head);
        int headSD = sinkDistances_[head] + eWeight;
        if (edge->isBackEdge()) {
            loopingSD = std::max(loopingSD, headSD);
        } else {
            sd = std::max(sd, headSD);
            auto headLSDIter = loopingSinkDistances_.find(head);
            if (headLSDIter != loopingSinkDistances_.end()) {
                loopingSD = std::max(
                    loopingSD, headLSDIter->second + eWeight);
            }
        }
    }
    if (sd < oldSD || loopingSD < oldLSD) {
        sinkDistances_[&n] = sd;
        if (loopingSD < oldLSD) {
            loopingSinkDistances_[&n] = loopingSD;
        }
 
        // propagate to predecessors
        auto edges = boost::in_edges(nd, graph_);
        for (auto j = edges.first; j != edges.second; j++) {
            EdgeDescriptor ed = *j;
            GraphEdge* edge = graph_[ed];
            if (!edge->isBackEdge() || sd < oldSD) {
                NodeDescriptor td = boost::source(ed, graph_);
                GraphNode* tail = graph_[td];
                sinkDistDecreased(*tail);
            }
        }
    }
}
 
template<typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::sourceDistDecreased(
    const GraphNode& n) const {
 
    if (height_ == -1) {
        return;
    }
 
    auto lsdIter = loopingSourceDistances_.find(&n);
    int oldSD = sourceDistances_[&n];
    int oldLSD = lsdIter != loopingSourceDistances_.end() ?
        lsdIter->second : 0;
 
    int sd = 0;
    int loopingSD = 0;
    int nd = descriptor(n);
    auto edges = boost::in_edges(nd, graph_);
    for (auto j = edges.first; j != edges.second; j++) {
        EdgeDescriptor ed = *j;
        NodeDescriptor td = boost::source(ed, graph_);
        GraphNode* tail = graph_[td];
        GraphEdge* edge = graph_[ed];
        int eWeight = edgeWeight(*edge, n);
        int tailSD = sourceDistances_[tail] + eWeight;
        if (edge->isBackEdge()) {
            loopingSD = std::max(loopingSD, tailSD);
        } else {
            sd = std::max(sd, tailSD);
            auto tailLSDIter = loopingSourceDistances_.find(tail);
            if (tailLSDIter != loopingSourceDistances_.end()) {
                loopingSD = std::max(
                    loopingSD, tailLSDIter->second + eWeight);
            }
        }
    }
 
    if (sd < oldSD || loopingSD < oldLSD) {
        sourceDistances_[&n] = sd;
        if (loopingSD < oldLSD) {
            loopingSourceDistances_[&n] = loopingSD;
        }
 
        // propagate to successors
        auto edges = boost::out_edges(nd, graph_);
        for (auto j = edges.first; j != edges.second; j++) {
            EdgeDescriptor ed = *j;
            GraphEdge* edge = graph_[ed];
            if (!edge->isBackEdge() || sd < oldSD) {
                NodeDescriptor hd = boost::target(ed, graph_);
                GraphNode* head = graph_[hd];
                sourceDistDecreased(*head);
            }
        }
    }
}
 
/**
 * Disconnects two nodes.
 *
 * All edges between the given nodes are deleted. It is not an error to
 * invoke this method on a pair of nodes that are not connected.
 *
 * @param nTail Tail node of the connection.
 * @param nHead Head node of the connection.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::disconnectNodes(
    const GraphNode& nTail,
    const GraphNode& nHead) {
 
    int maxW = 0;
    int maxwLoop = 0;
    while (hasEdge(nTail, nHead)) {
        EdgeDescriptor ed = connectingEdge(nTail, nHead);
        GraphEdge* e = graph_[ed];
        if (height_ != -1) {
            int eWeight = edgeWeight(*e, nHead);
            if (e->isBackEdge()) {
                maxwLoop = std::max(eWeight, maxW);
            } else {
                maxW = std::max(eWeight, maxW);
            }
        }
        removeEdge(*e, &nTail, &nHead);
    }
 
    if (height_ != -1) {
        bool recalc = false;
        if (sourceDistances_[&nTail] + maxW ==
            sourceDistances_[&nHead] ||
            (!loopingSourceDistances_.empty() &&
             (loopingSourceDistances_[&nTail] + maxW ==
              loopingSourceDistances_[&nHead] ||
              sourceDistances_[&nTail] + maxwLoop ==
              loopingSourceDistances_[&nHead]))) {
            recalc = true;
            sourceDistDecreased(nTail);
        }
 
        if (!sinkDistances_.empty() &&
            (sinkDistances_[&nHead] + maxW ==
             sinkDistances_[&nTail] ||
             (!loopingSinkDistances_.empty() &&
              (loopingSinkDistances_[&nHead] + maxW ==
               loopingSinkDistances_[&nTail] ||
               sinkDistances_[&nHead] +maxwLoop ==
               loopingSinkDistances_[&nTail])))) {
            recalc = true;
            sinkDistDecreased(nHead);
        }
 
        if (recalc) {
            delete pathCache_;
            pathCache_ = NULL;
        }
    }
}
 
/**
 * Moves all incoming edges from a node to another node.
 *
 * This reuses the origial Edge objects, thus should retain the original
 * properties (even if defined in a derived class).
 *
 * @param source The node to move the incoming edges from.
 * @param destination The node to move the incoming edges to.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::moveInEdges(
    const GraphNode& source, const GraphNode& destination) {
    moveInEdges(source, destination, NULL);
}
 
/**
 * Moves all incoming edges from a node to another node.
 *
 * This reuses the origial Edge objects, thus should retain the original
 * properties (even if defined in a derived class).
 *
 * @param source The node to move the incoming edges from.
 * @param destination The node to move the incoming edges to.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::moveInEdges(
    const GraphNode& source, const GraphNode& destination,
    BoostGraph* modifierGraph) {
    if (!hasNode(source)) {
        if (hasNode(destination)) {
            TCEString msg = "Illegal Graph update: "
                "copying edges from outside of the graph";
            throw NotAvailable(__FILE__,__LINE__,__func__, msg);
        } else {
            return; // no need to do anything
        }
 
    } else {
        EdgeSet edges = inEdges(source);
        for (typename EdgeSet::iterator i = edges.begin();
             i != edges.end(); ++i) {
            Edge& e = **i;
            const GraphNode& tail = tailNode(e);
            const GraphNode& head = destination;
            boost::remove_edge(descriptor(e), graph_);
 
            typename EdgeDescMap::iterator
                edIter = edgeDescriptors_.find(&e);
            if (edIter != edgeDescriptors_.end()) {
                edgeDescriptors_.erase(edIter);
            }
 
            sourceDistDecreased(source);
            sinkDistDecreased(tail);
 
            // if dest not in this graph, just remove
            if (hasNode(destination)) {
                std::pair<EdgeDescriptor,bool> tmpPair =
                    boost::add_edge(
                        descriptor(tail), descriptor(head), &e, graph_);
                edgeDescriptors_[&e] = tmpPair.first;
 
                if (height_ != -1) {
                    calculatePathLengthsOnConnect(tail, head, e);
                }
 
            }
        }
 
        // update parent- and childgraphs
        if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
            parentGraph_->moveInEdges(
                source, destination, this);
        }
 
        for (unsigned int i = 0; i < childGraphs_.size(); i++) {
            if (childGraphs_.at(i) != modifierGraph ) {
                childGraphs_.at(i)->moveInEdges(
                    source, destination, this);
            }
        }
    }
}
 
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::copyInEdge(
    const GraphNode& destination,
    GraphEdge& edge,
    const GraphNode* tail) {
        // start from the root tree.
    BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
    if (tail == NULL) {
        tail = &rg->tailNode(edge);
    }
    Edge* newEdge = new Edge(edge);
    rg->connectNodes(*tail, destination, *newEdge);
}
 
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::copyOutEdge(
//    const GraphNode& source,
    const GraphNode& destination,
    GraphEdge& edge,
    const GraphNode* head) {
        // start from the root tree.
    BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
    if (head == NULL) {
        head = &rg->headNode(edge);
    }
    Edge* newEdge = new Edge(edge);
    rg->connectNodes(destination, *head, *newEdge);
}
 
/**
 * Moves an edge which comes into source node to point into another node.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::moveInEdge(
    const GraphNode& originalHeadNode,
    const GraphNode& newHeadNode,
    GraphEdge& edge,
    const GraphNode* tail,
    bool childs) {
 
    // start from the root tree.
    if (!childs) {
        BoostGraph<GraphNode,GraphEdge>* rg = rootGraph();
        if (tail == NULL) {
            tail = &rg->tailNode(edge);
        }
        rg->moveInEdge(originalHeadNode, newHeadNode, edge, tail, true);
        return;
    }
 
    if (hasNode(*tail) && hasEdge(edge)) {
        bool hasSource = hasNode(originalHeadNode);
        bool hasDestination = hasNode(newHeadNode);
        const GraphNode& head = newHeadNode;
 
        if (hasSource) {
            boost::remove_edge(descriptor(edge), graph_);
 
            sourceDistDecreased(originalHeadNode);
            sinkDistDecreased(*tail);
        }
 
        if (hasDestination) {
            std::pair<EdgeDescriptor,bool> tmpPair =
                boost::add_edge(
                    descriptor(*tail), descriptor(head), &edge, graph_);
            edgeDescriptors_[&edge] = tmpPair.first;
 
            if (height_ != -1) {
                calculatePathLengthsOnConnect(*tail, head, edge);
            }
 
        }
        // need to process child graphs?
        if (hasSource | hasDestination) {
            for (unsigned int i = 0; i < childGraphs_.size(); i++) {
                childGraphs_.at(i)->moveInEdge(
                    originalHeadNode, newHeadNode, edge, tail, true);
            }
        }
    }
}
 
/*
 * Moves edge which originally points
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::moveOutEdge(
    const GraphNode& originalTailNode,
    const GraphNode& newTailNode,
    GraphEdge& edge,
    const GraphNode* head,
    bool childs) {
 
    if (!childs) {
        BoostGraph* rg = rootGraph();
        if (head == NULL) {
            head = &rg->headNode(edge);
        }
        rg->moveOutEdge(originalTailNode, newTailNode, edge, head, true);
        return;
    }
 
    if (hasNode(*head) && hasEdge(edge)) {
        bool hasSource = hasNode(originalTailNode);
        bool hasDestination = hasNode(newTailNode);
 
        const GraphNode& tail = newTailNode;
        if (hasSource) {
            boost::remove_edge(descriptor(edge), graph_);
 
            sourceDistDecreased(*head);
            sinkDistDecreased(originalTailNode);
 
        }
 
        if (hasDestination) {
            std::pair<EdgeDescriptor,bool> tmpPair =
                boost::add_edge(
                    descriptor(tail), descriptor(*head), &edge, graph_);
            edgeDescriptors_[&edge] = tmpPair.first;
 
            if (height_ != -1) {
                calculatePathLengthsOnConnect(tail, *head, edge);
            }
 
        }
 
        // need to process child graphs?
        if (hasSource | hasDestination) {
            for (unsigned int i = 0; i < childGraphs_.size(); i++) {
                childGraphs_.at(i)->moveOutEdge(
                    originalTailNode, newTailNode, edge, head, true);
            }
        }
    }
}
 
/**
 * Moves all outgoing edges from a node to another node.
 *
 * This reuses the origial Edge objects, thus should retain the original
 * properties (even if defined in a derived class).
 *
 * @param source The node to move the outgoing edges from.
 * @param destination The node to move the outgoing edges to.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::moveOutEdges(
    const GraphNode& source, const GraphNode& destination) {
    moveOutEdges(source, destination, this);
}
 
/**
 * Moves all outgoing edges from a node to another node.
 *
 * This reuses the origial Edge objects, thus should retain the original
 * properties (even if defined in a derived class).
 *
 * @param source The node to move the outgoing edges from.
 * @param destination The node to move the outgoing edges to.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::moveOutEdges(
    const GraphNode& source, const GraphNode& destination,
    BoostGraph* modifierGraph) {
    if (!hasNode(source)) {
        if (hasNode(destination)) {
            TCEString msg = "Illegal Graph update: "
                "copying edges from outside of the graph";
            throw NotAvailable(__FILE__,__LINE__,__func__, msg);
        } else {
            return; // no need to do anything
        }
 
    } else {
        EdgeSet edges = outEdges(source);
        for (typename EdgeSet::iterator i = edges.begin();
             i != edges.end(); ++i) {
            Edge& e = **i;
            const GraphNode& tail = destination;
            const GraphNode& head = headNode(e);
            boost::remove_edge(descriptor(e), graph_);
 
            sourceDistDecreased(head);
            sinkDistDecreased(source);
 
            typename EdgeDescMap::iterator
                edIter = edgeDescriptors_.find(&e);
            if (edIter != edgeDescriptors_.end()) {
                edgeDescriptors_.erase(edIter);
            }
 
            if (hasNode(destination)) {
                std::pair<EdgeDescriptor,bool> tmpPair =
                boost::add_edge(
                    descriptor(tail), descriptor(head), &e, graph_);
                edgeDescriptors_[&e] = tmpPair.first;
 
                if (height_ != -1) {
                    calculatePathLengthsOnConnect(tail, head, e);
                }
 
            }
        }
 
 
        // update parent- and childgraphs
        if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
            parentGraph_->moveOutEdges(source, destination, this);
        }
 
        for (unsigned int i = 0; i < childGraphs_.size(); i++) {
            if (childGraphs_.at(i) != modifierGraph ) {
                childGraphs_.at(i)->moveOutEdges(source, destination, this);
            }
        }
 
    }
}
 
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::clearDescriptorCache(EdgeSet edges) {
    for (typename EdgeSet::iterator i = edges.begin();
         i != edges.end(); ++i) {
        typename EdgeDescMap::iterator iedi = edgeDescriptors_.find(*i);
        if (iedi != edgeDescriptors_.end()) {
            edgeDescriptors_.erase(iedi);
        }
    }
}
 
/**
 * Removes a node of the graph, without deleting the associated properties.
 *
 * The connection between the given nodes and other nodes are removed from
 * the graph. The property object is not managed by the graph anymore.
 *
 * @param node Properties of the node to be removed.
 * @exception InstanceNotFound If the node propertes are not registered to a
 *     node of the graph.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::removeNode(
    GraphNode& nodeToRemove, BoostGraph* modifierGraph) {
    if (hasNode(nodeToRemove)) {
 
        replaceNodeWithLastNode(nodeToRemove);
 
        if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
            parentGraph_->removeNode(nodeToRemove, this);
        }
 
        for (unsigned int i = 0; i < childGraphs_.size(); i++) {
            if (childGraphs_.at(i) != modifierGraph ) {
                childGraphs_.at(i)->removeNode(nodeToRemove, this);
            }
        }
    } else {
        if (parentGraph_ == NULL) {
            TCEString msg = "Node not found in graph, cannot remove";
            throw InstanceNotFound(__FILE__,__LINE__,__func__, msg);
        }
    }
}
 
/**
 * Removes a node of the graph, without deleting the associated properties.
 *
 * The connection between the given nodes and other nodes are removed from
 * the graph. The property object is not managed by the graph anymore.
 *
 * @param node Properties of the node to be removed.
 * @exception InstanceNotFound If the node propertes are not registered to a
 *     node of the graph.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::removeNode(GraphNode& node) {
    removeNode(node, NULL);
}
 
/**
 * Removes a node of the subgraph, leaving it to the parent graph.
 *
 * Drops node also from all child graphs.
 *
 * @param node Properties of the node to be removed.
 * @exception InstanceNotFound If the node propertes are not registered to a
 *     node of the graph.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::dropNode(GraphNode& nodeToDrop) {
    if (!hasNode(nodeToDrop)) {
        return;
    }
 
    replaceNodeWithLastNode(nodeToDrop);
 
    for (unsigned int i = 0; i < childGraphs_.size(); i++) {
        childGraphs_.at(i)->dropNode(nodeToDrop);
    }
}
 
/**
 * Replaces a node with properties of the last node and then removes the
 * last node from the graph. This is semantically equal to removing
 * a node from the graph but runs much faster.
 * Does not remove anything from subgraphs.
 *
 * @param dest node to be removed/replaced with last one.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::replaceNodeWithLastNode(GraphNode& dest) {
 
    NodeDescriptor nd = descriptor(dest);
    typename BoostGraph<GraphNode, GraphEdge>::NodeSet preds;
    typename BoostGraph<GraphNode, GraphEdge>::NodeSet succs;
 
    succs = successors(dest);
    preds = predecessors(dest);
 
    // remove edge cache
    clearDescriptorCache(inEdges(dest));
    clearDescriptorCache(outEdges(dest));
 
    // clear all edges. from to node to remove/drop.
    boost::clear_vertex(nd, graph_);
 
    // Move last node to place of deleted node, then delete last node.
    GraphNode& lastNode = node(nodeCount()-1);
 
    NodeDescriptor lnd = descriptor(lastNode);
    if (&dest != &lastNode) {
        // move in edges from last node to place of deleted node.
        EdgeSet iEdges = inEdges(lastNode);
        for (typename EdgeSet::iterator i = iEdges.begin();
             i != iEdges.end(); ++i) {
            Edge& e = **i;
            const GraphNode& tail = tailNode(e);
            // remove the edge pointing to old place of last node
            boost::remove_edge(descriptor(e), graph_);
 
            // clear descriptor cache for that edge
            typename EdgeDescMap::iterator
                edIter = edgeDescriptors_.find(&e);
            if (edIter != edgeDescriptors_.end()) {
                edgeDescriptors_.erase(edIter);
            }
 
            // add the edge back, pointing to the new place
            // of the last node.
            std::pair<EdgeDescriptor,bool> tmpPair =
                boost::add_edge(
                    descriptor(tail), nd, &e, graph_);
            edgeDescriptors_[&e] = tmpPair.first;
        }
 
        // move out edges. from last node to place of deleted node.
        EdgeSet oEdges = outEdges(lastNode);
        for (typename EdgeSet::iterator i = oEdges.begin();
             i != oEdges.end(); ++i) {
            Edge& e = **i;
            const GraphNode& head = headNode(e);
            // remove the edge pointing to old place of last node
            boost::remove_edge(descriptor(e), graph_);
 
            // clear descriptor cache for that edge
            typename EdgeDescMap::iterator
                edIter = edgeDescriptors_.find(&e);
            if (edIter != edgeDescriptors_.end()) {
                edgeDescriptors_.erase(edIter);
            }
 
            // add the edge back, originating from the new place
            // of the last node.
            std::pair<EdgeDescriptor,bool> tmpPair =
                boost::add_edge(
                    nd, descriptor(head), &e, graph_);
            edgeDescriptors_[&e] = tmpPair.first;
        }
 
        // then move the Node class.
        graph_[nd] = &lastNode;
 
        // update descriptor map.
        nodeDescriptors_[&lastNode] = nd;
    }
 
    if (height_ != -1) {
        sinkDistances_.erase(&dest);
        sourceDistances_.erase(&dest);
        loopingSinkDistances_.erase(&dest);
        loopingSourceDistances_.erase(&dest);
    }
 
    for (auto n: succs) sourceDistDecreased(*n);
    for (auto n: preds) sinkDistDecreased(*n);
 
    nodeDescriptors_[&lastNode] = nd;
 
    // remove just the last node.
    boost::remove_vertex(lnd, graph_);
 
    // remove node from descriptor cache
    typename NodeDescMap::iterator ndi =
        nodeDescriptors_.find(&dest);
    if (ndi != nodeDescriptors_.end()) {
        nodeDescriptors_.erase(ndi);
    }
}
 
/**
 * Removes the edge connecting two nodes of the graph.
 * The associated properties are deleted automatically when
 * the graph is deleted, should not be deleted by the used.
 *
 * The connection between the head and tail nodes corresponding to the given
 * property object is removed from the graph.
 *
 * @param e Properties of the connecting edge to be removed.
 * @exception InstanceNotFound If the edge propertes are not registered to a
 *     connection of the graph.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::removeEdge(GraphEdge& e) {
    removeEdge(e, NULL, NULL, NULL);
}
 
/**
 * Removes the edge connecting two nodes of the graph from a subgraph,
 * but leaves it into the original graph
 *
 * @param e Properties of the connecting edge to be removed.
 * @exception InstanceNotFound If the edge propertes are not registered to a
 *     connection of the graph.
 
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::dropEdge(GraphEdge& e) {
    boost::remove_edge(descriptor(e), graph_);
 
    typename EdgeDescMap::iterator
        edIter = edgeDescriptors_.find(&e);
    if (edIter != edgeDescriptors_.end()) {
        edgeDescriptors_.erase(edIter);
    }
 
    for (unsigned int i = 0; i < childGraphs_.size(); i++) {
        childGraphs_.at(i)->dropEdge(e);
    }
}
 
/**
 * Removes the edge connecting two nodes of the graph, without deleting the
 * associated properties.
 *
 * The connection between the head and tail nodes corresponding to the given
 * property object is removed from the graph. The property object is not
 * managed by the graph anymore.
 *
 * @param e Properties of the connecting edge to be removed.
 * @exception InstanceNotFound If the edge propertes are not registered to a
 *     connection of the graph.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::removeEdge(
    GraphEdge& e, const GraphNode* tailNode, const GraphNode* headNode,
    BoostGraph* modifierGraph) {
    if (hasEdge(e, tailNode, headNode)) {
        boost::remove_edge(descriptor(e), graph_);
 
        typename EdgeDescMap::iterator
            edIter = edgeDescriptors_.find(&e);
        if (edIter != edgeDescriptors_.end()) {
            edgeDescriptors_.erase(edIter);
        }
 
        if (parentGraph_ != NULL && parentGraph_ != modifierGraph) {
            parentGraph_->removeEdge(e, tailNode, headNode, this);
        }
 
        for (unsigned int i = 0; i < childGraphs_.size(); i++) {
            if (childGraphs_.at(i) != modifierGraph ) {
                childGraphs_.at(i)->removeEdge(e, tailNode, headNode, this);
            }
        }
        delete pathCache_;
        pathCache_ = NULL;
    }
}
 
//////////////////////////////////////////////////////////////////////////////
// Subgraph related public methods
//////////////////////////////////////////////////////////////////////////////
 
/**
 * Returns the parent graph of this subgraph.
 * If the graph has no parent, returns NULL.
 *
 * @return parent graph of this subgraph or NULL if is not subgraph.
 */
template <typename GraphNode, typename GraphEdge>
BoostGraph<GraphNode, GraphEdge>*
BoostGraph<GraphNode, GraphEdge>::parentGraph() {
    return parentGraph_;
}
 
/**
 * Returns the root graph of this subgraph.
 * If this has no parent, return this.
 *
 * @return parent graph of this subgraph.
 */
template <typename GraphNode, typename GraphEdge>
BoostGraph<GraphNode, GraphEdge>*
BoostGraph<GraphNode, GraphEdge>::rootGraph() {
    if (parentGraph_ == NULL) {
        return this;
    }
    return parentGraph_;
}
 
/**
 * Returns the root graph of this subgraph.
 * If this has no parent, return this.
 *
 * @return parent graph of this subgraph.
 */
template <typename GraphNode, typename GraphEdge>
const BoostGraph<GraphNode, GraphEdge>*
BoostGraph<GraphNode, GraphEdge>::rootGraph() const {
    if (parentGraph_ == NULL) {
        return this;
    }
    return parentGraph_;
}
 
/**
 * Creates a subgraph from this graph.
 *
 * This procedure is suposed to be called from derived class's
 * createSubGraph method which also wold create the new object.
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::constructSubGraph(
    BoostGraph& subGraph, NodeSet& nodes) {
    // first add nodes
    for( typename NodeSet::iterator i = nodes.begin();
         i != nodes.end(); i++ ) {
        GraphNode& gn = *(*i);
        subGraph.addNode(gn);
    }
    // then edges
    for( typename NodeSet::iterator i = nodes.begin();
         i != nodes.end(); i++ ) {
        GraphNode& gn = *(*i);
        NodeDescriptor nd = descriptor(gn);
 
        std::pair<OutEdgeIter, OutEdgeIter> edges =
            boost::out_edges(nd, graph_);
        for (OutEdgeIter j = edges.first; j != edges.second; j++) {
            EdgeDescriptor ed = *j;
            NodeDescriptor hd = boost::target(ed, graph_);
            GraphNode* head = graph_[hd];
            if (nodes.find(head) != nodes.end()) {
                subGraph.connectNodes(gn, *head, *graph_[ed], NULL, true);
            }
        }
    }
    subGraph.parentGraph_ = this;
    childGraphs_.push_back(&subGraph);
    subGraph.name_ = name() + "_" + Conversion::toString(++sgCounter_);
}
 
/**
 * When a node has been dropped from a subgraph, this restores it,
 * based on the edges on the parent graph
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::restoreNodeFromParent(
    GraphNode& n) {
    assert(parentGraph_ != NULL);
 
    BoostGraph<GraphNode, GraphEdge>* parent = parentGraph_;
    parentGraph_ = NULL;
 
    addNode(n);
    NodeDescriptor ndp = parent->descriptor(n);
 
    std::pair<OutEdgeIter, OutEdgeIter> oEdges =
        boost::out_edges(ndp, parent->graph_);
 
    for (OutEdgeIter j = oEdges.first; j != oEdges.second; j++) {
        NodeDescriptor hd = boost::target(*j, parent->graph_);
        GraphNode* head = parent->graph_[hd];
        if (hasNode(*head)) {
            Edge& e = *graph_[*j];
            connectNodes(n, *head, e, NULL, true);
            calculatePathLengthsOnConnect(n, *head, e);
        }
    }
 
    std::pair<InEdgeIter, InEdgeIter> iEdges =
        boost::in_edges(ndp, parent->graph_);
 
    for (InEdgeIter j = iEdges.first; j != iEdges.second; j++) {
        NodeDescriptor tl = boost::source(*j, parent->graph_);
        GraphNode* tail = parent->graph_[tl];
        if (hasNode(*tail) && tail != &n) {
            Edge& e = *graph_[*j];
            connectNodes(*tail, n, e, NULL, true);
            calculatePathLengthsOnConnect(*tail, n, e);
        }
    }
    parentGraph_ = parent;
}
 
/*
 * Detach a subgraph from this graph.
 *
 * After this the subgraph is no longer updated when the graph is changed.
 * Does NOT remove parent_ of the subgraph, ie. leaves the subgraph in
 * non-functional stage. Should be used only just before deleting subgraph.
 *
 * @param subGraph subgraph to remove from the graph
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::detachSubgraph(BoostGraph& subGraph) {
    for (typename std::vector<BoostGraph<GraphNode, GraphEdge>*>::iterator
             iter = childGraphs_.begin(); iter != childGraphs_.end();iter++) {
        if ( *iter == &subGraph ) {
            childGraphs_.erase(iter);
            return;
        }
    }
}
 
 
/////////////////////////////////////////////////////////////////////////////
// Private helper methods
/////////////////////////////////////////////////////////////////////////////
 
/**
 *
 * Checks whether the given node belongs to the graph
 *
 * @param node node being tested
 * @return whether the ndoe belongs to the graph
 */
template <typename GraphNode, typename GraphEdge>
bool
BoostGraph<GraphNode, GraphEdge>::hasNode(const GraphNode& node) const {
 
    if (AssocTools::containsKey(nodeDescriptors_,&node)) {
        return true;
    }
 
    typedef std::pair<NodeIter, NodeIter> NodeIterPair;
    NodeIterPair nodes = boost::vertices(graph_);
    for (NodeIter i = nodes.first; i != nodes.second; i++) {
        if (graph_[*i] == &node) {
            nodeDescriptors_[&node] = *i;
            return true;
        }
    }
    return false;
}
 
/**
 *
 * Checks whether there exists and edge between the given nodes
 *
 * @param nTail tail node of the edge
 * @param nHead head node of the edge
 * @return whether there is an edge from nTail to nHead
 */
template <typename GraphNode, typename GraphEdge>
bool
BoostGraph<GraphNode, GraphEdge>::hasEdge(
    const GraphNode& nTail,
    const GraphNode& nHead) const {
 
    typedef std::pair<EdgeDescriptor, bool> EdgeReturned;
    EdgeReturned er = boost::edge(
        descriptor(nTail), descriptor(nHead), graph_);
    if (er.second == true) {
        return true;
    }
    return false;
}
 
/**
 *
 * Checks whether the given edge connects the given nodes
 *
 * @param nTail tail node of the edge
 * @param nHead head node of the edge
 * @param edge edge which may connect the nodes
 * @return whether the given edge does from nTail to nHead
 */
template <typename GraphNode, typename GraphEdge>
bool
BoostGraph<GraphNode, GraphEdge>::hasEdge(
    const GraphNode& nTail,
    const GraphNode& nHead,
    const GraphEdge& edge) const {
 
    typedef std::pair<OutEdgeIter, OutEdgeIter> OutEdgeIterPair;
 
    unsigned int hd = descriptor(nHead);
    OutEdgeIterPair edges = boost::out_edges(descriptor(nTail), graph_);
 
    for (OutEdgeIter i = edges.first; i != edges.second; i++) {
        if (graph_[*i] == &edge && target(*i, graph_) == hd) {
            return true;
        }
    }
    return false;
}
 
/**
 *
 * Checks whether the given edge belongs to the graph.
 *
 * @param edge edge being tested
 * @param tailnode, if known. makes this routine faster.
 * @param headnode, if known. makes this routine faster.
 * @return whether the edge belongs to the graph
 */
template <typename GraphNode, typename GraphEdge>
bool
BoostGraph<GraphNode, GraphEdge>::hasEdge(
    const GraphEdge& e,
    const GraphNode* nTail,
    const GraphNode* nHead) const {
 
    if (AssocTools::containsKey(edgeDescriptors_,&e)) {
        return true;
    }
 
    // if we have tails, check if's out edges
    if (nTail != NULL && hasNode(*nTail)) {
        typedef std::pair<OutEdgeIter, OutEdgeIter> OutEdgeIterPair;
 
        OutEdgeIterPair edges = boost::out_edges(descriptor(*nTail), graph_);
 
        for (OutEdgeIter i = edges.first; i != edges.second; i++) {
            if (graph_[*i] == &e) {
                edgeDescriptors_[&e] = *i;
                return true;
            }
        }
        return false;
    } else { // if we have head, check it's in edges.
        if (nHead != NULL && hasNode(*nHead)) {
            typedef std::pair<InEdgeIter, InEdgeIter> InEdgeIterPair;
 
            InEdgeIterPair edges = boost::in_edges(descriptor(*nHead), graph_);
 
            for (InEdgeIter i = edges.first; i != edges.second; i++) {
                if (graph_[*i] == &e) {
                    edgeDescriptors_[&e] = *i;
                    return true;
                }
            }
            return false;
        }
    }
 
    // we don't have head or tail, slowly go thru all edges.
    typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::edges(graph_);
 
    for (EdgeIter i = edges.first; i != edges.second; i++) {
        if (graph_[*i] == &e) {
            edgeDescriptors_[&e] = *i;
            return true;
        }
    }
    return false;
}
 
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
BoostGraph<GraphNode, GraphEdge>::descriptor(const GraphEdge& e) const {
 
    typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
    if (cacheIter != edgeDescriptors_.end()) {
        return cacheIter->second;
    }
 
    typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::edges(graph_);
 
    for (EdgeIter i = edges.first; i != edges.second; i++) {
        if (graph_[*i] == &e) {
            edgeDescriptors_[&e] = *i;
            return *i;
        }
    }
    assert(false && "Descriptor for edge not found!");
    return *edges.second;
}
 
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
BoostGraph<GraphNode, GraphEdge>::edgeDescriptor(
    const GraphEdge& e, const NodeDescriptor& headNode) const {
 
    typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
    if (cacheIter != edgeDescriptors_.end()) {
        return cacheIter->second;
    }
 
    typedef std::pair<InEdgeIter, InEdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::in_edges(headNode,graph_);
 
    for (InEdgeIter i = edges.first; i != edges.second; i++) {
        if (graph_[*i] == &e) {
            edgeDescriptors_[&e] = *i;
            return *i;
        }
    }
    assert(false);
    return *edges.second;
}
 
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
BoostGraph<GraphNode, GraphEdge>::edgeDescriptor(
    const NodeDescriptor& tailNode, const GraphEdge& e) const {
 
    typename EdgeDescMap::iterator cacheIter = edgeDescriptors_.find(&e);
    if (cacheIter != edgeDescriptors_.end()) {
    return cacheIter->second;
    }
 
    typedef std::pair<OutEdgeIter, OutEdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::out_edges(tailNode,graph_);
 
    for (OutEdgeIter i = edges.first; i != edges.second; i++) {
        if (graph_[*i] == &e) {
            edgeDescriptors_[&e] = *i;
            return *i;
        }
    }
    assert(false);
    return *edges.second;
}
 
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::NodeDescriptor
BoostGraph<GraphNode, GraphEdge>::descriptor(const GraphNode& n) const {
 
    typename NodeDescMap::iterator cacheIter = nodeDescriptors_.find(&n);
    if (cacheIter != nodeDescriptors_.end()) {
    return cacheIter->second;
    }
 
    typedef std::pair<NodeIter, NodeIter> NodeIterPair;
    NodeIterPair nodes = boost::vertices(graph_);
 
    for (NodeIter i = nodes.first; i != nodes.second; i++) {
        if (graph_[*i] == &n) {
            nodeDescriptors_[&n] = *i;
            return *i;
        }
    }
    Application::logStream() 
        << "Node " << n.toString() << "not in graph!" << std::endl;
    BoostGraph<GraphNode, GraphEdge>::writeToDotFile("missing_node.dot");
 
    assert(false);
    return *nodes.second;
}
 
 
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeDescriptor
BoostGraph<GraphNode, GraphEdge>::connectingEdge(
    const GraphNode& nTail,
    const GraphNode& nHead) const {
 
    typedef std::pair<EdgeDescriptor, bool> EdgeReturned;
 
    EdgeReturned edges = boost::edge(
        descriptor(nTail), descriptor(nHead), graph_);
    if (edges.second == false) {
        abortWithError("Connecting edge not found!");
    }
    return edges.first;
}
 
/**
 * Returns all the root nodes of the graph.
 *
 * Root nodes are nodes of which input degree is 0 (no edges entering, only
 * leaving). Also known as 'source nodes'.
 *
 * @return Set of root nodes, can be empty.
 */
template<typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::NodeSet
BoostGraph<GraphNode, GraphEdge>::rootNodes() const {
 
    NodeSet rootNodes;
    for (int nodeIndex = 0; nodeIndex < nodeCount(); ++nodeIndex) {
        GraphNode& nod = node(nodeIndex);
        if (inDegree(nod) == 0)
            rootNodes.insert(&nod);
    }
    return rootNodes;
}
 
 
/**
 * Returns all the sink nodes of the graph.
 *
 * Sink nodes are nodes of which output degree is 0 (no edges exiting, only
 * incoming).
 *
 * @return Set of sink nodes, can be empty.
 */
template<typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::NodeSet
BoostGraph<GraphNode, GraphEdge>::sinkNodes() const {
 
    NodeSet sinkNodes;
    for (int nodeIndex = 0; nodeIndex < nodeCount(); ++nodeIndex) {
        GraphNode& nod = node(nodeIndex);
        if (outDegree(nod) == 0)
            sinkNodes.insert(&nod);
    }
    return sinkNodes;
}
 
/**
 * Returns all the successors of the given node.
 *
 * If node has no successors, an empty set is returned. Note: the node can
 * also be a successor of itself.
 *
 * @param node The node of which successors to find.
 * @return Set of root nodes, can be empty.
 */
template<typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::NodeSet
BoostGraph<GraphNode, GraphEdge>::successors(
    const Node& node, bool ignoreBackEdges, bool ignoreForwardEdges) const {
 
    NodeSet succ;
 
    NodeDescriptor nd = descriptor(node);
    typedef typename GraphTraits::out_edge_iterator outEdgeIter;
    std::pair<outEdgeIter, outEdgeIter> edges = boost::out_edges(nd, graph_);
 
    for (outEdgeIter ei = edges.first; ei != edges.second; ei++) {
        EdgeDescriptor ed = *ei;
        GraphEdge* edge = graph_[ed];
        bool backEdge = edge->isBackEdge();
        if (!((ignoreBackEdges && backEdge) ||
              (ignoreForwardEdges && !backEdge))) {
            NodeDescriptor ndHead = boost::target(ed, graph_);
            GraphNode* head = graph_[ndHead];
            succ.insert(head);
        }
    }
 
    return succ;
}
 
/**
 * Returns all the predecessors of the given node.
 *
 * If node has no predecessors, an empty set is returned. Note: the node can
 * also be a predecessor of itself.
 *
 * @param node The node of which predecessors to find.
 * @return Set of root nodes, can be empty.
 */
template<typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::NodeSet
BoostGraph<GraphNode, GraphEdge>::predecessors(
    const Node& node, bool ignoreBackEdges, bool ignoreForwardEdges) const {
 
    NodeSet pred;
 
    typedef typename GraphTraits::in_edge_iterator InEdgeIter;
    std::pair<InEdgeIter, InEdgeIter> edges = boost::in_edges(
        descriptor(node), graph_);
 
    for (InEdgeIter ei = edges.first; ei != edges.second; ++ei) {
        EdgeDescriptor ed = *ei;
        GraphEdge* edge = graph_[ed];
        bool backEdge = edge->isBackEdge();
        if (!((ignoreBackEdges && backEdge) ||
              (ignoreForwardEdges && !backEdge))) {
            NodeDescriptor nTail = boost::source(ed, graph_);
            GraphNode* tail = graph_[nTail];
            pred.insert(tail);
        }
    }
    return pred;
}
 
/**
 * Calculates maximum path lengths from sinks and sources to all nodes.
 *
 * This procedure is called internally when this information is needed
 */
template<typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::calculatePathLengthsFast() const {
    std::vector<NodeDescriptor> sortedNodes;
    sortedNodes.reserve(nodeCount());
    // inserts first elements into end?
    topological_sort(graph_, std::back_inserter(sortedNodes));
    for (unsigned int i = 0 ; i < sortedNodes.size(); i++) {
        NodeDescriptor& nd = sortedNodes[i];
        const Node* node = graph_[nd];
        int len = sinkDistances_[node];
 
        // loop over all in edges.
        std::pair <InEdgeIter, InEdgeIter> edges = boost::in_edges(nd, graph_);
        for (InEdgeIter ii = edges.first; ii != edges.second; ii++) {
            EdgeDescriptor ed = *ii;
            Edge* edge = graph_[ed];
            NodeDescriptor td = boost::source(*ii, graph_);
            const Node* tailNode = graph_[td];
            int eWeight = edgeWeight(*edge, *node);
            int sdLen = len + eWeight;
            
            // find the place in the sourcedistances table
            typename std::map<
                const GraphNode*,int, typename GraphNode::Comparator>
            ::iterator sdIter = sinkDistances_.find(tailNode);
            // update if this path is longer.
            if (sdIter == sinkDistances_.end()) {
                sinkDistances_[tailNode] = sdLen;
                if (sdLen > height_) {
                    height_ = sdLen;
                }
            } else if(sdIter->second < sdLen) {
                sdIter->second = sdLen;
                if (sdLen > height_) {
                    height_ = sdLen;
                }
            }
        }
    }
}
 
/**
 * Calculates maximum path lengths from sinks and sources to all nodes.
 *
 * This procedure is called internally when this information is needed
 */
template<typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::calculatePathLengths() const {
 
    calculateSourceDistances();
 
    if (!allowLoopEdges_) {
        calculatePathLengthsFast();
        return;
    } 
 
    // priority queue of all sink nodes.
    std::priority_queue<PathLengthHelper> sinkDistanceQueue;
 
    // insert all sink nodes to the pqueue
    for (int i = nodeCount() -1 ; i >= 0 ; i--) {
 
        NodeDescriptor nd = descriptor(node(i));
        std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
            nd, graph_);
 
        bool outEdgeFound = false;
        for (OutEdgeIter ii = edges.first; ii != edges.second;
             ii++) {
            EdgeDescriptor ed = *ii;
            if (!graph_[ed]->isBackEdge()) {
                outEdgeFound = true;
            }
        }
        if (!outEdgeFound) {
            sinkDistanceQueue.push(
                PathLengthHelper(nd, 0, sourceDistances_[&node(i)]));
        }
    }
 
    // and then start sink calculation from each of them.
    while (!sinkDistanceQueue.empty()) {
        calculateSinkDistance(*graph_[sinkDistanceQueue.top().nd_],0);
        sinkDistanceQueue.pop();
    }
}
 
/**
 * Calculates source distances of nodes.
 *
 * Iterative algorithm, starts from given node or all source nodes.
 *
 * Does a breadth-first search, prioritizating first nodes in the graph.
 *
 * @param startingNode node whose successors's source dist to calculate,
 * or NULL if start from all sources.
 *
 * @param startingLength source distance of the startingnode.
 */
template<typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::calculateSourceDistances(
    const GraphNode* startingNode, int startingLength, bool looping) const {
 
    if (startingLength > height_) {
        height_ = startingLength;
    }
 
    // priority queue of nodes to be processed
    typename std::map <NodeDescriptor, int> sourceDistanceQueue;
 
    // priority queue of nodes to be processed
    typename std::map <NodeDescriptor, int> loopingSourceDistanceQueue;
 
    // first initialize starting nodes to the queue
 
    // one starting node?
    if (startingNode != NULL) {
        if (!looping) {
            sourceDistances_[startingNode] = startingLength;
            sourceDistanceQueue[descriptor(*startingNode)] = startingLength;
        } else {
            loopingSourceDistances_[startingNode] = startingLength;
            loopingSourceDistanceQueue[descriptor(*startingNode)] =
                startingLength;
        }
 
    } else {
        // insert all source nodes to the pqueue
        for (int i = 0; i < nodeCount(); i++) {
            NodeDescriptor nd = boost::vertex(i, graph_);
            std::pair <InEdgeIter, InEdgeIter> edges = boost::in_edges(
                nd, graph_);
 
            bool inEdgeFound = false;
            for (InEdgeIter ii = edges.first; ii != edges.second;
                 ii++) {
                EdgeDescriptor ed = *ii;
                if (!graph_[ed]->isBackEdge()) {
                    inEdgeFound = true;
                }
            }
            if (!inEdgeFound) {
                sourceDistances_[graph_[nd]] = startingLength;
                sourceDistanceQueue[nd] = startingLength;
            }
        }
    }
 
    // and then start sink calculation from each of them.
    while (!sourceDistanceQueue.empty()) {
        typename std::map <NodeDescriptor, int>::iterator sdBegin =
            sourceDistanceQueue.begin();
 
        NodeDescriptor nd = sdBegin->first;
        int len = sdBegin->second;
        sourceDistanceQueue.erase(sdBegin);
 
        // then test all successors..
        std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
            nd, graph_);
        for (OutEdgeIter oi = edges.first; oi != edges.second; oi++) {
            EdgeDescriptor ed = *oi;
            GraphEdge *edge = graph_[ed];
            NodeDescriptor headDesc = boost::target(ed, graph_);
            Node* headNode = graph_[headDesc];
            int eWeight = edgeWeight(*edge, *headNode);
            int destLen = len + eWeight;
 
            if (destLen > height_) {
                height_ = destLen;
            }
 
            // normal or loop-containing length?
            typename std::map<
            const GraphNode*,int, typename GraphNode::Comparator> &
                sourceDistances =
                edge->isBackEdge() ? loopingSourceDistances_:sourceDistances_;
 
            // find the place in the sourcedistances table
            typename std::map<
                const GraphNode*,int, typename GraphNode::Comparator>
                ::iterator sdIter = sourceDistances.find(headNode);
 
            // if not yet there, add
            if (sdIter == sourceDistances.end()) {
                sourceDistances[headNode] = destLen;
            } else {
                // this is longer? replace with this
                if (sdIter->second < destLen ) {
                    sdIter->second = destLen;
                } else {
                    // we have already been here, with bigger path.
                    // no need to check successors.
                    continue;
                }
            }
 
            // add to normal or loop-containing queue?
            typename std::map<
                NodeDescriptor,int> &
                mySourceDistanceQueue =
                edge->isBackEdge() ?
                loopingSourceDistanceQueue : sourceDistanceQueue;
 
            // then may enqueue the successor for processing it.
            typename std::map <NodeDescriptor, int>::iterator qiter =
                mySourceDistanceQueue.find(headDesc);
            if (qiter == mySourceDistanceQueue.end()) {
                // not found from queue, add it there.
                mySourceDistanceQueue[headDesc] = destLen;
            } else {
                // already is in queue.
                if (qiter->second < destLen) {
                    // if this one has longer path, replace the queued
                    // ath lenght with this path length.
                    qiter->second = destLen;
                }
            }
        }
    }
 
    // then iterate over nodes that have one loop node pointing to them.
    // do not follow any other loop edges.
 
    while (!loopingSourceDistanceQueue.empty()) {
        typename std::map <NodeDescriptor, int>::iterator sdBegin =
            loopingSourceDistanceQueue.begin();
 
        NodeDescriptor nd = sdBegin->first;
        int len = sdBegin->second;
        loopingSourceDistanceQueue.erase(sdBegin);
 
        // then test all successors..
        std::pair <OutEdgeIter, OutEdgeIter> edges = boost::out_edges(
            nd, graph_);
        for (OutEdgeIter oi = edges.first; oi != edges.second; oi++) {
            EdgeDescriptor ed = *oi;
            GraphEdge *edge = graph_[ed];
            // do not follow no more loop edges.
            if (edge->isBackEdge()) {
                continue;
            }
            NodeDescriptor headDesc = boost::target(ed, graph_);
            Node* headNode = graph_[headDesc];
            int eWeight = edgeWeight(*edge, *headNode);
            int destLen = len + eWeight;
 
            // find the place in the sourcedistances table
            typename std::map<
            const GraphNode*,int, typename GraphNode::Comparator>
                ::iterator sdIter = loopingSourceDistances_.find(headNode);
 
            // if not yet there, add
            if (sdIter == loopingSourceDistances_.end()) {
                loopingSourceDistances_[headNode] = destLen;
            } else {
                // this is longer? replace with this
                if (sdIter->second < destLen ) {
                    sdIter->second  = destLen;
                } else {
                    // we have already been here, with bigger path.
                    // no need to check successors.
                    continue;
                }
            }
 
            // then may enqueue the successor for processing it.
            typename std::map <NodeDescriptor, int>::iterator qiter =
                loopingSourceDistanceQueue.find(headDesc);
            if (qiter == loopingSourceDistanceQueue.end()) {
                // not found from queue, add it there.
                loopingSourceDistanceQueue[headDesc] = destLen;
            } else {
                // already is in queue.
                if (qiter->second < destLen) {
                    // if this one has longer path, replace the queued
                    // ath lenght with this path length.
                    qiter->second = destLen;
                }
            }
        }
    }
}
 
/**
 * Recursively calculates path lenght from sinks to sources.
 *
 * @param node Node curently being processed
 * @param len Current lenght from sink.
 */
template<typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::calculateSinkDistance(
    const Node& node, int len, bool looping ) const {
    if (len > 26000) {
        GraphBase<GraphNode,GraphEdge>::writeToDotFile("not_dag.dot");
        assert(false&&"cannot calc sink distance for graph which is not dag");
    }
 
    std::map<const GraphNode*,int, typename GraphNode::Comparator> &
        sinkDistances = looping ? loopingSinkDistances_ : sinkDistances_;
 
    // find the place in the sourcedistances table
    typename std::map<
        const GraphNode*,int, typename GraphNode::Comparator>
        ::iterator sdIter = sinkDistances.find(&node);
 
    // if not yet there, add
    if (sdIter == sinkDistances.end()) {
        sinkDistances[&node] = len;
    } else {
        // this is longer? replace with this
        if (sdIter->second <= len ) {
            sdIter->second = len;
        } else {
            // we have already been here, with bigger path.
            // no need to check successors.
            return;
        }
    }
 
    if (len > height_) {
        height_ = len;
    }
 
    // priority queue of predecessor nodes. recurse always
    // to one with highest source distance
    std::priority_queue<PathLengthHelper> predecessorQueue;
    NodeDescriptor nd = descriptor(node);
    std::pair <InEdgeIter, InEdgeIter> edges = boost::in_edges(nd, graph_);
    for (InEdgeIter ii = edges.first; ii != edges.second; ii++) {
        EdgeDescriptor ed = *ii;
        Edge* edge = graph_[ed];
        // if already looping, may not be backedge.
        if (!looping || !edge->isBackEdge()) {
            NodeDescriptor td = boost::source(*ii, graph_);
            Node* tailNode = graph_[td];
            int eWeight = edgeWeight(*edge, node);
            int sdLen = len + eWeight;
            if (sdLen > height_) {
                height_ = sdLen;
            }
 
            // the predecessor is thru one loop?
            if (looping || edge->isBackEdge()) {
                sdIter = loopingSinkDistances_.find(tailNode);
                // if not yet there, add
                if (sdIter == loopingSinkDistances_.end()) {
                    loopingSinkDistances_[tailNode] = sdLen;
                } else {
                    // this is longer? replace with this
                    if (sdIter->second < sdLen) {
                        sdIter->second = sdLen;
                    } else {
                        // we have already been here, with bigger path.
                        // no need to check successors.
                        continue;
                    }
                }
                predecessorQueue.push(
                    PathLengthHelper(
                        td, sdLen, sourceDistances_[tailNode], true));
            } else {
                sdIter = sinkDistances_.find(tailNode);
                // if not yet there, add
                if (sdIter == sinkDistances_.end()) {
                    sinkDistances_[tailNode] = sdLen;
                } else {
                    // this is longer? replace with this
                    if (sdIter->second < sdLen ) {
                        sdIter->second = sdLen;
                    } else {
                        // we have already been here, with bigger path.
                        // no need to check successors.
                        continue;
                    }
                }
                predecessorQueue.push(
                    PathLengthHelper(
                        td, sdLen, sourceDistances_[tailNode], false));
            }
        }
    }
 
    // all predecessors are in the queue, loop it thru in
    // correct order.
    while (!predecessorQueue.empty()) {
 
        PathLengthHelper plh = predecessorQueue.top();
        calculateSinkDistance(
            *graph_[plh.nd_], plh.len_, plh.looping_);
        predecessorQueue.pop();
    }
}
 
/**
 * Gives the lenght of a longest path a node belongs in a graph.
 *
 * If the path lenghts are not calculated calculates them.
 * If the graph is a cyclic graph, the function may never return.
 *
 * @param node Node belonging to a path.
 *
 * @return length of the longest path where given node belongs to
 */
template<typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::maxPathLength(const GraphNode& node) const {
    return maxSinkDistance(node) + maxSourceDistance(node);
}
 
/**
 * Gives the lenght of a longest path from any source node to given node.
 *
 * If the path lenghts are not calculated calculates them.
 * If the graph is a cyclic graph without back edges correctly set,
 * the function may never return. If all cycles contain at least one
 * backedge, this should work, and it will then return longest path where
 * maximum of one loop is looped.
 *
 * @param node Node belonging to a path.
 *
 * @return length of the longest path where given node belongs to
 */
template<typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::maxSourceDistance(const GraphNode& node)
    const {
 
    if (!hasNode(node)) {
        return -1;
    }
 
 
    for (int i = 0; i < 2; i++) {
        typename std::map<
        const GraphNode*,int,typename GraphNode::Comparator>::
            iterator iter = loopingSourceDistances_.find(&node);
        if (iter != loopingSourceDistances_.end()) {
            return iter->second;
        }
 
        typename std::map<
        const GraphNode*,int,typename GraphNode::Comparator>::
            iterator iter2 = sourceDistances_.find(&node);
 
        if (iter2 == sourceDistances_.end()) {
            if (i == 0) {
                calculateSourceDistances();
            }
        } else {
            return iter2->second;
        }
    }
    if (!hasNode(node)) {
        return -1;
    }
    std::cerr << "Node lacks source distance! " << node.nodeID() << " " << node.nodeID() << " "
              << node.toString() << std::endl;
    BoostGraph<GraphNode, GraphEdge>::writeToDotFile("lacking_sourced.dot");
    assert(0 && "source distance should have been found.");
    return -1;
}
 
/**
 * Gives the lenght of a longest path from the given node to any sink node.
 *
 * If the path lenghts are not calculated calculates them.
 * If the graph is a cyclic graph without back edges correctly set,
 * the function may never return. If all cycles contain at least one
 * backedge, this should work, and it will then return longest path where
 * maximum of one loop is looped.
 *
 * @param node Node belonging to a path.
 *
 * @return length of the longest path where given node belongs to
 */
template<typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::maxSinkDistance(const GraphNode& node)
    const {
 
    if (!hasNode(node)) {
        return -1;
    }
 
    for (int i = 0; i < 2; i++) {
        typename std::map<
        const GraphNode*,int,typename GraphNode::Comparator>::
            iterator iter = loopingSinkDistances_.find(&node);
        if (iter != loopingSinkDistances_.end()) {
            if (sinkDistances_.find(&node) == sinkDistances_.end() ||
                iter->second > sinkDistances_[&node]) {
                return iter->second;
            }
        }
 
        typename std::map<
        const GraphNode*,int,typename GraphNode::Comparator>::
            iterator iter2 = sinkDistances_.find(&node);
 
        if (iter2 == sinkDistances_.end()) {
            calculatePathLengths();
        } else {
            return iter2->second;
        }
    }
    if (!hasNode(node)) {
        return -1;
    }
    std::cerr << "Node lacks sink distance! " << node.nodeID() << " "
              << node.toString() << std::endl;
    BoostGraph<GraphNode, GraphEdge>::writeToDotFile("lacking_sinkd.dot");
 
    assert(0 && "sink distance should have been found.");
    return -1;
}
 
/**
 * Gives the longest path in acyclic graph.
 *
 * If the path lenghts are not calculated calculates them.
 * If the graph is a cyclic graph, the function may never return.
 *
 * @return Longst path in acyclic graph.
 */
template<typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::height() const {
 
    if (height_ == -1) {
        calculatePathLengths();
    }
 
    return height_;
}
 
/**
 * Gives weight of a one edge in a graph.
 *
 * Derived class should overrider this with real implementation
 * which does the actual node weight calculation.
 *
 * This base class implementation always returns 1.
 *
 * @return The weight of an edge.
 */
template <typename GraphNode, typename GraphEdge>
int
BoostGraph<GraphNode, GraphEdge>::edgeWeight(
    GraphEdge&,const GraphNode&) const {
    return 1;
}
 
/**
 * Returns all edges that connect two nodes.
 *
 * @param nTail source node
 * @param nHead destination node
 * @return a set containing all edges from nTail to nHead
 */
template <typename GraphNode, typename GraphEdge>
typename BoostGraph<GraphNode, GraphEdge>::EdgeSet
BoostGraph<GraphNode, GraphEdge>::connectingEdges(
    const GraphNode& nTail, const GraphNode& nHead) const {
 
    EdgeSet headIn = inEdges(nHead);
    EdgeSet tailOut = outEdges(nTail);
    EdgeSet intersection;
    SetTools::intersection(headIn, tailOut, intersection);
    return intersection;
}
 
template <typename GraphNode, typename GraphEdge>
const TCEString&
BoostGraph<GraphNode, GraphEdge>::name() const {
    return name_;
}
 
/**
 * Finds all paths between nodes and updates the internal path cache.
 *
 * This data is used internally to speed up hasPath(). 
 */
template <typename GraphNode, typename GraphEdge>
void
BoostGraph<GraphNode, GraphEdge>::findAllPaths() const {
    
    using namespace boost;    
 
    typedef std::map<EdgeDescriptor, int> WeightMap;
    WeightMap weightsMap;
    associative_property_map<WeightMap> weights(weightsMap);
 
    typedef std::pair<EdgeIter, EdgeIter> EdgeIterPair;
    EdgeIterPair edges = boost::edges(graph_);
    for (EdgeIter i = edges.first; i != edges.second; i++) {
        weightsMap[*i] = 0;
    }
 
    const int nodes = nodeCount();
    delete pathCache_;
    pathCache_ = new PathCache;
    for (int i = 0; i < nodes; ++i) {
        pathCache_->push_back(std::vector<int>(nodes));
    }
    johnson_all_pairs_shortest_paths(graph_, *pathCache_, weight_map(weights));
}
 
template <typename GraphNode, typename GraphEdge>
bool
BoostGraph<GraphNode, GraphEdge>::hasPath(
    GraphNode& src, const GraphNode& dest) const {
 
    if (&src == &dest) {
        return true;
    }
 
    if (pathCache_ != NULL) {
        return (*pathCache_)[descriptor(src)][descriptor(dest)] !=
            (std::numeric_limits<int>::max)();
    }
    NodeSet foundNodes;
    NodeSet queue;
    queue.insert(&src);
    int dstSinkDist = -1;
    if (height_ != -1) {
        dstSinkDist = maxSinkDistance(dest);
    }
    while (!queue.empty()) {
        GraphNode* current = *queue.begin();
        queue.erase(current);
 
        int sd = INT_MAX;
        if (height_ != -1) {
            sd = maxSinkDistance(*current);
        }
        if (sd >= dstSinkDist) {
            NodeDescriptor nd = descriptor(*current);
            std::pair<OutEdgeIter, OutEdgeIter> edges =
                boost::out_edges(nd, graph_);
            for (OutEdgeIter ei = edges.first; ei != edges.second; ei++) {
                EdgeDescriptor ed = *ei;
                const Edge& edge = *graph_[ed];
                if (edge.isBackEdge()) {
                    continue;
                }
                NodeDescriptor hd = boost::target(ed, graph_);
                Node* const head = graph_[hd];
 
                if (head == &dest) {
                    return true;
                }
                if (foundNodes.find(head) == foundNodes.end()) {
                    queue.insert(head);
                    foundNodes.insert(head);
                    // make sure found from the descriptor cache.
                    nodeDescriptors_[head] = hd;
                }
            }
        }
    }
    return false;
}
 
/**
 * Detects cycles that happen without proper backedge properties
 * This routine is currently quite slow , there is room for
 * optimization. This is to be used for debugging.
 */
template <typename GraphNode, typename GraphEdge>
bool
BoostGraph<GraphNode, GraphEdge>::detectIllegalCycles() const {
    for (int i = 0; i < nodeCount(); i++) {
        GraphNode* originalNode = &node(i);
        NodeSet queuedNodes;
        NodeSet foundNodes;
        queuedNodes.insert(originalNode);
        foundNodes.insert(originalNode);
        while (!queuedNodes.empty()) {
            const GraphNode* n = *queuedNodes.begin();
            queuedNodes.erase(queuedNodes.begin());
            EdgeSet es = outEdges(*n);
            for (typename EdgeSet::iterator ei = es.begin(); ei != es.end(); ei++) {
                const GraphEdge* e = *ei;
                if (!e->isBackEdge()) {
                    GraphNode& head = headNode(*e);
                    if (&head == originalNode) {
                        std::cerr << "Detected illegal cycle between nodes: "
                                  << originalNode->toString() << " and "
                                  << n->toString() << " edge: " <<
                            e->toString() << std::endl;
                        return true;
                    }
                    if (!AssocTools::containsKey(foundNodes,&head)) {
                        foundNodes.insert(&head);
                        queuedNodes.insert(&head);
                    }
                }
            }
        }
    }
    return false;
}
 
template <typename GraphNode, typename GraphEdge>
bool
BoostGraph<GraphNode, GraphEdge>::PathLengthHelper::operator<(
    const BoostGraph<GraphNode, GraphEdge>::PathLengthHelper& other) const {
    return sd_ < other.sd_;
}
 
template <typename GraphNode, typename GraphEdge>
BoostGraph<GraphNode, GraphEdge>::PathLengthHelper::PathLengthHelper(
    typename BoostGraph<GraphNode,GraphEdge>::NodeDescriptor nd,
    int len, int sd, bool looping) :
    nd_(nd), len_(len), sd_(sd), looping_(looping) {}