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

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