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 :
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
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
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;
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;
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;
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: {";
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;
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;
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)
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)
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 << ",";
}
//...
#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;
}