Confused with BGL-- Six Degrees of Kevin Bacon example
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? Thanks. Zhiyu LI 2013-05-29 lizy10b
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
? 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
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: 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
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
Dear Jeremiah Willcock, Thanks for your explanations. I think I am starting to walk out of the chaos... For the adjacency_list, there isn't an edge_index property. That means the edge_index property is not used by the graph internally, but could be used by user just like the edge_weight or edge_name, and these property should be assgined by user manually. So in the examples "exterior_properties.cpp", I could replace all the strings "edge_index" with "edge_weight", and doing this will not affect the result. The property map works in this case beacuse the edge_index property is type of int, and the value of the edge_index property is the offset to the beginning of the underlying property containers (int capacity[] and int flow[]). And the whole mapping process when calling the "boost::get(capacity, *out)" includes two mappings: Frist mapping: KEY=*out (edge descriptor)-->VALUE = offset value (int) Second mapping: KEY=offset value (int) --> VALUE= the corresponding property value Am I right? Thanks. Zhiyu LI "exterior_properties.cpp": typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::property<boost::edge_index_t, std::size_t> > Graph; int capacity[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 }; int flow[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 }; boost::add_edge(0, 1, 0, G); boost::add_edge(1, 4, 1, G); ... typedef boost::property_map<Graph, boost::edge_index_t>::type EdgeIndexMap; EdgeIndexMap edge_id = boost::get(boost::edge_index, G); boost::iterator_property_map <int*, EdgeIndexMap, int, int&> capacity_array(capacity, edge_id), flow_array(flow, edge_id); print_network(G, capacity_array, flow_array); inside the function print_network: boost::get(capacity, *out) ...
On Fri, 31 May 2013, lizy10b wrote:
Dear Jeremiah Willcock, Thanks for your explanations. I think I am starting to walk out of the chaos... For the adjacency_list, there isn't an edge_index property. That means the edge_index property is not used by the graph internally, but could be used by user just like the edge_weight or edge_name, and these property should be assgined by user manually. So in the examples "exterior_properties.cpp", I could replace all the strings "edge_index" with "edge_weight", and doing this will not affect the result.
Yes, except that algorithms that create their own external property maps on edges (I don't know if there are any) would by default use the name edge_index_t, and you would need to pass in a different property map as an argument to use it instead.
The property map works in this case beacuse the edge_index property is type of int, and the value of the edge_index property is the offset to the beginning of the underlying property containers (int capacity[] and int flow[]). And the whole mapping process when calling the "boost::get(capacity, *out)" includes two mappings: Frist mapping: KEY=*out (edge descriptor)-->VALUE = offset value (int) Second mapping: KEY=offset value (int) --> VALUE= the corresponding property value Am I right?
Yes, that's exactly how it works. For put(), the first mapping is the same, while the second one writes to the array at the offset instead of reading from it. -- Jeremiah Willcock
"exterior_properties.cpp": typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::property<boost::edge_index_t, std::size_t> > Graph; int capacity[] = { 10, 20, 20, 20, 40, 40, 20, 20, 20, 10 }; int flow[] = { 8, 12, 12, 12, 12, 12, 16, 16, 16, 8 }; boost::add_edge(0, 1, 0, G); boost::add_edge(1, 4, 1, G); ... typedef boost::property_map<Graph, boost::edge_index_t>::type EdgeIndexMap; EdgeIndexMap edge_id = boost::get(boost::edge_index, G); boost::iterator_property_map <int*, EdgeIndexMap, int, int&> capacity_array(capacity, edge_id), flow_array(flow, edge_id); print_network(G, capacity_array, flow_array); inside the function print_network: boost::get(capacity, *out) ...
participants (2)
-
Jeremiah Willcock
-
lizy10b