template class mrpt::graphs::CDirectedGraph

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

#include <mrpt/graphs/CDirectedGraph.h>

template <
    class TYPE_EDGES,
    class EDGE_ANNOTATIONS = detail::edge_annotations_empty
    >
class CDirectedGraph
{
public:
    // typedefs

    typedef TYPE_EDGES edge_underlying_t;
    typedef std::multimap<TPairNodeIDs, edge_t> edges_map_t;
    typedef CDirectedGraph<TYPE_EDGES, EDGE_ANNOTATIONS> self_t;

    // structs

    struct edge_t;

    //
fields

    edges_map_t edges;

    // construction

    CDirectedGraph(const edges_map_t& obj);
    CDirectedGraph();

    //
methods

    size_t edgeCount() const;
    void clearEdges();
    void insertEdge(TNodeID from_nodeID, TNodeID to_nodeID, const edge_t& edge_value);
    void insertEdgeAtEnd(TNodeID from_nodeID, TNodeID to_nodeID, const edge_t& edge_value);
    bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const;
    edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID);
    const edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const;
    std::pair<iterator, iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID);
    std::pair<const_iterator, const_iterator> getEdges(TNodeID from_nodeID, TNodeID to_nodeID) const;
    void eraseEdge(TNodeID from_nodeID, TNodeID to_nodeID);
    void getAllNodes(std::set<TNodeID>& lstNode_IDs) const;
    std::set<TNodeID> getAllNodes() const;
    size_t countDifferentNodesInEdges() const;
    void getNeighborsOf(TNodeID const nodeID, std::set<TNodeID>& neighborIDs) const;
    std::set<TNodeID> getNeighborsOf(TNodeID const nodeID) const;

    template <class MAP_NODEID_SET_NODEIDS>
    void getAdjacencyMatrix(MAP_NODEID_SET_NODEIDS& outAdjacency) const;

    template <class MAP_NODEID_SET_NODEIDS, class SET_NODEIDS>
    void getAdjacencyMatrix(
        MAP_NODEID_SET_NODEIDS& outAdjacency,
        const SET_NODEIDS& onlyForTheseNodes
        ) const;

    bool saveAsDot(std::ostream& o, const TGraphvizExportParams& p = TGraphvizExportParams()) const;
    bool saveAsDot(const std::string& fileName, const TGraphvizExportParams& p = TGraphvizExportParams()) const;
};

// direct descendants

template <
    class CPOSE,
    class MAPS_IMPLEMENTATION = mrpt::containers::map_traits_stdmap,
    class NODE_ANNOTATIONS = mrpt::graphs::detail::TNodeAnnotationsEmpty,
    class EDGE_ANNOTATIONS = mrpt::graphs::detail::edge_annotations_empty
    >
class CNetworkOfPoses;

Typedefs

typedef TYPE_EDGES edge_underlying_t

Underlying type for edge_t = TYPE_EDGES + annotations.

typedef std::multimap<TPairNodeIDs, edge_t> edges_map_t

The type of the member edges.

typedef CDirectedGraph<TYPE_EDGES, EDGE_ANNOTATIONS> self_t

Handy self type.

Fields

edges_map_t edges

The public member with the directed edges in the graph.

Construction

CDirectedGraph(const edges_map_t& obj)

Copy constructor from a multimap<pair< >, >

CDirectedGraph()

Default constructor.

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.

See also:

insertEdgeAtEnd

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).

See also:

insertEdge

bool edgeExists(TNodeID from_nodeID, TNodeID to_nodeID) const

Test if the given directed edge exists.

edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID)

Return a reference to the content of a given edge.

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

Parameters:

std::exception

if the given edge does not exist

See also:

getEdges

const edge_t& getEdge(TNodeID from_nodeID, TNodeID to_nodeID) const

Return a reference to the content of a given edge.

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

Parameters:

std::exception

if the given edge does not exist

See also:

getEdges

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.

See also:

getEdge

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.

See also:

getEdge

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.

See also:

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

size_t countDifferentNodesInEdges() const

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

void getNeighborsOf(TNodeID const nodeID, std::set<TNodeID>& neighborIDs) const

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

See also:

getAdjacencyMatrix

std::set<TNodeID> getNeighborsOf(TNodeID const nodeID) const

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

See also:

getAdjacencyMatrix

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.

Possible values for the template argument MAP_NODEID_SET_NODEIDS are:

• std::map<TNodeID, std::set<TNodeID> >

• mrpt::containers::map_as_vector <TNodeID, std::set<TNodeID> >

See also:

getNeighborsOf

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)

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”.

Returns:

false on any error

bool saveAsDot(const std::string& fileName, const TGraphvizExportParams& p = TGraphvizExportParams()) const

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