mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS > Class Template Reference

Detailed Description

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
class mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >

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::graphs::CNetworkOfPoses, mrpt::graphs::CDirectedTree

Definition at line 62 of file CDirectedGraph.h.

#include <mrpt/graphs/CDirectedGraph.h>

Inheritance diagram for mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >:

Classes
struct	edge_t
	The type of each global pose in nodes: an extension of the TYPE_EDGES pose with any optional user-defined data. More...

Public Types
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_t &	getEdge (TNodeID from_nodeID, TNodeID to_nodeID)
	Return a reference to the content of a given edge.
const edge_t &	getEdge (TNodeID from_nodeID, TNodeID to_nodeID) const
	Return a reference to the content of a given edge.
std::pair< iterator, iterator >	getEdges (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< TNodeID >	getAllNodes () 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.
template<class MAP_NODEID_SET_NODEIDS , class SET_NODEIDS >
void	getAdjacencyMatrix (MAP_NODEID_SET_NODEIDS &outAdjacency, const SET_NODEIDS &onlyForTheseNodes) const
	Just like getAdjacencyMatrix but return only the adjacency for those node_ids in the set onlyForTheseNodes (both endings nodes of an edge must be within the set for it to be returned)

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

Member Typedef Documentation

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

typedef edges_map_t::const_iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::const_iterator

Definition at line 77 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

typedef mrpt::aligned_containers<TPairNodeIDs,edge_t>::multimap_t mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::edges_map_t

The type of the member edges.

Definition at line 75 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

typedef edges_map_t::iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::iterator

Definition at line 76 of file CDirectedGraph.h.

Constructor & Destructor Documentation

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::CDirectedGraph ( const edges_map_t &  obj )

inline

Copy constructor from a multimap<pair< >, >

Definition at line 83 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::CDirectedGraph ( )

inline

Default constructor.

Definition at line 84 of file CDirectedGraph.h.

Member Function Documentation

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::begin ( )

inline

Definition at line 86 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

const_iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::begin ( ) const

inline

Definition at line 88 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::clearEdges ( )

inline

Erase all edges.

Definition at line 96 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

size_t mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::countDifferentNodesInEdges ( ) const

inline

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

Definition at line 179 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

size_t mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::edgeCount ( ) const

inline

The number of edges in the graph.

Definition at line 95 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

bool mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::edgeExists ( TNodeID  from_nodeID, TNodeID  to_nodeID  ) const

inline

Test is the given directed edge exists.

Definition at line 118 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::end ( )

inline

Definition at line 87 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

const_iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::end ( ) const

inline

Definition at line 89 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 158 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

template<class MAP_NODEID_SET_NODEIDS >

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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:

• std::map<TNodeID, std::set<TNodeID> >
• mrpt::utils::map_as_vector<TNodeID, std::set<TNodeID> >

  See Also

  getNeighborsOf

Definition at line 211 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

template<class MAP_NODEID_SET_NODEIDS , class SET_NODEIDS >

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::getAdjacencyMatrix ( MAP_NODEID_SET_NODEIDS &  outAdjacency, const SET_NODEIDS &  onlyForTheseNodes  ) const

inline

Just like getAdjacencyMatrix but return only the adjacency for those node_ids in the set onlyForTheseNodes (both endings nodes of an edge must be within the set for it to be returned)

Definition at line 224 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 164 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

std::set<TNodeID> mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 175 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getAllNodes().

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

edge_t& mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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::exception

if the given edge does not exist

See Also

getEdges

Definition at line 126 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

const edge_t& mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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::exception

if the given edge does not exist

See Also

getEdges

Definition at line 139 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

std::pair<iterator,iterator> mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 148 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

std::pair<const_iterator,const_iterator> mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 152 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 191 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 100 of file CDirectedGraph.h.

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

void mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::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 109 of file CDirectedGraph.h.

Member Data Documentation

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>

edges_map_t mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::edges

The public member with the directed edges in the graph.

Definition at line 80 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::begin(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::clearEdges(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::countDifferentNodesInEdges(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::edgeCount(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::edgeExists(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::end(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::eraseEdge(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getAdjacencyMatrix(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getAllNodes(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getEdge(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getEdges(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getNeighborsOf(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::insertEdge(), and mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::insertEdgeAtEnd().