breadth_first_searchable graph, without invalidable vertex descriptors

older
RE: [Boost-Users] question about...

cristipp＠ics.uci.edu

21 Nov 2001 21 Nov '01

2:03 a.m.

Hello, I am trying to use the BCG as backbone for a ControlFlowGraph in a compiler project. It seems that I cannot use BCG for this task because of the follow contradicting (from BCG point of view) requirements: 1. I want to be able to breadth_first_search through my graph. 2. I want to be able to keep descriptors to vertices 'for ever' so I can refer a specific vertex at any given time (for removal or whatever other reasons). To implement requirement 1 my adjacency_list should have its VertexList of type vecS. To implement requirement 2 my adjacency_list should have its VertexList of type listS. Unfortunately those are mutualy exclusive and it seems that BCG is unsuited for the job. But I can't really think of a decent generic graph library unable to support those requirements. After all, it's all about being able to use basic graph traversals on randomly mutating graphs. STL has the list which has those nice properties, why a graph library should be different?! Perhaps I am missing something and I am asking for help: how should I declare my graph and how can I do a bfs on it? Thanks in advance, Cristi

Show replies by date

Jeremy Siek

21 Nov 21 Nov

3:44 a.m.

New subject: [Boost-Users] breadth_first_searchable graph, without invalidable vertex descriptors

Hi Cristy, On Wed, 21 Nov 2001 cristipp@ics.uci.edu wrote: cristi> I am trying to use the BCG as backbone for a ControlFlowGraph in a cristi> compiler project. It seems that I cannot use BCG for this task cristi> because of the follow contradicting (from BCG point of view) cristi> requirements: What is BCG? I will assume you mean the boost::adjacency_list class. cristi> 1. I want to be able to breadth_first_search through my graph. cristi> 2. I want to be able to keep descriptors to vertices 'for ever' so I cristi> can refer a specific vertex at any given time (for removal or cristi> whatever other reasons). cristi> cristi> To implement requirement 1 my adjacency_list should have its cristi> VertexList of type vecS. This is not required. The VertexList can be listS. However, you do need to provide your own color map parameter if you use listS. Cheers, Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------

cristipp＠ics.uci.edu

4:16 a.m.

Thanks. I added the vertex_color property to my graph and it works just fine. As a BGL (and not BCG :-)) novice I would like to understand why the breadth_first_search compiles for boost::adjacency_list with VertexType vecS, but not for boost::adjacency_list with VertexType listS (unless the colormap is passed as a parameter). Is there any piece of documentation I should have read and I did not? Or could anybody explain this for us, the big herd of users? Keep up the good work! Cristi --- In Boost-Users@y..., Jeremy Siek wrote:

...

Hi Cristy,

On Wed, 21 Nov 2001 cristipp@i... wrote: cristi> I am trying to use the BCG as backbone for a ControlFlowGraph in a cristi> compiler project. It seems that I cannot use BCG for this task cristi> because of the follow contradicting (from BCG point of view) cristi> requirements:

What is BCG? I will assume you mean the boost::adjacency_list class.

cristi> 1. I want to be able to breadth_first_search through my graph. cristi> 2. I want to be able to keep descriptors to vertices 'for ever' so I cristi> can refer a specific vertex at any given time (for removal or cristi> whatever other reasons). cristi> cristi> To implement requirement 1 my adjacency_list should have its cristi> VertexList of type vecS.

This is not required. The VertexList can be listS. However, you do need to provide your own color map parameter if you use listS.

Cheers, Jeremy

-------------------------------------------------------------------- -- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@o... C++ Booster (http://www.boost.org) office phone: (812) 855-3608 -------------------------------------------------------------------- --

Jeremy Siek

1:59 p.m.

New subject: [Boost-Users] Re: breadth_first_searchable graph, without invalidable vertex descriptors

...

From adjacency_list.html: "If the VertexList of the graph is vecS, then the graph has a builtin vertex indices accessed via the property map for the vertex_index_t

On Wed, 21 Nov 2001 cristipp@ics.uci.edu wrote: cristi> Thanks. I added the vertex_color property to my graph and it works cristi> just fine. Great! cristi> As a BGL (and not BCG :-)) novice I would like to cristi> understand why the breadth_first_search compiles for cristi> boost::adjacency_list with VertexType vecS, but not for cristi> boost::adjacency_list with VertexType listS (unless the cristi> colormap is passed as a parameter). Is there any piece of cristi> documentation I should have read and I did not? Or could cristi> anybody explain this for us, the big herd of users? Sure. Take a look at the docs in breadth_first_search.html, specifically the color_map named parameter. As with most named parameters, you can either pass in an argument, or use the default. The default in this case is: "Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map." where i_map is the vertex index map given as another named paremeter: "IN: vertex_index_map(VertexIndexMap i_map) This maps each vertex to an integer in the range [0, num_vertices(g)). This parameter is only necessary when the default color property map is used. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map. Default: get(vertex_index, g)" Now, an adjacency_list only has a builtin vertex index map if it has VertexList=vecS: property." Alternatively, you could add a vertex index map to an adjacency_list with VertexList=listS using a property but you would need to remember to initialize the indices yourself and make sure that the vertices are numbered in the range [0,num_vertices(g)) (which is a needed by the BFS algorithm and others). cristi> Keep up the good work! cristi> Cristi Thanks! Jeremy ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------

Jeremy Siek

4:17 a.m.

New subject: [Boost-Users] breadth_first_searchable graph, without invalidable vertex descriptors

I've attached an example of using breadth_first_search with an adjacency_list where VertexList=listS. Cheers, Jeremy On Tue, 20 Nov 2001, Jeremy Siek wrote: jsiek> cristi> To implement requirement 1 my adjacency_list should have its jsiek> cristi> VertexList of type vecS. jsiek> jsiek> This is not required. The VertexList can be listS. However, you do need jsiek> to provide your own color map parameter if you use listS. ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ---------------------------------------------------------------------- ---------- //======================================================================= // Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee, // // This file is part of the Boost Graph Library // // You should have received a copy of the License Agreement for the // Boost Graph Library along with the software; see the file LICENSE. // If not, contact Office of Research, Indiana University, // Bloomington, IN 47405. // // Permission to modify the code and to distribute the code is // granted, provided the text of this NOTICE is retained, a notice if // the code was modified is included with the above COPYRIGHT NOTICE // and with the COPYRIGHT NOTICE in the LICENSE file, and that the // LICENSE file is distributed with the modified code. // // LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED. // By way of example, but not limitation, Licensor MAKES NO // REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY // PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS // OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS // OR OTHER RIGHTS. //======================================================================= #include #include #include #include using namespace boost; template < typename TimeMap > class bfs_time_visitor:public default_bfs_visitor { typedef typename property_traits < TimeMap >::value_type T; public: bfs_time_visitor(TimeMap tmap, T & t):m_timemap(tmap), m_time(t) { } template < typename Vertex, typename Graph > void discover_vertex(Vertex u, const Graph & g) const { put(m_timemap, u, m_time++); } TimeMap m_timemap; T & m_time; }; int main() { using namespace boost; // Select the graph type we wish to use typedef adjacency_list < listS, listS, undirectedS, property > > graph_t; // Set up the vertex IDs and names enum { r, s, t, u, v, w, x, y, N }; const char *name = "rstuvwxy"; // Specify the edges in the graph typedef std::pair < int, int >E; E edge_array[] = { E(r, s), E(r, v), E(s, w), E(w, r), E(w, t), E(w, x), E(x, t), E(t, u), E(x, y), E(u, y) }; // Create the graph object const int n_edges = sizeof(edge_array) / sizeof(E); #ifdef BOOST_MSVC // VC++ has trouble with the edge iterator constructor graph_t g; std::vector::vertex_descriptor> verts; for (std::size_t i = 0; i < N; ++i) verts.push_back(add_vertex(g)); for (std::size_t j = 0; j < n_edges; ++j) add_edge(verts[edge_array[j].first], verts[edge_array[j].second], g); #else typedef graph_traits::vertices_size_type v_size_t; graph_t g(edge_array, edge_array + n_edges, v_size_t(N)); #endif // Typedefs typedef graph_traits::vertex_descriptor Vertex; typedef graph_traits::vertices_size_type Size; typedef Size* Iiter; Size time = 0; typedef property_map::type dtime_map_t; dtime_map_t dtime_map = get(vertex_discover_time, g); bfs_time_visitor < dtime_map_t > vis(dtime_map, time); breadth_first_search(g, vertex(s, g), color_map(get(vertex_color, g)). visitor(vis)); // a vector to hold the discover time property for each vertex std::vector < Size > dtime(num_vertices(g)); graph_traits::vertex_iterator vi, vi_end; std::size_t c = 0; for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++c) dtime[c] = dtime_map[*vi]; // Use std::sort to order the vertices by their discover time std::vector::vertices_size_type > discover_order(N); integer_range < int >range(0, N); std::copy(range.begin(), range.end(), discover_order.begin()); std::sort(discover_order.begin(), discover_order.end(), indirect_cmp < Iiter, std::less < Size > >(&dtime[0])); std::cout << "order of discovery: "; for (int i = 0; i < N; ++i) std::cout << name[discover_order[i]] << " "; std::cout << std::endl; return EXIT_SUCCESS; } [Non-text portions of this message have been removed]

Jeremy Siek

4:20 a.m.

New subject: [Boost-Users] breadth_first_searchable graph, without invalidable vertex descriptors

P.S. The attached example exposed a subtle const correctness bug in property_map.hpp. I've checked the fix into CVS, so you'll need to get an update. ---------------------------------------------------------------------- Jeremy Siek http://php.indiana.edu/~jsiek/ Ph.D. Student, Indiana Univ. B'ton email: jsiek@osl.iu.edu C++ Booster (http://www.boost.org) office phone: (812) 855-3608 ----------------------------------------------------------------------

8407

Age (days ago)

8407

Last active (days ago)

List overview

Download

5 comments

2 participants

participants (2)

cristipp＠ics.uci.edu
Jeremy Siek