How to use the graph classes

The basic idea of the implementation of graphs in aGrUM is to leave it "as pure as possible". Hence graphs consist of integers (gum::NodeId) and binary relations between them (Edge, Arc).

The Graph Hierarchy

Precisely a graph contains a compact representation of a set of gum::NodeId, and can contain a set of gum::Arc and a set of gum::Edge.

In aGrUM,

• 3 classes wrap these 3 sets : gum::NodeGraphPart, gum::ArcGraphPart and gum::EdgeGraphPart (resp. wrapping gum::NodeSet, gum::ArcSet and gum::EdgeSet, 3 typedefs of Set),
• gum::UndiGraph inherits from gum::EdgeGraphPart and gum::NodeGraphPart,
• gum::DiGraph inherits from gum::ArcGraphPart and gum::NodeGraphPart and
• gum::MixedGraph inherits from gum::DiGraph and gum::UndiGraph.

(as shown in the inheritance diagram for gum::MixedGraph, the class hierarchy for graphs in aGrUM uses multiple inheritance.)

This pattern of inheritance allows aGrUM to have a quite standardized API for all basic operations in graphs: manipulating and iterating over nodes, edges and arcs.

IDs, iterators and properties

Such representation of graphs has two major drawbacks that aGrUM has to face:

• how to certify that all node ids are unique in a graph?
• how to iterate on nodes, arcs, edges in a graph ?
• how to put properties (name/position/integer/flag) on nodes, edges and arcs?

ID factory

For aGrUM, each node has (is) an id. IDs begin from 1 (id>0).

For the uniqueness of ids, addNode() in NodeGraphPart contains an internal idFactory which guarantees this property.

There are two ways to bypass the idFactory :

• use the copy constructor or the gum::NodeGraphPart::populateNodes(). These very two methods copy a set of nodes and ensure that the ids are the same as those of their argument (gum::NodeGraphPart::populateNodes() clears the gum::NodeGraphPart before copying).
• use gum::NodeGraphPart::addNode(gum::NodeId id) which allow the user to give a specific id to a new node. This method should be used very carefully !! It may throw exception (id=0 or id already used) and it may deteriorate the compacity of the gum::NodeGraphPart.

Good programmers should treat with respect the idFactory.

Iterators

gum::NodeSet, gum::EdgeSet and gum::ArcSet have their own iterators (see gum::NodeSetIterator etc.). However aGrUM gives specialized iterators for graphs. These iterators are herited from the different 3 graphs part and may be (or not) a typedef for set iterators. We encourage to use these iterators when iterating on a graph.

For a graph gr of type G (G is gum::DiGraph, gum::DAG, gum::UndiGraph or gum::MixedGraph, etc.) :

G gr;

// iterate on nodes
for(const auto node : gr.nodes()) {
  ... // node is a gum::NodeId
}

// iterate on edges (if possible)
for(const auto & edge : gr.edges()) {
  ... // edge is a const gum::Edge&
}

// iterate on arcs (if possible)
for(const auto & arc =gr.arcs()) {
  ... // arc is a const gum::Arc&
}

Properties

Properties are the way to put (dynamic) informations within nodes, edges and arcs. Properties are just HashTable in which keys are gum::NodeId, Edge or Arc. NodeProperty, ArcProperty and EdgeProperty are the names of these classes.

gum::UndiGraph g;
gum::NodeProperty<bool> is_id_odd=g.nodesProperty( false );

g.addNode();
g.addNode();
g.addNode();

for ( auto nodeId : g.nodes()) {
  is_id_odd.set( nodeId, nodeId % 2 == 0 );
}

std::cout<<is_id_odd<<std::cout<<std::endl;

for ( auto i : is_id_odd)
  std::cout<<i.first()<<" : "<<i.second()<<std::endl;

Equivalently, you could have written :

bool is_it_odd(const gum::NodeId& i) {
  return i%2==0;
}

gum::UndiGraph g;
g.addNode();
g.addNode();
g.addNodeWithId();

gum::NodeProperty<bool> is_id_odd=g.nodesProperty(is_it_odd);

std::cout<<is_id_odd<<std::endl<<std::endl;

for (const auto & elt :is_id_odd) {
  std::cout<<i.first<<" : "<<i.second<<std::endl;
}

Here is a code for searching directed pathin a DiGraph" g from gum::NodeId n1 to gum::NodeId n2.