8. TUTORIAL 002 : Iterating over a graph (class Iterator and the macro forEach)

In this tutorial, we will, display on the standard output, all the structure using iterators. For each node, we will display its ancestors, successors, neighbors, and, its incoming and outgoing edges.

In this tutorial, the graph created is the same that in Tutorial 1 (after the 3 edges were added) see the following picture :

1. Header files (Same as Tutorial 1)

Let's start with the files we need to include :

#include <iostream>
#include <tulip/Graph.h>
		

  • iostream : This "file" contains the C++ standard declarations for in and out streams. We need it in this tutorial to print the final graph on the standard output.

  • tulip/Graph.h : This file is the core of the tulip graph API. It provides declarations for graphs (edges , nodes) and functions to load one from a file, to save one, and a lot more. You can find a list in the doxygen documentation.

As you can see, we just need the "Graph.h" header file to create a graph and iterate over its nodes, even though the declaration of the abstract class "Iterator" is in Iterator.h

2. Iterating over all nodes

To iterate over all nodes, we need to create an Iterator on the graph nodes with the member function Iterator* Graph::getNodes () const, we will make it point on the graphs nodes.

  Iterator<node> *itNodes = graph->getNodes();
        	

The documentation of the interface Iterator can be found here.

With the functions template <class itType > bool tlp::Iterator< itType >::hasNext ( ) and node next ( ), we can iterate through our graph nodes with a simple while :

   while(itNodes->hasNext()) {
   	node n = itNodes->next();
        	

In this while loop, we display some node topological properties :

    cout << "node: " <<  n.id << endl;
    cout << " degree: " << graph->deg(n) << endl;
    cout << " in-degree: " << graph->indeg(n) << endl;
    cout << " out-degree: " << graph->outdeg(n) << endl;
        	

At the end of the loop, we will need to delete the iterator: delete itNodes;

Following is the output of this simple while loop :

[root@atlas tutorial-002]# ./tutorial002
node: 0
 degree: 2
 in-degree: 1
 out-degree: 1
node: 1
 degree: 2
 in-degree: 1
 out-degree: 1
node: 2
 degree: 2
 in-degree: 1
 out-degree: 1
        	

3. Iterating through a node predecessors

To iterate through predecessors of node, we use the same type of Iterator, but, instead of using the function getNodes() of the class Graph, we will use the function Iterator<node>* getInNodes (const node) const that will return an iterator on the predecessors of a node.

    //===========================
    //iterate all predecessors of a node
    cout << " predecessors: {";
    Iterator<node> *itN=graph->getInNodes(n);
    while(itN->hasNext()) {
      cout << itN->next().id;
      if (itN->hasNext()) cout << ",";
    } delete itN; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;
        	

4. Iterating through a node successors

To iterate through successors of a node, we just need to use the function Iterator<node>* Graph::getOutNodes (const node) const to have an Iterator on its successors.

    //===========================
    //iterate all successors of a node
    cout << " successors: {";
    itN = graph->getOutNodes(n);
    while (itN->hasNext()) {
      cout << itN->next().id;
      if (itN->hasNext()) cout << ",";
    } delete itN; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;
        	

5. Iterating through a node neighbors (predecessors and successors)

For neighbors, we will use the function Iterator<node>* Graph::getInOutNodes (const node) const to have an Iterator on its neighbors.

    //===========================
    //iterate the neighborhood of a node
    cout << " neighborhood: {";
    itN = graph->getInOutNodes(n);
    while(itN->hasNext()) {
      cout << itN->next().id;
      if (itN->hasNext()) cout << ",";
    } delete itN; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;
        	

6. Iterating through a node incoming edges

For incoming edges, we will use an Iterator on edges with the member function Iterator<edge>* Graph::getInEdges (const node) const.

   //===========================
    //iterate the incoming edges
    cout << " incoming edges: {";
    Iterator<edge> *itE=graph->getInEdges(n);
    while(itE->hasNext()) {
      cout << itE->next().id;
      if (itE->hasNext()) cout << ",";
    } delete itE; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;
    cout << " outcoming edges: {";
        	

7. Iterating through a node outgoing edges

For outgoing edges, we will use the function Iterator<edge>* Graph::getOutEdges (const node) const.

     //===========================
    //iterate the outcomming edges
    itE = graph->getOutEdges(n);
    while(itE->hasNext()) {
      cout << itE->next().id;
      if (itE->hasNext()) cout << ",";
    } delete itE; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;
        	

8. Iterating through a node adjacent edges

For adjacent edges, we will use the function Iterator<edge>* Graph::getInOutEdges (const node) const.

    //===========================
    //iterate the adjacent edges
    cout << " adjacent edges: {";
    itE = graph->getInOutEdges(n);
    while(itE->hasNext()) {
      cout << itE->next().id;
      if (itE->hasNext()) cout << ",";
    } delete itE; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;
        	

Don't forget memory leaks

As we are still in the first while (iterating through all nodes) we need to delete the Iterator on Nodes :

}// end while 
delete itNodes; //!!!Warning : do not forget to delete iterators (memory leak)
        	

9. Iterating on edges (all edges).

Some times it can be useful to iterate on edges, for example in the algorithm of Kruskal. That is why the graph class owns the function Iterator<edge>* Graph::getEdges (const node) const, that return a pointer on an Iterator of type edge. Following is an exemple of its use.

  //===========================
  //Iterate all edges
  Iterator<edge> *itEdges=graph->getEdges();
  while(itEdges->hasNext()) {
    edge e = itEdges->next();
    cout << "edge: " << e.id;
    cout << " source: " << graph->source(e).id;
    cout << " target: " << graph->target(e).id;
    cout << endl;
  } delete itEdges; //!!!Warning : do not forget to delete iterators (memory leak)
        	

10. The forEach Macro

To simplify the use of Iterators, the API of tulip provides a macro forEach which is quite similar to the foreach of C# or Java. It takes two parameters :

  • A variable :

  • An Iterator for the same type as the variable, for example : Variable of type node, Graph::getNodes().

Warning

  • Must use breakForEach to break iteration

  • Must use returnForEach to return during iteration

This macro function is defined in the header file : tulip/ForEach.h

Following is a small example of its use.

#include <tulip/ForEach.h>

  //...
  //main
  //load Graph 
  //... 
  
  node n = graph->getOneNode();	
  cout << "In Edges :" << endl;		
  edge e;
  forEach(e, graph->getInEdges(n))
  {
    cout << e.id << ",";
  }
  
  //...
        	

Source Code

#include <iostream>
#include <tulip/Graph.h>

/**
 * Tutorial 002
 *
 * Create a graph 
 * display all the structure using iterators
 *
 */

using namespace std;
using namespace tlp;

void buildGraph(Graph *graph) {
  //add three nodes
  node n0=graph->addNode();
  node n1=graph->addNode();
  node n2=graph->addNode();
  //add three edges
  graph->addEdge(n1,n2);
  graph->addEdge(n0,n1);
  graph->addEdge(n2,n0);
}

int main() {
  //create an empty graph
  Graph *graph=tlp::newGraph();

  //build the graph
  buildGraph(graph);
  
  //===========================
  //Iterate all nodes and display the structure
  Iterator<node> *itNodes = graph->getNodes();
  while(itNodes->hasNext()) {
    node n = itNodes->next();
    cout << "node: " <<  n.id << endl;
    cout << " degree: " << graph->deg(n) << endl;
    cout << " in-degree: " << graph->indeg(n) << endl;
    cout << " out-degree: " << graph->outdeg(n) << endl;

    //===========================
    //iterate all ancestors of a node
    cout << " ancestors: {";
    Iterator<node> *itN=graph->getInNodes(n);
    while(itN->hasNext()) {
      cout << itN->next().id;
      if (itN->hasNext()) cout << ",";
    } delete itN; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;

    //===========================
    //iterate all successors of a node
    cout << " successors: {";
    itN = graph->getOutNodes(n);
    while (itN->hasNext()) {
      cout << itN->next().id;
      if (itN->hasNext()) cout << ",";
    } delete itN; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;

    //===========================
    //iterate the neighborhood of a node
    cout << " neighborhood: {";
    itN = graph->getInOutNodes(n);
    while(itN->hasNext()) {
      cout << itN->next().id;
      if (itN->hasNext()) cout << ",";
    } delete itN; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;

    //===========================
    //iterate the incoming edges
    cout << " incoming edges: {";
    Iterator<edge> *itE=graph->getInEdges(n);
    while(itE->hasNext()) {
      cout << itE->next().id;
      if (itE->hasNext()) cout << ",";
    } delete itE; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;
    cout << " outcoming edges: {";

    //===========================
    //iterate the outcomming edges
    itE = graph->getOutEdges(n);
    while(itE->hasNext()) {
      cout << itE->next().id;
      if (itE->hasNext()) cout << ",";
    } delete itE; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;

    //===========================
    //iterate the adjacent edges
    cout << " adjacent edges: {";
    itE = graph->getInOutEdges(n);
    while(itE->hasNext()) {
      cout << itE->next().id;
      if (itE->hasNext()) cout << ",";
    } delete itE; //!!!Warning : do not forget to delete iterators (memory leak)
    cout << "}" << endl;

  } delete itNodes; //!!!Warning : do not forget to delete iterators (memory leak)

  //===========================
  //Iterate all edges
  Iterator<edge> *itEdges=graph->getEdges();
  while(itEdges->hasNext()) {
    edge e = itEdges->next(); 
    cout << "edge: " << e.id;
    cout << " source: " << graph->source(e).id;
    cout << " target: " << graph->target(e).id;
    cout << endl;
  } delete itEdges; //!!!Warning : do not forget to delete iterators (memory leak)

  delete graph; //delete the entire graph
  return EXIT_SUCCESS;
}