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

Subject: Re: [Boost-users] Confused with BGL-- Six Degrees of Kevin Baconexample
From: lizy10b (lizy10b_at_[hidden])
Date: 2013-05-29 22:48:37

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.

1.So does it mean the value stored in a vertex descriptor or edge descriptor is the internal ids of the corresponding 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?
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.
If I did so, when I evaluate num_vertices(g) or loop over all the vertices using vertices(g), I got 10 vertices instead of 5.
And the internal id of edge is the subscript number in the edge_array.

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?

Thanks.

Zhiyu LI
2013-05-30 



lizy10b 



·¢¼þÈË£º Jeremiah Willcock 
·¢ËÍʱ¼ä£º 2013-05-30  02:17:52 
ÊÕ¼þÈË£º boost-users 
³­ËÍ£º lizy10b 
Ö÷Ì⣺ Re: [Boost-users] Confused with BGL-- Six Degrees of Kevin Baconexample 
 
On Wed, 29 May 2013, lizy10b wrote:
> ?
> Hi there,
>   I am new to BGL library.?
>   I am walking through the online tutorial and just finished the "10.2. Six Degrees of Kevin Bacon".
>   
>   As it is said at the end of the example:?Note that vertex descriptor objects can not always be used as?
> indices into vectors or arrays such as bacon_number. This is valid with the?
> adjacency_list class with VertexList=vecS, but not with other variations of?
> adjacency_list. A more generic way to index based on vertices is to use the?
> ID property map?vertex_index_t) in coordination with the iterator_property_map.".
>   
> ?So I turn to have a look at the iterator_property_map page and its sample.?
> First, this sample uses VertexList=vecS too.?
> Second, I know this sample is using iterator_property_map to build a property map,?
> but I think the property is still indexed by the edge descriptor objects.    
>  So what is the difference?
I'm not sure I fully understand what you are asking, but here is the 
general picture of iterator_property_map, vertex_index[_t], and 
edge_index[_t]:
The fastest-to-access property maps in BGL for data storage are the 
iterator property maps, which use a vector, array, or similar as 
underlying storage and allow it to be indexed by vertex or edge 
descriptors.  The "catch" with that is that vectors and such require 
integers to index into them, and a vertex or edge descriptor may not be an 
integer (or may not map one-to-one onto a contiguous sequence of numbers 
in the correct range).  Although many BGL graph types do have that 
property for vertex descriptors (such as the vecS case you mention), some 
don't (such as grid_graph) and most do not have it for edge descriptors. 
Thus, a separate property map is needed to map from descriptors to indexes 
into the underlying containers.  By default, the vertex_index and 
edge_index property maps of a graph are used for that.  In the vecS case, 
the vertex index map is an identity function, but generic code cannot rely 
on that.  For grid_graph, the mapping can be accessed but is not the 
identity function, and the same is true for edge descriptors in 
compressed_sparse_row_graph.
One problem you may see with this is how you would create an index map 
when it is not built into a graph: after all, iterator_property_map 
requires the index map to already exist.  There are two solutions for 
that, both involving the user creating the index numbers manually.  The 
first is to have a vertex_index_t or edge_index_t internal property as one 
of the user-defined properties added to the graph, and the other is to use 
something like an associative_property_map (assuming there are comparison 
operators on the descriptors in question).  For either type of storage, 
the user would need to loop over the vertices and edges, assign them 
sequential numbers, and put those into the map.
Does that start to answer your question, or did you intend to ask 
something else?
-- Jeremiah Willcock
_______________________________________________
Boost-users mailing list
Boost-users_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users