mrpt::graphs::CDirectedGraph Class Reference

---

Detailed Description

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

#include <mrpt/graphs/CDirectedGraph.h>

Inheritance diagram for mrpt::graphs::CDirectedGraph:

List of all members.

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

typedef edges_map_t::const_iterator mrpt::graphs::CDirectedGraph::const_iterator

Definition at line 77 of file CDirectedGraph.h.

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

The type of the member edges.

Definition at line 75 of file CDirectedGraph.h.

typedef edges_map_t::iterator mrpt::graphs::CDirectedGraph::iterator

Definition at line 76 of file CDirectedGraph.h.

---

Constructor & Destructor Documentation

mrpt::graphs::CDirectedGraph::CDirectedGraph

(

const edges_map_t &

obj

)

[inline]

Copy constructor from a multimap<pair< >, >

Definition at line 83 of file CDirectedGraph.h.

mrpt::graphs::CDirectedGraph::CDirectedGraph

(

)

[inline]

Default constructor.

Definition at line 84 of file CDirectedGraph.h.

---

Member Function Documentation

iterator mrpt::graphs::CDirectedGraph::begin

(

)

[inline]

Definition at line 86 of file CDirectedGraph.h.

const_iterator mrpt::graphs::CDirectedGraph::begin

(

)

const [inline]

Definition at line 88 of file CDirectedGraph.h.

void mrpt::graphs::CDirectedGraph::clearEdges

(

)

[inline]

Erase all edges.

Definition at line 96 of file CDirectedGraph.h.

size_t mrpt::graphs::CDirectedGraph::countDifferentNodesInEdges

(

)

const [inline]

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

Definition at line 179 of file CDirectedGraph.h.

size_t mrpt::graphs::CDirectedGraph::edgeCount

(

)

const [inline]

The number of edges in the graph.

Definition at line 95 of file CDirectedGraph.h.

bool mrpt::graphs::CDirectedGraph::edgeExists	(	TNodeID	from_nodeID,
		TNodeID	to_nodeID
	)		const [inline]

Test is the given directed edge exists.

Definition at line 118 of file CDirectedGraph.h.

iterator mrpt::graphs::CDirectedGraph::end

(

)

[inline]

Definition at line 87 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CNetworkOfPoses< CPose3DPDFGaussian, map_traits_stdmap >::getGlobalSquareError().

const_iterator mrpt::graphs::CDirectedGraph::end

(

)

const [inline]

Definition at line 89 of file CDirectedGraph.h.

void mrpt::graphs::CDirectedGraph::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 MAP_NODEID_SET_NODEIDS >

void mrpt::graphs::CDirectedGraph::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 MAP_NODEID_SET_NODEIDS , class SET_NODEIDS >

void mrpt::graphs::CDirectedGraph::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.

void mrpt::graphs::CDirectedGraph::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.

std::set<TNodeID> mrpt::graphs::CDirectedGraph::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().

edge_t& mrpt::graphs::CDirectedGraph::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.

const edge_t& mrpt::graphs::CDirectedGraph::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.

std::pair<iterator,iterator> mrpt::graphs::CDirectedGraph::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.

std::pair<const_iterator,const_iterator> mrpt::graphs::CDirectedGraph::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.

void mrpt::graphs::CDirectedGraph::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.

void mrpt::graphs::CDirectedGraph::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.

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

edges_map_t mrpt::graphs::CDirectedGraph::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 >::end(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::edgeCount(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::clearEdges(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::insertEdge(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::insertEdgeAtEnd(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::edgeExists(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getEdge(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getEdges(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::eraseEdge(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getAllNodes(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::countDifferentNodesInEdges(), mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getNeighborsOf(), and mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getAdjacencyMatrix().