93 void setIndex(uint16_t index) { mIndex = index; }
99 VertexData mVertexData;
103 mpNode(aNode), mVertexData(vertexData), mWeight(weight) { };
109 VertexData &
getData() {
return mVertexData; }
111 void setWeight(
const uint16_t weight) { mWeight=weight; }
120 typedef typename std::vector<CAmNode<T>*> CAmListNodePtrs;
121 typedef typename std::list<CAmVertex<T,V>> CAmListVertices;
122 typedef typename std::list<CAmVertex<T,V>>::iterator CAmListVerticesItr;
123 typedef typename std::list<CAmVertex<T,V>>::const_iterator CAmListVerticesItrConst;
124 typedef typename std::list<CAmListVertices> CAmNodesAdjList;
125 typedef typename std::list<CAmListVertices>::iterator CAmNodesAdjListItr;
126 typedef typename std::list<CAmListVertices>::const_iterator CAmNodesAdjListItrConst;
127 typedef typename std::list<CAmNode<T>> CAmListNodes;
128 typedef typename std::list<CAmNode<T>>::iterator CAmListNodesItr;
129 typedef typename std::list<CAmNode<T>>::const_iterator CAmListNodesItrConst;
130 typedef typename std::vector<CAmNode<T>*> CAmNodeReferenceList;
131 typedef typename std::vector<CAmListVertices*> CAmVertexReferenceList;
133 CAmListNodes mStoreNodes;
134 CAmNodesAdjList mStoreAdjList;
135 CAmNodeReferenceList mPointersNodes;
136 CAmVertexReferenceList mPointersAdjList;
144 void updateIndexes(
const int16_t fromIndex)
146 if( fromIndex<mPointersNodes.size() )
148 for(
auto iter = mPointersNodes.begin()+fromIndex; iter!=mPointersNodes.end(); iter++)
149 (*iter)->setIndex(iter-mPointersNodes.begin());
162 typedef uint16_t vertex_t;
163 typedef uint16_t weight_t;
165 void findShortestsPathsFromNode(
const CAmNode<T> & node, std::vector<weight_t> &minDistance, std::vector<
CAmNode<T> *> &previous)
167 typename CAmListVertices::const_iterator nIter;
168 CAmListVertices * neighbors;
169 weight_t dist, weight, v, distanceThroughU;
174 size_t n = mPointersAdjList.size();
175 std::set<std::pair<weight_t, CAmNode<T>*> > vertexQueue;
178 minDistance.resize(n, std::numeric_limits<weight_t>::max());
181 previous.resize(n, NULL);
185 while (!vertexQueue.empty())
187 dist = vertexQueue.begin()->first;
188 pU = vertexQueue.begin()->second;
189 vertexQueue.erase(vertexQueue.begin());
193 neighbors = mPointersAdjList[pU->
getIndex()];
194 nIter = neighbors->begin();
195 for (; nIter != neighbors->end(); nIter++)
202 distanceThroughU = dist + weight;
203 if (distanceThroughU < minDistance[pDstNode->
getIndex()])
205 vertexQueue.erase(std::make_pair(minDistance[v], pDstNode));
206 minDistance[v] = distanceThroughU;
208 vertexQueue.insert(std::make_pair(minDistance[v], pDstNode));
221 void constructShortestPathTo(
const CAmNode<T> & node,
const std::vector<
CAmNode<T> *> &previous, CAmListNodePtrs & result)
226 while ( (vertex = previous[vertex->
getIndex()])!=NULL )
228 result.insert(result.begin(), vertex);
248 while ( (vertex = previous[vertex->
getIndex()])!=NULL )
255 cb(GRAPH_PATH_END, *prev);
266 void goThroughAllPaths(
const CAmNode<T> & dst, std::vector<
CAmNode<T>*> & visited, std::function<
void(
const CAmNodeReferenceList & path)> cb)
268 CAmListVertices * nodes = mPointersAdjList[visited.back()->getIndex()];
269 CAmListVerticesItrConst vItr(nodes->begin());
270 for (; vItr != nodes->end(); ++vItr)
278 visited.push_back(vertex.
getNode());
282 auto last = visited.end()-1;
288 vItr = nodes->begin();
290 for (; vItr != nodes->end(); ++vItr)
296 visited.push_back(vertex.
getNode());
297 goThroughAllPaths(dst, visited, cb);
299 auto last = visited.end()-1;
306 explicit CAmGraph(
const std::vector<T> &v):mStoreNodes(), mStoreAdjList(), mPointersNodes(), mPointersAdjList()
308 typedef typename std::vector<T>::const_iterator inItr;
309 inItr itr(v.begin());
311 for (; itr != v.end(); ++itr)
318 CAmGraph():mStoreNodes(), mStoreAdjList(), mPointersNodes(), mPointersAdjList(), mIsCyclic(false){};
328 return mPointersAdjList;
337 typename CAmNodeReferenceList::const_iterator itr (mPointersNodes.begin());
339 for (; itr != mPointersNodes.end(); ++itr)
341 if ((*itr)->getData() == in) {
355 const CAmListVertices * list = mPointersAdjList[edge1.
getIndex()];
356 CAmListVerticesItrConst result = std::find_if(list->begin(), list->end(), [&](
const CAmVertex<T,V> & refObject){
357 return refObject.getNode()==pEdge2;
359 if(result!=list->end())
377 size_t index = mStoreNodes.size();
378 mStoreNodes.emplace_back(in, index);
379 mStoreAdjList.emplace_back();
380 mPointersNodes.push_back(&mStoreNodes.back());
381 mPointersAdjList.push_back(&mStoreAdjList.back());
382 return mStoreNodes.back();
390 const CAmListVertices * list = mPointersAdjList[edge1.
getIndex()];
391 CAmListVerticesItr iter = std::find_if(list->begin(), list->end(), [&edge2](
const CAmVertex<T,V> & refVertex){
392 return (refVertex.getNode()==&edge2);
394 if(iter!=list->end())
404 return (refVertex.getNode()==&node);
406 auto itr = mPointersAdjList.begin();
407 for(;itr!=mPointersAdjList.end();itr++)
409 CAmListVertices * vertices = *itr;
410 auto iterVert = std::find_if(vertices->begin(), vertices->end(), comparator);
411 if(iterVert!=vertices->end())
412 vertices->erase(iterVert);
433 mPointersAdjList.erase(mPointersAdjList.begin()+index);
434 mPointersNodes.erase(mPointersNodes.begin()+index);
435 auto iter = std::find_if(mStoreNodes.begin(), mStoreNodes.end(), [&node](
const CAmNode<T> & otherNode){
436 return &otherNode==&node;
438 if(iter!=mStoreNodes.end())
439 mStoreNodes.erase(iter);
440 updateIndexes(index);
448 CAmListVertices * list = mPointersAdjList[first.
getIndex()];
450 list->emplace_back(node, vertexData, weight);
468 std::for_each(mPointersNodes.begin(), mPointersNodes.end(), [](
CAmNode<T> * refNode){
469 if(refNode->getStatus()!= GES_NOT_VISITED)
470 refNode->setStatus(GES_NOT_VISITED);
474 if(refVertex.getStatus()!= GES_NOT_VISITED)
475 refVertex.setStatus(GES_NOT_VISITED);
477 auto itr1(mPointersAdjList.begin());
478 for (; itr1 != mPointersAdjList.end(); ++itr1)
480 CAmListVertices * vertices = *itr1;
481 std::for_each(vertices->begin(), vertices->end(), action);
491 mStoreAdjList.clear();
492 mPointersAdjList.clear();
493 mPointersNodes.clear();
494 mPointersAdjList.clear();
502 std::for_each(mPointersNodes.begin(), mPointersNodes.end(), [&](
CAmNode<T> * refNode){
503 CAmListVertices * vertices = this->mPointersAdjList[refNode->getIndex()];
504 std::vector<CAmVertex<T,V>*> list;
505 std::for_each(vertices->begin(), vertices->end(), [&list](
CAmVertex<T,V> & refVertex){
506 list.push_back(&refVertex);
521 const size_t numberOfNodes = mPointersNodes.size();
525 std::vector<weight_t> min_distance;
526 std::vector<CAmNode<T>*> previous;
527 findShortestsPathsFromNode(source, min_distance, previous);
529 for(
auto it=listTargets.begin(); it!=listTargets.end(); it++)
532 resultPath.emplace_back();
533 CAmListNodePtrs & path = resultPath.back();
534 constructShortestPathTo(*node, previous, path);
537 typename std::vector<CAmListNodePtrs>::iterator iter = resultPath.end();
538 resultPath.erase(--iter);
552 const size_t numberOfNodes = mPointersNodes.size();
555 std::vector<weight_t> min_distance;
556 std::vector<CAmNode<T>*> previous;
557 findShortestsPathsFromNode(source, min_distance, previous);
558 constructShortestPathTo(destination, previous, resultPath);
570 const CAmListNodePtrs & listTargets,
573 const size_t numberOfNodes = mPointersNodes.size();
577 std::vector<weight_t> min_distance;
578 std::vector<CAmNode<T>*> previous;
579 findShortestsPathsFromNode(source, min_distance, previous);
581 for(
auto it=listTargets.begin(); it!=listTargets.end(); it++)
584 constructShortestPathTo(*node, previous, cb);
600 const size_t numberOfNodes = mPointersNodes.size();
604 std::vector<weight_t> min_distance;
605 std::vector<CAmNode<T>*> previous;
606 findShortestsPathsFromNode(source, min_distance, previous);
607 constructShortestPathTo(destination, previous, cb);
620 CAmNodeReferenceList visited;
623 goThroughAllPaths(dst, visited, cb);
void removeNode(const CAmNode< T > &node)
Removes the given node from the graph .
void setWeight(const uint16_t weight)
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.
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(const CAmNode< T > &src, const CAmNode< T > &dst, std::function< void(const CAmNodeReferenceList &path)> cb)
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)