MRPT  1.9.9
List of all members | Classes | Public Types | Public Member Functions | Public Attributes
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::graphs::CDijkstra, mrpt::graphs::CNetworkOfPoses, mrpt::graphs::CDirectedTree

Definition at line 66 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

using edge_underlying_t = TYPE_EDGES
 Underlying type for edge_t = TYPE_EDGES + annotations. More...
 
using edges_map_t = std::multimap< TPairNodeIDs, edge_t >
 The type of the member edges. More...
 
using iterator = typename edges_map_t::iterator
 
using reverse_iterator = typename edges_map_t::reverse_iterator
 
using const_iterator = typename edges_map_t::const_iterator
 
using const_reverse_iterator = typename edges_map_t::const_reverse_iterator
 
using self_t = CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >
 Handy self type. More...
 

Public Member Functions

 CDirectedGraph (const edges_map_t &obj)
 Copy constructor from a multimap<pair< >, > More...
 
 CDirectedGraph ()
 Default constructor. More...
 
iterator begin ()
 
iterator rbegin ()
 
iterator end ()
 
iterator rend ()
 
const_iterator begin () const
 
const_iterator rbegin () const
 
const_iterator end () const
 
const_iterator rend () const
 
Edges/nodes utility methods
size_t edgeCount () const
 The number of edges in the graph. More...
 
void clearEdges ()
 Erase all edges. More...
 
void insertEdge (TNodeID from_nodeID, TNodeID to_nodeID, const edge_t &edge_value)
 Insert an edge (from -> to) with the given edge value. More...
 
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). More...
 
bool edgeExists (TNodeID from_nodeID, TNodeID to_nodeID) const
 Test if the given directed edge exists. More...
 
edge_tgetEdge (TNodeID from_nodeID, TNodeID to_nodeID)
 Return a reference to the content of a given edge. More...
 
const edge_tgetEdge (TNodeID from_nodeID, TNodeID to_nodeID) const
 Return a reference to the content of a given edge. More...
 
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. More...
 
std::pair< const_iterator, const_iteratorgetEdges (TNodeID from_nodeID, TNodeID to_nodeID) const
 Return a pair<first,last> of const iterators to the range of edges between two given nodes. More...
 
void eraseEdge (TNodeID from_nodeID, TNodeID to_nodeID)
 Erase all edges between the given nodes (it has no effect if no edge existed) More...
 
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. More...
 
std::set< TNodeIDgetAllNodes () const
 Less efficient way to get all nodes that returns a copy of the set object. More...
 
size_t countDifferentNodesInEdges () const
 Count how many different node IDs appear in the graph edges. More...
 
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. More...
 
std::set< TNodeIDgetNeighborsOf (const TNodeID nodeID) const
 Return the list of all neighbors of "nodeID", by creating a list of their node IDs. More...
 
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. More...
 
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) More...
 
I/O utilities
bool saveAsDot (std::ostream &o, const TGraphvizExportParams &p=TGraphvizExportParams()) const
 Save the graph in a Graphviz (.dot files) text format; useful for quickly rendering the graph with "dot". More...
 
bool saveAsDot (const std::string &fileName, const TGraphvizExportParams &p=TGraphvizExportParams()) const
 

Public Attributes

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

Member Typedef Documentation

◆ const_iterator

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
using mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::const_iterator = typename edges_map_t::const_iterator

Definition at line 93 of file CDirectedGraph.h.

◆ const_reverse_iterator

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
using mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::const_reverse_iterator = typename edges_map_t::const_reverse_iterator

Definition at line 94 of file CDirectedGraph.h.

◆ edge_underlying_t

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

Underlying type for edge_t = TYPE_EDGES + annotations.

Definition at line 88 of file CDirectedGraph.h.

◆ edges_map_t

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
using mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::edges_map_t = std::multimap<TPairNodeIDs, edge_t>

The type of the member edges.

Definition at line 90 of file CDirectedGraph.h.

◆ iterator

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
using mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::iterator = typename edges_map_t::iterator

Definition at line 91 of file CDirectedGraph.h.

◆ reverse_iterator

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
using mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::reverse_iterator = typename edges_map_t::reverse_iterator

Definition at line 92 of file CDirectedGraph.h.

◆ self_t

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

Handy self type.

Definition at line 96 of file CDirectedGraph.h.

Constructor & Destructor Documentation

◆ CDirectedGraph() [1/2]

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 102 of file CDirectedGraph.h.

◆ CDirectedGraph() [2/2]

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 104 of file CDirectedGraph.h.

Member Function Documentation

◆ begin() [1/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::begin ( )
inline

Definition at line 105 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CNetworkOfPoses< CPOSE, MAPS_IMPLEMENTATION, NODE_ANNOTATIONS, EDGE_ANNOTATIONS >::mergeGraph(), and mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::saveAsDot().

Here is the caller graph for this function:

◆ begin() [2/2]

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 109 of file CDirectedGraph.h.

◆ clearEdges()

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 119 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CNetworkOfPoses< CPOSE, MAPS_IMPLEMENTATION, NODE_ANNOTATIONS, EDGE_ANNOTATIONS >::extractSubGraph().

Here is the caller graph for this function:

◆ countDifferentNodesInEdges()

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 235 of file CDirectedGraph.h.

◆ edgeCount()

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 117 of file CDirectedGraph.h.

◆ edgeExists()

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 if the given directed edge exists.

Definition at line 144 of file CDirectedGraph.h.

◆ end() [1/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::end ( )
inline

Definition at line 107 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CNetworkOfPoses< CPOSE, MAPS_IMPLEMENTATION, NODE_ANNOTATIONS, EDGE_ANNOTATIONS >::mergeGraph(), and mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::saveAsDot().

Here is the caller graph for this function:

◆ end() [2/2]

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 111 of file CDirectedGraph.h.

◆ eraseEdge()

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 206 of file CDirectedGraph.h.

◆ getAdjacencyMatrix() [1/2]

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:

Definition at line 281 of file CDirectedGraph.h.

◆ getAdjacencyMatrix() [2/2]

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 296 of file CDirectedGraph.h.

◆ getAllNodes() [1/2]

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 214 of file CDirectedGraph.h.

◆ getAllNodes() [2/2]

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 226 of file CDirectedGraph.h.

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

Here is the caller graph for this function:

◆ getEdge() [1/2]

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::exceptionif the given edge does not exist
See also
getEdges

Definition at line 156 of file CDirectedGraph.h.

◆ getEdge() [2/2]

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::exceptionif the given edge does not exist
See also
getEdges

Definition at line 175 of file CDirectedGraph.h.

◆ getEdges() [1/2]

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 190 of file CDirectedGraph.h.

◆ getEdges() [2/2]

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 197 of file CDirectedGraph.h.

◆ getNeighborsOf() [1/2]

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 249 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CNetworkOfPoses< CPOSE, MAPS_IMPLEMENTATION, NODE_ANNOTATIONS, EDGE_ANNOTATIONS >::extractSubGraph(), and mrpt::graphs::CDirectedGraph< CPOSE, EDGE_ANNOTATIONS >::getNeighborsOf().

Here is the caller graph for this function:

◆ getNeighborsOf() [2/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
std::set<TNodeID> mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::getNeighborsOf ( const TNodeID  nodeID) const
inline

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

See also
getAdjacencyMatrix

Definition at line 264 of file CDirectedGraph.h.

◆ insertEdge()

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 122 of file CDirectedGraph.h.

Referenced by mrpt::graphs::CNetworkOfPoses< CPOSE, MAPS_IMPLEMENTATION, NODE_ANNOTATIONS, EDGE_ANNOTATIONS >::addVirtualEdge(), and mrpt::graphs::CNetworkOfPoses< CPOSE, MAPS_IMPLEMENTATION, NODE_ANNOTATIONS, EDGE_ANNOTATIONS >::extractSubGraph().

Here is the caller graph for this function:

◆ insertEdgeAtEnd()

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 134 of file CDirectedGraph.h.

Referenced by mrpt::hmtslam::CHierarchicalMapMHPartition::computeGloballyConsistentNodeCoordinates().

Here is the caller graph for this function:

◆ rbegin() [1/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::rbegin ( )
inline

Definition at line 106 of file CDirectedGraph.h.

◆ rbegin() [2/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
const_iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::rbegin ( ) const
inline

Definition at line 110 of file CDirectedGraph.h.

◆ rend() [1/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::rend ( )
inline

Definition at line 108 of file CDirectedGraph.h.

◆ rend() [2/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
const_iterator mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::rend ( ) const
inline

Definition at line 112 of file CDirectedGraph.h.

◆ saveAsDot() [1/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
bool mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::saveAsDot ( std::ostream &  o,
const TGraphvizExportParams p = TGraphvizExportParams() 
) const
inline

Save the graph in a Graphviz (.dot files) text format; useful for quickly rendering the graph with "dot".

Returns
false on any error

Definition at line 322 of file CDirectedGraph.h.

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

Here is the caller graph for this function:

◆ saveAsDot() [2/2]

template<class TYPE_EDGES, class EDGE_ANNOTATIONS = detail::edge_annotations_empty>
bool mrpt::graphs::CDirectedGraph< TYPE_EDGES, EDGE_ANNOTATIONS >::saveAsDot ( const std::string &  fileName,
const TGraphvizExportParams p = TGraphvizExportParams() 
) const
inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 360 of file CDirectedGraph.h.

Member Data Documentation

◆ edges

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



Page generated by Doxygen 1.8.14 for MRPT 1.9.9 Git: c7a3bec24 Sun Mar 29 18:33:13 2020 +0200 at dom mar 29 18:50:38 CEST 2020