37#ifndef TTA_BOOST_GRAPH_HH
38#define TTA_BOOST_GRAPH_HH
40#include <boost/version.hpp>
42#if BOOST_VERSION < 103500
44#include <boost/graph/detail/edge.hpp>
48 template <
class D,
class V>
50 operator<(
const detail::edge_desc_impl<D,V>& a,
51 const detail::edge_desc_impl<D,V>& b) {
52 return a.get_property() < b.get_property();
69#include <boost/config.hpp>
70#include <boost/graph/adjacency_list.hpp>
71#include <boost/graph/subgraph.hpp>
82template <
typename GraphNode,
typename GraphEdge>
86 typedef std::set<GraphNode*, typename GraphNode::Comparator >
NodeSet;
87 typedef std::set<GraphEdge*, typename GraphEdge::Comparator >
EdgeSet;
102 Node&
node(
const int index,
bool cacheResult)
const;
141 const Node* tail = NULL,
bool childs =
false);
145 const Node* head = NULL,
bool childs =
false);
148 const Node* tail = NULL);
151 const Node* head = NULL);
162 const Node& nHead)
const;
169 const Node&
node,
bool ignoreBackEdges=
false,
170 bool ignoreForwardEdges=
false)
const;
172 const Node&
node,
bool ignoreBackEdges=
false,
173 bool ignoreForwardEdges=
false)
const;
203 const Node& nTail,
const Node& nHead)
const;
214 int tmp =
reinterpret_cast<size_t>(
node);
215 return tmp ^ (tmp >> 16);
218 int tmp =
reinterpret_cast<size_t>(
edge);
219 return tmp ^ (tmp >> 16);
245 typedef typename boost::adjacency_list<
246 boost::listS, boost::vecS,
257 typedef typename GraphTraits::edge_iterator
EdgeIter;
259 typedef typename GraphTraits::vertex_iterator
NodeIter;
286 const Node& nHead)
const;
304 const GraphNode* startNode = NULL,
int startingLength = 0,
305 bool looping =
false)
const;
317 mutable std::unordered_map<const GraphNode*,int>
319 mutable std::unordered_map<const GraphNode*,int>
323 mutable std::unordered_map<const GraphNode*,int>
325 mutable std::unordered_map<const GraphNode*,int>
335 typedef hash_map<const Edge*, EdgeDescriptor, GraphHashFunctions>
337 typedef hash_map<const Node*, NodeDescriptor, GraphHashFunctions>
#define IGNORE_CLANG_WARNING(X)
size_t operator()(const GraphNode *node) const
size_t operator()(const GraphEdge *edge) const
void restoreRemovedEdges(RemovedEdgeMap removedEdges)
int maxSourceDistance(const GraphNode &node) const
virtual EdgeSet rootGraphOutEdges(const Node &node) const
void sinkDistDecreased(const GraphNode &n) const
virtual void removeEdge(Edge &e)
BoostGraph(bool allowLoopEdges=true)
std::set< RemovedEdgeDatum > RemovedEdgeMap
virtual void disconnectNodes(const Node &nTail, const Node &nHead)
bool hasEdge(const Edge &edge, const Node *nTail=NULL, const Node *nHead=NULL) const
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e, GraphBase< GraphNode, GraphEdge > *modifier, bool creatingSG=false)
virtual void moveOutEdges(const Node &source, const Node &destination, BoostGraph *modifierGraph)
EdgeDescriptor descriptor(const Edge &e) const
GraphTraits::vertex_descriptor NodeDescriptor
Type with which nodes of the graph are seen internally.
GraphTraits::out_edge_iterator OutEdgeIter
Output edge iterator type.
virtual void moveOutEdges(const Node &source, const Node &destination)
virtual Node & headNode(const Edge &edge) const
Node & tailNode(const Edge &edge, const NodeDescriptor &headNode) const
virtual int edgeWeight(GraphEdge &e, const GraphNode &n) const
void calculateSourceDistances(const GraphNode *startNode=NULL, int startingLength=0, bool looping=false) const
boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, Node *, Edge * > Graph
Internal graph type, providing actual graph-like operations. This type definition relies on bundled p...
virtual NodeSet rootNodes() const
useful utility functions
NodeDescriptor descriptor(const Node &n) const
void detachSubgraph(BoostGraph &subGraph)
void sourceDistDecreased(const GraphNode &n) const
virtual void copyOutEdge(const Node &destination, Edge &edge, const Node *head=NULL)
int maxSinkDistance(const GraphNode &node) const
int maxPathLength(const GraphNode &node) const
Node & headNode(const Edge &edge, const NodeDescriptor &tailNode) const
std::set< GraphEdge *, typename GraphEdge::Comparator > EdgeSet
virtual int rootGraphInDegree(const Node &node) const
void calculatePathLengths() const
virtual Edge & outEdge(const Node &node, const int index) const
BoostGraph * parentGraph()
void setName(const TCEString &newName)
hash_map< const Node *, NodeDescriptor, GraphHashFunctions > NodeDescMap
virtual void removeNode(Node &node)
EdgeDescMap edgeDescriptors_
virtual void dropEdge(Edge &edge)
virtual Edge & inEdge(const Node &node, const int index) const
void restoreNodeFromParent(GraphNode &node)
BoostGraph(const TCEString &name, bool allowLoopEdges=true)
virtual bool hasEdge(const Node &nTail, const Node &nHead) const
virtual void copyInEdge(const Node &destination, Edge &edge, const Node *tail=NULL)
virtual int rootGraphOutDegree(const Node &node) const
virtual Edge & rootGraphInEdge(const Node &node, const int index) const
void calculatePathLengthsOnConnect(const GraphNode &nTail, const GraphNode &nHead, GraphEdge &e)
virtual void addNode(Node &node)
GraphTraits::in_edge_iterator InEdgeIter
Input edge iterator type.
virtual void moveOutEdge(const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false)
EdgeDescriptor edgeDescriptor(const NodeDescriptor &tailNode, const Edge &e) const
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
Node & node(const int index) const
bool hasNode(const Node &) const
BoostGraph(const BoostGraph &other, bool allowLoopEdges=true)
EdgeDescriptor connectingEdge(const Node &nTail, const Node &nHead) const
virtual void dropNode(Node &node)
virtual const TCEString & name() const
bool hasPath(GraphNode &src, const GraphNode &dest) const
GraphTraits::edge_descriptor EdgeDescriptor
Type with which edges of the graph are seen internally.
void replaceNodeWithLastNode(GraphNode &dest)
virtual Edge & rootGraphOutEdge(const Node &node, const int index) const
boost::graph_traits< Graph > GraphTraits
Traits characterising the internal graph type.
virtual int inDegree(const Node &node) const
std::unordered_map< const GraphNode *, int > loopingSinkDistances_
std::vector< BoostGraph< GraphNode, GraphEdge > * > childGraphs_
void calculatePathLengthsFast() const
std::unordered_map< const GraphNode *, int > loopingSourceDistances_
std::set< GraphNode *, typename GraphNode::Comparator > NodeSet
bool detectIllegalCycles() const
virtual void moveInEdge(const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
void findAllPaths() const
virtual NodeSet predecessors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
virtual int outDegree(const Node &node) const
GraphNode Node
The (base) node type managed by this graph.
EdgeSet connectingEdges(const Node &nTail, const Node &nHead) const
virtual EdgeSet outEdges(const Node &node) const
virtual void removeEdge(Edge &e, const GraphNode *tailNode, const GraphNode *headNode, BoostGraph *modifierGraph=NULL)
std::set< Edge * > ownedEdges_
GraphTraits::vertex_iterator NodeIter
Iterator type for the list of all nodes in the graph.
bool isInCriticalPath(const GraphNode &node) const
hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions > EdgeDescMap
virtual Node & tailNode(const Edge &edge) const
bool hasEdge(const Node &nTail, const Node &nHead, const Edge &edge) const
EdgeDescriptor edgeDescriptor(const Edge &e, const NodeDescriptor &headNode) const
void clearDescriptorCache(EdgeSet edges)
std::unordered_map< const GraphNode *, int > sourceDistances_
virtual void moveInEdges(const Node &source, const Node &destination)
Node & node(const int index, bool cacheResult) const
virtual void removeNode(Node &node, BoostGraph *modifierGraph)
virtual Edge & edge(const int index) const
GraphEdge Edge
The (base) edge type managed by this graph.
NodeDescMap nodeDescriptors_
Graph graph_
The internal graph structure.
std::vector< std::vector< int > > PathCache
const BoostGraph * rootGraph() const
std::unordered_map< const GraphNode *, int > sinkDistances_
void constructSubGraph(BoostGraph &subGraph, NodeSet &nodes)
virtual NodeSet sinkNodes() const
void moveInEdges(const Node &source, const Node &destination, BoostGraph *modifierGraph)
BoostGraph< GraphNode, GraphEdge > * parentGraph_
virtual EdgeSet inEdges(const Node &node) const
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
BoostGraph & operator=(const BoostGraph &)
Assignment forbidden.
virtual EdgeSet rootGraphInEdges(const Node &node) const
GraphTraits::edge_iterator EdgeIter
Iterator type for the list of all edges in the graph.
void calculateSinkDistance(const GraphNode &node, int len, bool looping=false) const
virtual int edgeID() const
bool operator<(const detail::edge_desc_impl< D, V > &a, const detail::edge_desc_impl< D, V > &b)
bool operator<(const PathLengthHelper &other) const
PathLengthHelper(NodeDescriptor nd, int len, int sd, bool looping=false)
RemovedEdgeDatum(GraphNode &tail, GraphNode &head, GraphEdge &e)
bool operator<(const RemovedEdgeDatum &other) const