[Contents] [TitleIndex] [WordIndex] 

Contributor - BoostMetanet

The goal is to use the Boost.graph library (see Boost) to replace some of the Metanet fortran code and to enhance Metanet.

Note that metanet has been moved on the Scilab forge and is available through ATOMS.

Such an implementation already exists under matlab: see Matlab BGL

A message sent by David Gleich (the author of MatlabBGL):

Yann:

I saw on the Scilab development ideas wiki that there is a proposal to add graph functionality to Scilab like the MatlabBGL code that I wrote.

https://scilab.gitlab.io/legacy_wiki/Contributor_-_BoostMetanet

I was wondering if you could put a note on that page to say that I'd be willing to advise anyone on ways of re-using pieces of MatlabBGL to aid scilab integration. MatlabBGL works _almost verbatim_ in Octave --- so I suspect the same might hold for Scilab too, given

https://scilab.gitlab.io/legacy_wiki/mattosci/toolbox.

Of course, it would require translation of the sparse matrix format to the CSR arrays Matlab uses, but most MatlabBGL calls need to transpose the matrix in Matlab anyway... (it looks like Scilab uses something interesting for it's sparse matrix format).

Best wishes,

David Gleich

Toolbox BGL

An example of use of the toolbox_bgl

bst_graph = makeGraph('test');
addNode(bst_graph, "node_1")
addNode(bst_graph, "node_2")
addNode(bst_graph, "node_3")
/* after a bit of testing, refactoring this */ 
addEdge(bst_graph, "node1", "node2");
addEdge(bst_graph, 2, 3); // 2 & 3 are indices!

printGraph(bst_graph)

// -->printGraph(bst_graph)
// node1:  node2 node3
// node2:  node1 node3
// node3:  node2 node1

addDoubleProperty(bst_graph, getNodeByLabel('node1'), 'x_coord', 2.4) 
addDoubleProperty(bst_graph, getNodeByLabel('node1'), 'y_coord', -1.5)
Or, even better
addCoordinates(bst_graph, getNodeByLabel('node1'), [2.4 -1.5])

addStringProperty(bst_graph, getNodeByIndex(1:n), 'labels', [label1, label2, ... , labeln])

A list of examples that works using matlabBGL.

Things to be done

How to get Toolbox BGL

On the Scilab forge, as soon as code is reviewed :) http://forge.scilab.org/index.php/p/boost-metanet/source/tree/master/

For a demo on how to use, see demos/bfs_demo.dem

Starting development plan

Focus on the few simple properties we need and implement the according functions. The starting set is:

Each node will have: 

size_t index
string label
double[] coordinates
double weight

Each edge will have: 

string label
double weight

Basic functions 

printNode
printEdge

Retrieving nodes/edges 

getNodeByLabel()
getNodeByIndex()
getEdgeByLabel()

Adding nodes/edges 

addNode(string label)
addNode() //gets an automatic index, leaves the label blank
addEdge(node1, node2)
addEdge(node1, node2, label),

where node1 is retrieved by one of the functions above (getNodeByX)

Setting properties 

setNodeStringProperty(graph, node1, propertyName, propertyValue)

where propertyName is a name of a property to set, e.g. 'labels', and propertyValue must be a string, e.g. 

setNodeStringProperty(graph, getNodeByLabel('myNode'), 'labels', 'newLabelForMyNode')

setNodeWeight(graphName, node1, weight)
setNodeCoordinates(graphName, node1, num_coordinates, coordinates_array) e.g. setNodeCoordinates(graph, getNodeByLabel('mynode'), 3, [1.2 -5.41 5.1])
setEdgeWeight(graphName, edge1, weight)
setEdgeLabel(graphName, edge1, 'newLabel')

Weekly reports

24th-28th May

31st May - 4th June

7th - 11th June

14th - 18th June

21th - 25th June

Plan for next week:

28th June - 2nd July

Next week:

5th - 9th July

Next week:

12th - 16th July

19th July - 23rd July

== 26th July - 3rd August ==

== 4th August - 13th August (end of GSoC :( )

Next steps --

Test how Scilab handles this when it comes to bigger graphs. If the performance improvement is significant, the IOHelper allows to add more algorithms quite easily. Even though Metanet should handle the coordinates, consider adding some Boost layout algorithms which could calculate these coordinates, instead of the user manually typing them in. Although it wasn't the goal of the project, one of the biggest takeaways could be exactly the IOHelper library - it's making communication between Scilab & C++ quite easy so porting any C++ code to Scilab is simplified. Therefore anyone knowing C++ could just jump on to coding in Scilab without having to get a deep knowledge in the Scilab API first.

An example of how to use the BoostMetanet can be found in the demos directory

To create a graph, you must give it a name. You are always able to lookup the graph by using that name. Use addNode/addEdge functions to add nodes and edges. They except various number of arguments so you can optionally add weights/labels to edges, while the vertices need to have labels. Getting nodes and edges is very flexible and you can use either labels or indices. You can retrieve the data for the nodes/edges in the same flexible way. The algorithms have the exact same signature as the MatlabBGL toolbox

Until I generate some documentation from the comments, please refer to the code itself (there is many comments :) ) or the MatlabBGL manual for description of some graph algorithms and their usage.

Here are some "tutorial C++ codes" wrote to illustrate the use of Boost Graph:

These examples can be downloaded here: boostgraph.zip

The file test1.cpp: 

#include <iostream>                  // for std::cout
#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

using namespace boost;
using namespace std;

int main()
{
  int i;

  //////////////////////////////////
  // A graph without property_map //
  //////////////////////////////////

  // create a typedef for the Graph type
  typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
  
  // Make convenient labels for the vertices
  enum { A, B, C, D, E, N };
  const char* name = "ABCDE";
  
  // writing out the edges in the graph
  typedef pair<int, int> Edge;

  Edge edge_array[] = { 
    Edge(A,B), Edge(A,D), 
    Edge(C,A), Edge(D,C),
    Edge(C,E), Edge(B,D), 
    Edge(D,E) 
  };

  const int n_edges = sizeof(edge_array)/sizeof(edge_array[0]);
  
  // declare a graph object
  Graph G(N);
  
  // add the edges to the graph object
  for (int i = 0; i < n_edges; ++i) add_edge(edge_array[i].first, edge_array[i].second, G);
  
  graph_traits<Graph>::edges_size_type size_edge = num_edges(G);
  graph_traits<Graph>::vertices_size_type size_vertex = num_vertices(G);

  cout << "Number of edges: " << size_edge << endl;
  cout << "Number of vertices: " << size_vertex << endl;

  // Now, we run across all edges and print info
  graph_traits<Graph>::edge_iterator ei, ei_end, ei_next;
  graph_traits<Graph>::vertex_descriptor index_vertex;

  // edges returns a tuple. It defines then range of valid edges
  tie(ei, ei_end) = edges(G);
  for (i=0, ei_next = ei; ei != ei_end; ei = ei_next, i++) 
    {
      ++ei_next;
      cout << "Edges n° " << i << " : ";
      index_vertex = source(*ei, G);
      cout << "source " << name[index_vertex] << " - ";
      index_vertex = target(*ei, G);
      cout << "destination " << name[index_vertex] << endl;
    }

  // Now, we run across all vertices and print info
  graph_traits<Graph>::vertex_iterator vi, vi_end, vi_next;

  // Vertices returns a tuple. It defines then range of valid vertices
  tie(vi, vi_end) = vertices(G);
  for (i=0, vi_next = vi; vi != vi_end; vi = vi_next, i++) 
    {
      ++vi_next;
      cout << "Vertex n° " << i << " : source " << name[i] << endl;
    }

  // Now print this graph in a graphviz file.
  ofstream dotfile;
  dotfile.open("test1.dot");
  write_graphviz(dotfile, G);

  return 0;
}

The file test2.cpp: 

#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/properties.hpp>
#include <boost/utility.hpp>

using namespace boost;
using namespace std;

// We add a name to the edges and vertex
enum edge_mylabel_t {edge_mylabel};
enum vertex_mylabel_t {vertex_mylabel};

namespace boost {
  BOOST_INSTALL_PROPERTY(edge,mylabel);
  BOOST_INSTALL_PROPERTY(vertex,mylabel);
}

typedef property<edge_mylabel_t,string> EMylabel_type;
typedef property<vertex_mylabel_t,string> VMylabel_type;

// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS, VMylabel_type, EMylabel_type> Graph;

typedef property_map<Graph,edge_mylabel_t>::type EMylabel_list_type;
typedef property_map<Graph,vertex_mylabel_t>::type VMylabel_list_type;

template <class T>
class edge_label_writer 
{
public:
  edge_label_writer(T str) : _label(str) {}
  template <class Edge>
  void operator()(ostream &out, const Edge& e) const
  {
    out << "[label=\"" << _label[e] << "\", fontsize=\"11\"]";
  }
private:
  EMylabel_list_type _label;
};

template <class T>
class vertex_label_writer
{
public:
  vertex_label_writer(T str) : _label(str) {}
  template <class Vertex>
  void operator()(ostream &out, const Vertex& w) const
  {
    out << "[label=\"" << _label[w] << "\", fontsize=\"11\"]";
  }
private:
  VMylabel_list_type _label;
};

int main()
{
  unsigned int i;

  ////////////////////////////////
  // A graph with property maps //
  ////////////////////////////////

  // Make convenient labels for the vertices
  enum { A, B, C, D, E, N };
  const char* name = "ABCDE";
  
  // writing out the edges in the graph
  typedef pair<int, int> Edge;

  Edge edge_array[] = { 
    Edge(A,B),
    Edge(A,D), 
    Edge(C,A), 
    Edge(D,C),
    Edge(C,E), 
    Edge(B,D), 
    Edge(D,E) 
  };

  // declare a graph object
  Graph G(N);

  vector<string> edge_mylabel(7);
  edge_mylabel[0] = "AB";
  edge_mylabel[1] = "AD";
  edge_mylabel[2] = "CA";
  edge_mylabel[3] = "DC";
  edge_mylabel[4] = "CE";
  edge_mylabel[5] = "BD";
  edge_mylabel[6] = "DE";
  
  vector<string> vertex_mylabel(5);
  vertex_mylabel[0] = "label A";
  vertex_mylabel[1] = "label B";
  vertex_mylabel[2] = "label C";
  vertex_mylabel[3] = "label D";
  vertex_mylabel[4] = "label E";

  // add the edges to the graph object
  for(i=0; i<7; ++i) 
    {
      add_edge(edge_array[i].first, edge_array[i].second, G);
    }
  
  cout << "Number of edges    : " << num_edges(G) << endl;
  cout << "Number of vertices : " << num_vertices(G) << endl;

  // Now, we run across all edges and print info
  graph_traits<Graph>::edge_iterator ei, ei_end, ei_next;
  graph_traits<Graph>::vertex_descriptor index_vertex;

  // Get the edge label property map
  EMylabel_list_type EMylabel_list = get(edge_mylabel_t(),G);

  // edges returns a tuple. It defines then range of valid edges
  tie(ei, ei_end) = edges(G);
  for (i=0, ei_next = ei; ei != ei_end; ei = ei_next, i++) 
    {
      ++ei_next;
      cout << "Edges n° " << i << " : ";
      index_vertex = source(*ei, G);
      cout << "source " << name[index_vertex] << " - ";
      index_vertex = target(*ei, G);
      cout << "destination " << name[index_vertex] << endl;
      
      // We add the property info to the edge
      //EMylabel_list[*ei] = edge_mylabel[i];
      put(EMylabel_list,*ei,edge_mylabel[i]);
    }

  // Now, we run across all vertices and print info
  graph_traits<Graph>::vertex_iterator vi, vi_end, vi_next;

  // Get the vertex label property map
  VMylabel_list_type VMylabel_list = get(vertex_mylabel_t(),G);

  // Vertices returns a tuple. It defines then range of valid vertices
  tie(vi, vi_end) = vertices(G);
  for (i=0, vi_next = vi; vi != vi_end; vi = vi_next, i++) 
    {
      ++vi_next;
      cout << "Vertex n° " << i << " : source " << name[i] << endl;

      // We add the property info to the vertex
      //VMylabel_list[*vi] = vertex_mylabel[i];
      put(VMylabel_list,*vi,vertex_mylabel[i]);
    }

  // Now print this graph in a graphviz file.
  ofstream dotfile;
  dotfile.open("test2.dot");

  write_graphviz(dotfile, G,
                 vertex_label_writer<VMylabel_list_type>(VMylabel_list),
                 edge_label_writer<EMylabel_list_type>(EMylabel_list));

  return 0;
}

The file test3.cpp: 

#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/properties.hpp>
#include <boost/utility.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

using namespace boost;
using namespace std;

// We add a name to the edges and vertex
enum edge_mylabel_t {edge_mylabel};
enum vertex_mylabel_t {vertex_mylabel};

namespace boost {
  BOOST_INSTALL_PROPERTY(edge,mylabel);
  BOOST_INSTALL_PROPERTY(vertex,mylabel);
}

typedef property<edge_mylabel_t,string> EMylabel_type;
//typedef property<edge_weight_t, int, EMylabel_type> Edge_type;
typedef property<edge_weight_t, double, EMylabel_type> Edge_type;

typedef property<vertex_mylabel_t,string> VMylabel_type;

// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS, VMylabel_type, Edge_type> Graph;

typedef property_map<Graph,edge_mylabel_t>::type   EMylabel_list_type;
typedef property_map<Graph,edge_weight_t>::type    EWeight_list_type;
typedef property_map<Graph,vertex_mylabel_t>::type VMylabel_list_type;

template <class T>
class edge_label_writer 
{
public:
  edge_label_writer(T str) : _label(str) {}
  template <class Edge>
  void operator()(ostream &out, const Edge& e) const
  {
    out << "[label=\"" << _label[e] << "\", fontsize=\"11\"]";
  }
private:
  EMylabel_list_type _label;
};

template <class T>
class vertex_label_writer
{
public:
  vertex_label_writer(T str) : _label(str) {}
  template <class Vertex>
  void operator()(ostream &out, const Vertex& w) const
  {
    out << "[label=\"" << _label[w] << "\", fontsize=\"11\"]";
  }
private:
  VMylabel_list_type _label;
};

int main()
{
  unsigned int i;

  ////////////////////////////////
  // A graph with property maps //
  ////////////////////////////////

  // Make convenient labels for the vertices
  enum { A, B, C, D, E, N };
  const char* name = "ABCDE";
  
  // writing out the edges in the graph
  typedef pair<int, int> Edge;

  Edge edge_array[] = { 
    Edge(A,B),
    Edge(A,D), 
    Edge(C,A), 
    Edge(D,C),
    Edge(C,E), 
    Edge(B,D), 
    Edge(D,E) 
  };

  // declare a graph object
  Graph G(N);

  typedef graph_traits<Graph>::edge_descriptor EdgeDescr;
  typedef graph_traits<Graph>::vertex_descriptor VertexDescr;

  vector<string> edge_mylabel(7);
  edge_mylabel[0] = "AB";
  edge_mylabel[1] = "AD";
  edge_mylabel[2] = "CA";
  edge_mylabel[3] = "DC";
  edge_mylabel[4] = "CE";
  edge_mylabel[5] = "BD";
  edge_mylabel[6] = "DE";
  
  vector<string> vertex_mylabel(5);
  vertex_mylabel[0] = "label A";
  vertex_mylabel[1] = "label B";
  vertex_mylabel[2] = "label C";
  vertex_mylabel[3] = "label D";
  vertex_mylabel[4] = "label E";

  // Some weights for the kruskal algorithm
  //vector<int> edge_weight(7);
  vector<double> edge_weight(7);
  edge_weight[0] = 1;
  edge_weight[1] = 1;
  edge_weight[2] = 1;
  edge_weight[3] = 3;
  edge_weight[4] = 2;
  edge_weight[5] = 5;
  edge_weight[6] = 3;

  // add the edges to the graph object
  for(i=0; i<7; ++i) 
    {
      add_edge(edge_array[i].first, edge_array[i].second, G);
    }
  
  cout << "Number of edges    : " << num_edges(G) << endl;
  cout << "Number of vertices : " << num_vertices(G) << endl;

  // Now, we run across all edges and print info
  graph_traits<Graph>::edge_iterator ei, ei_end, ei_next;
  graph_traits<Graph>::vertex_descriptor index_vertex;

  // Get the edge property maps
  EMylabel_list_type EMylabel_list = get(edge_mylabel_t(),G);
  EWeight_list_type  EWeight_list  = get(edge_weight_t(),G);

  // edges returns a tuple. It defines then range of valid edges
  tie(ei, ei_end) = edges(G);
  for (i=0, ei_next = ei; ei != ei_end; ei = ei_next, i++) 
    {
      ++ei_next;
      cout << "Edges n° " << i << " : ";
      index_vertex = source(*ei, G);
      cout << "source " << name[index_vertex] << " - ";
      index_vertex = target(*ei, G);
      cout << "destination " << name[index_vertex] << endl;
      
      // We add the property info to the edge
      put(EMylabel_list,*ei,edge_mylabel[i]);
      put(EWeight_list,*ei,edge_weight[i]);
    }

  // Now, we run across all vertices and print info
  graph_traits<Graph>::vertex_iterator vi, vi_end, vi_next;

  // Get the vertex label property map
  VMylabel_list_type VMylabel_list = get(vertex_mylabel_t(),G);

  // Vertices returns a tuple. It defines then range of valid vertices
  tie(vi, vi_end) = vertices(G);
  for (i=0, vi_next = vi; vi != vi_end; vi = vi_next, i++) 
    {
      ++vi_next;
      cout << "Vertex n° " << i << " : source " << name[i] << endl;

      // We add the property info to the vertex
      put(VMylabel_list,*vi,vertex_mylabel[i]);
    }

  // Now print this graph in a graphviz file.
  ofstream dotfile;
  dotfile.open("test3.dot");

  write_graphviz(dotfile, G,
                 vertex_label_writer<VMylabel_list_type>(VMylabel_list),
                 edge_label_writer<EMylabel_list_type>(EMylabel_list));

  /////////////////////////////////
  // Apply the Kruskal algorithm //
  /////////////////////////////////

  vector<EdgeDescr> spanning_tree;

  kruskal_minimum_spanning_tree(G, back_inserter(spanning_tree));

  cout << "Print the edges in the MST:" << endl;

  for(vector<EdgeDescr>::iterator ei=spanning_tree.begin(); ei!=spanning_tree.end(); ++ei) 
    {
      cout << source(*ei, G) << " <--> " << target(*ei, G) << " with weight of " << EWeight_list[*ei] << endl;
    }

  // Create a spanning tree
  Graph Gspt(N);

  for(i=0; i<spanning_tree.size(); ++i)
    {
      add_edge(edge_array[i].first, edge_array[i].second, Gspt);
    }

  // Get the edge property maps
  EMylabel_list = get(edge_mylabel_t(),Gspt);
  EWeight_list  = get(edge_weight_t(),Gspt);

  // edges returns a tuple. It defines then range of valid edges
  tie(ei, ei_end) = edges(Gspt);
  for (i=0, ei_next = ei; ei != ei_end; ei = ei_next, i++) 
    {
      ++ei_next;
      // We add the property info to the edge
      put(EMylabel_list,*ei,edge_mylabel[i]);
      put(EWeight_list,*ei,edge_weight[i]);
    }

  // Get the vertex label property map
  VMylabel_list = get(vertex_mylabel_t(),Gspt);

  // Vertices returns a tuple. It defines then range of valid vertices
  tie(vi, vi_end) = vertices(Gspt);
  for (i=0, vi_next = vi; vi != vi_end; vi = vi_next, i++) 
    {
      ++vi_next;
      // We add the property info to the vertex
      put(VMylabel_list,*vi,vertex_mylabel[i]);
    }

  // Now print this graph in a graphviz file.
  ofstream dotfile_spt;
  dotfile_spt.open("test3spt.dot");

  write_graphviz(dotfile_spt, Gspt,
                 vertex_label_writer<VMylabel_list_type>(VMylabel_list),
                 edge_label_writer<EMylabel_list_type>(EMylabel_list));

  return 0;
}

The file test4.cpp: 

#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <sstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/utility.hpp>
#include <boost/graph/graph_utility.hpp>

#include <boost/graph/graphviz.hpp>

#include <boost/random/mersenne_twister.hpp> 
#include <boost/random/uniform_real.hpp>
#include <boost/graph/random.hpp>

#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>

using namespace boost;
using namespace std;

// We add a name to the edges and vertex
enum edge_mylabel_t {edge_mylabel};
enum vertex_mylabel_t {vertex_mylabel};

namespace boost {
  BOOST_INSTALL_PROPERTY(edge,mylabel);
  BOOST_INSTALL_PROPERTY(vertex,mylabel);
}

typedef property<edge_mylabel_t,string>               EMylabel_type;
typedef property<edge_weight_t,double, EMylabel_type> EWeight_type;
typedef property<vertex_mylabel_t,string>             VMylabel_type;

// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS, VMylabel_type, EWeight_type> Graph;

typedef property_map<Graph,edge_mylabel_t>::type   EMylabel_list_type;
typedef property_map<Graph,edge_weight_t>::type    EWeight_list_type;
typedef property_map<Graph,vertex_mylabel_t>::type VMylabel_list_type;

template <class T>
class edge_label_writer 
{
public:
  edge_label_writer(T str) : _label(str) {}
  template <class Edge>
  void operator()(ostream &out, const Edge& e) const
  {
    out << "[label=\"" << _label[e] << "\", fontsize=\"11\"]";
  }
private:
  EMylabel_list_type _label;
};

template <class T>
class vertex_label_writer
{
public:
  vertex_label_writer(T str) : _label(str) {}
  template <class Vertex>
  void operator()(ostream &out, const Vertex& w) const
  {
    out << "[label=\"" << _label[w] << "\", fontsize=\"11\"]";
  }
private:
  VMylabel_list_type _label;
};

template <class Tag>
struct edge_printer : public base_visitor<edge_printer<Tag> > 
{
  typedef Tag event_filter;
  edge_printer(string edge_t) : m_edge_type(edge_t) { }
  template <class Edge, class Graph>
  void operator()(Edge e, Graph& G) 
  {
    cout << m_edge_type << ": " << source(e, G) << " --> " <<  target(e, G) << endl;
  }
  string m_edge_type;
};

template <class Tag>
edge_printer<Tag> print_edge(string type, Tag) 
{ 
  return edge_printer<Tag>(type);
}

template <class Tag>
struct vertex_printer : public base_visitor<vertex_printer<Tag> > 
{
  typedef Tag event_filter;
  vertex_printer(string vertex_t) : m_vertex_type(vertex_t) { }
  template <class Vertex, class Graph>
  void operator()(Vertex v, Graph& G) 
  {
    cout << m_vertex_type << ": " << v << endl;
  }
  string m_vertex_type;
};

template <class Tag>
vertex_printer<Tag> print_vertex(string type, Tag) 
{ 
  return vertex_printer<Tag>(type);
}

int main()
{
  unsigned int i;
  stringstream tmp_str;

  ////////////////////////////////
  // A graph with property maps //
  ////////////////////////////////

  int nVertices = 10;
  int nEdges    = 20;

  // declare a graph object
  Graph G;

  boost::mt19937 rng;

//   template <typename MutableGraph, class RandNumGen>
//     void generate_random_graph
//     (MutableGraph& g, 
//      typename graph_traits<MutableGraph>::vertices_size_type V,
//      typename graph_traits<MutableGraph>::vertices_size_type E,
//      RandNumGen& gen,
//      bool allow_parallel = true,
//      bool self_edges = false);

  boost::generate_random_graph(G, nVertices, nEdges, rng, true, true);
  
  // Now, we randomize the weights
  boost::uniform_real<> ur(-1,10); 
  boost::variate_generator<boost::mt19937&, boost::uniform_real<> > ew1rg(rng, ur);
  randomize_property<edge_weight_t>(G, ew1rg);

  cout << "Number of edges    : " << num_edges(G) << endl;
  cout << "Number of vertices : " << num_vertices(G) << endl;
  cout << endl;

  // Now, we run across all edges and print info
  graph_traits<Graph>::edge_iterator ei, ei_end, ei_next;

  // Get the edge property maps
  EMylabel_list_type EMylabel_list = get(edge_mylabel_t(),G);
  EWeight_list_type  EWeight_list  = get(edge_weight_t(),G);

  // edges returns a tuple. It defines then range of valid edges
  tie(ei, ei_end) = edges(G);
  for (i=0, ei_next=ei; ei!=ei_end; ei=ei_next, i++) 
    {
      ++ei_next;
      // We add the property info to the edge
      tmp_str.str("");
      tmp_str << "e" << i;
      put(EMylabel_list,*ei,tmp_str.str());
      // Display the random weight
      cout << "Edge n° " << i << " Weight = " << EWeight_list[*ei] << endl;
    }

  // Now, we run across all vertices and print info
  graph_traits<Graph>::vertex_iterator vi, vi_end, vi_next;

  // Get the vertex label property map
  VMylabel_list_type VMylabel_list = get(vertex_mylabel_t(),G);

  // Vertices returns a tuple. It defines then range of valid vertices
  tie(vi, vi_end) = vertices(G);
  for (i=0, vi_next = vi; vi != vi_end; vi = vi_next, i++) 
    {
      ++vi_next;
      // We add the property info to the vertex
      tmp_str.str("");
      tmp_str << "a" << i;
      put(VMylabel_list,*vi,tmp_str.str());
    }

  cout << endl;

  typedef boost::graph_traits<Graph>::vertex_descriptor VertexDescr;
  typedef boost::graph_traits<Graph>::vertices_size_type vertex_size_type;
  
  std::vector<vertex_size_type> d(num_vertices(G));  
  std::vector<vertex_size_type> f(num_vertices(G));

  cout << "DFS categorized directed graph" << endl;

  depth_first_search(G, visitor(make_dfs_visitor(
                                                 make_list(print_edge("tree",             on_tree_edge()),
                                                           print_edge("back",             on_back_edge()),
                                                           print_edge("forward or cross", on_forward_or_cross_edge())))));

  cout << endl;

  cout << "DFS list of discovered vertices" << endl;

  //   struct on_initialize_vertex { };
  //   struct on_start_vertex { };
  //   struct on_discover_vertex { };
  //   struct on_finish_vertex { };

  //   struct on_examine_edge { };
  //   struct on_tree_edge { };
  //   struct on_cycle_edge { };
  //   struct on_forward_or_cross_edge { };
  //   struct on_back_edge { };
  //   struct on_edge_relaxed { };
  //   struct on_edge_not_relaxed { };
  //   struct on_edge_minimized { };
  //   struct on_edge_not_minimized { };
  
  depth_first_search(G, visitor(make_dfs_visitor(
                                                 make_list(print_vertex("init",     on_initialize_vertex()),
                                                           print_vertex("discover", on_discover_vertex()),
                                                           print_vertex("finish",   on_finish_vertex())))));

  cout << endl;

  cout << "BFS categorized directed graph" << endl;
  
  breadth_first_search(G, vertex(0, G), visitor(make_bfs_visitor(
                                                                 make_pair(print_edge("tree",  on_tree_edge()),
                                                                           print_edge("cycle", on_non_tree_edge())))));
  
  cout << endl;

  cout << "BFS list of discovered vertices" << endl;

  breadth_first_search(G, vertex(0, G), visitor(make_bfs_visitor(
                                                                 make_list(print_vertex("init",     on_initialize_vertex()),
                                                                           print_vertex("discover", on_discover_vertex()),
                                                                           print_vertex("finish",   on_finish_vertex())))));

  // Now print this graph in a graphviz file.
  ofstream dotfile;
  dotfile.open("test4.dot");

  write_graphviz(dotfile, G,
                 vertex_label_writer<VMylabel_list_type>(VMylabel_list),
                 edge_label_writer<EMylabel_list_type>(EMylabel_list));

  return 0;
}

The file test5.cpp: 

#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <vector>
#include <sstream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/utility.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/filtered_graph.hpp>

#include <boost/graph/graphviz.hpp>

#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/depth_first_search.hpp>

#include <boost/random/mersenne_twister.hpp> 
#include <boost/random/uniform_real.hpp>
#include <boost/graph/random.hpp>

using namespace boost;
using namespace std;

// We get all the edges for which the weight is superior to a certain threshold //

typedef adjacency_list<vecS, vecS, directedS, property<vertex_name_t, string>, property<edge_weight_t, double, property<edge_name_t, string> > > Graph;
typedef property_map<Graph, edge_weight_t>::type EdgeWeightMap;
typedef property_map<Graph, vertex_name_t>::type VertexNameMap;
typedef property_map<Graph, edge_name_t>::type   EdgeNameMap;

template <typename EdgeWeightMap>
struct positive_edge_weight 
{
  positive_edge_weight() : _Threshold(0.0) { } // Necessary because there is no inheritance. We just define a template functor
  positive_edge_weight(EdgeWeightMap weight) : m_weight(weight), _Threshold(0.0) { }
  template <typename Edge>
  bool operator()(const Edge& e) const 
  {
    return _Threshold < get(m_weight, e);
  }
  void setThreshold(double Threshold) {_Threshold = Threshold;}
  EdgeWeightMap m_weight;
  double _Threshold;
};

template <class T>
class edge_name_writer 
{
public:
  edge_name_writer(T str) : _label(str) {}
  template <class Edge>
  void operator()(ostream &out, const Edge& e) const
  {
    out << "[label=\"" << _label[e] << "\", fontsize=\"11\"]";
  }
private:
  EdgeNameMap _label;
};

template <class T>
class vertex_name_writer
{
public:
  vertex_name_writer(T str) : _label(str) {}
  template <class Vertex>
  void operator()(ostream &out, const Vertex& w) const
  {
    out << "[label=\"" << _label[w] << "\", fontsize=\"11\"]";
  }
private:
  VertexNameMap _label;
};

int main()
{
  stringstream tmp_str;

  int nVertices = 10;
  int nEdges    = 20;
  int i;

  // declare a graph object
  Graph G;

  boost::mt19937 rng;

//   template <typename MutableGraph, class RandNumGen>
//     void generate_random_graph
//     (MutableGraph& g, 
//      typename graph_traits<MutableGraph>::vertices_size_type V,
//      typename graph_traits<MutableGraph>::vertices_size_type E,
//      RandNumGen& gen,
//      bool allow_parallel = true,
//      bool self_edges = false);

  boost::generate_random_graph(G, nVertices, nEdges, rng, true, true);
  
  // Now, we randomize the weights
  boost::uniform_real<> ur(-1,10); 
  boost::variate_generator<boost::mt19937&, boost::uniform_real<> > ew1rg(rng, ur);
  randomize_property<edge_weight_t>(G, ew1rg);

  VertexNameMap list_vertex_names = get(vertex_name_t(),G);
  EdgeNameMap   list_edge_names   = get(edge_name_t(),G);
  EdgeWeightMap list_of_weights   = get(edge_weight_t(),G);

  cout << "Number of edges    : " << num_edges(G) << endl;
  cout << "Number of vertices : " << num_vertices(G) << endl;

  cout << endl;

  for(i=0;i<nVertices;i++)
    {
      tmp_str.str("");
      tmp_str << "v" << i;

      list_vertex_names[i] = tmp_str.str();
    }

  graph_traits<Graph>::edge_iterator ei, ei_end, ei_next;

  tie(ei, ei_end) = edges(G);

  double _min = list_of_weights[*ei];
  double _max = list_of_weights[*ei];

  for (i=0, ei_next=ei; ei!=ei_end; ei=ei_next, i++) 
    {
      ++ei_next;
      _min = min(_min,list_of_weights[*ei]);
      _max = max(_max,list_of_weights[*ei]);

      tmp_str.str("");
      tmp_str << "e" << i;

      list_edge_names[*ei] = tmp_str.str();
    }

  cout << "Min weight         : " << _min << endl;
  cout << "Max weight         : " << _max << endl;
  cout << endl;

  positive_edge_weight<EdgeWeightMap> filter(get(edge_weight, G));
  filter.setThreshold((_max - _min) * 0.3 + _min);

  filtered_graph<Graph, positive_edge_weight<EdgeWeightMap> > fg(G, filter);

  std::cout << "filtered edge set: ";
  print_edges(fg, list_vertex_names);

  std::cout << "filtered out-edges:" << std::endl;
  print_graph(fg, list_vertex_names);
  
  // Now print this graph in a graphviz file.
  ofstream dotfile;
  dotfile.open("test5.dot");

  write_graphviz(dotfile, G,
                 vertex_name_writer<VertexNameMap>(list_vertex_names),
                 edge_name_writer<EdgeNameMap>(list_edge_names));

  dotfile.close();

  dotfile.open("test5_filtered.dot");

  write_graphviz(dotfile, fg,
                 vertex_name_writer<VertexNameMap>(list_vertex_names),
                 edge_name_writer<EdgeNameMap>(list_edge_names));

  dotfile.close();

  return 0;
}

The file test6.cpp 

#include <boost/graph/graphviz.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>

using namespace boost;
using namespace std;

char name[] = "abcdefghij";

// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;  

struct parenthesis_visitor : public default_dfs_visitor
{
  template <class Vertex, class Graph> void
  start_vertex(Vertex v, const Graph &)
  {
    cout << ' ';
  }
  template <class Vertex, class Graph> void
  discover_vertex(Vertex v, const Graph &)
  {
    cout << "(" << name[v] << ' ';
  }
  template <class Vertex, class Graph> void
  finish_vertex(Vertex v, const Graph &)
  {
    cout << ' ' << name[v] << ")";
  }
};

int main()
{
  // Make convenient labels for the vertices
  enum { A, B, C, D, E, F, G, H, I, J, N };
  
  // writing out the edges in the graph
  typedef pair<int, int> Edge;

  Edge edge_array[] = 
    { 
      Edge(C,A), 
      Edge(A,B), 
      Edge(F,C), 
      Edge(G,F),
      Edge(F,H), 
      Edge(G,D), 
      Edge(B,E),
      Edge(B,D),
      Edge(E,D),
      Edge(I,J)
    };

  const int n_edges = sizeof(edge_array)/sizeof(edge_array[0]);
  
  // declare a graph object
  Graph Gr(N);
  
  // add the edges to the graph object
  for (int i=0;i<n_edges; ++i) add_edge(edge_array[i].first, edge_array[i].second, Gr);

  graph_traits<Graph>::edge_iterator e, e_end;
  for (tie(e,e_end)=edges(Gr); e!=e_end; ++e)
    cout << '(' << name[source(*e, Gr)] << ' ' << name[target(*e, Gr)] << ')' << endl;

  parenthesis_visitor paren_vis;
  depth_first_search(Gr, visitor(paren_vis));

  cout << endl;

  return 0;
}

The file test7.cpp 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <iostream>

using namespace boost;
using namespace std;

char name[] = "abcdefghij";

// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;  
// typedef adjacency_list<vecS, vecS, directedS>      Graph;  // in_edges not compatible with this option
// typedef adjacency_list<vecS, vecS, undirectedS>    Graph;  // out_edges = in_edges

int main()
{
  int i;

  // Make convenient labels for the vertices
  enum { A, B, C, D, E, F, G, H, I, J, N };
  
  // writing out the edges in the graph
  typedef pair<int, int> Edge;

  Edge edge_array[] = 
    { 
      Edge(C,A), 
      Edge(A,B), 
      Edge(F,C), 
      Edge(G,F),
      Edge(F,H), 
      Edge(G,D), 
      Edge(B,E),
      Edge(B,D),
      Edge(E,D),
      Edge(I,J)
    };

  const int n_edges = sizeof(edge_array)/sizeof(edge_array[0]);
  
  // declare a graph object
  Graph Gr(N);
  
  // add the edges to the graph object
  for (i=0;i<n_edges; ++i) add_edge(edge_array[i].first, edge_array[i].second, Gr);

  graph_traits<Graph>::out_edge_iterator e_out, e_out_end;
  graph_traits<Graph>::in_edge_iterator  e_in,  e_in_end;
  graph_traits<Graph>::vertex_iterator   v,     v_end;

  for(tie(v, v_end) = vertices(Gr); v!=v_end; ++v)
    {
      for (tie(e_out,e_out_end)=out_edges(*v,Gr); e_out!=e_out_end; ++e_out)
        cout << "Out edge" << *v << " -> " << name[source(*e_out, Gr)] << " - " << name[target(*e_out, Gr)] << endl;

      for (tie(e_in,e_in_end)=in_edges(*v,Gr); e_in!=e_in_end; ++e_in)
        cout << "In edge" << *v << " -> " << name[source(*e_in, Gr)] << " - " << name[target(*e_in, Gr)] << endl;

      cout << "Sum-up: leaving edges = " << out_degree(*v,Gr) << " - entering edges = " << in_degree(*v,Gr) << endl;
    }

  for(tie(v, v_end) = vertices(Gr); v!=v_end; ++v)
    {
      if ((out_degree(*v,Gr)!=0)&&(in_degree(*v,Gr)==0))
        {
          cout << "Vertex " << *v << " - source node" << endl;
        }
      else if ((out_degree(*v,Gr)==0)&&(in_degree(*v,Gr)!=0))
        {
          cout << "Vertex " << *v << " - consumer node" << endl;
        }

      else
        {
          cout << "Vertex " << *v << " - normal node" << endl;
        }
    }

  cout << endl;

  // directed_category        This says whether the graph is undirected (undirected_tag) or directed (directed_tag).
  // edge_parallel_category   This says whether the graph allows parallel edges to be inserted (allow_parallel_edge_tag) or if it 
  //                          automatically removes parallel edges (disallow_parallel_edge_tag).
  // traversal_category       The ways in which the vertices in the graph can be traversed. The traversal category tags are: 
  //                          - incidence_graph_tag
  //                          - adjacency_graph_tag
  //                          - bidirectional_graph_tag
  //                          - vertex_list_graph_tag
  //                          - edge_list_graph_tag
  //                          - vertex_and_edge_list_graph_tag
  //                          - adjacency_matrix_tag
  //                          You can also create your own tag which should inherit from one of the above. 

  if (graph_traits<Graph>::directed_category==undirected_tag)
    cout << "undirected_tag" << endl;
  if (graph_traits<Graph>::directed_category==directed_tag)
    cout << "directed_tag" << endl;

//   switch(graph_traits<Graph>::directed_category)
//     {
//     case undirected_tag:
//       cout << "undirected_tag" << endl;
//       break;
//     case directed_tag:
//       cout << "directed_tag" << endl;
//       break;
//     default:
//       cout << "error" << endl;
//     }

//   switch(graph_traits<Graph>::edge_parallel_category)
//     {
//     case allow_parallel_edge_tag:
//       cout << "allow_parallel_edge_tag" << endl;
//       break;
//     case disallow_parallel_edge_tag:
//       cout << "disallow_parallel_edge_tag" << endl;
//       break;
//     default:
//       cout << "error" << endl;
//     }

//   switch(graph_traits<Graph>::traversal_category)
//     {
//     case incidence_graph_tag:
//       cout << "incidence_graph_tag" << endl;
//       break;
//     case adjacency_graph_tag:
//       cout << "adjacency_graph_tag" << endl;
//       break;
//     case bidirectional_graph_tag:
//       cout << "bidirectional_graph_tag" << endl;
//       break;
//     case vertex_list_graph_tag:
//       cout << "vertex_list_graph_tag" << endl;
//       break;
//     case edge_list_graph_tag:
//       cout << "edge_list_graph_tag" << endl;
//       break;
//     case vertex_and_edge_list_graph_tag:
//       cout << "vertex_and_edge_list_graph_tag" << endl;
//       break;
//     case adjacency_matrix_tag:
//       cout << "adjacency_matrix_tag" << endl;
//       break;
//     default:
//       cout << "error" << endl;
//       break;
//     }

  // Now print this graph in a graphviz file.
  ofstream dotfile;
  dotfile.open("test7.dot");

  write_graphviz(dotfile, Gr);

  return 0;
}
2022-09-08 09:26