Main MRPT website > C++ reference
MRPT logo
Public Types | Public Member Functions | Public Attributes

mrpt::math::CDirectedGraph< TYPE_EDGES > Class Template Reference


Detailed Description

template<class TYPE_EDGES>
class mrpt::math::CDirectedGraph< TYPE_EDGES >

A directed graph with the argument of the template specifying the type of the annotations in the edges.

This class only keeps a list of edges (in the member edges), so there is no information stored for each node but its existence referred by a node_ID.

Note that edges are stored as a std::multimap<> to allow multiple edges between the same pair of nodes.

See also:
mrpt::math::CDijkstra, mrpt::poses::CNetworkOfPoses, mrpt::math::CDirectedTree

Definition at line 54 of file graphs.h.

#include <mrpt/math/graphs.h>

Inheritance diagram for mrpt::math::CDirectedGraph< TYPE_EDGES >:
Inheritance graph
[legend]

List of all members.

Public Types

typedef TYPE_EDGES edge_t
 The type of the graph edges.
typedef
mrpt::aligned_containers
< TPairNodeIDs, edge_t >
::multimap_t 
edges_map_t
 The type of the member edges.
typedef edges_map_t::iterator iterator
typedef edges_map_t::const_iterator const_iterator

Public Member Functions

 CDirectedGraph (const edges_map_t &obj)
 Copy constructor from a multimap<pair< >, >
 CDirectedGraph ()
 Default constructor.
iterator begin ()
iterator end ()
const_iterator begin () const
const_iterator end () const
Edges/nodes utility methods
size_t edgeCount () const
 The number of edges in the graph.
void clearEdges ()
 Erase all edges.
void insertEdge (TNodeID from_nodeID, TNodeID to_nodeID, const edge_t &edge_value)
 Insert an edge (from -> to) with the given edge value.
void insertEdgeAtEnd (TNodeID from_nodeID, TNodeID to_nodeID, const edge_t &edge_value)
 Insert an edge (from -> to) with the given edge value (more efficient version to be called if you know that the end will go at the end of the sorted std::multimap).
bool edgeExists (TNodeID from_nodeID, TNodeID to_nodeID) const
 Test is the given directed edge exists.
edge_tgetEdge (TNodeID from_nodeID, TNodeID to_nodeID)
 Return a reference to the content of a given edge.
const edge_tgetEdge (TNodeID from_nodeID, TNodeID to_nodeID) const
 Return a reference to the content of a given edge.
std::pair< iterator, iteratorgetEdges (TNodeID from_nodeID, TNodeID to_nodeID)
 Return a pair<first,last> of iterators to the range of edges between two given nodes.
std::pair< const_iterator,
const_iterator
getEdges (TNodeID from_nodeID, TNodeID to_nodeID) const
 Return a pair<first,last> of const iterators to the range of edges between two given nodes.
void eraseEdge (TNodeID from_nodeID, TNodeID to_nodeID)
 Erase all edges between the given nodes (it has no effect if no edge existed)
void getAllNodes (std::set< TNodeID > &lstNode_IDs) const
 Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list of edges.
std::set< TNodeIDgetAllNodes () const
 Less efficient way to get all nodes that returns a copy of the set object.
size_t countDifferentNodesInEdges () const
 Count how many different node IDs appear in the graph edges.
void getNeighborsOf (const TNodeID nodeID, std::set< TNodeID > &neighborIDs) const
 Return the list of all neighbors of "nodeID", by creating a list of their node IDs.
template<class MAP_NODEID_SET_NODEIDS >
void getAdjacencyMatrix (MAP_NODEID_SET_NODEIDS &outAdjacency) const
 Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge direction) This is a much more efficient method than calling getNeighborsOf() for each node in the graph.

Public Attributes

edges_map_t edges
 The public member with the directed edges in the graph.

Member Typedef Documentation

template<class TYPE_EDGES>
typedef edges_map_t::const_iterator mrpt::math::CDirectedGraph< TYPE_EDGES >::const_iterator

Definition at line 60 of file graphs.h.

template<class TYPE_EDGES>
typedef TYPE_EDGES mrpt::math::CDirectedGraph< TYPE_EDGES >::edge_t

The type of the graph edges.

Definition at line 57 of file graphs.h.

template<class TYPE_EDGES>
typedef mrpt::aligned_containers<TPairNodeIDs,edge_t>::multimap_t mrpt::math::CDirectedGraph< TYPE_EDGES >::edges_map_t

The type of the member edges.

Definition at line 58 of file graphs.h.

template<class TYPE_EDGES>
typedef edges_map_t::iterator mrpt::math::CDirectedGraph< TYPE_EDGES >::iterator

Definition at line 59 of file graphs.h.


Constructor & Destructor Documentation

template<class TYPE_EDGES>
mrpt::math::CDirectedGraph< TYPE_EDGES >::CDirectedGraph ( const edges_map_t obj) [inline]

Copy constructor from a multimap<pair< >, >

Definition at line 66 of file graphs.h.

template<class TYPE_EDGES>
mrpt::math::CDirectedGraph< TYPE_EDGES >::CDirectedGraph ( ) [inline]

Default constructor.

Definition at line 67 of file graphs.h.


Member Function Documentation

template<class TYPE_EDGES>
iterator mrpt::math::CDirectedGraph< TYPE_EDGES >::begin ( ) [inline]

Definition at line 69 of file graphs.h.

template<class TYPE_EDGES>
const_iterator mrpt::math::CDirectedGraph< TYPE_EDGES >::begin ( ) const [inline]

Definition at line 71 of file graphs.h.

template<class TYPE_EDGES>
void mrpt::math::CDirectedGraph< TYPE_EDGES >::clearEdges ( ) [inline]

Erase all edges.

Definition at line 79 of file graphs.h.

template<class TYPE_EDGES>
size_t mrpt::math::CDirectedGraph< TYPE_EDGES >::countDifferentNodesInEdges ( ) const [inline]

Count how many different node IDs appear in the graph edges.

Definition at line 162 of file graphs.h.

template<class TYPE_EDGES>
size_t mrpt::math::CDirectedGraph< TYPE_EDGES >::edgeCount ( ) const [inline]

The number of edges in the graph.

Definition at line 78 of file graphs.h.

template<class TYPE_EDGES>
bool mrpt::math::CDirectedGraph< TYPE_EDGES >::edgeExists ( TNodeID  from_nodeID,
TNodeID  to_nodeID 
) const [inline]

Test is the given directed edge exists.

Definition at line 101 of file graphs.h.

template<class TYPE_EDGES>
const_iterator mrpt::math::CDirectedGraph< TYPE_EDGES >::end ( ) const [inline]

Definition at line 72 of file graphs.h.

template<class TYPE_EDGES>
iterator mrpt::math::CDirectedGraph< TYPE_EDGES >::end ( ) [inline]

Definition at line 70 of file graphs.h.

template<class TYPE_EDGES>
void mrpt::math::CDirectedGraph< TYPE_EDGES >::eraseEdge ( TNodeID  from_nodeID,
TNodeID  to_nodeID 
) [inline]

Erase all edges between the given nodes (it has no effect if no edge existed)

Definition at line 141 of file graphs.h.

template<class TYPE_EDGES>
template<class MAP_NODEID_SET_NODEIDS >
void mrpt::math::CDirectedGraph< TYPE_EDGES >::getAdjacencyMatrix ( MAP_NODEID_SET_NODEIDS &  outAdjacency) const [inline]

Return a map from node IDs to all its neighbors (that is, connected nodes, regardless of the edge direction) This is a much more efficient method than calling getNeighborsOf() for each node in the graph.

Possible values for the template argument MAP_NODEID_SET_NODEIDS are:

Definition at line 194 of file graphs.h.

Referenced by mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::CDijkstra().

template<class TYPE_EDGES>
std::set<TNodeID> mrpt::math::CDirectedGraph< TYPE_EDGES >::getAllNodes ( ) const [inline]

Less efficient way to get all nodes that returns a copy of the set object.

See also:
getAllNodes( std::set<TNodeID> &lstNode_IDs)

Definition at line 158 of file graphs.h.

Referenced by mrpt::math::CDirectedGraph< CPose3DPDFGaussian >::getAllNodes().

template<class TYPE_EDGES>
void mrpt::math::CDirectedGraph< TYPE_EDGES >::getAllNodes ( std::set< TNodeID > &  lstNode_IDs) const [inline]

Return a list of all the node_ID's of the graph, generated from all the nodes that appear in the list of edges.

Definition at line 147 of file graphs.h.

Referenced by mrpt::math::CDijkstra< TYPE_EDGES, MAPS_IMPLEMENTATION >::CDijkstra().

template<class TYPE_EDGES>
edge_t& mrpt::math::CDirectedGraph< TYPE_EDGES >::getEdge ( TNodeID  from_nodeID,
TNodeID  to_nodeID 
) [inline]

Return a reference to the content of a given edge.

If several edges exist between the given nodes, the first one is returned.

Exceptions:
std::exceptionif the given edge does not exist
See also:
getEdges

Definition at line 109 of file graphs.h.

template<class TYPE_EDGES>
const edge_t& mrpt::math::CDirectedGraph< TYPE_EDGES >::getEdge ( TNodeID  from_nodeID,
TNodeID  to_nodeID 
) const [inline]

Return a reference to the content of a given edge.

If several edges exist between the given nodes, the first one is returned.

Exceptions:
std::exceptionif the given edge does not exist
See also:
getEdges

Definition at line 122 of file graphs.h.

template<class TYPE_EDGES>
std::pair<const_iterator,const_iterator> mrpt::math::CDirectedGraph< TYPE_EDGES >::getEdges ( TNodeID  from_nodeID,
TNodeID  to_nodeID 
) const [inline]

Return a pair<first,last> of const iterators to the range of edges between two given nodes.

See also:
getEdge

Definition at line 135 of file graphs.h.

template<class TYPE_EDGES>
std::pair<iterator,iterator> mrpt::math::CDirectedGraph< TYPE_EDGES >::getEdges ( TNodeID  from_nodeID,
TNodeID  to_nodeID 
) [inline]

Return a pair<first,last> of iterators to the range of edges between two given nodes.

See also:
getEdge

Definition at line 131 of file graphs.h.

template<class TYPE_EDGES>
void mrpt::math::CDirectedGraph< TYPE_EDGES >::getNeighborsOf ( const TNodeID  nodeID,
std::set< TNodeID > &  neighborIDs 
) const [inline]

Return the list of all neighbors of "nodeID", by creating a list of their node IDs.

See also:
getAdjacencyMatrix

Definition at line 174 of file graphs.h.

template<class TYPE_EDGES>
void mrpt::math::CDirectedGraph< TYPE_EDGES >::insertEdge ( TNodeID  from_nodeID,
TNodeID  to_nodeID,
const edge_t edge_value 
) [inline]

Insert an edge (from -> to) with the given edge value.

See also:
insertEdgeAtEnd

Definition at line 83 of file graphs.h.

template<class TYPE_EDGES>
void mrpt::math::CDirectedGraph< TYPE_EDGES >::insertEdgeAtEnd ( TNodeID  from_nodeID,
TNodeID  to_nodeID,
const edge_t edge_value 
) [inline]

Insert an edge (from -> to) with the given edge value (more efficient version to be called if you know that the end will go at the end of the sorted std::multimap).

See also:
insertEdge

Definition at line 92 of file graphs.h.


Member Data Documentation

template<class TYPE_EDGES>
edges_map_t mrpt::math::CDirectedGraph< TYPE_EDGES >::edges



Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN:exported at Tue Jan 25 21:56:31 UTC 2011