Boost Graph some newbie questions
Hello, Although some time ago I used boost graph in some of my projects I found this library too generic for me :) I still have some questions: 1. How to check if my graph is a tree? 2. How to generate random graph? (using generate_random_graph) - I can't find any examples of random graph generation so it should be very very easy and I need the simplest possible example. 3. How to use layout functions like random_graph_layout? - as in the question above I can't find any examples. 4. Can I perform all this actions on graph of type boost::adjacency_matrixboost::directedS ? -- Regards Michał Nowotka
For the first question, I think you can use the breadth first search with a
BFSVistor which throws an exception in vis.non_tree_edge(e,g).
if any exception throwed, the graph is not a tree
2010/3/30 Michał Nowotka
Hello, Although some time ago I used boost graph in some of my projects I found this library too generic for me :) I still have some questions:
1. How to check if my graph is a tree? 2. How to generate random graph? (using generate_random_graph) - I can't find any examples of random graph generation so it should be very very easy and I need the simplest possible example. 3. How to use layout functions like random_graph_layout? - as in the question above I can't find any examples.
4. Can I perform all this actions on graph of type boost::adjacency_matrixboost::directedS ?
-- Regards
Michał Nowotka _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Tue, 30 Mar 2010, Michał Nowotka wrote:
Hello, Although some time ago I used boost graph in some of my projects I found this library too generic for me :) I still have some questions:
1. How to check if my graph is a tree?
For undirected graphs, the easiest way is to use breadth_first_search with a visitor that throws an exception when a non-tree edge is found. If there are no such edges, the graph is a tree. This should work on directed graphs as well as long as you start at the root; you would then also want to be sure all vertices in the graph were visited.
2. How to generate random graph? (using generate_random_graph) - I can't find any examples of random graph generation so it should be very very easy and I need the simplest possible example.
Look at section 24.7 (Tools for random graphs) of the BGL documentation table of contents. In particular, you probably want erdos_renyi_iterator, plod_iterator, or small_world_iterator. Look on the erdos_renyi_iterator page for an example of how to use it.
3. How to use layout functions like random_graph_layout? - as in the question above I can't find any examples.
boost::minstd_rand gen; boost::rectangle_topology<> rect_top(gen, -25, -25, 25, 25); boost::random_graph_layout(g, get(vertex_position, g), rect_top); (extracted from libs/graph/test/layout_test.cpp) is approximately what you need for the basic case. The four numbers in rect_top are the bounding box to lay the graph out within.
4. Can I perform all this actions on graph of type boost::adjacency_matrixboost::directedS ?
You should be able to. -- Jeremiah Willcock
Thanks, you helped me o lot. Answers for questions 1,2 and 4 are clear for me. In question 3 I don't know how to define vertex_position (what type it has?) and how to retrieve actual vertex positions from it? And one more question: Given a graph of type boost::adjacency_matrixboost::directedS how can I access (directly) adjacency matrix for this graph? I suppose this graph is based on same std container. I want to use some genetic algorithm with genetic operators that should be able to operate directly on such container in order to (for example) flip some items or invert random selected items. -- Regards Michał Nowotka
On Tue, 30 Mar 2010, Michał Nowotka wrote:
Thanks, you helped me o lot. Answers for questions 1,2 and 4 are clear for me. In question 3 I don't know how to define vertex_position (what type it has?) and how to retrieve actual vertex positions from it?
You just define a property map (either internal or external) whose value type is rectangle_topology<>::point_type and pass that into the algorithm as the position map. That type has operator[] to get individual coordinates (0 for x, 1 for y).
And one more question:
Given a graph of type boost::adjacency_matrixboost::directedS how can I access (directly) adjacency matrix for this graph? I suppose this graph is based on same std container. I want to use some genetic algorithm with genetic operators that should be able to operate directly on such container in order to (for example) flip some items or invert random selected items.
I do not believe there is an "official" way to do that -- you can use add_edge and remove_edge, and those are reasonably direct (when your edges don't have properties). The m_matrix member is (unofficially) public, so you can get to the raw matrix, but what is stored in there is complicated and it has a triangular layout for undirected graphs. Try using edge(), add_edge(), and remove_edge() and see if those are too slow before using internal details. -- Jeremiah Willcock
participants (3)
-
Jeremiah Willcock -
Michał Nowotka -
吴焱