Re: [Boost-users] distributed breadth first search doesn't work properly?

Subject: Re: [Boost-users] distributed breadth first search doesn't work properly?
From: Cedric Laczny (cedric.laczny_at_[hidden])
Date: 2010-12-08 09:40:22

Hi,

On Wednesday, 8. December 2010 10:49:54 Mattia Lambertini wrote:
> Hi, i am new to boost and i'm using the PBGL to write a software that
> compute some graph analysis. I've installed boost 1.44.0 and openmpi 1.5
> 
> I tried to run the breadth first search example located in
> $BOOST_ROOT/libs/graph_parallel/example
> 
> with the graph $BOOST_ROOT/libs/graph/test/weighted_graph.gr
> 
> 
> All went well since i figure out that the result is different if i run the
> algorithm with a different number of processors.
> Only with one processor the values are corrected.
> 
> here's what happens:
> 
> mpirun -np 1 ./breadth_first_search.out
> 
> graph g {
>   subgraph cluster_0 {
>     label="p0";
>     n0[label=0];
>     n1[label=2];
>     n2[label=1];
>     n3[label=2];
>     n4[label=1];
>   }
> 
>   n0 -- n2;
>   n1 -- n1;
>   n1 -- n3;
>   n1 -- n4;
>   n2 -- n1;
>   n2 -- n3;
>   n3 -- n4;
>   n4 -- n0;
>   n4 -- n1;
> }
> 
> ---------------------
> 
> mpirun -np 2 ./breadth_first_search.out
> 
> graph g {
>   subgraph cluster_0 {
>     label="p0";
>     n0[label=0];
>     n1[label=1];
>     n2[label=1];
>   }
> 
>   n0 -- n2;
>   n1 -- n1;
>   n1 -- n3;
>   n1 -- n4;
>   n2 -- n1;
>   n2 -- n3;
> 
>   subgraph cluster_1 {
>     label="p1";
>     n3[label=1];
>     n4[label=0];
>   }
> 
>   n3 -- n4;
>   n4 -- n0;
>   n4 -- n1;
> }
> 
> Is that correct?

I am not sure if this correct, but respecting the concept of PBGL, where the 
vertices are local to processors, it seems reasonable.
After all, the edges are the same, except they are split up into different 
subgraphs, which again looks reasonable if one thinks of the subgraphs local 
to the processors (due to the local vertices).

Perhaps you might try to run it on more processors and see if you get the 
according number ob subgraphs?

> >From the doc i can't figure out why..

Best,

Cedric