69 am_GraphElementStatus_e mStatus;
76 void setStatus(
const am_GraphElementStatus_e s) { mStatus = s; };
77 am_GraphElementStatus_e
getStatus()
const {
return mStatus; };
92 const NodeData &
getData()
const {
return mData; }
94 void setIndex(uint16_t index) { mIndex = index; }
100 VertexData mVertexData;
104 mpNode(aNode), mVertexData(vertexData), mWeight(weight) { };
110 VertexData &
getData() {
return mVertexData; }
112 void setWeight(
const uint16_t weight) { mWeight=weight; }
121 typedef typename std::vector<CAmNode<T>*> CAmListNodePtrs;
122 typedef typename std::list<CAmVertex<T,V>> CAmListVertices;
123 typedef typename std::list<CAmVertex<T,V>>::iterator CAmListVerticesItr;
124 typedef typename std::list<CAmVertex<T,V>>::const_iterator CAmListVerticesItrConst;
125 typedef typename std::list<CAmListVertices> CAmNodesAdjList;
126 typedef typename std::list<CAmListVertices>::iterator CAmNodesAdjListItr;
127 typedef typename std::list<CAmListVertices>::const_iterator CAmNodesAdjListItrConst;
128 typedef typename std::list<CAmNode<T>> CAmListNodes;
129 typedef typename std::list<CAmNode<T>>::iterator CAmListNodesItr;
130 typedef typename std::list<CAmNode<T>>::const_iterator CAmListNodesItrConst;
131 typedef typename std::vector<CAmNode<T>*> CAmNodeReferenceList;
132 typedef typename std::vector<CAmListVertices*> CAmVertexReferenceList;
134 CAmListNodes mStoreNodes;
135 CAmNodesAdjList mStoreAdjList;
136 CAmNodeReferenceList mPointersNodes;
137 CAmVertexReferenceList mPointersAdjList;
140 struct IterateThroughAllNodesDelegate
144 CAmNodeReferenceList visited;
145 std::function<bool(const CAmNode<T> * )> shouldVisitNode;
146 std::function<void(const CAmNode<T> *)> willVisitNode;
147 std::function<void(const CAmNode<T> *)> didVisitNode;
148 std::function<void(const CAmNodeReferenceList & path)> didFindPath;
151 struct VisitNodeDelegate
155 std::function<void(const am_GraphPathPosition_e, CAmNode<T> &)> visitedNode;
163 void updateIndexes(
const int16_t fromIndex)
165 if( fromIndex<mPointersNodes.size() )
167 for(
auto iter = mPointersNodes.begin()+fromIndex; iter!=mPointersNodes.end(); iter++)
168 (*iter)->
setIndex(iter-mPointersNodes.begin());
181 typedef uint16_t vertex_t;
182 typedef uint16_t weight_t;
184 void findShortestPathsFromNode(
const CAmNode<T> & node, std::vector<weight_t> &minDistance, std::vector<
CAmNode<T> *> &previous)
186 typename CAmListVertices::const_iterator nIter;
187 CAmListVertices * neighbors;
188 weight_t dist, weight, v, distanceThroughU;
193 size_t n = mPointersAdjList.size();
194 std::set<std::pair<weight_t, CAmNode<T>*> > vertexQueue;
197 minDistance.resize(n, std::numeric_limits<weight_t>::max());
200 previous.resize(n, NULL);
204 while (!vertexQueue.empty())
206 dist = vertexQueue.begin()->first;
207 pU = vertexQueue.begin()->second;
208 vertexQueue.erase(vertexQueue.begin());
212 neighbors = mPointersAdjList[pU->
getIndex()];
213 nIter = neighbors->begin();
214 for (; nIter != neighbors->end(); nIter++)
221 distanceThroughU = dist + weight;
222 if (distanceThroughU < minDistance[pDstNode->
getIndex()])
224 vertexQueue.erase(std::make_pair(minDistance[v], pDstNode));
225 minDistance[v] = distanceThroughU;
227 vertexQueue.insert(std::make_pair(minDistance[v], pDstNode));
240 void constructShortestPathTo(
const CAmNode<T> & node,
const std::vector<
CAmNode<T> *> &previous, CAmListNodePtrs & result)
245 while ( (vertex = previous[vertex->
getIndex()])!=NULL )
247 result.insert(result.begin(), vertex);
262 void constructShortestPathTo(
const CAmNode<T> & node,
const std::vector<
CAmNode<T> *> &previous, std::function<
void(
const am_GraphPathPosition_e pos,
CAmNode<T> &)> cb)
267 while ( (vertex = previous[vertex->
getIndex()])!=NULL )
274 cb(GRAPH_PATH_END, *prev);
284 void findAllPaths(IterateThroughAllNodesDelegate & delegate)
286 CAmListVertices * nodes = mPointersAdjList[delegate.visited.back()->getIndex()];
287 CAmListVerticesItrConst vItr(nodes->begin());
291 for (; vItr != nodes->end(); ++vItr)
294 pNextNode = pNextVertex->getNode();
296 pNextNode->
getStatus()!=GES_NOT_VISITED ||
297 !delegate.shouldVisitNode(pNextNode)
300 if (pNextNode==delegate.destination)
302 delegate.willVisitNode(pNextNode);
304 delegate.visited.push_back(pNextNode);
306 delegate.didFindPath(delegate.visited);
308 auto last = delegate.visited.end()-1;
309 delegate.visited.erase(last);
311 delegate.didVisitNode(pNextNode);
315 vItr = nodes->begin();
317 for (; vItr != nodes->end(); ++vItr)
320 pNextNode = pNextVertex->getNode();
322 if(pNextNode->
getStatus()!=GES_NOT_VISITED ||
323 pNextNode==delegate.destination ||
324 !delegate.shouldVisitNode(pNextNode)
327 delegate.willVisitNode(pNextNode);
329 delegate.visited.push_back(pNextNode);
330 findAllPaths(delegate);
332 auto last = delegate.visited.end()-1;
333 delegate.visited.erase(last);
335 delegate.didVisitNode(pNextNode);
341 explicit CAmGraph(
const std::vector<T> &v):mStoreNodes(), mStoreAdjList(), mPointersNodes(), mPointersAdjList()
343 typedef typename std::vector<T>::const_iterator inItr;
344 inItr itr(v.begin());
346 for (; itr != v.end(); ++itr)
353 CAmGraph():mStoreNodes(), mStoreAdjList(), mPointersNodes(), mPointersAdjList(), mIsCyclic(false){};
363 return mPointersAdjList;
372 typename CAmNodeReferenceList::const_iterator itr (mPointersNodes.begin());
374 for (; itr != mPointersNodes.end(); ++itr)
376 if ((*itr)->getData() == in) {
390 const CAmListVertices * list = mPointersAdjList[edge1.
getIndex()];
391 CAmListVerticesItrConst result = std::find_if(list->begin(), list->end(), [&](
const CAmVertex<T,V> & refObject){
392 return refObject.getNode()==pEdge2;
394 if(result!=list->end())
412 size_t index = mStoreNodes.size();
413 mStoreNodes.emplace_back(in, index);
414 mStoreAdjList.emplace_back();
415 mPointersNodes.push_back(&mStoreNodes.back());
416 mPointersAdjList.push_back(&mStoreAdjList.back());
417 return mStoreNodes.back();
425 const CAmListVertices * list = mPointersAdjList[edge1.
getIndex()];
426 CAmListVerticesItr iter = std::find_if(list->begin(), list->end(), [&edge2](
const CAmVertex<T,V> & refVertex){
427 return (refVertex.getNode()==&edge2);
429 if(iter!=list->end())
439 return (refVertex.getNode()==&node);
441 auto itr = mPointersAdjList.begin();
442 for(;itr!=mPointersAdjList.end();itr++)
444 CAmListVertices * vertices = *itr;
445 auto iterVert = std::find_if(vertices->begin(), vertices->end(), comparator);
446 if(iterVert!=vertices->end())
447 vertices->erase(iterVert);
467 removeAllVerticesToNode(node);
468 mPointersAdjList.erase(mPointersAdjList.begin()+index);
469 mPointersNodes.erase(mPointersNodes.begin()+index);
470 auto iter = std::find_if(mStoreNodes.begin(), mStoreNodes.end(), [&node](
const CAmNode<T> & otherNode){
471 return &otherNode==&node;
473 if(iter!=mStoreNodes.end())
474 mStoreNodes.erase(iter);
475 updateIndexes(index);
483 CAmListVertices * list = mPointersAdjList[first.
getIndex()];
485 list->emplace_back(node, vertexData, weight);
494 return findVertex(edge1, edge2)!=NULL;
503 std::for_each(mPointersNodes.begin(), mPointersNodes.end(), [](
CAmNode<T> * refNode){
504 if(refNode->getStatus()!= GES_NOT_VISITED)
505 refNode->setStatus(GES_NOT_VISITED);
509 if(refVertex.getStatus()!= GES_NOT_VISITED)
510 refVertex.setStatus(GES_NOT_VISITED);
512 auto itr1(mPointersAdjList.begin());
513 for (; itr1 != mPointersAdjList.end(); ++itr1)
515 CAmListVertices * vertices = *itr1;
516 std::for_each(vertices->begin(), vertices->end(), action);
526 mStoreAdjList.clear();
527 mPointersAdjList.clear();
528 mPointersNodes.clear();
529 mPointersAdjList.clear();
537 std::for_each(mPointersNodes.begin(), mPointersNodes.end(), [&](
CAmNode<T> * refNode){
538 CAmListVertices * vertices = this->mPointersAdjList[refNode->getIndex()];
539 std::vector<CAmVertex<T,V>*> list;
540 std::for_each(vertices->begin(), vertices->end(), [&list](
CAmVertex<T,V> & refVertex){
541 list.push_back(&refVertex);
556 const size_t numberOfNodes = mPointersNodes.size();
560 std::vector<weight_t> min_distance;
561 std::vector<CAmNode<T>*> previous;
562 findShortestPathsFromNode(source, min_distance, previous);
564 for(
auto it=listTargets.begin(); it!=listTargets.end(); it++)
567 resultPath.emplace_back();
568 CAmListNodePtrs & path = resultPath.back();
569 constructShortestPathTo(*node, previous, path);
572 typename std::vector<CAmListNodePtrs>::iterator iter = resultPath.end();
573 resultPath.erase(--iter);
587 const size_t numberOfNodes = mPointersNodes.size();
590 std::vector<weight_t> min_distance;
591 std::vector<CAmNode<T>*> previous;
592 findShortestPathsFromNode(source, min_distance, previous);
593 constructShortestPathTo(destination, previous, resultPath);
605 const CAmListNodePtrs & listTargets,
606 std::function<
void(
const am_GraphPathPosition_e,
CAmNode<T> &)> cb )
608 const size_t numberOfNodes = mPointersNodes.size();
612 std::vector<weight_t> min_distance;
613 std::vector<CAmNode<T>*> previous;
614 findShortestPathsFromNode(source, min_distance, previous);
616 for(
auto it=listTargets.begin(); it!=listTargets.end(); it++)
619 constructShortestPathTo(*node, previous, cb);
633 std::function<
void(
const am_GraphPathPosition_e,
CAmNode<T> &)> cb )
635 const size_t numberOfNodes = mPointersNodes.size();
639 std::vector<weight_t> min_distance;
640 std::vector<CAmNode<T>*> previous;
641 findShortestPathsFromNode(source, min_distance, previous);
642 constructShortestPathTo(destination, previous, cb);
658 std::function<
bool(
const CAmNode<T> * )> cbShouldVisitNode,
659 std::function<
void(
const CAmNode<T> *)> cbWillVisitNode,
660 std::function<
void(
const CAmNode<T> *)> cbDidVisitNode,
661 std::function<
void(
const CAmNodeReferenceList & path)> cbDidFindPath)
663 IterateThroughAllNodesDelegate delegate;
664 delegate.source = &src;
665 delegate.destination = &dst;
666 delegate.shouldVisitNode = cbShouldVisitNode;
667 delegate.willVisitNode = cbWillVisitNode;
668 delegate.didVisitNode = cbDidVisitNode;
669 delegate.didFindPath = cbDidFindPath;
670 delegate.visited.push_back((
CAmNode<T>*)&src);
672 findAllPaths(delegate);
673 ((
CAmNode<T>*)&src)->setStatus(GES_NOT_VISITED);
void removeNode(const CAmNode< T > &node)
Removes the given node from the graph .
void setWeight(const uint16_t weight)
A Common-API wrapper class, which loads the common-api runtime and instantiates all necessary objects...
const CAmNode< T > * findNode(const T &in)
Returns pointer to a node which data is equal to the given.
void getShortestPath(const CAmNode< T > &source, const CAmListNodePtrs &listTargets, std::vector< CAmListNodePtrs > &resultPath)
Finds the shortest path from given node to all nodes in listTargets.
void connectNodes(const CAmNode< T > &first, const CAmNode< T > &last, const V &vertexData, const int16_t weight=1)
Connect first with last node and set user data and weight to the vertex.
const NodeData & getData() const
NodeData & getData()
Setters and getters.
const CAmVertex< T, V > * findVertex(const CAmNode< T > &edge1, const CAmNode< T > &edge2) const
Returns pointer to a vertex which two ends are equal to the given nodes.
CAmNode< T > & addNode(const T &in)
Adds a new node to the graph with given user data.
Class representing a directed or undirected graph.
CAmVertex(CAmNode< NodeData > *aNode, const VertexData &vertexData, const uint16_t weight)
bool isAnyVertex(const CAmNode< T > &edge1, const CAmNode< T > &edge2) const
Exists any vertex with two given ends.
CAmGraph(const std::vector< T > &v)
void setStatus(const am_GraphElementStatus_e s)
Setter and getter.
CAmNode< NodeData > * getNode() const
Setters and getters.
GRAPH_PATH_END am_GraphPathPosition_e
am_GraphElementStatus_e getStatus() const
GES_VISITED am_GraphElementStatus_e
CAmNode(const NodeData &in)
This class is base class for nodes and vertices.
void trace(std::function< void(const CAmNode< T > &, const std::vector< CAmVertex< T, V > * > &)> cb)
Goes through all nodes and vertices and calls the callback.
void getShortestPath(const CAmNode< T > &source, const CAmListNodePtrs &listTargets, std::function< void(const am_GraphPathPosition_e, CAmNode< T > &)> cb)
Finds the shortest path from given node to all nodes in listTargets.
const CAmListNodes & getNodes() const
void getShortestPath(const CAmNode< T > &source, const CAmNode< T > &destination, std::function< void(const am_GraphPathPosition_e, CAmNode< T > &)> cb)
Finds the shortest path between two given nodes.
typedef GRAPH_PATH_MIDDLE
void clear()
Clears all nodes and vertices.
void reset()
Sets the status of all nodes and vertices to GES_NOT_VISITED.
void removeNode(const T &in)
Removes a node with given user data .
uint16_t getIndex() const
void getAllPaths(CAmNode< T > &src, CAmNode< T > &dst, std::function< bool(const CAmNode< T > *)> cbShouldVisitNode, std::function< void(const CAmNode< T > *)> cbWillVisitNode, std::function< void(const CAmNode< T > *)> cbDidVisitNode, std::function< void(const CAmNodeReferenceList &path)> cbDidFindPath)
Finds all possible paths between two given nodes.
uint16_t getWeight() const
void getShortestPath(const CAmNode< T > &source, const CAmNode< T > &destination, CAmListNodePtrs &resultPath)
Finds the shortest path between two nodes.
const CAmVertexReferenceList & getVertexList() const
void removeVertex(const CAmNode< T > &edge1, const CAmNode< T > &edge2)
Removes a vertex with two ends equal to the given nodes .
void removeAllVerticesToNode(const CAmNode< T > &node)
Removes all vertices to given node .
void setIndex(uint16_t index)
CAmNode(const NodeData &in, const uint16_t index)