Re: [Boost-users] Boost Graph some newbie questions

Subject: Re: [Boost-users] Boost Graph some newbie questions
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-03-30 08:55:26

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_matrix<boost::directedS> ?

You should be able to.

-- Jeremiah Willcock