From 57c2f4ea0148287d0bcea913cb34ba716489df4b Mon Sep 17 00:00:00 2001 From: Aleksandar Donchev Date: Tue, 26 Aug 2014 18:15:19 +0200 Subject: * Converter Implementation . Signed-off-by: Christian Linke --- AudioManagerDaemon/include/CAmGraph.h | 622 ++++++++++++++++++++++++++++++++++ 1 file changed, 622 insertions(+) create mode 100644 AudioManagerDaemon/include/CAmGraph.h (limited to 'AudioManagerDaemon/include/CAmGraph.h') diff --git a/AudioManagerDaemon/include/CAmGraph.h b/AudioManagerDaemon/include/CAmGraph.h new file mode 100644 index 0000000..16783e6 --- /dev/null +++ b/AudioManagerDaemon/include/CAmGraph.h @@ -0,0 +1,622 @@ +/** + * Copyright (C) 2012, BMW AG + * + * This file is part of GENIVI Project AudioManager. + * + * Contributions are licensed to the GENIVI Alliance under one or more + * Contribution License Agreements. + * + * \copyright + * This Source Code Form is subject to the terms of the + * Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with + * this file, You can obtain one at http://mozilla.org/MPL/2.0/. + * + * + * \author Aleksandar Donchev, aleksander.donchev@partner.bmw.de BMW 2014 + * + * \file CAmGraph.h + * For further information see http://www.genivi.org/. + * + */ + +#ifndef GRAPH_H +#define GRAPH_H + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + + +namespace am +{ + /** + * Graph element status. + */ + typedef enum:uint8_t + { + GES_NOT_VISITED, + GES_IN_PROGRESS, + GES_VISITED + }am_GraphElementStatus_e; + + /** + * Callback parameter telling on which position in the path we are. + */ + typedef enum:uint8_t + { + GRAPH_PATH_START, //at the beginning of the path + GRAPH_PATH_MIDDLE, //in middle of the path + GRAPH_PATH_END //at the end of the path + }am_GraphPathPosition_e; + + + /** + * This class is base class for nodes and vertices. + */ + class CAmGraphElement + { + am_GraphElementStatus_e mStatus; //!< item status + public: + CAmGraphElement(): mStatus(GES_NOT_VISITED) { }; + ~CAmGraphElement() { }; + /** + * Setter and getter. + */ + void setStatus(const am_GraphElementStatus_e s) { mStatus = s; }; + am_GraphElementStatus_e getStatus() const { return mStatus; }; + }; + + template class CAmNode : public CAmGraphElement + { + uint16_t mIndex; //!< uint16_t index used for direct access + NodeData mData; //!< NodeData user data + public: + CAmNode(const NodeData & in):CAmGraphElement(), mIndex(0), mData(in) { }; + CAmNode(const NodeData & in, const uint16_t index):CAmGraphElement(), mIndex(index), mData(in) { }; + ~CAmNode() { }; + /** + * Setters and getters. + */ + NodeData & getData() { return mData; } + uint16_t getIndex() const { return mIndex; } + void setIndex(uint16_t index) { mIndex = index; } + }; + + template class CAmVertex : public CAmGraphElement + { + CAmNode* mpNode; //!< CAmNode* pointer to a node + VertexData mVertexData; //!< VertexData vertex user data + uint16_t mWeight; //!< uint16_t a positive value used in the shortest path algorithms + public: + CAmVertex(CAmNode *aNode, const VertexData & vertexData, const uint16_t weight):CAmGraphElement(), + mpNode(aNode), mVertexData(vertexData), mWeight(weight) { }; + ~CAmVertex() { }; + /** + * Setters and getters. + */ + CAmNode* getNode() const { return mpNode; } + VertexData & getData() { return mVertexData; } + uint16_t getWeight() const { return mWeight; } + void setWeight(const uint16_t weight) { mWeight=weight; } + }; + + /** + * Class representing a directed or undirected graph. It contains nodes and connections. + * T, V are types for custom user data. + */ + template class CAmGraph + { + typedef typename std::vector*> CAmListNodePtrs; + typedef typename std::list> CAmListVertices; + typedef typename std::list>::iterator CAmListVerticesItr; + typedef typename std::list>::const_iterator CAmListVerticesItrConst; + typedef typename std::list CAmNodesAdjList; + typedef typename std::list::iterator CAmNodesAdjListItr; + typedef typename std::list::const_iterator CAmNodesAdjListItrConst; + typedef typename std::list> CAmListNodes; + typedef typename std::list>::iterator CAmListNodesItr; + typedef typename std::list>::const_iterator CAmListNodesItrConst; + typedef typename std::vector*> CAmNodeReferenceList; + typedef typename std::vector CAmVertexReferenceList; + + CAmListNodes mStoreNodes; //!< CAmListNodes list with all nodes + CAmNodesAdjList mStoreAdjList; //!< CAmNodesAdjList adjacency list + CAmNodeReferenceList mPointersNodes; //!< CAmNodeReferenceList vector with pointers to nodes for direct access + CAmVertexReferenceList mPointersAdjList; //!< CAmVertexReferenceList vector with pointers to vertices for direct access + bool mIsCyclic; //!< bool the graph has cycles or not + + /** + * Updates the node indexes after adding or removing nodes. + * + * @param fromIndex updates all nodes from given index. + */ + void updateIndexes(const int16_t fromIndex) + { + if( fromIndexsetIndex(iter-mPointersNodes.begin()); + } + } + + + /** + * Finds the shortest path and the minimal weights from given node. + * + * @param node start node. + * @param minDistance vector with all result distances. + * @param previous vector with previous nodes. + */ + + typedef uint16_t vertex_t; + typedef uint16_t weight_t; + + void findShortestsPathsFromNode(const CAmNode & node, std::vector &minDistance, std::vector *> &previous) + { + typename CAmListVertices::const_iterator nIter; + CAmListVertices * neighbors; + weight_t dist, weight, v, distanceThroughU; + CAmNode* pU; + CAmVertex * pVertex; + CAmNode *pDstNode; + + size_t n = mPointersAdjList.size(); + std::set*> > vertexQueue; + + minDistance.clear(); + minDistance.resize(n, std::numeric_limits::max()); + minDistance[node.getIndex()] = 0; + previous.clear(); + previous.resize(n, NULL); + + vertexQueue.insert(std::make_pair(minDistance[node.getIndex()], (CAmNode*)&node)); + + while (!vertexQueue.empty()) + { + dist = vertexQueue.begin()->first; + pU = vertexQueue.begin()->second; + vertexQueue.erase(vertexQueue.begin()); + //todo: terminate the search at this position if you want the path to a target node ( if(pU==target)break; ) + + // Visit each edge exiting u + neighbors = mPointersAdjList[pU->getIndex()]; + nIter = neighbors->begin(); + for (; nIter != neighbors->end(); nIter++) + { + pVertex = (CAmVertex *)&(*nIter); + pDstNode = pVertex->getNode(); + + v = pDstNode->getIndex(); + weight = pVertex->getWeight(); + distanceThroughU = dist + weight; + if (distanceThroughU < minDistance[pDstNode->getIndex()]) + { + vertexQueue.erase(std::make_pair(minDistance[v], pDstNode)); + minDistance[v] = distanceThroughU; + previous[v] = pU; + vertexQueue.insert(std::make_pair(minDistance[v], pDstNode)); + } + } + } + } + + /** + * Constructs a path to given node after findShortestsPathsFromNode has been called. + * + * @param node end node. + * @param previous vector with previous nodes. + * @param result result path. + */ + void constructShortestPathTo(const CAmNode & node, const std::vector *> &previous, CAmListNodePtrs & result) + { + CAmNode * vertex = (CAmNode *)&node; + + int i=0; + while ( (vertex = previous[vertex->getIndex()])!=NULL ) + { + result.insert(result.begin(), vertex); + i++; + } + if(i) + result.push_back((CAmNode *)&node); + } + + /** + * Calls a function with every node from this path after findShortestsPathsFromNode has been called. + * The construction of the path is delegated to the caller. + * + * @param node end node. + * @param previous vector with previous nodes. + * @param cb callback which is mostly used for constructing. + */ + void constructShortestPathTo(const CAmNode & node, const std::vector *> &previous, std::function &)> cb) + { + CAmNode * vertex = (CAmNode *)&node; + CAmNode * prev = vertex; + int i=0; + while ( (vertex = previous[vertex->getIndex()])!=NULL ) + { + cb(i==0?GRAPH_PATH_START:GRAPH_PATH_MIDDLE, *prev); + prev = vertex; + i++; + } + if(i) + cb(GRAPH_PATH_END, *prev); + } + + /** + * Generates list with all possible paths to given destination node after findShortestsPathsFromNode has been called. + * Finding paths is observed through the callback. The caller is informed after a new path has been found. + * + * @param dst end node. + * @param visited vector with current path. + * @param cb callback which is mostly used for constructing. + */ + void goThroughAllPaths(const CAmNode & dst, std::vector*> & visited, std::function cb) + { + CAmListVertices * nodes = mPointersAdjList[visited.back()->getIndex()]; + CAmListVerticesItrConst vItr(nodes->begin()); + for (; vItr != nodes->end(); ++vItr) + { + const CAmVertex & vertex = (*vItr); + if(vertex.getNode()->getStatus()!=GES_NOT_VISITED) + continue; + if (vertex.getNode()==&dst) + { + vertex.getNode()->setStatus(GES_IN_PROGRESS); + visited.push_back(vertex.getNode()); + //notify observer + cb(visited); + //remove last node from the list + auto last = visited.end()-1; + visited.erase(last); + vertex.getNode()->setStatus(GES_NOT_VISITED); + break; + } + } + vItr = nodes->begin(); + //bfs like loop + for (; vItr != nodes->end(); ++vItr) + { + const CAmVertex & vertex = (*vItr); + if(vertex.getNode()->getStatus()!=GES_NOT_VISITED||vertex.getNode()==&dst) + continue; + vertex.getNode()->setStatus(GES_IN_PROGRESS); + visited.push_back(vertex.getNode()); + goThroughAllPaths(dst, visited, cb); + //remove last node from the list + auto last = visited.end()-1; + visited.erase(last); + vertex.getNode()->setStatus(GES_NOT_VISITED); + } + reset(); + } + + public: + explicit CAmGraph(const std::vector &v):mStoreNodes(), mStoreAdjList(), mPointersNodes(), mPointersAdjList() + { + typedef typename std::vector::const_iterator inItr; + inItr itr(v.begin()); + + for (; itr != v.end(); ++itr) + { + addNode(*itr); + } + + mIsCyclic = false; + }; + CAmGraph():mStoreNodes(), mStoreAdjList(), mPointersNodes(), mPointersAdjList(), mIsCyclic(false){}; + ~CAmGraph(){} + + const CAmListNodes & getNodes() const + { + return mStoreNodes; + } + + /** + * Returns pointer to a node which data is equal to the given. + * @return pointer to a node or NULL. + */ + const CAmNode* findNode(const T & in) + { + typename CAmNodeReferenceList::const_iterator itr (mPointersNodes.begin()); + + for (; itr != mPointersNodes.end(); ++itr) + { + if ((*itr)->getData() == in) { + return (*itr); + } + } + return NULL; + } + + /** + * Returns pointer to a vertex which two ends are equal to the given nodes. + * @return pointer to a vertex or NULL. + */ + const CAmVertex* findVertex(const CAmNode & edge1, const CAmNode & edge2) const + { + const CAmNode * pEdge2 = (CAmNode *)&edge2; + const CAmListVertices * list = mPointersAdjList[edge1.getIndex()]; + CAmListVerticesItrConst result = std::find_if(list->begin(), list->end(), [&](const CAmVertex & refObject){ + return refObject.getNode()==pEdge2; + }); + if(result!=list->end()) + return (CAmVertex*)&(*result); + + return NULL; + } + + bool hasCycles() const + { + return mIsCyclic; + } + + + /** + * Adds a new node to the graph with given user data. + * @return reference to the newly inserted node. + */ + CAmNode & addNode(const T & in) + { + size_t index = mStoreNodes.size(); + mStoreNodes.emplace_back(in, index); + mStoreAdjList.emplace_back(); + mPointersNodes.push_back(&mStoreNodes.back()); + mPointersAdjList.push_back(&mStoreAdjList.back()); + return mStoreNodes.back(); + } + + /** + * Removes a vertex with two ends equal to the given nodes . + */ + void removeVertex(const CAmNode & edge1, const CAmNode & edge2) + { + const CAmListVertices * list = mPointersAdjList[edge1.getIndex()]; + CAmListVerticesItr iter = std::find_if(list->begin(), list->end(), [&edge2](const CAmVertex & refVertex){ + return (refVertex.getNode()==&edge2); + }); + if(iter!=list->end()) + list->erase(iter); + } + + /** + * Removes all vertices to given node . + */ + void removeAllVerticesToNode(const CAmNode & node) + { + auto comparator = [&node](const CAmVertex & refVertex){ + return (refVertex.getNode()==&node); + }; + auto itr = mPointersAdjList.begin(); + for(;itr!=mPointersAdjList.end();itr++) + { + CAmListVertices * vertices = *itr; + auto iterVert = std::find_if(vertices->begin(), vertices->end(), comparator); + if(iterVert!=vertices->end()) + vertices->erase(iterVert); + } + } + + /** + * Removes a node with given user data . + */ + void removeNode(const T & in) + { + CAmNode * node = findNode(in); + if(node!=NULL) + removeNode(*node); + } + + /** + * Removes the given node from the graph . + */ + void removeNode(const CAmNode & node) + { + uint16_t index = node.getIndex(); + removeAllVerticesToNode(node); + mPointersAdjList.erase(mPointersAdjList.begin()+index); + mPointersNodes.erase(mPointersNodes.begin()+index); + auto iter = std::find_if(mStoreNodes.begin(), mStoreNodes.end(), [&node](const CAmNode & otherNode){ + return &otherNode==&node; + }); + if(iter!=mStoreNodes.end()) + mStoreNodes.erase(iter); + updateIndexes(index); + } + + /** + * Connect first with last node and set user data and weight to the vertex. + */ + void connectNodes(const CAmNode & first, const CAmNode & last, const V & vertexData, const int16_t weight = 1) + { + CAmListVertices * list = mPointersAdjList[first.getIndex()]; + CAmNode * node = mPointersNodes[last.getIndex()]; + list->emplace_back(node, vertexData, weight); + } + + /** + * Exists any vertex with two given ends. + * @return TRUE on successfully changed ID. + */ + bool isAnyVertex(const CAmNode & edge1, const CAmNode & edge2) const + { + return findVertex(edge1, edge2)!=NULL; + } + + /** + * Sets the status of all nodes and vertices to GES_NOT_VISITED. + */ + void reset() + { + // set all nodes to GES_NOT_VISITED + std::for_each(mPointersNodes.begin(), mPointersNodes.end(), [](CAmNode * refNode){ + if(refNode->getStatus()!= GES_NOT_VISITED) + refNode->setStatus(GES_NOT_VISITED); + }); + // set all vertices to GES_NOT_VISITED + auto action = [](CAmVertex & refVertex){ + if(refVertex.getStatus()!= GES_NOT_VISITED) + refVertex.setStatus(GES_NOT_VISITED); + }; + auto itr1(mPointersAdjList.begin()); + for (; itr1 != mPointersAdjList.end(); ++itr1) + { + CAmListVertices * vertices = *itr1; + std::for_each(vertices->begin(), vertices->end(), action); + } + } + + /** + * Clears all nodes and vertices. + */ + void clear() + { + mStoreNodes.clear(); + mStoreAdjList.clear(); + mPointersAdjList.clear(); + mPointersNodes.clear(); + mPointersAdjList.clear(); + } + + /** + * Goes through all nodes and vertices and calls the callback. + */ + void trace(std::function &, const std::vector*> &)> cb) + { + std::for_each(mPointersNodes.begin(), mPointersNodes.end(), [&](CAmNode * refNode){ + CAmListVertices * vertices = mPointersAdjList[refNode->getIndex()]; + std::vector*> list; + std::for_each(vertices->begin(), vertices->end(), [&list](CAmVertex & refVertex){ + list.push_back(&refVertex); + }); + cb(*refNode, list); + }); + } + + /** + * Finds the shortest path from given node to all nodes in listTargets. + * + * @param source start node. + * @param listTargets destination nodes. + * @param resultPath list with all shortest paths. + */ + void getShortestPath(const CAmNode & source, const CAmListNodePtrs & listTargets, std::vector & resultPath ) + { + const size_t numberOfNodes = mPointersNodes.size(); + if(numberOfNodes==0) + return; + + std::vector min_distance; + std::vector*> previous; + findShortestsPathsFromNode(source, min_distance, previous); + + for(auto it=listTargets.begin(); it!=listTargets.end(); it++) + { + CAmNode *node = *it; + resultPath.emplace_back(); + CAmListNodePtrs & path = resultPath.back(); + constructShortestPathTo(*node, previous, path); + if(path.empty()) + { + typename std::vector::iterator iter = resultPath.end(); + resultPath.erase(--iter); + } + } + } + + /** + * Finds the shortest path between two nodes. + * + * @param source start node. + * @param destination destination node. + * @param resultPath list with the found shortest paths. + */ + void getShortestPath(const CAmNode & source, const CAmNode & destination, CAmListNodePtrs & resultPath ) + { + const size_t numberOfNodes = mPointersNodes.size(); + if(numberOfNodes==0) + return; + std::vector min_distance; + std::vector*> previous; + findShortestsPathsFromNode(source, min_distance, previous); + constructShortestPathTo(destination, previous, resultPath); + } + + /** + * Finds the shortest path from given node to all nodes in listTargets. + * Delegates the construction of the path to the caller. + * + * @param source start node. + * @param listTargets destination nodes. + * @param cb callabck. + */ + void getShortestPath(const CAmNode & source, + const CAmListNodePtrs & listTargets, + std::function &)> cb ) + { + const size_t numberOfNodes = mPointersNodes.size(); + if(numberOfNodes==0) + return; + + std::vector min_distance; + std::vector*> previous; + findShortestsPathsFromNode(source, min_distance, previous); + + for(auto it=listTargets.begin(); it!=listTargets.end(); it++) + { + CAmNode* node = *it; + constructShortestPathTo(*node, previous, cb); + } + } + + /** + * Finds the shortest path between two given nodes. + * Delegates the construction of the path to the caller. + * + * @param source start node. + * @param destination destination node. + * @param cb callabck. + */ + void getShortestPath(const CAmNode & source, + const CAmNode & destination, + std::function &)> cb ) + { + const size_t numberOfNodes = mPointersNodes.size(); + if(numberOfNodes==0) + return; + + std::vector min_distance; + std::vector*> previous; + findShortestsPathsFromNode(source, min_distance, previous); + constructShortestPathTo(destination, previous, cb); + } + + /** + * Finds all possible paths between two given nodes. + * Delegates the construction of the path to the caller. + * + * @param src start node. + * @param dst destination node. + * @param cb callabck. + */ + void getAllPaths(const CAmNode & src, const CAmNode & dst, std::function cb) + { + CAmNodeReferenceList visited; + visited.push_back((CAmNode*)&src); + goThroughAllPaths(dst, visited, cb); + } + }; + +} + +#endif -- cgit v1.2.1