0

I have a table of vertices and edges and from this tables i created a Boost graph. each of the vertex edges had its id assign to it while the edges also contains length. now i want to prune the graph by removing nodes. my algorithm is done by creating a matrix of num_vertices. My problem is how to associate my matrix with the boost::vertices that is how do i know which of the matrix column correspond to my vertex in the graph since the matrix has no id. hope i am not thinking too complicated. 

void Nodekiller::build_matrix(){
    int ndsize=num_vertices(graph);
    double matrixtb[ndsize][ndsize];
    for(int i=0; i<ndsize;i++){
        for (int j=0;j<ndsize; j++){
            if(i==j) {matrixtb[i][j]=0;}
            else {
                matrixtb[i][j]=addEdgeValue(); //if none add random value
            }
        }
    }
}

//i want to to sum each column and then prioritize them based on the values gotten.

so i don't know how to associate the boost::vertices(graph) with the matrix in other to be able to prune the graph.

Nazaf Anwar
  • 339
  • 1
  • 8
  • 17
festy
  • 1
  • 1

1 Answers1

0

The question is not very clear. Do I understand right:

  1. You have a boost graph
  2. You create a matrix from that graph?

So a first trivial question (maybe outside of the scope): do you really need two representations of the same graphe? one as a boost::graph, and an other as your matrix?

You can add and remove edges from a boost::graph easily. The easiest representation is the adjacency list: http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/adjacency_list.html

Maybe a starting point could be this answer: adding custom vertices to a boost graph

You can create all your nodes, iterate on every node, and add a vertice only if the two nodes are different. Something like :

boost::graph_traits<Graph>::vertex_iterator vi, vi_end;

boost::tie(vi, vi_end) = boost::vertices(g);
boost::tie(vi2, vi2_end) = boost::vertices(g);
  for (; vi != vi_end; ++vi) {
    for (; vi2 != vi2_end; ++vi2) {
      if(*vi != *vi2) {
         boost::add_edge(
         edge_t e; bool b;
         boost::tie(e,b) = boost::add_edge(u,v,g);
         g[e] = addEdgeValue();
      }
  }
}
Community
  • 1
  • 1
Tristram Gräbener
  • 9,601
  • 3
  • 34
  • 50
  • maybe i didn't place the question right, the first thing is that i have a boost graph with edges and node. from this graph i have to prune nodes from the graph. the algorithm that is available to me is based on travelling time matrix while the diagonal is always zero because there is no value from travelling from node A to A. my question is, if i create a matrix of size n and compute each cells of the matrix according to the algorithm and obtain each value of the nodes, how do i identify the nodes from boost graph since no id where entered in the matrix table. – festy Dec 25 '15 at 08:28
  • well, in my example you can also remove edges that loop on a single node ;) Otherwise, if you persist in having your graph represented twice, `typedef boost::graph_traits::vertex_descriptor vertex_t;` is in fact a simple integer so you could use as an id. You might also want to look at the matrix representation of boost::graph: http://www.boost.org/doc/libs/1_58_0/libs/graph/doc/adjacency_matrix.html – Tristram Gräbener Dec 25 '15 at 15:23