00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #ifndef MRPT_GRAPHS_H
00029 #define MRPT_GRAPHS_H
00030
00031 #include <mrpt/math/utils.h>
00032 #include <set>
00033
00034
00035
00036
00037 namespace mrpt
00038 {
00039 namespace math
00040 {
00041
00042
00043
00044
00045 template<class TYPE_EDGES>
00046 class CDirectedGraph
00047 {
00048 public:
00049 typedef TYPE_EDGES type_edges;
00050 typedef std::map< std::pair<size_t,size_t>, TYPE_EDGES > type_edges_map;
00051 typedef typename type_edges_map::const_iterator const_iterator;
00052 typedef typename type_edges_map::iterator iterator;
00053
00054
00055 type_edges_map edges;
00056
00057 CDirectedGraph(const type_edges_map &obj) : edges(obj) { }
00058 CDirectedGraph() : edges() {}
00059
00060 size_t edgeCount() const { return edges.size(); }
00061 void clearEdges() { edges.clear(); }
00062
00063 iterator begin() { return edges.begin(); }
00064 iterator end() { return edges.end(); }
00065 const_iterator begin() const { return edges.begin(); }
00066 const_iterator end() const { return edges.end(); }
00067
00068
00069 void insertEdge(size_t from_nodeID, size_t to_nodeID,const TYPE_EDGES &edge_value )
00070 { edges.insert(std::make_pair(std::make_pair(from_nodeID,to_nodeID),edge_value) ); }
00071
00072
00073 bool edgeExists(size_t from_nodeID, size_t to_nodeID) const
00074 { return edges.find(std::make_pair(from_nodeID,to_nodeID))!=edges.end(); }
00075
00076
00077
00078
00079 TYPE_EDGES & getEdge(size_t from_nodeID, size_t to_nodeID)
00080 {
00081 iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
00082 if (it==edges.end())
00083 THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
00084 else return it->second;
00085 }
00086
00087
00088
00089
00090 const TYPE_EDGES & getEdge(size_t from_nodeID, size_t to_nodeID) const
00091 {
00092 const_iterator it = edges.find(std::make_pair(from_nodeID,to_nodeID));
00093 if (it==edges.end())
00094 THROW_EXCEPTION( format("Edge %u->%u does not exist",(unsigned)from_nodeID,(unsigned)to_nodeID) )
00095 else return it->second;
00096 }
00097
00098
00099
00100 void eraseEdge(size_t from_nodeID, size_t to_nodeID)
00101 {
00102 edges.erase(std::make_pair(from_nodeID,to_nodeID));
00103 }
00104
00105
00106
00107 void getAllNodes( std::set<size_t> &lstNode_IDs) const
00108 {
00109 lstNode_IDs.clear();
00110 for (typename type_edges_map::const_iterator it=edges.begin();it!=edges.end();++it)
00111 {
00112 lstNode_IDs.insert(it->first.first);
00113 lstNode_IDs.insert(it->first.second);
00114 }
00115 }
00116
00117
00118 void getNeighborsOf(const size_t nodeID, std::set<size_t> &neighborIDs) const
00119 {
00120 neighborIDs.clear();
00121 for (typename type_edges_map::const_iterator it=edges.begin();it!=edges.end();++it)
00122 {
00123 if (it->first.first==nodeID)
00124 neighborIDs.insert(it->first.second);
00125 else if (it->first.second==nodeID)
00126 neighborIDs.insert(it->first.first);
00127 }
00128 }
00129
00130 };
00131
00132 }
00133 }
00134 #endif