Re: [Boost-users] Confused with BGL-- Six Degrees of Kevin Baconexample

Subject: Re: [Boost-users] Confused with BGL-- Six Degrees of Kevin Baconexample
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-05-30 10:29:33

On Thu, 30 May 2013, lizy10b wrote:

> Dear Jeremiah Willcock,
> Thanks for your reply.
>  
> As far as I am walking through the tutorial till now, all the examples use the adjacency_list < vecS, vecS....
> Though there are several different ways to construct a graph object, the "internal ids" of each vertex or edge are
?? ?all 0-based sequence and assigned implicitly.

What do you mean by "internal ids"?

> 1.So does it mean the value stored in a vertex descriptor or edge descriptor is the internal ids of the correspondi
> ng vertex or edge?
> 2.And when I am constrcting the graph using either the following 3 ways, do
> the internal ids of each vertex or edge will be stored in the vertex_index or edge_index
> property automatically? or say are the "internal ids" and the vertex_index or edge_index property the same thing?

For adjacency_list, there isn't an edge_index property.  Edge descriptors 
are not usually integers in order to make it easier to get the source 
and/or target.

> Thanks.
>  
> Example 1:
>  Edge edge_array[] = { Edge(0, 2),
>   Edge(1, 1), Edge(1, 3), Edge(1, 4),
>   Edge(2, 1), Edge(2, 3),
>   Edge(3, 4), 
>   Edge(4, 0), Edge(4, 1)
>   };
>  int num_arcs = sizeof(edge_array) / sizeof(Edge); 
>  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
>  
> For this example, I cannot number the vertex id starting from 5 to 9 for the graph which has 5 vertices.

Not unless you build your own graph type.

> If I did so, when I evaluate num_vertices(g) or loop over all the vertices using vertices(g), I got 10 vertices ins
> tead of 5.
> And the internal id of edge is the subscript number in the edge_array.

There aren't integernal ids for adjacency_list.  For 
compressed_sparse_row_graph, which does have edge numbers, they won't 
match your array indexes unless the array starts out sorted.

> Example 2:
> typedef pair<int,int> Pair;
> Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3), Pair(0,4), 
>                             Pair(2,0), Pair(3,0), Pair(2,4), Pair(3,1), 
>                             Pair(3,4), Pair(4,0), Pair(4,1) };
> MyGraphType G(5);
> for (int i=0; i<11; ++i)
>     add_edge(edge_array[i].first, edge_array[i].second, G);
>  
> For this example, the internal id of each verteices are already assgined, but the internal id of each edge depends
?? ?on its adding order?
> If I change the the "for (int i=0; i<11; ++i)" to "for (int i=10; i>=0; --i)", the internal id of each edge will be
>  inversed?
>  
>  
> Example 3 (Kevin Bacon's example):
> v = add_vertex(g); //the internal id of vertex v will be 0?
> u = add_vertex(g); //the internal id of vertex u will be 1?
> add_edge(u, v, g); //the internal id of this edge will be 0?

The edge descriptors (that you see) don't have ids directly, so there 
isn't really an answer to your question.

-- Jeremiah Willcock