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

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

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');
/* after a bit of testing, refactoring this */
addEdge(bst_graph, 2, 3); // 2 & 3 are indices!

printGraph(bst_graph)

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

Or, even better

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

A list of examples that works using matlabBGL.

## Things to be done

• Define which properties we need, and then according to that, write appropriate addX functions
• write a add_data_to_nodes functions (when (1) is decided)
• write a add_data_to_edges functions (when (1) is decided)
• interface an algorithm
• read / write boost.graph format file
• read / write graphviz format file

## 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()```

```addNode(string label)
addNode() //gets an automatic index, leaves the label blank

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

• Wrote SEP and put some details on the Wiki
• Made a detailed development plan for supporting graph operations using an independent toolbox
• Reorganized the class encapsulating the Boost graph structure from the example to support the new design ideas of the toolbox
• Refactored the existing parts of the toolbox that were previously written to use the new Api Scilab
• On track with implementing the functions from the development plan
• Did sanity check testing of the functions written

## 31st May - 4th June

• Setup eclipse to handle the toolbox code for easier development and refactoring
• Completely reorganized the code to use helper methods that would read the Scilab input arguments
• Implemented more methods for graph manipulation

## 7th - 11th June

• added more helper methods to the toolbox that read the arguments from scilab and changed the code to use them
• tried to make our version of graph print with to the graphviz format
• changed the method that gets labels and edges to use overloading
• sent code to Yann for review whose comments it will take me whole next week to apply

## 14th - 18th June

• Forgot to send out a weekly report

• wasted a day trying to make my toolbox print the graph to graphviz
• seeked help with writing the graph to graphviz with some contacts in the university that know how to use it better than myself (unfortunatelly I'm still waiting on reply)
• Applied most of the feedback I got from Yann's code review
• got a great new laptop I setup for Scilab development
• found a few bugs in the toolbox and fixed them
• Ordered matlab for the university so I could test the matlab BGL toolbox
• read through almost entire code of matlab bgl and I'm still thinking of a way to apply it to my project
• replied to Sylvestre's e-mails

## 21th - 25th June

• Finally made the toolbox work with edge & vertex weights!

• Given up on GraphViz and will discuss with mentors about possible graph visualization solutions

• Added support for altering graphs - Now node/edge properties can be set after the graph is created
• changed the getNode() to be even more flexible by taking the vertex descriptor as well. With this change all methods become more flexible and some methods become redundant so less implementation is necessary in the future
• Really noticed the need for unit testing since I've done a lot of refactoring and broke some stuff, so in progress with writing them now
• Started to implement the BFS algorithm as it is in the MatlabBGL toolbox. That required restructuring the graph class a bit, but despite that it still doesn't work correctly, so debugging in progress

Plan for next week:

• solve the problem with BFS and hopefully add more algorithms
• now that we have the ability to change graphs, write some sce files that will generate graphs and will enable creating a unit test for BFS as well

## 28th June - 2nd July

• BFS & Dijsktra written according to MatlabBGL and tested they work as they're supposed to

• Unit testing writing in progress
• DFS almost there!

Next week:

• More algorithms!

• Finish unit testing
• Get feedback from mentor and the team and wrap up for mid term review

## 5th - 9th July

• Finished DFS, Bellman-ford
• Finished unit testing
• Fixed various bugs found along the way
• Added the ability to look-up graphs by name
• Wrote unit tests for all the functionality of BglGraph structure and tests for manually checked BFS, DFS, Dijkstra algorithms

Next week:

• Tidying up files and writing comments, getting feedback

## 12th - 16th July

• Improved the graph handling library which enables a user to add/remove/lookup graphs by name, so you don't end up 'loosing' a variable
• Finalized toolbox for the midterm review

## 19th July - 23rd July

• Fixed and extended the IOHelper thanks to Yann finding a bug on 64bit!
• Read the Metanet manual to learn how to convert from Boost graph to a Metanet graph
• Extended the IOHelper library for more types for easier input/output
• Started to write functions for handing off data to Metanet

== 26th July - 3rd August ==

• Vacation Finally got the half-sister married

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

• Committed work to git
• Finished the macro and the supporting functions to convert the graph to a Metanet graph so we could display it using Metanet. In agreement with YC, the coordinates will be entered from SciLab, and not enclosed with the Boost graph itself

• Examined the examples from MatlabBGL and realized they don't apply to much to our toolbox, however, got some ideas on how to further improve and expand the toolbox
• Added the red-black tree ordering as a macro since the BFS implementation was already very flexible

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:

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/graphviz.hpp>

using namespace boost;
using namespace std;

int main()
{
int i;

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

// create a typedef for the Graph type

// 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/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[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)
{
}

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/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[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)
{
}

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)
{
}

// 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/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/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;

make_pair(print_edge("tree",  on_tree_edge()),
print_edge("cycle", on_non_tree_edge())))));

cout << endl;

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

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/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/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

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, 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
//                          - bidirectional_graph_tag
//                          - vertex_list_graph_tag
//                          - edge_list_graph_tag
//                          - vertex_and_edge_list_graph_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;
//       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;
//       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