[BGL] Trying to get a correclty working Parallel BFS code

[sansanx]

Hi All,
  I  have spent significant effort on parallel bfs. Currently its almost
working. I would really appreciate some help to get it running correctly. I
have attached the code (self contained and requires no input file).
I think I have followed all the guidelines regarding distributed property
maps mentioned in the docs (
http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
).
I am out of ideas of where things can could have gone wrong.

The correct output of input graph
0 --> 1 2
1 --> 2 3
2 --> 3
3 --> 4 6
4 --> 5
5 -->
6 -->
should be
Node ID    :  Level
0  :  0
1  :  1
2  :  1
3  :  2
4  :  3
5  :  4
6  :  3

But when ran with 2 processes the output comes out to be
Node ID    :  Level
0  :  0
1  :  1
2  :  1
3  :  2
4  :  3
5  :  4294967295
6  :  3

Not sure why this is happening. Any suggestions or pointers would indeed be
quite appreciated. Thanks for your time.

-Sandeep


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jeremiah Willcock]

On Mon, 26 Oct 2009, Sandeep Gupta wrote:

> Hi All,
>  I  have spent significant effort on parallel bfs. Currently its almost
> working. I would really appreciate some help to get it running correctly. I
> have attached the code (self contained and requires no input file).
> I think I have followed all the guidelines regarding distributed property
> maps mentioned in the docs (
> http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
> ).
> I am out of ideas of where things can could have gone wrong.

The graph is distributed by source vertex across all processors, and so
you need to add them on every processor (or at least on the processor that
owns them, which is probably not processor 0).  Thus, your graph is
missing whichever edges would be on processor 1, leading to incorrect
results.  Try adding all of the edges on all processors and see if this
fixes your problem.

-- Jeremiah Willcock
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Mon, Oct 26, 2009 at 11:29 PM, Jeremiah Willcock <jewillco@...>wrote:

> On Mon, 26 Oct 2009, Sandeep Gupta wrote:
>
>  Hi All,
>>  I  have spent significant effort on parallel bfs. Currently its almost
>> working. I would really appreciate some help to get it running correctly.
>> I
>> have attached the code (self contained and requires no input file).
>> I think I have followed all the guidelines regarding distributed property
>> maps mentioned in the docs (
>>
>> http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
>> ).
>> I am out of ideas of where things can could have gone wrong.
>>
>
> The graph is distributed by source vertex across all processors, and so you
> need to add them on every processor (or at least on the processor that owns
> them, which is probably not processor 0).  Thus, your graph is missing
> whichever edges would be on processor 1, leading to incorrect results.  Try
> adding all of the edges on all processors and see if this fixes your
> problem.
>
> -- Jeremiah Willcock
>
>

Jeremiah, thanks so much looking into this promptly. I took cues from
building distributed graph section of distributed adjacency list page which
has an example:

///---------------Begin example

Graph g(n); // initialize with the total number of vertices, n
if (process_id(g.process_group()) == 0) {
  // Only process 0 loads the graph, which is distributed automatically
  int source, target;
  for (std::cin >> source >> target)
    add_edge(vertex(source, g), vertex(target, g), g);
}

// All processes synchronize at this point, then the graph is complete
synchronize(g.process_group());
//---------End

Looking at this, it seems that distribution happens automatically which is
what the manual says.
This is further confirmed when I output the subgraphs at each process.

Subgraph For process 0
  n0 -> n1;
  n0 -> n2;
  n1 -> n2;
  n1 -> n3;
  n2 -> n3;
  n3 -> n4;
  n3 -> n6;
Subgraph End

Subgraph For process 1
  n4 -> n5;
Subgraph End



As you suggested I also tried adding all the edges on all the processes.
Unfortunately, the problem still remains the same. The BFS output is

Node ID    :  Level
0  :  0
1  :  1
2  :  1
3  :  2
4  :  3
5  :  4294967295
6  :  3

and the edges gets duplicated
Subgraph For process 0
  n0 -> n1;
  n0 -> n2;
  n0 -> n1;
  n0 -> n2;
  n1 -> n2;
  n1 -> n3;
  n1 -> n2;
  n1 -> n3;
  n2 -> n3;
  n2 -> n3;
  n3 -> n4;
  n3 -> n6;
  n3 -> n4;
  n3 -> n6;
Subgraph End

 Subgraph For process 1
  n4 -> n5;
  n4 -> n5;
Subgraph End


Hope this  clarifies  the problem a bit better and that i helps to pinpoint
the source of error. Appreciate your input.

Thanks
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jeremiah Willcock]

On Tue, 27 Oct 2009, Sandeep Gupta wrote:

> On Mon, Oct 26, 2009 at 11:29 PM, Jeremiah Willcock <jewillco@...>wrote:
>
>> On Mon, 26 Oct 2009, Sandeep Gupta wrote:
>>
>>  Hi All,
>>>  I  have spent significant effort on parallel bfs. Currently its almost
>>> working. I would really appreciate some help to get it running correctly.
>>> I
>>> have attached the code (self contained and requires no input file).
>>> I think I have followed all the guidelines regarding distributed property
>>> maps mentioned in the docs (
>>>
>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
>>> ).
>>> I am out of ideas of where things can could have gone wrong.
>>>
>>
>> The graph is distributed by source vertex across all processors, and so you
>> need to add them on every processor (or at least on the processor that owns
>> them, which is probably not processor 0).  Thus, your graph is missing
>> whichever edges would be on processor 1, leading to incorrect results.  Try
>> adding all of the edges on all processors and see if this fixes your
>> problem.
>>
>> -- Jeremiah Willcock
>>
>>
>
> Jeremiah, thanks so much looking into this promptly. I took cues from
> building distributed graph section of distributed adjacency list page which
> has an example:
>
> ///---------------Begin example
>
> Graph g(n); // initialize with the total number of vertices, n
> if (process_id(g.process_group()) == 0) {
>  // Only process 0 loads the graph, which is distributed automatically
>  int source, target;
>  for (std::cin >> source >> target)
>    add_edge(vertex(source, g), vertex(target, g), g);
> }
>
> // All processes synchronize at this point, then the graph is complete
> synchronize(g.process_group());
> //---------End
>
> Looking at this, it seems that distribution happens automatically which is
> what the manual says.
> This is further confirmed when I output the subgraphs at each process.

OK.  I was mistaken on this point then.  Could you please try the
following graph with a distribution that puts vertices 0-3 on rank 0 and
4 on rank 1 (just add three dummy vertices on the end and use a block
distribution)?

0 -> 1
1 -> 2
2 -> 3
0 -> 4
4 -> 3

See if the depths are reasonable for that graph.  Also, the contents of
the predecessor maps output by your search (both the original one and the
graph I just gave) would be nice too; that is just an extra map you can
give to BFS and you can just dump it the same way you dump depth values.

-- Jeremiah Willcock
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Tue, Oct 27, 2009 at 10:27 AM, Jeremiah Willcock <jewillco@...>wrote:

> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>
>  On Mon, Oct 26, 2009 at 11:29 PM, Jeremiah Willcock <jewillco@...
>> >wrote:
>>
>>  On Mon, 26 Oct 2009, Sandeep Gupta wrote:
>>>
>>>  Hi All,
>>>
>>>>  I  have spent significant effort on parallel bfs. Currently its almost
>>>> working. I would really appreciate some help to get it running
>>>> correctly.
>>>> I
>>>> have attached the code (self contained and requires no input file).
>>>> I think I have followed all the guidelines regarding distributed
>>>> property
>>>> maps mentioned in the docs (
>>>>
>>>>
>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
>>>> ).
>>>> I am out of ideas of where things can could have gone wrong.
>>>>
>>>>
>>> The graph is distributed by source vertex across all processors, and so
>>> you
>>> need to add them on every processor (or at least on the processor that
>>> owns
>>> them, which is probably not processor 0).  Thus, your graph is missing
>>> whichever edges would be on processor 1, leading to incorrect results.
>>>  Try
>>> adding all of the edges on all processors and see if this fixes your
>>> problem.
>>>
>>> -- Jeremiah Willcock
>>>
>>>
>>>
>> Jeremiah, thanks so much looking into this promptly. I took cues from
>> building distributed graph section of distributed adjacency list page
>> which
>> has an example:
>>
>> ///---------------Begin example
>>
>> Graph g(n); // initialize with the total number of vertices, n
>> if (process_id(g.process_group()) == 0) {
>>  // Only process 0 loads the graph, which is distributed automatically
>>  int source, target;
>>  for (std::cin >> source >> target)
>>   add_edge(vertex(source, g), vertex(target, g), g);
>> }
>>
>> // All processes synchronize at this point, then the graph is complete
>> synchronize(g.process_group());
>> //---------End
>>
>> Looking at this, it seems that distribution happens automatically which is
>> what the manual says.
>> This is further confirmed when I output the subgraphs at each process.
>>
>
> OK.  I was mistaken on this point then.  Could you please try the following
> graph with a distribution that puts vertices 0-3 on rank 0 and 4 on rank 1
> (just add three dummy vertices on the end and use a block distribution)?
>
> 0 -> 1
> 1 -> 2
> 2 -> 3
> 0 -> 4
> 4 -> 3
>
> See if the depths are reasonable for that graph.  Also, the contents of the
> predecessor maps output by your search (both the original one and the graph
> I just gave) would be nice too; that is just an extra map you can give to
> BFS and you can just dump it the same way you dump depth values.
>
>

> I tried adding predecessor map but I don't think its currently. No
> reduction function is defined for predecessor map. Please see below for the
> attached error.
>
 I tried the bfs with your input (and distribution) and the depth number are
coming out to be incorrect. This is a surely a better input to debug this
problem:-).
The depth value of node n=3 should be d=2 but its coming out to be d=0.
I believe the update message from node n=4 on process 1 is not received or
updated by process 0.
Attached below is the output of levels:
Finished Parallel BFS
Node ID    :  Level
0  :  0
1  :  1
2  :  2
3  :  0
4  :  1
5  :  4294967295
6  :  4294967295
7  :  4294967295

The two subgraphs on each process
Subgraph Begin
  n0 -> n1;
  n0 -> n4;
  n1 -> n2;
  n2 -> n3;
Subgraph End

Subgraph Begin
  n4 -> n3;
Subgraph End

Thanks,
Sandeep

//-------------------------
The error snippet regarding  predecessor map:

error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
(const boost::detail::parallel::global_descriptor<unsigned int>&)'


../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
error: no match for call to
'(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
(const boost::detail::parallel::global_descriptor<unsigned int>&,
boost::detail::error_property_not_found&, const
boost::detail::error_property_not_found&)'
../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
const [with T = boost::detail::error_property_not_found]
../../../boost/graph/parallel/properties.hpp:96: note:                 T
boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
T, T) const [with T = boost::detail::error_property_not_found]
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Tue, Oct 27, 2009 at 12:33 PM, Sandeep Gupta <gupta.sandeep@...>wrote:

>
>
> On Tue, Oct 27, 2009 at 10:27 AM, Jeremiah Willcock <jewillco@...>wrote:
>
>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>
>>  On Mon, Oct 26, 2009 at 11:29 PM, Jeremiah Willcock <jewillco@...
>>> >wrote:
>>>
>>>  On Mon, 26 Oct 2009, Sandeep Gupta wrote:
>>>>
>>>>  Hi All,
>>>>
>>>>>  I  have spent significant effort on parallel bfs. Currently its almost
>>>>> working. I would really appreciate some help to get it running
>>>>> correctly.
>>>>> I
>>>>> have attached the code (self contained and requires no input file).
>>>>> I think I have followed all the guidelines regarding distributed
>>>>> property
>>>>> maps mentioned in the docs (
>>>>>
>>>>>
>>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
>>>>> ).
>>>>> I am out of ideas of where things can could have gone wrong.
>>>>>
>>>>>
>>>> The graph is distributed by source vertex across all processors, and so
>>>> you
>>>> need to add them on every processor (or at least on the processor that
>>>> owns
>>>> them, which is probably not processor 0).  Thus, your graph is missing
>>>> whichever edges would be on processor 1, leading to incorrect results.
>>>>  Try
>>>> adding all of the edges on all processors and see if this fixes your
>>>> problem.
>>>>
>>>> -- Jeremiah Willcock
>>>>
>>>>
>>>>
>>> Jeremiah, thanks so much looking into this promptly. I took cues from
>>> building distributed graph section of distributed adjacency list page
>>> which
>>> has an example:
>>>
>>> ///---------------Begin example
>>>
>>> Graph g(n); // initialize with the total number of vertices, n
>>> if (process_id(g.process_group()) == 0) {
>>>  // Only process 0 loads the graph, which is distributed automatically
>>>  int source, target;
>>>  for (std::cin >> source >> target)
>>>   add_edge(vertex(source, g), vertex(target, g), g);
>>> }
>>>
>>> // All processes synchronize at this point, then the graph is complete
>>> synchronize(g.process_group());
>>> //---------End
>>>
>>> Looking at this, it seems that distribution happens automatically which
>>> is
>>> what the manual says.
>>> This is further confirmed when I output the subgraphs at each process.
>>>
>>
>> OK.  I was mistaken on this point then.  Could you please try the
>> following graph with a distribution that puts vertices 0-3 on rank 0 and 4
>> on rank 1 (just add three dummy vertices on the end and use a block
>> distribution)?
>>
>> 0 -> 1
>> 1 -> 2
>> 2 -> 3
>> 0 -> 4
>> 4 -> 3
>>
>> See if the depths are reasonable for that graph.  Also, the contents of
>> the predecessor maps output by your search (both the original one and the
>> graph I just gave) would be nice too; that is just an extra map you can give
>> to BFS and you can just dump it the same way you dump depth values.
>>
>>
>
>> I tried adding predecessor map but I don't think its currently. No
>> reduction function is defined for predecessor map. Please see below for the
>> attached error.
>>
>  I tried the bfs with your input (and distribution) and the depth number
> are coming out to be incorrect. This is a surely a better input to debug
> this problem:-).
> The depth value of node n=3 should be d=2 but its coming out to be d=0.
> I believe the update message from node n=4 on process 1 is not received or
> updated by process 0.
> Attached below is the output of levels:
> Finished Parallel BFS
> Node ID    :  Level
> 0  :  0
>
> 1  :  1
> 2  :  2
> 3  :  0
> 4  :  1
> 5  :  4294967295
> 6  :  4294967295
> 7  :  4294967295
>
> The two subgraphs on each process
> Subgraph Begin
>   n0 -> n1;
>   n0 -> n4;
>   n1 -> n2;
>   n2 -> n3;
> Subgraph End
>
> Subgraph Begin
>   n4 -> n3;
> Subgraph End
>
> Thanks,
> Sandeep
>
> //-------------------------
> The error snippet regarding  predecessor map:
>
> error: no match for call to
> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>
>
> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
> error: no match for call to
> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
> (const boost::detail::parallel::global_descriptor<unsigned int>&,
> boost::detail::error_property_not_found&, const
> boost::detail::error_property_not_found&)'
> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
> const [with T = boost::detail::error_property_not_found]
> ../../../boost/graph/parallel/properties.hpp:96: note:                 T
> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
> T, T) const [with T = boost::detail::error_property_not_found]
>
>
> Jeremiah, Do you think that I should file a bug report for this.

Although I was hoping (and actually needed quite urgently) that it would be
minor issue and get fixed quickly.

Thanks,
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jeremiah Willcock]

On Tue, 27 Oct 2009, Sandeep Gupta wrote:

>> The error snippet regarding  predecessor map:
>>
>> error: no match for call to
>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>
>>
>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>> error: no match for call to
>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>> boost::detail::error_property_not_found&, const
>> boost::detail::error_property_not_found&)'
>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>> const [with T = boost::detail::error_property_not_found]
>> ../../../boost/graph/parallel/properties.hpp:96: note:                 T
>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>> T, T) const [with T = boost::detail::error_property_not_found]
>>
>>
>> Jeremiah, Do you think that I should file a bug report for this.
> Although I was hoping (and actually needed quite urgently) that it would be
> minor issue and get fixed quickly.

You need to pass a predecessor map to the algorithm as one of the parameters
(or put it as a part of your graph but making an external property map to give
to the algorithm is easier).

-- Jeremiah Willcock
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@...>wrote:

> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>
>  The error snippet regarding  predecessor map:
>>>
>>> error: no match for call to
>>>
>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>
>>>
>>>
>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>> error: no match for call to
>>>
>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>> boost::detail::error_property_not_found&, const
>>> boost::detail::error_property_not_found&)'
>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
>>>
>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>> const [with T = boost::detail::error_property_not_found]
>>> ../../../boost/graph/parallel/properties.hpp:96: note:                 T
>>>
>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>
>>>
>>> Jeremiah, Do you think that I should file a bug report for this.
>>>
>> Although I was hoping (and actually needed quite urgently) that it would
>> be
>> minor issue and get fixed quickly.
>>
>
> You need to pass a predecessor map to the algorithm as one of the
> parameters
> (or put it as a part of your graph but making an external property map to
> give
> to the algorithm is easier).
>
> Hi Jeremy,

> It took me a while but I finally figure out how to pass the predecessor
> map. Unfortunately it doesn't have any effect. Also, I might be wrong  but I
> don't see any logical reason why predecessor map should have any bearing on
> the correctness of the depth. I have attached the new code.  I am not able
> to print out the predecessor because I am not able to figure out its type.
> Maybe you could help me resolve this.
>

It would be nice to have this code running. I need to profile graph
performance on a new machine by tomorrow. Again, thanks for you patience and
time. I really appreciate you looking into this.

-Sandeep

[bfs_clean.cpp]

---

// Copyright (C) 2004-2008 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine

// Example usage of breadth_first_search algorithm

// Enable PBGL interfaces to BGL algorithms
#include <boost/graph/use_mpi.hpp>

// Communicate via MPI
#include <boost/graph/distributed/mpi_process_group.hpp>

// Breadth-first search algorithm
#include <boost/graph/breadth_first_search.hpp>

// Distributed adjacency list
#include <boost/graph/distributed/adjacency_list.hpp>

// METIS Input
#include <boost/graph/metis.hpp>

// Graphviz Output
#include <boost/graph/distributed/graphviz.hpp>

// Standard Library includes
#include <fstream>
#include <string>
#include <boost/foreach.hpp>

#include <boost/graph/graph_utility.hpp>
#include <boost/property_map/parallel/distributed_property_map.hpp>

#ifdef BOOST_NO_EXCEPTIONS
void
boost::throw_exception(std::exception const& ex)
{
    std::cout << ex.what() << std::endl;
    abort();
}
#endif

using namespace boost;
using boost::graph::distributed::mpi_process_group;


template<typename DistanceMap>
struct bfs_discovery_visitor : bfs_visitor<>
{
  bfs_discovery_visitor(DistanceMap distance) : distance(distance)
  {
    set_property_map_role(vertex_distance, distance);
  }

  template<typename Edge, typename Graph>
  void tree_edge(Edge e, const Graph& g)
  {
    typename property_map<Graph, vertex_index_t>::type vidxx = get(vertex_index, g);
    typename graph_traits<Graph>::vertex_descriptor src = source(e,g);
    typename graph_traits<Graph>::vertex_descriptor des = target(e,g);
   
    std::size_t new_distance = get(distance, source(e, g)) + 1;
    std::cout<<"NowVisiting: ("<<owner(src)<<":"<<local(src)<<")--> ("<<owner(des)<<":"<<local(des)<<")"<<" distance "<<new_distance<<std::endl;
    put(distance, target(e, g), new_distance);
  }
 
private:
  DistanceMap distance;
};

typedef adjacency_list_traits<vecS, distributedS<mpi_process_group, vecS>, directedS >::vertex_descriptor vertex_descriptor;

/* An undirected graph with distance values stored on the vertices. */
typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, directedS,
                       /*Vertex properties=*/property<vertex_distance_t, std::size_t>
                       // property<vertex_predecessor_t, vertex_descriptor>
                       >
  Graph;

int main(int argc, char* argv[])
{
  boost::mpi::environment env(argc,argv);

  // Parse command-line options
   
  int n = 8;
  Graph g(n);
  if(process_id(g.process_group()) == 0){

    std::vector<std::pair<int, int> > allEdges;
    allEdges.push_back(std::pair<int, int>(0,1));
    allEdges.push_back(std::pair<int, int>(1,2));
    allEdges.push_back(std::pair<int, int>(2,3));
    allEdges.push_back(std::pair<int, int>(0,4));
    allEdges.push_back(std::pair<int, int>(4,3));
   
    std::vector<std::pair<int, int> >::iterator git = allEdges.begin();
    for( ; git != allEdges.end(); git++)
      {
        add_edge(vertex(git->first, g), vertex(git->second, g), g);
      }
   
    //   print_graph(g);
  }

  synchronize(g.process_group());
  typedef  boost::graph::parallel::process_group_type<Graph>::type process_group_type;
  typedef property_map<Graph, vertex_distance_t>::type VertexDistanceMap;
  typedef graph_traits<Graph>::vertex_descriptor key_type;
  typedef property_map<Graph, vertex_index_t>::type VertexIndexMap;
  property_map<Graph, vertex_distance_t>::type distance =
    get(vertex_distance, g);
  property_map<Graph, vertex_global_t>::type vertex_global_map = get(vertex_global, g);

  //  property_map<Graph, vertex_predecessor_t>::type predecessor =
  //  get(vertex_predecessor, g);
 
  typedef graph_traits<Graph>::vertex_descriptor Vertex;
  typedef Graph::local_vertex_descriptor local_vertex;

 
  std::map<local_vertex, Vertex> pred_map_gd;
  boost::associative_property_map< std::map< local_vertex, Vertex> >
    pred_pmap_gd(pred_map_gd);
 
 

  // Get vertex 0 in the graph
  graph_traits<Graph>::vertex_descriptor start = vertex(0, g);

  // Compute BFS levels from vertex 0
 

 
  property_map<Graph, vertex_index_t>::type vidx = get(vertex_index, g);

  put(distance, start, 0);
 
  distance.set_consistency_model(boost::parallel::cm_forward);
 
   boost::breadth_first_search
     (g, start,
      boost::visitor
      (
       boost::make_bfs_visitor
       (
        std::make_pair
        (
         boost::record_distances(distance, boost::on_tree_edge()),
         boost::record_predecessors(boost::parallel::make_distributed_property_map(g.process_group(), vertex_global_map, pred_pmap_gd ), boost::on_tree_edge())
         )
        )
       )
      );
   
   
    synchronize(g.process_group());
    synchronize(g.process_group());
    synchronize(g.process_group());
    synchronize(g.process_group());
    //synchronize(distance);
     

 
 
 
  typedef  property_map<Graph, vertex_index_t>::const_type
    VertexIndexMap;
  typedef  property_map<Graph, vertex_global_t>::const_type
    VertexGlobalMap;
 
  if(process_id(g.process_group()) == 0){
 
    using boost::graph::parallel::process_group;
    process_group_type pg = process_group(g);
    std::cout<<"Finished Parallel BFS "<<std::endl;
    std::cout<<"Node ID    :  Level "<<std::endl;
    for(int i = 0; i < n; i++)
      {
        graph_traits<Graph>::vertex_descriptor vtx = vertex(i, g);
        std::cout<<i<<"  :  "<<get(distance, vtx)<<" "<<std::endl;
       
      }
  }

  std::string outfile("edges.dot");
  //write_graphviz(outfile, g, make_label_writer(distance));

  //synchronize(distance);
 synchronize(g.process_group());
 synchronize(g.process_group());
 synchronize(g.process_group());

  return 0;
}

---

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@...>wrote:

>
>
> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@...>wrote:
>
>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>
>>  The error snippet regarding  predecessor map:
>>>>
>>>> error: no match for call to
>>>>
>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>>
>>>>
>>>>
>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>> error: no match for call to
>>>>
>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>>> boost::detail::error_property_not_found&, const
>>>> boost::detail::error_property_not_found&)'
>>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
>>>>
>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>> const [with T = boost::detail::error_property_not_found]
>>>> ../../../boost/graph/parallel/properties.hpp:96: note:                 T
>>>>
>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>
>>>>
>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>
>>> Although I was hoping (and actually needed quite urgently) that it would
>>> be
>>> minor issue and get fixed quickly.
>>>
>>
>> You need to pass a predecessor map to the algorithm as one of the
>> parameters
>> (or put it as a part of your graph but making an external property map to
>> give
>> to the algorithm is easier).
>>
>> Hi Jeremy,
>
>>  It took me a while but I finally figure out how to pass the predecessor
>> map. Unfortunately it doesn't have any effect. Also, I might be wrong  but I
>> don't see any logical reason why predecessor map should have any bearing on
>> the correctness of the depth. I have attached the new code.  I am not able
>> to print out the predecessor because I am not able to figure out its type.
>> Maybe you could help me resolve this.
>>
>
> It would be nice to have this code running. I need to profile graph
> performance on a new machine by tomorrow. Again, thanks for you patience and
> time. I really appreciate you looking into this.
>
> Hi Jeremiah,
>

   Was just wondering if you had time to look into this or any suggestion on
how further proceed. I can get you the output of predecessor map if that
would help.
Just that I haven't be been able to figure out what the is type of the
property map returned by make_distributed_property_map.
Please let me know your thoughts.

Thanks,
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jeremiah Willcock]

On Thu, 29 Oct 2009, Sandeep Gupta wrote:

> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@...>wrote:
>
>>
>>
>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@...>wrote:
>>
>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>
>>>  The error snippet regarding  predecessor map:
>>>>>
>>>>> error: no match for call to
>>>>>
>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>>>
>>>>>
>>>>>
>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>> error: no match for call to
>>>>>
>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>>>> boost::detail::error_property_not_found&, const
>>>>> boost::detail::error_property_not_found&)'
>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are: T
>>>>>
>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>> const [with T = boost::detail::error_property_not_found]
>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:                 T
>>>>>
>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>
>>>>>
>>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>>
>>>> Although I was hoping (and actually needed quite urgently) that it would
>>>> be
>>>> minor issue and get fixed quickly.
>>>>
>>>
>>> You need to pass a predecessor map to the algorithm as one of the
>>> parameters
>>> (or put it as a part of your graph but making an external property map to
>>> give
>>> to the algorithm is easier).
>>>
>>> Hi Jeremy,
>>
>>>  It took me a while but I finally figure out how to pass the predecessor
>>> map. Unfortunately it doesn't have any effect. Also, I might be wrong  but I
>>> don't see any logical reason why predecessor map should have any bearing on
>>> the correctness of the depth. I have attached the new code.  I am not able
>>> to print out the predecessor because I am not able to figure out its type.
>>> Maybe you could help me resolve this.
>>>
>>
>> It would be nice to have this code running. I need to profile graph
>> performance on a new machine by tomorrow. Again, thanks for you patience and
>> time. I really appreciate you looking into this.
>>
>> Hi Jeremiah,
>>
>   Was just wondering if you had time to look into this or any suggestion on
> how further proceed. I can get you the output of predecessor map if that
> would help.
> Just that I haven't be been able to figure out what the is type of the
> property map returned by make_distributed_property_map.
> Please let me know your thoughts.

The person who really knows this library is not around as far as I know;
he might be on vacation.  The type returned from
make_distributed_property_map is documented on
<URL:http://www.osl.iu.edu/research/pbgl/documentation/graph/
distributed_property_map.html>.  One thing that you could do to debug
things is to put in your own color map and look at what values it ends up
with at the end of the algorithm, and possibly even to put in a local
color map that prints out when elements are changed.  That might be a lot
of work for what could end up being an obvious problem (that I just don't
know how to diagnose), though.  BTW, does the example in
libs/graph_parallel/example/breadth_first_search.cpp work for you?  It
appears to be doing the same thing you want to do.  If that works, it
could be a problem in your visitor.

-- Jeremiah Willcock
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@...>wrote:

> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>
>  On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@...
>> >wrote:
>>
>>
>>>
>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@...
>>> >wrote:
>>>
>>>  On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>
>>>>  The error snippet regarding  predecessor map:
>>>>
>>>>>
>>>>>> error: no match for call to
>>>>>>
>>>>>>
>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>> error: no match for call to
>>>>>>
>>>>>>
>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>>>>> boost::detail::error_property_not_found&, const
>>>>>> boost::detail::error_property_not_found&)'
>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are:
>>>>>> T
>>>>>>
>>>>>>
>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>> T
>>>>>>
>>>>>>
>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>
>>>>>>
>>>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>>>
>>>>>>  Although I was hoping (and actually needed quite urgently) that it
>>>>> would
>>>>> be
>>>>> minor issue and get fixed quickly.
>>>>>
>>>>>
>>>> You need to pass a predecessor map to the algorithm as one of the
>>>> parameters
>>>> (or put it as a part of your graph but making an external property map
>>>> to
>>>> give
>>>> to the algorithm is easier).
>>>>
>>>> Hi Jeremy,
>>>>
>>>
>>>   It took me a while but I finally figure out how to pass the predecessor
>>>> map. Unfortunately it doesn't have any effect. Also, I might be wrong
>>>>  but I
>>>> don't see any logical reason why predecessor map should have any bearing
>>>> on
>>>> the correctness of the depth. I have attached the new code.  I am not
>>>> able
>>>> to print out the predecessor because I am not able to figure out its
>>>> type.
>>>> Maybe you could help me resolve this.
>>>>
>>>>
>>> It would be nice to have this code running. I need to profile graph
>>> performance on a new machine by tomorrow. Again, thanks for you patience
>>> and
>>> time. I really appreciate you looking into this.
>>>
>>> Hi Jeremiah,
>>>
>>>   Was just wondering if you had time to look into this or any suggestion
>> on
>> how further proceed. I can get you the output of predecessor map if that
>> would help.
>> Just that I haven't be been able to figure out what the is type of the
>> property map returned by make_distributed_property_map.
>> Please let me know your thoughts.
>>
>
> The person who really knows this library is not around as far as I know; he
> might be on vacation.  The type returned from make_distributed_property_map
> is documented on <URL:
> http://www.osl.iu.edu/research/pbgl/documentation/graph/
> distributed_property_map.html>.  One thing that you could do to debug
> things is to put in your own color map and look at what values it ends up
> with at the end of the algorithm, and possibly even to put in a local color
> map that prints out when elements are changed.  That might be a lot of work
> for what could end up being an obvious problem (that I just don't know how
> to diagnose), though.  BTW, does the example in
> libs/graph_parallel/example/breadth_first_search.cpp work for you?  It
> appears to be doing the same thing you want to do.  If that works, it could
> be a problem in your visitor.
>
>
> I derived this code from graph_parallel/example/breadth_first_search.cpp.

The problem is that I don't understand the input and the output of the
example code. It would be great if I could get an explanation for  the
format of the input file. Then I can transform my graph into that  format
and pass to the algorithm. That would be enough for my current purpose.

As time permits I would try out your suggestions and let know of update. In
the meantime I am hoping that I would get input from other relevant authors.

Thanks,
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Jeremiah Willcock]

On Thu, 29 Oct 2009, Sandeep Gupta wrote:

> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@...>wrote:
>
>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>
>>  On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@...
>>>> wrote:
>>>
>>>
>>>>
>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco@...
>>>>> wrote:
>>>>
>>>>  On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>
>>>>>  The error snippet regarding  predecessor map:
>>>>>
>>>>>>
>>>>>>> error: no match for call to
>>>>>>>
>>>>>>>
>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>>> error: no match for call to
>>>>>>>
>>>>>>>
>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are:
>>>>>>> T
>>>>>>>
>>>>>>>
>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>> T
>>>>>>>
>>>>>>>
>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>>
>>>>>>>
>>>>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>>>>
>>>>>>>  Although I was hoping (and actually needed quite urgently) that it
>>>>>> would
>>>>>> be
>>>>>> minor issue and get fixed quickly.
>>>>>>
>>>>>>
>>>>> You need to pass a predecessor map to the algorithm as one of the
>>>>> parameters
>>>>> (or put it as a part of your graph but making an external property map
>>>>> to
>>>>> give
>>>>> to the algorithm is easier).
>>>>>
>>>>> Hi Jeremy,
>>>>>
>>>>
>>>>   It took me a while but I finally figure out how to pass the predecessor
>>>>> map. Unfortunately it doesn't have any effect. Also, I might be wrong
>>>>>  but I
>>>>> don't see any logical reason why predecessor map should have any bearing
>>>>> on
>>>>> the correctness of the depth. I have attached the new code.  I am not
>>>>> able
>>>>> to print out the predecessor because I am not able to figure out its
>>>>> type.
>>>>> Maybe you could help me resolve this.
>>>>>
>>>>>
>>>> It would be nice to have this code running. I need to profile graph
>>>> performance on a new machine by tomorrow. Again, thanks for you patience
>>>> and
>>>> time. I really appreciate you looking into this.
>>>>
>>>> Hi Jeremiah,
>>>>
>>>>   Was just wondering if you had time to look into this or any suggestion
>>> on
>>> how further proceed. I can get you the output of predecessor map if that
>>> would help.
>>> Just that I haven't be been able to figure out what the is type of the
>>> property map returned by make_distributed_property_map.
>>> Please let me know your thoughts.
>>>
>>
>> The person who really knows this library is not around as far as I know; he
>> might be on vacation.  The type returned from make_distributed_property_map
>> is documented on <URL:
>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>> distributed_property_map.html>.  One thing that you could do to debug
>> things is to put in your own color map and look at what values it ends up
>> with at the end of the algorithm, and possibly even to put in a local color
>> map that prints out when elements are changed.  That might be a lot of work
>> for what could end up being an obvious problem (that I just don't know how
>> to diagnose), though.  BTW, does the example in
>> libs/graph_parallel/example/breadth_first_search.cpp work for you?  It
>> appears to be doing the same thing you want to do.  If that works, it could
>> be a problem in your visitor.
>>
>>
>> I derived this code from graph_parallel/example/breadth_first_search.cpp.
> The problem is that I don't understand the input and the output of the
> example code. It would be great if I could get an explanation for  the
> format of the input file. Then I can transform my graph into that  format
> and pass to the algorithm. That would be enough for my current purpose.
>
> As time permits I would try out your suggestions and let know of update. In
> the meantime I am hoping that I would get input from other relevant authors.

This is what I could tell from the code.

Input:
http://people.sc.fsu.edu/~burkardt/data/metis_graph/metis_graph.html

Output:
http://www.graphviz.org/doc/info/lang.html

-- Jeremiah Willcock
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@...>wrote:

> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>
>  On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@...
>> >wrote:
>>
>>  On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>
>>>  On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@...
>>>
>>>> wrote:
>>>>>
>>>>
>>>>
>>>>
>>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>> jewillco@...
>>>>>
>>>>>> wrote:
>>>>>>
>>>>>
>>>>>  On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>
>>>>>>
>>>>>>  The error snippet regarding  predecessor map:
>>>>>>
>>>>>>
>>>>>>>  error: no match for call to
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>>>> error: no match for call to
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates
>>>>>>>> are:
>>>>>>>> T
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>> T
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>>>
>>>>>>>>
>>>>>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>>>>>
>>>>>>>>  Although I was hoping (and actually needed quite urgently) that it
>>>>>>>>
>>>>>>> would
>>>>>>> be
>>>>>>> minor issue and get fixed quickly.
>>>>>>>
>>>>>>>
>>>>>>>  You need to pass a predecessor map to the algorithm as one of the
>>>>>> parameters
>>>>>> (or put it as a part of your graph but making an external property map
>>>>>> to
>>>>>> give
>>>>>> to the algorithm is easier).
>>>>>>
>>>>>> Hi Jeremy,
>>>>>>
>>>>>>
>>>>>  It took me a while but I finally figure out how to pass the
>>>>> predecessor
>>>>>
>>>>>> map. Unfortunately it doesn't have any effect. Also, I might be wrong
>>>>>>  but I
>>>>>> don't see any logical reason why predecessor map should have any
>>>>>> bearing
>>>>>> on
>>>>>> the correctness of the depth. I have attached the new code.  I am not
>>>>>> able
>>>>>> to print out the predecessor because I am not able to figure out its
>>>>>> type.
>>>>>> Maybe you could help me resolve this.
>>>>>>
>>>>>>
>>>>>>  It would be nice to have this code running. I need to profile graph
>>>>> performance on a new machine by tomorrow. Again, thanks for you
>>>>> patience
>>>>> and
>>>>> time. I really appreciate you looking into this.
>>>>>
>>>>> Hi Jeremiah,
>>>>>
>>>>>  Was just wondering if you had time to look into this or any suggestion
>>>>>
>>>> on
>>>> how further proceed. I can get you the output of predecessor map if that
>>>> would help.
>>>> Just that I haven't be been able to figure out what the is type of the
>>>> property map returned by make_distributed_property_map.
>>>> Please let me know your thoughts.
>>>>
>>>>
>>> The person who really knows this library is not around as far as I know;
>>> he
>>> might be on vacation.  The type returned from
>>> make_distributed_property_map
>>> is documented on <URL:
>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>> distributed_property_map.html>.  One thing that you could do to debug
>>> things is to put in your own color map and look at what values it ends up
>>> with at the end of the algorithm, and possibly even to put in a local
>>> color
>>> map that prints out when elements are changed.  That might be a lot of
>>> work
>>> for what could end up being an obvious problem (that I just don't know
>>> how
>>> to diagnose), though.  BTW, does the example in
>>> libs/graph_parallel/example/breadth_first_search.cpp work for you?  It
>>> appears to be doing the same thing you want to do.  If that works, it
>>> could
>>> be a problem in your visitor.
>>>
>>>
>>> I derived this code from graph_parallel/example/breadth_first_search.cpp.
>>>
>> The problem is that I don't understand the input and the output of the
>> example code. It would be great if I could get an explanation for  the
>> format of the input file. Then I can transform my graph into that  format
>> and pass to the algorithm. That would be enough for my current purpose.
>>
>> As time permits I would try out your suggestions and let know of update.
>> In
>> the meantime I am hoping that I would get input from other relevant
>> authors.
>>
>
> This is what I could tell from the code.
>
> Input:
> http://people.sc.fsu.edu/~burkardt/data/metis_graph/metis_graph.html<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html>
>
> Output:
> http://www.graphviz.org/doc/info/lang.html
>
>
> Thanks Jeremiah. The link was helpful. I understood the input graph format.
> Its for undirected graph only. However the BFS output is still coming out to
> be  incorrect. I  tried with  a sample line graph  of 4 nodes and it
> exhibits the same problem as before.
>

 The distances of nodes on process 2 is not getting updated. On the other
hand dijkstra shortest paths example is working correctly.

Thanks
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Nick Edmonds]

On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:

> On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@...
> >wrote:
>
>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>
>> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@...
>>>> wrote:
>>>
>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>
>>>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep@...
>>>>
>>>>> wrote:
>>>>>>
>>>>>
>>>>>
>>>>>
>>>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>>> jewillco@...
>>>>>>
>>>>>>> wrote:
>>>>>>>
>>>>>>
>>>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>>
>>>>>>>
>>>>>>> The error snippet regarding  predecessor map:
>>>>>>>
>>>>>>>
>>>>>>>> error: no match for call to
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> '(boost
>>>>>>>>> ::property_reduce
>>>>>>>>> <
>>>>>>>>> boost
>>>>>>>>> ::vertex_predecessor_t
>>>>>>>>> >::apply<boost::detail::error_property_not_found>)
>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned  
>>>>>>>>> int>&)'
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> ../../../boost/property_map/parallel/impl/
>>>>>>>>> distributed_property_map.ipp:141:
>>>>>>>>> error: no match for call to
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> '(boost
>>>>>>>>> ::property_reduce
>>>>>>>>> <
>>>>>>>>> boost
>>>>>>>>> ::vertex_predecessor_t
>>>>>>>>> >::apply<boost::detail::error_property_not_found>)
>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned  
>>>>>>>>> int>&,
>>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note:  
>>>>>>>>> candidates
>>>>>>>>> are:
>>>>>>>>> T
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> boost
>>>>>>>>> ::property_reduce
>>>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>>> T
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> boost
>>>>>>>>> ::property_reduce
>>>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Jeremiah, Do you think that I should file a bug report for  
>>>>>>>>> this.
>>>>>>>>>
>>>>>>>>> Although I was hoping (and actually needed quite urgently)  
>>>>>>>>> that it
>>>>>>>>>
>>>>>>>> would
>>>>>>>> be
>>>>>>>> minor issue and get fixed quickly.
>>>>>>>>
>>>>>>>>
>>>>>>>> You need to pass a predecessor map to the algorithm as one of  
>>>>>>>> the
>>>>>>> parameters
>>>>>>> (or put it as a part of your graph but making an external  
>>>>>>> property map
>>>>>>> to
>>>>>>> give
>>>>>>> to the algorithm is easier).
>>>>>>>
>>>>>>> Hi Jeremy,
>>>>>>>
>>>>>>>
>>>>>> It took me a while but I finally figure out how to pass the
>>>>>> predecessor
>>>>>>
>>>>>>> map. Unfortunately it doesn't have any effect. Also, I might  
>>>>>>> be wrong
>>>>>>> but I
>>>>>>> don't see any logical reason why predecessor map should have any
>>>>>>> bearing
>>>>>>> on
>>>>>>> the correctness of the depth. I have attached the new code.  I  
>>>>>>> am not
>>>>>>> able
>>>>>>> to print out the predecessor because I am not able to figure  
>>>>>>> out its
>>>>>>> type.
>>>>>>> Maybe you could help me resolve this.
>>>>>>>
>>>>>>>
>>>>>>> It would be nice to have this code running. I need to profile  
>>>>>>> graph
>>>>>> performance on a new machine by tomorrow. Again, thanks for you
>>>>>> patience
>>>>>> and
>>>>>> time. I really appreciate you looking into this.
>>>>>>
>>>>>> Hi Jeremiah,
>>>>>>
>>>>>> Was just wondering if you had time to look into this or any  
>>>>>> suggestion
>>>>>>
>>>>> on
>>>>> how further proceed. I can get you the output of predecessor map  
>>>>> if that
>>>>> would help.
>>>>> Just that I haven't be been able to figure out what the is type  
>>>>> of the
>>>>> property map returned by make_distributed_property_map.
>>>>> Please let me know your thoughts.
>>>>>
>>>>>
>>>> The person who really knows this library is not around as far as  
>>>> I know;
>>>> he
>>>> might be on vacation.  The type returned from
>>>> make_distributed_property_map
>>>> is documented on <URL:
>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>>> distributed_property_map.html>.  One thing that you could do to  
>>>> debug
>>>> things is to put in your own color map and look at what values it  
>>>> ends up
>>>> with at the end of the algorithm, and possibly even to put in a  
>>>> local
>>>> color
>>>> map that prints out when elements are changed.  That might be a  
>>>> lot of
>>>> work
>>>> for what could end up being an obvious problem (that I just don't  
>>>> know
>>>> how
>>>> to diagnose), though.  BTW, does the example in
>>>> libs/graph_parallel/example/breadth_first_search.cpp work for  
>>>> you?  It
>>>> appears to be doing the same thing you want to do.  If that  
>>>> works, it
>>>> could
>>>> be a problem in your visitor.
>>>>
>>>>
>>>> I derived this code from graph_parallel/example/
>>>> breadth_first_search.cpp.
>>>>
>>> The problem is that I don't understand the input and the output of  
>>> the
>>> example code. It would be great if I could get an explanation for  
>>> the
>>> format of the input file. Then I can transform my graph into that  
>>> format
>>> and pass to the algorithm. That would be enough for my current  
>>> purpose.
>>>
>>> As time permits I would try out your suggestions and let know of  
>>> update.
>>> In
>>> the meantime I am hoping that I would get input from other relevant
>>> authors.
>>>
>>
>> This is what I could tell from the code.
>>
>> Input:
>> http://people.sc.fsu.edu/~burkardt/data/metis_graph/ 
>> metis_graph.html<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html 
>> >
>>
>> Output:
>> http://www.graphviz.org/doc/info/lang.html
>>
>>
>> Thanks Jeremiah. The link was helpful. I understood the input graph  
>> format.
>> Its for undirected graph only. However the BFS output is still  
>> coming out to
>> be  incorrect. I  tried with  a sample line graph  of 4 nodes and it
>> exhibits the same problem as before.
>>
> The distances of nodes on process 2 is not getting updated. On the  
> other
> hand dijkstra shortest paths example is working correctly.
>
> Thanks
> Sandeep

I rewrote most of your code before I realized that you're outputting  
all your distances on process 0, even for vertices process 0 doesn't  
own.  The large value you see is  
std::numeric_limits<distance_type>::max.  When you call get(distance,  
vertex(i, g)) for some i not owned by the current process a ghost cell  
is created for the requested value and a request sent to the owner of  
that vertex for the correct value.  get() then returns whatever the  
default value is for the distance property map, which in this case is  
infinity (i.e. std::numeric_limits<distance_type>::max.

In some cases you may get the correct distance value because process 0  
has previously requested that value (and it may or may not be up to  
date).  If process 0 has never requested that distance value and it  
doesn't own the vertex, then you'll get infinity.

You need to gather all your data before you output it from a single  
node (i.e. issue a get() or request() which is a get with no return  
value, for each data element).  If you want your code to be scalable  
you should output your data in a distributed fashion from all nodes at  
once.  Remember that updated values won't be guaranteed to arrive  
until the next synchronization step.

If you want the modified version of your code let me know and I'll  
finish it and ship it your way.

-Nick

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@...>wrote:

>
> On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
>
>  On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@...
>> >wrote:
>>
>>  On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>
>>> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@...
>>>
>>>> wrote:
>>>>>
>>>>
>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>
>>>>>
>>>>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <
>>>>> gupta.sandeep@...
>>>>>
>>>>>  wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>>
>>>>>>
>>>>>>  On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>>>> jewillco@...
>>>>>>>
>>>>>>>  wrote:
>>>>>>>>
>>>>>>>>
>>>>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>>>
>>>>>>>
>>>>>>>> The error snippet regarding  predecessor map:
>>>>>>>>
>>>>>>>>
>>>>>>>>  error: no match for call to
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>>>>>> error: no match for call to
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates
>>>>>>>>>> are:
>>>>>>>>>> T
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>>>> T
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>>>>>>>
>>>>>>>>>> Although I was hoping (and actually needed quite urgently) that it
>>>>>>>>>>
>>>>>>>>>>  would
>>>>>>>>> be
>>>>>>>>> minor issue and get fixed quickly.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> You need to pass a predecessor map to the algorithm as one of the
>>>>>>>>>
>>>>>>>> parameters
>>>>>>>> (or put it as a part of your graph but making an external property
>>>>>>>> map
>>>>>>>> to
>>>>>>>> give
>>>>>>>> to the algorithm is easier).
>>>>>>>>
>>>>>>>> Hi Jeremy,
>>>>>>>>
>>>>>>>>
>>>>>>>>  It took me a while but I finally figure out how to pass the
>>>>>>> predecessor
>>>>>>>
>>>>>>>  map. Unfortunately it doesn't have any effect. Also, I might be
>>>>>>>> wrong
>>>>>>>> but I
>>>>>>>> don't see any logical reason why predecessor map should have any
>>>>>>>> bearing
>>>>>>>> on
>>>>>>>> the correctness of the depth. I have attached the new code.  I am
>>>>>>>> not
>>>>>>>> able
>>>>>>>> to print out the predecessor because I am not able to figure out its
>>>>>>>> type.
>>>>>>>> Maybe you could help me resolve this.
>>>>>>>>
>>>>>>>>
>>>>>>>> It would be nice to have this code running. I need to profile graph
>>>>>>>>
>>>>>>> performance on a new machine by tomorrow. Again, thanks for you
>>>>>>> patience
>>>>>>> and
>>>>>>> time. I really appreciate you looking into this.
>>>>>>>
>>>>>>> Hi Jeremiah,
>>>>>>>
>>>>>>> Was just wondering if you had time to look into this or any
>>>>>>> suggestion
>>>>>>>
>>>>>>>  on
>>>>>> how further proceed. I can get you the output of predecessor map if
>>>>>> that
>>>>>> would help.
>>>>>> Just that I haven't be been able to figure out what the is type of the
>>>>>> property map returned by make_distributed_property_map.
>>>>>> Please let me know your thoughts.
>>>>>>
>>>>>>
>>>>>>  The person who really knows this library is not around as far as I
>>>>> know;
>>>>> he
>>>>> might be on vacation.  The type returned from
>>>>> make_distributed_property_map
>>>>> is documented on <URL:
>>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>>>> distributed_property_map.html>.  One thing that you could do to debug
>>>>> things is to put in your own color map and look at what values it ends
>>>>> up
>>>>> with at the end of the algorithm, and possibly even to put in a local
>>>>> color
>>>>> map that prints out when elements are changed.  That might be a lot of
>>>>> work
>>>>> for what could end up being an obvious problem (that I just don't know
>>>>> how
>>>>> to diagnose), though.  BTW, does the example in
>>>>> libs/graph_parallel/example/breadth_first_search.cpp work for you?  It
>>>>> appears to be doing the same thing you want to do.  If that works, it
>>>>> could
>>>>> be a problem in your visitor.
>>>>>
>>>>>
>>>>> I derived this code from
>>>>> graph_parallel/example/breadth_first_search.cpp.
>>>>>
>>>>>  The problem is that I don't understand the input and the output of the
>>>> example code. It would be great if I could get an explanation for  the
>>>> format of the input file. Then I can transform my graph into that
>>>>  format
>>>> and pass to the algorithm. That would be enough for my current purpose.
>>>>
>>>> As time permits I would try out your suggestions and let know of update.
>>>> In
>>>> the meantime I am hoping that I would get input from other relevant
>>>> authors.
>>>>
>>>>
>>> This is what I could tell from the code.
>>>
>>> Input:
>>> http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>> metis_graph.html<
>>> http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html>
>>>
>>>
>>> Output:
>>> http://www.graphviz.org/doc/info/lang.html
>>>
>>>
>>> Thanks Jeremiah. The link was helpful. I understood the input graph
>>> format.
>>> Its for undirected graph only. However the BFS output is still coming out
>>> to
>>> be  incorrect. I  tried with  a sample line graph  of 4 nodes and it
>>> exhibits the same problem as before.
>>>
>>>  The distances of nodes on process 2 is not getting updated. On the other
>> hand dijkstra shortest paths example is working correctly.
>>
>> Thanks
>> Sandeep
>>
>
> I rewrote most of your code before I realized that you're outputting all
> your distances on process 0, even for vertices process 0 doesn't own.  The
> large value you see is std::numeric_limits<distance_type>::max.  When you
> call get(distance, vertex(i, g)) for some i not owned by the current process
> a ghost cell is created for the requested value and a request sent to the
> owner of that vertex for the correct value.  get() then returns whatever the
> default value is for the distance property map, which in this case is
> infinity (i.e. std::numeric_limits<distance_type>::max.
>
> In some cases you may get the correct distance value because process 0 has
> previously requested that value (and it may or may not be up to date).  If
> process 0 has never requested that distance value and it doesn't own the
> vertex, then you'll get infinity.
>
> You need to gather all your data before you output it from a single node
> (i.e. issue a get() or request() which is a get with no return value, for
> each data element).  If you want your code to be scalable you should output
> your data in a distributed fashion from all nodes at once.  Remember that
> updated values won't be guaranteed to arrive until the next synchronization
> step.
>
> If you want the modified version of your code let me know and I'll finish
> it and ship it your way.
>
> -Nick
>
>
> Hi Nick,
>

   Thanks so much for looking into this. Sorry, I couldn't get to it earlier
due to other concerns. I corrected the mistake you mentioned and I don't get
numeric_limit<>::max() for any nodes anymore.

I believe the graph/distributed/graphviz.hpp was outputting the distance in
correct fashion.

Unfortunately, the output is still coming out to be incorrect.
It was also the case with output from graphviz.hpp.

For the test graph that we mentioned before, essentially
0 --> 1 --> 2 --> 3,
0 --> 4 --> 3

the distance output is as follows:
global node-id : distance
0 : 0
1 : 1
2 : 2
3 : 1            //(wrong: should be 2)
4 :  0          // should be 1

If possible can you send me your version of the code. Let me know if you
need mine (the updated version).

Thanks
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Nick Edmonds]

On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:

> On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds  
> <ngedmond@...>wrote:
>
>>
>> On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
>>
>> On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@...
>>>> wrote:
>>>
>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>
>>>> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco@...
>>>>
>>>>> wrote:
>>>>>>
>>>>>
>>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>
>>>>>>
>>>>>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <
>>>>>> gupta.sandeep@...
>>>>>>
>>>>>> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>>>>> jewillco@...
>>>>>>>>
>>>>>>>> wrote:
>>>>>>>>>
>>>>>>>>>
>>>>>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>> The error snippet regarding  predecessor map:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> error: no match for call to
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> '(boost
>>>>>>>>>>> ::property_reduce
>>>>>>>>>>> <
>>>>>>>>>>> boost
>>>>>>>>>>> ::vertex_predecessor_t
>>>>>>>>>>> >::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned  
>>>>>>>>>>> int>&)'
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> ../../../boost/property_map/parallel/impl/
>>>>>>>>>>> distributed_property_map.ipp:141:
>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> '(boost
>>>>>>>>>>> ::property_reduce
>>>>>>>>>>> <
>>>>>>>>>>> boost
>>>>>>>>>>> ::vertex_predecessor_t
>>>>>>>>>>> >::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned  
>>>>>>>>>>> int>&,
>>>>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note:  
>>>>>>>>>>> candidates
>>>>>>>>>>> are:
>>>>>>>>>>> T
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> boost
>>>>>>>>>>> ::property_reduce
>>>>>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>>>>> T
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> boost
>>>>>>>>>>> ::property_reduce
>>>>>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>>>>> T, T) const [with T =  
>>>>>>>>>>> boost::detail::error_property_not_found]
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> Jeremiah, Do you think that I should file a bug report for  
>>>>>>>>>>> this.
>>>>>>>>>>>
>>>>>>>>>>> Although I was hoping (and actually needed quite urgently)  
>>>>>>>>>>> that it
>>>>>>>>>>>
>>>>>>>>>>> would
>>>>>>>>>> be
>>>>>>>>>> minor issue and get fixed quickly.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> You need to pass a predecessor map to the algorithm as one  
>>>>>>>>>> of the
>>>>>>>>>>
>>>>>>>>> parameters
>>>>>>>>> (or put it as a part of your graph but making an external  
>>>>>>>>> property
>>>>>>>>> map
>>>>>>>>> to
>>>>>>>>> give
>>>>>>>>> to the algorithm is easier).
>>>>>>>>>
>>>>>>>>> Hi Jeremy,
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> It took me a while but I finally figure out how to pass the
>>>>>>>> predecessor
>>>>>>>>
>>>>>>>> map. Unfortunately it doesn't have any effect. Also, I might be
>>>>>>>>> wrong
>>>>>>>>> but I
>>>>>>>>> don't see any logical reason why predecessor map should have  
>>>>>>>>> any
>>>>>>>>> bearing
>>>>>>>>> on
>>>>>>>>> the correctness of the depth. I have attached the new code.  
>>>>>>>>> I am
>>>>>>>>> not
>>>>>>>>> able
>>>>>>>>> to print out the predecessor because I am not able to figure  
>>>>>>>>> out its
>>>>>>>>> type.
>>>>>>>>> Maybe you could help me resolve this.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> It would be nice to have this code running. I need to  
>>>>>>>>> profile graph
>>>>>>>>>
>>>>>>>> performance on a new machine by tomorrow. Again, thanks for you
>>>>>>>> patience
>>>>>>>> and
>>>>>>>> time. I really appreciate you looking into this.
>>>>>>>>
>>>>>>>> Hi Jeremiah,
>>>>>>>>
>>>>>>>> Was just wondering if you had time to look into this or any
>>>>>>>> suggestion
>>>>>>>>
>>>>>>>> on
>>>>>>> how further proceed. I can get you the output of predecessor  
>>>>>>> map if
>>>>>>> that
>>>>>>> would help.
>>>>>>> Just that I haven't be been able to figure out what the is  
>>>>>>> type of the
>>>>>>> property map returned by make_distributed_property_map.
>>>>>>> Please let me know your thoughts.
>>>>>>>
>>>>>>>
>>>>>>> The person who really knows this library is not around as far  
>>>>>>> as I
>>>>>> know;
>>>>>> he
>>>>>> might be on vacation.  The type returned from
>>>>>> make_distributed_property_map
>>>>>> is documented on <URL:
>>>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>>>>> distributed_property_map.html>.  One thing that you could do to  
>>>>>> debug
>>>>>> things is to put in your own color map and look at what values  
>>>>>> it ends
>>>>>> up
>>>>>> with at the end of the algorithm, and possibly even to put in a  
>>>>>> local
>>>>>> color
>>>>>> map that prints out when elements are changed.  That might be a  
>>>>>> lot of
>>>>>> work
>>>>>> for what could end up being an obvious problem (that I just  
>>>>>> don't know
>>>>>> how
>>>>>> to diagnose), though.  BTW, does the example in
>>>>>> libs/graph_parallel/example/breadth_first_search.cpp work for  
>>>>>> you?  It
>>>>>> appears to be doing the same thing you want to do.  If that  
>>>>>> works, it
>>>>>> could
>>>>>> be a problem in your visitor.
>>>>>>
>>>>>>
>>>>>> I derived this code from
>>>>>> graph_parallel/example/breadth_first_search.cpp.
>>>>>>
>>>>>> The problem is that I don't understand the input and the output  
>>>>>> of the
>>>>> example code. It would be great if I could get an explanation  
>>>>> for  the
>>>>> format of the input file. Then I can transform my graph into that
>>>>> format
>>>>> and pass to the algorithm. That would be enough for my current  
>>>>> purpose.
>>>>>
>>>>> As time permits I would try out your suggestions and let know of  
>>>>> update.
>>>>> In
>>>>> the meantime I am hoping that I would get input from other  
>>>>> relevant
>>>>> authors.
>>>>>
>>>>>
>>>> This is what I could tell from the code.
>>>>
>>>> Input:
>>>> http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/ 
>>>> >
>>>> metis_graph.html<
>>>> http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html 
>>>> >
>>>>
>>>>
>>>> Output:
>>>> http://www.graphviz.org/doc/info/lang.html
>>>>
>>>>
>>>> Thanks Jeremiah. The link was helpful. I understood the input graph
>>>> format.
>>>> Its for undirected graph only. However the BFS output is still  
>>>> coming out
>>>> to
>>>> be  incorrect. I  tried with  a sample line graph  of 4 nodes and  
>>>> it
>>>> exhibits the same problem as before.
>>>>
>>>> The distances of nodes on process 2 is not getting updated. On  
>>>> the other
>>> hand dijkstra shortest paths example is working correctly.
>>>
>>> Thanks
>>> Sandeep
>>>
>>
>> I rewrote most of your code before I realized that you're  
>> outputting all
>> your distances on process 0, even for vertices process 0 doesn't  
>> own.  The
>> large value you see is std::numeric_limits<distance_type>::max.  
>> When you
>> call get(distance, vertex(i, g)) for some i not owned by the  
>> current process
>> a ghost cell is created for the requested value and a request sent  
>> to the
>> owner of that vertex for the correct value.  get() then returns  
>> whatever the
>> default value is for the distance property map, which in this case is
>> infinity (i.e. std::numeric_limits<distance_type>::max.
>>
>> In some cases you may get the correct distance value because  
>> process 0 has
>> previously requested that value (and it may or may not be up to  
>> date).  If
>> process 0 has never requested that distance value and it doesn't  
>> own the
>> vertex, then you'll get infinity.
>>
>> You need to gather all your data before you output it from a single  
>> node
>> (i.e. issue a get() or request() which is a get with no return  
>> value, for
>> each data element).  If you want your code to be scalable you  
>> should output
>> your data in a distributed fashion from all nodes at once.  
>> Remember that
>> updated values won't be guaranteed to arrive until the next  
>> synchronization
>> step.
>>
>> If you want the modified version of your code let me know and I'll  
>> finish
>> it and ship it your way.
>>
>> -Nick
>>
>>
>> Hi Nick,
>>
>   Thanks so much for looking into this. Sorry, I couldn't get to it  
> earlier
> due to other concerns. I corrected the mistake you mentioned and I  
> don't get
> numeric_limit<>::max() for any nodes anymore.
>
> I believe the graph/distributed/graphviz.hpp was outputting the  
> distance in
> correct fashion.
>
> Unfortunately, the output is still coming out to be incorrect.
> It was also the case with output from graphviz.hpp.
>
> For the test graph that we mentioned before, essentially
> 0 --> 1 --> 2 --> 3,
> 0 --> 4 --> 3
>
> the distance output is as follows:
> global node-id : distance
> 0 : 0
> 1 : 1
> 2 : 2
> 3 : 1            //(wrong: should be 2)
> 4 :  0          // should be 1
>
> If possible can you send me your version of the code. Let me know if  
> you
> need mine (the updated version).

Given the description of your problem above, and assuming you're using  
a block distribution with 8 vertices, it sounds like you're  
initializing the distance to the first vertex on *each* process to 0,  
as opposed to only the distance to the source.  The vertex with global  
index 4 is actually local index 0 on process one using the above  
distribution.  If you initialize the distances to the vertices with  
global indices 0 and 4 to 0, then your results make sense.  Let me  
know if that's not the case, but I surmise that it is.

Also there's a problem in your depth labeling visitor.  In the case of  
cross-processor edges the process that owns the target of the edge  
doesn't necessarily have the distance to the source of the edge  
available locally.  This will lead to incorrect distance labels even  
though tree and non-tree edges will still be correctly recognized  
since the BFS is level-synchronized.  The fastest way to handle this  
is to modify the BFS queue to also pass distance data (which is how  
the shortest paths algorithms do it).  You could also send the data  
separately and probe for it on the receiving side.  Check out the  
distributed betweenness centrality code for how to create a  
distributed queue which contains tuples of data one element of which  
is a vertex (in order to know where to route the data).  Integrating  
this type of vertex queue (i.e. one that contains a data payload) with  
BFS basically just requires handling the data payload on the receiving  
side.

Cheers,
Nick
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@...>wrote:

>
> On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
>
>  On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@...
>> >wrote:
>>
>>
>>> On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
>>>
>>> On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@...
>>>
>>>> wrote:
>>>>>
>>>>
>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>
>>>>>
>>>>> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <
>>>>> jewillco@...
>>>>>
>>>>>  wrote:
>>>>>>
>>>>>>>
>>>>>>>
>>>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>>
>>>>>>
>>>>>>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <
>>>>>>> gupta.sandeep@...
>>>>>>>
>>>>>>> wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>>>>>
>>>>>>>>> jewillco@...
>>>>>>>>>
>>>>>>>>> wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>  On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>  The error snippet regarding  predecessor map:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> error: no match for call to
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>> int>&)'
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>> int>&,
>>>>>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note:
>>>>>>>>>>>> candidates
>>>>>>>>>>>> are:
>>>>>>>>>>>> T
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>>>>>> T
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>>>>>>>>>
>>>>>>>>>>>> Although I was hoping (and actually needed quite urgently) that
>>>>>>>>>>>> it
>>>>>>>>>>>>
>>>>>>>>>>>> would
>>>>>>>>>>>>
>>>>>>>>>>> be
>>>>>>>>>>> minor issue and get fixed quickly.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> You need to pass a predecessor map to the algorithm as one of the
>>>>>>>>>>>
>>>>>>>>>>>  parameters
>>>>>>>>>> (or put it as a part of your graph but making an external property
>>>>>>>>>> map
>>>>>>>>>> to
>>>>>>>>>> give
>>>>>>>>>> to the algorithm is easier).
>>>>>>>>>>
>>>>>>>>>> Hi Jeremy,
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> It took me a while but I finally figure out how to pass the
>>>>>>>>>>
>>>>>>>>> predecessor
>>>>>>>>>
>>>>>>>>> map. Unfortunately it doesn't have any effect. Also, I might be
>>>>>>>>>
>>>>>>>>>> wrong
>>>>>>>>>> but I
>>>>>>>>>> don't see any logical reason why predecessor map should have any
>>>>>>>>>> bearing
>>>>>>>>>> on
>>>>>>>>>> the correctness of the depth. I have attached the new code.  I am
>>>>>>>>>> not
>>>>>>>>>> able
>>>>>>>>>> to print out the predecessor because I am not able to figure out
>>>>>>>>>> its
>>>>>>>>>> type.
>>>>>>>>>> Maybe you could help me resolve this.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> It would be nice to have this code running. I need to profile
>>>>>>>>>> graph
>>>>>>>>>>
>>>>>>>>>>  performance on a new machine by tomorrow. Again, thanks for you
>>>>>>>>> patience
>>>>>>>>> and
>>>>>>>>> time. I really appreciate you looking into this.
>>>>>>>>>
>>>>>>>>> Hi Jeremiah,
>>>>>>>>>
>>>>>>>>> Was just wondering if you had time to look into this or any
>>>>>>>>> suggestion
>>>>>>>>>
>>>>>>>>> on
>>>>>>>>>
>>>>>>>> how further proceed. I can get you the output of predecessor map if
>>>>>>>> that
>>>>>>>> would help.
>>>>>>>> Just that I haven't be been able to figure out what the is type of
>>>>>>>> the
>>>>>>>> property map returned by make_distributed_property_map.
>>>>>>>> Please let me know your thoughts.
>>>>>>>>
>>>>>>>>
>>>>>>>> The person who really knows this library is not around as far as I
>>>>>>>>
>>>>>>> know;
>>>>>>> he
>>>>>>> might be on vacation.  The type returned from
>>>>>>> make_distributed_property_map
>>>>>>> is documented on <URL:
>>>>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>>>>>> distributed_property_map.html>.  One thing that you could do to debug
>>>>>>> things is to put in your own color map and look at what values it
>>>>>>> ends
>>>>>>> up
>>>>>>> with at the end of the algorithm, and possibly even to put in a local
>>>>>>> color
>>>>>>> map that prints out when elements are changed.  That might be a lot
>>>>>>> of
>>>>>>> work
>>>>>>> for what could end up being an obvious problem (that I just don't
>>>>>>> know
>>>>>>> how
>>>>>>> to diagnose), though.  BTW, does the example in
>>>>>>> libs/graph_parallel/example/breadth_first_search.cpp work for you?
>>>>>>>  It
>>>>>>> appears to be doing the same thing you want to do.  If that works, it
>>>>>>> could
>>>>>>> be a problem in your visitor.
>>>>>>>
>>>>>>>
>>>>>>> I derived this code from
>>>>>>> graph_parallel/example/breadth_first_search.cpp.
>>>>>>>
>>>>>>> The problem is that I don't understand the input and the output of
>>>>>>> the
>>>>>>>
>>>>>> example code. It would be great if I could get an explanation for  the
>>>>>> format of the input file. Then I can transform my graph into that
>>>>>> format
>>>>>> and pass to the algorithm. That would be enough for my current
>>>>>> purpose.
>>>>>>
>>>>>> As time permits I would try out your suggestions and let know of
>>>>>> update.
>>>>>> In
>>>>>> the meantime I am hoping that I would get input from other relevant
>>>>>> authors.
>>>>>>
>>>>>>
>>>>>>  This is what I could tell from the code.
>>>>>
>>>>> Input:
>>>>> http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>>
>>>>> metis_graph.html<
>>>>> http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html
>>>>> >
>>>>>
>>>>>
>>>>> Output:
>>>>> http://www.graphviz.org/doc/info/lang.html
>>>>>
>>>>>
>>>>> Thanks Jeremiah. The link was helpful. I understood the input graph
>>>>> format.
>>>>> Its for undirected graph only. However the BFS output is still coming
>>>>> out
>>>>> to
>>>>> be  incorrect. I  tried with  a sample line graph  of 4 nodes and it
>>>>> exhibits the same problem as before.
>>>>>
>>>>> The distances of nodes on process 2 is not getting updated. On the
>>>>> other
>>>>>
>>>> hand dijkstra shortest paths example is working correctly.
>>>>
>>>> Thanks
>>>> Sandeep
>>>>
>>>>
>>> I rewrote most of your code before I realized that you're outputting all
>>> your distances on process 0, even for vertices process 0 doesn't own.
>>>  The
>>> large value you see is std::numeric_limits<distance_type>::max.  When you
>>> call get(distance, vertex(i, g)) for some i not owned by the current
>>> process
>>> a ghost cell is created for the requested value and a request sent to the
>>> owner of that vertex for the correct value.  get() then returns whatever
>>> the
>>> default value is for the distance property map, which in this case is
>>> infinity (i.e. std::numeric_limits<distance_type>::max.
>>>
>>> In some cases you may get the correct distance value because process 0
>>> has
>>> previously requested that value (and it may or may not be up to date).
>>>  If
>>> process 0 has never requested that distance value and it doesn't own the
>>> vertex, then you'll get infinity.
>>>
>>> You need to gather all your data before you output it from a single node
>>> (i.e. issue a get() or request() which is a get with no return value, for
>>> each data element).  If you want your code to be scalable you should
>>> output
>>> your data in a distributed fashion from all nodes at once.  Remember that
>>> updated values won't be guaranteed to arrive until the next
>>> synchronization
>>> step.
>>>
>>> If you want the modified version of your code let me know and I'll finish
>>> it and ship it your way.
>>>
>>> -Nick
>>>
>>>
>>> Hi Nick,
>>>
>>>   Thanks so much for looking into this. Sorry, I couldn't get to it
>> earlier
>> due to other concerns. I corrected the mistake you mentioned and I don't
>> get
>> numeric_limit<>::max() for any nodes anymore.
>>
>> I believe the graph/distributed/graphviz.hpp was outputting the distance
>> in
>> correct fashion.
>>
>> Unfortunately, the output is still coming out to be incorrect.
>> It was also the case with output from graphviz.hpp.
>>
>> For the test graph that we mentioned before, essentially
>> 0 --> 1 --> 2 --> 3,
>> 0 --> 4 --> 3
>>
>> the distance output is as follows:
>> global node-id : distance
>> 0 : 0
>> 1 : 1
>> 2 : 2
>> 3 : 1            //(wrong: should be 2)
>> 4 :  0          // should be 1
>>
>> If possible can you send me your version of the code. Let me know if you
>> need mine (the updated version).
>>
>
>
> Given the description of your problem above, and assuming you're using a
> block distribution with 8 vertices, it sounds like you're initializing the
> distance to the first vertex on *each* process to 0, as opposed to only the
> distance to the source.  The vertex with global index 4 is actually local
> index 0 on process one using the above distribution.  If you initialize the
> distances to the vertices with global indices 0 and 4 to 0, then your
> results make sense.  Let me know if that's not the case, but I surmise that
> it is.
>
>   Very much so :-). Thanks for getting me started with by catching these

minor but fatal mis-understandings with PBFS code. I get the  feeling the I
haven't read some vital documentation, apart from the manual, on regarding
distributed graph.

Also there's a problem in your depth labeling visitor.  In the case of

> cross-processor edges the process that owns the target of the edge doesn't
> necessarily have the distance to the source of the edge available locally.
>  This will lead to incorrect distance labels even though tree and non-tree
> edges will still be correctly recognized since the BFS is
> level-synchronized.  The fastest way to handle this is to modify the BFS
> queue to also pass distance data (which is how the shortest paths algorithms
> do it).  You could also send the data separately and probe for it on the
> receiving side.  Check out the distributed betweenness centrality code for
> how to create a distributed queue which contains tuples of data one element
> of which is a vertex (in order to know where to route the data).
>  Integrating this type of vertex queue (i.e. one that contains a data
> payload) with BFS basically just requires handling the data payload on the
> receiving side.
>
> I would try this out. So basically the default call

 boost::breadth_first_search
     (g, start,
boost::visitor(boost::make_bfs_visitor(boost::record_distances(distance,
boost::on_tree_edge()))));

wouldn't work.  I assumed that distributed BFS implementation did exactly
what you mentioned.
Although I would write my own, parallel  visitor as well per your
suggestions.

thanks
Sandeep







> Cheers,
>
>
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Wed, Nov 4, 2009 at 3:11 PM, Sandeep Gupta <gupta.sandeep@...>wrote:

>
>
> On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@...>wrote:
>
>>
>> On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
>>
>>  On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@...
>>> >wrote:
>>>
>>>
>>>> On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
>>>>
>>>> On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@...
>>>>
>>>>> wrote:
>>>>>>
>>>>>
>>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>
>>>>>>
>>>>>> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <
>>>>>> jewillco@...
>>>>>>
>>>>>>  wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>>>
>>>>>>>
>>>>>>>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <
>>>>>>>> gupta.sandeep@...
>>>>>>>>
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>>>>>>
>>>>>>>>>> jewillco@...
>>>>>>>>>>
>>>>>>>>>> wrote:
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>  On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>  The error snippet regarding  predecessor map:
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>>> int>&)'
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>>> int>&,
>>>>>>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note:
>>>>>>>>>>>>> candidates
>>>>>>>>>>>>> are:
>>>>>>>>>>>>> T
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>>>>>>> T
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> Jeremiah, Do you think that I should file a bug report for
>>>>>>>>>>>>> this.
>>>>>>>>>>>>>
>>>>>>>>>>>>> Although I was hoping (and actually needed quite urgently) that
>>>>>>>>>>>>> it
>>>>>>>>>>>>>
>>>>>>>>>>>>> would
>>>>>>>>>>>>>
>>>>>>>>>>>> be
>>>>>>>>>>>> minor issue and get fixed quickly.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> You need to pass a predecessor map to the algorithm as one of
>>>>>>>>>>>> the
>>>>>>>>>>>>
>>>>>>>>>>>>  parameters
>>>>>>>>>>> (or put it as a part of your graph but making an external
>>>>>>>>>>> property
>>>>>>>>>>> map
>>>>>>>>>>> to
>>>>>>>>>>> give
>>>>>>>>>>> to the algorithm is easier).
>>>>>>>>>>>
>>>>>>>>>>> Hi Jeremy,
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> It took me a while but I finally figure out how to pass the
>>>>>>>>>>>
>>>>>>>>>> predecessor
>>>>>>>>>>
>>>>>>>>>> map. Unfortunately it doesn't have any effect. Also, I might be
>>>>>>>>>>
>>>>>>>>>>> wrong
>>>>>>>>>>> but I
>>>>>>>>>>> don't see any logical reason why predecessor map should have any
>>>>>>>>>>> bearing
>>>>>>>>>>> on
>>>>>>>>>>> the correctness of the depth. I have attached the new code.  I am
>>>>>>>>>>> not
>>>>>>>>>>> able
>>>>>>>>>>> to print out the predecessor because I am not able to figure out
>>>>>>>>>>> its
>>>>>>>>>>> type.
>>>>>>>>>>> Maybe you could help me resolve this.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> It would be nice to have this code running. I need to profile
>>>>>>>>>>> graph
>>>>>>>>>>>
>>>>>>>>>>>  performance on a new machine by tomorrow. Again, thanks for you
>>>>>>>>>> patience
>>>>>>>>>> and
>>>>>>>>>> time. I really appreciate you looking into this.
>>>>>>>>>>
>>>>>>>>>> Hi Jeremiah,
>>>>>>>>>>
>>>>>>>>>> Was just wondering if you had time to look into this or any
>>>>>>>>>> suggestion
>>>>>>>>>>
>>>>>>>>>> on
>>>>>>>>>>
>>>>>>>>> how further proceed. I can get you the output of predecessor map if
>>>>>>>>> that
>>>>>>>>> would help.
>>>>>>>>> Just that I haven't be been able to figure out what the is type of
>>>>>>>>> the
>>>>>>>>> property map returned by make_distributed_property_map.
>>>>>>>>> Please let me know your thoughts.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> The person who really knows this library is not around as far as I
>>>>>>>>>
>>>>>>>> know;
>>>>>>>> he
>>>>>>>> might be on vacation.  The type returned from
>>>>>>>> make_distributed_property_map
>>>>>>>> is documented on <URL:
>>>>>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>>>>>>> distributed_property_map.html>.  One thing that you could do to
>>>>>>>> debug
>>>>>>>> things is to put in your own color map and look at what values it
>>>>>>>> ends
>>>>>>>> up
>>>>>>>> with at the end of the algorithm, and possibly even to put in a
>>>>>>>> local
>>>>>>>> color
>>>>>>>> map that prints out when elements are changed.  That might be a lot
>>>>>>>> of
>>>>>>>> work
>>>>>>>> for what could end up being an obvious problem (that I just don't
>>>>>>>> know
>>>>>>>> how
>>>>>>>> to diagnose), though.  BTW, does the example in
>>>>>>>> libs/graph_parallel/example/breadth_first_search.cpp work for you?
>>>>>>>>  It
>>>>>>>> appears to be doing the same thing you want to do.  If that works,
>>>>>>>> it
>>>>>>>> could
>>>>>>>> be a problem in your visitor.
>>>>>>>>
>>>>>>>>
>>>>>>>> I derived this code from
>>>>>>>> graph_parallel/example/breadth_first_search.cpp.
>>>>>>>>
>>>>>>>> The problem is that I don't understand the input and the output of
>>>>>>>> the
>>>>>>>>
>>>>>>> example code. It would be great if I could get an explanation for
>>>>>>>  the
>>>>>>> format of the input file. Then I can transform my graph into that
>>>>>>> format
>>>>>>> and pass to the algorithm. That would be enough for my current
>>>>>>> purpose.
>>>>>>>
>>>>>>> As time permits I would try out your suggestions and let know of
>>>>>>> update.
>>>>>>> In
>>>>>>> the meantime I am hoping that I would get input from other relevant
>>>>>>> authors.
>>>>>>>
>>>>>>>
>>>>>>>  This is what I could tell from the code.
>>>>>>
>>>>>> Input:
>>>>>> http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>>> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>>>
>>>>>> metis_graph.html<
>>>>>> http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html
>>>>>> >
>>>>>>
>>>>>>
>>>>>> Output:
>>>>>> http://www.graphviz.org/doc/info/lang.html
>>>>>>
>>>>>>
>>>>>> Thanks Jeremiah. The link was helpful. I understood the input graph
>>>>>> format.
>>>>>> Its for undirected graph only. However the BFS output is still coming
>>>>>> out
>>>>>> to
>>>>>> be  incorrect. I  tried with  a sample line graph  of 4 nodes and it
>>>>>> exhibits the same problem as before.
>>>>>>
>>>>>> The distances of nodes on process 2 is not getting updated. On the
>>>>>> other
>>>>>>
>>>>> hand dijkstra shortest paths example is working correctly.
>>>>>
>>>>> Thanks
>>>>> Sandeep
>>>>>
>>>>>
>>>> I rewrote most of your code before I realized that you're outputting all
>>>> your distances on process 0, even for vertices process 0 doesn't own.
>>>>  The
>>>> large value you see is std::numeric_limits<distance_type>::max.  When
>>>> you
>>>> call get(distance, vertex(i, g)) for some i not owned by the current
>>>> process
>>>> a ghost cell is created for the requested value and a request sent to
>>>> the
>>>> owner of that vertex for the correct value.  get() then returns whatever
>>>> the
>>>> default value is for the distance property map, which in this case is
>>>> infinity (i.e. std::numeric_limits<distance_type>::max.
>>>>
>>>> In some cases you may get the correct distance value because process 0
>>>> has
>>>> previously requested that value (and it may or may not be up to date).
>>>>  If
>>>> process 0 has never requested that distance value and it doesn't own the
>>>> vertex, then you'll get infinity.
>>>>
>>>> You need to gather all your data before you output it from a single node
>>>> (i.e. issue a get() or request() which is a get with no return value,
>>>> for
>>>> each data element).  If you want your code to be scalable you should
>>>> output
>>>> your data in a distributed fashion from all nodes at once.  Remember
>>>> that
>>>> updated values won't be guaranteed to arrive until the next
>>>> synchronization
>>>> step.
>>>>
>>>> If you want the modified version of your code let me know and I'll
>>>> finish
>>>> it and ship it your way.
>>>>
>>>> -Nick
>>>>
>>>>
>>>> Hi Nick,
>>>>
>>>>   Thanks so much for looking into this. Sorry, I couldn't get to it
>>> earlier
>>> due to other concerns. I corrected the mistake you mentioned and I don't
>>> get
>>> numeric_limit<>::max() for any nodes anymore.
>>>
>>> I believe the graph/distributed/graphviz.hpp was outputting the distance
>>> in
>>> correct fashion.
>>>
>>> Unfortunately, the output is still coming out to be incorrect.
>>> It was also the case with output from graphviz.hpp.
>>>
>>> For the test graph that we mentioned before, essentially
>>> 0 --> 1 --> 2 --> 3,
>>> 0 --> 4 --> 3
>>>
>>> the distance output is as follows:
>>> global node-id : distance
>>> 0 : 0
>>> 1 : 1
>>> 2 : 2
>>> 3 : 1            //(wrong: should be 2)
>>> 4 :  0          // should be 1
>>>
>>> If possible can you send me your version of the code. Let me know if you
>>> need mine (the updated version).
>>>
>>
>>
>> Given the description of your problem above, and assuming you're using a
>> block distribution with 8 vertices, it sounds like you're initializing the
>> distance to the first vertex on *each* process to 0, as opposed to only the
>> distance to the source.  The vertex with global index 4 is actually local
>> index 0 on process one using the above distribution.  If you initialize the
>> distances to the vertices with global indices 0 and 4 to 0, then your
>> results make sense.  Let me know if that's not the case, but I surmise that
>> it is.
>>
>>   Very much so :-). Thanks for getting me started with by catching these
> minor but fatal mis-understandings with PBFS code. I understood that call
> vertex(i,g) creates a descriptor for ith global vertex.
>
> Also there's a problem in your depth labeling visitor.  In the case of
>> cross-processor edges the process that owns the target of the edge doesn't
>> necessarily have the distance to the source of the edge available locally.
>>  This will lead to incorrect distance labels even though tree and non-tree
>> edges will still be correctly recognized since the BFS is
>> level-synchronized.  The fastest way to handle this is to modify the BFS
>> queue to also pass distance data (which is how the shortest paths algorithms
>> do it).  You could also send the data separately and probe for it on the
>> receiving side.  Check out the distributed betweenness centrality code for
>> how to create a distributed queue which contains tuples of data one element
>> of which is a vertex (in order to know where to route the data).
>>  Integrating this type of vertex queue (i.e. one that contains a data
>> payload) with BFS basically just requires handling the data payload on the
>> receiving side.
>>
>> I would try this out. So basically the default call
>
>  boost::breadth_first_search
>      (g, start,
> boost::visitor(boost::make_bfs_visitor(boost::record_distances(distance,
> boost::on_tree_edge()))));
>
> wouldn't work.  I assumed that distributed BFS implementation did exactly
> what you mentioned.
> Although I would write my own, parallel  visitor as well per your
> suggestions.
>
> thanks
> Sandeep
>
>
>
>    Let me also add that I did modified code that initializes only the

distance to 0th vertex of processor 0. In this case i am facing the dilemma
of what should I pass as start vertex for processes > 0. I can't pass the
global start vertex (probably the type won't be acceptable to
breadth_first_search.

I will dig further into the betweeness centrality and dijkstra code to
figure this out. Appreciate your input.

Thanks
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[Nick Edmonds]

On Nov 4, 2009, at 6:22 PM, Sandeep Gupta wrote:

> On Wed, Nov 4, 2009 at 3:11 PM, Sandeep Gupta  
> <gupta.sandeep@...>wrote:
>
>>
>>
>> On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@...
>> >wrote:
>>
>>>
>>> On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
>>>
>>> On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@...
>>>>> wrote:
>>>>
>>>>
>>>>> On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
>>>>>
>>>>> On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <jewillco@...
>>>>>
>>>>>> wrote:
>>>>>>>
>>>>>>
>>>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>>
>>>>>>>
>>>>>>> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <
>>>>>>> jewillco@...
>>>>>>>
>>>>>>> wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>>>>
>>>>>>>>
>>>>>>>>> On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <
>>>>>>>>> gupta.sandeep@...
>>>>>>>>>
>>>>>>>>> wrote:
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>>>>>>>
>>>>>>>>>>> jewillco@...
>>>>>>>>>>>
>>>>>>>>>>> wrote:
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> The error snippet regarding  predecessor map:
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> '(boost
>>>>>>>>>>>>>> ::property_reduce
>>>>>>>>>>>>>> <
>>>>>>>>>>>>>> boost
>>>>>>>>>>>>>> ::vertex_predecessor_t
>>>>>>>>>>>>>> >::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>>>> (const  
>>>>>>>>>>>>>> boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>>>> int>&)'
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> ../../../boost/property_map/parallel/impl/
>>>>>>>>>>>>>> distributed_property_map.ipp:141:
>>>>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> '(boost
>>>>>>>>>>>>>> ::property_reduce
>>>>>>>>>>>>>> <
>>>>>>>>>>>>>> boost
>>>>>>>>>>>>>> ::vertex_predecessor_t
>>>>>>>>>>>>>> >::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>>>> (const  
>>>>>>>>>>>>>> boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>>>> int>&,
>>>>>>>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note:
>>>>>>>>>>>>>> candidates
>>>>>>>>>>>>>> are:
>>>>>>>>>>>>>> T
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> boost
>>>>>>>>>>>>>> ::property_reduce
>>>>>>>>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>>>>>>>> T
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> boost
>>>>>>>>>>>>>> ::property_reduce
>>>>>>>>>>>>>> <boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>>>>>>>> T, T) const [with T =  
>>>>>>>>>>>>>> boost::detail::error_property_not_found]
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Jeremiah, Do you think that I should file a bug report  
>>>>>>>>>>>>>> for
>>>>>>>>>>>>>> this.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> Although I was hoping (and actually needed quite  
>>>>>>>>>>>>>> urgently) that
>>>>>>>>>>>>>> it
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> would
>>>>>>>>>>>>>>
>>>>>>>>>>>>> be
>>>>>>>>>>>>> minor issue and get fixed quickly.
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> You need to pass a predecessor map to the algorithm as  
>>>>>>>>>>>>> one of
>>>>>>>>>>>>> the
>>>>>>>>>>>>>
>>>>>>>>>>>>> parameters
>>>>>>>>>>>> (or put it as a part of your graph but making an external
>>>>>>>>>>>> property
>>>>>>>>>>>> map
>>>>>>>>>>>> to
>>>>>>>>>>>> give
>>>>>>>>>>>> to the algorithm is easier).
>>>>>>>>>>>>
>>>>>>>>>>>> Hi Jeremy,
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> It took me a while but I finally figure out how to pass the
>>>>>>>>>>>>
>>>>>>>>>>> predecessor
>>>>>>>>>>>
>>>>>>>>>>> map. Unfortunately it doesn't have any effect. Also, I  
>>>>>>>>>>> might be
>>>>>>>>>>>
>>>>>>>>>>>> wrong
>>>>>>>>>>>> but I
>>>>>>>>>>>> don't see any logical reason why predecessor map should  
>>>>>>>>>>>> have any
>>>>>>>>>>>> bearing
>>>>>>>>>>>> on
>>>>>>>>>>>> the correctness of the depth. I have attached the new  
>>>>>>>>>>>> code.  I am
>>>>>>>>>>>> not
>>>>>>>>>>>> able
>>>>>>>>>>>> to print out the predecessor because I am not able to  
>>>>>>>>>>>> figure out
>>>>>>>>>>>> its
>>>>>>>>>>>> type.
>>>>>>>>>>>> Maybe you could help me resolve this.
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> It would be nice to have this code running. I need to  
>>>>>>>>>>>> profile
>>>>>>>>>>>> graph
>>>>>>>>>>>>
>>>>>>>>>>>> performance on a new machine by tomorrow. Again, thanks  
>>>>>>>>>>>> for you
>>>>>>>>>>> patience
>>>>>>>>>>> and
>>>>>>>>>>> time. I really appreciate you looking into this.
>>>>>>>>>>>
>>>>>>>>>>> Hi Jeremiah,
>>>>>>>>>>>
>>>>>>>>>>> Was just wondering if you had time to look into this or any
>>>>>>>>>>> suggestion
>>>>>>>>>>>
>>>>>>>>>>> on
>>>>>>>>>>>
>>>>>>>>>> how further proceed. I can get you the output of  
>>>>>>>>>> predecessor map if
>>>>>>>>>> that
>>>>>>>>>> would help.
>>>>>>>>>> Just that I haven't be been able to figure out what the is  
>>>>>>>>>> type of
>>>>>>>>>> the
>>>>>>>>>> property map returned by make_distributed_property_map.
>>>>>>>>>> Please let me know your thoughts.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> The person who really knows this library is not around as  
>>>>>>>>>> far as I
>>>>>>>>>>
>>>>>>>>> know;
>>>>>>>>> he
>>>>>>>>> might be on vacation.  The type returned from
>>>>>>>>> make_distributed_property_map
>>>>>>>>> is documented on <URL:
>>>>>>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>>>>>>>> distributed_property_map.html>.  One thing that you could do  
>>>>>>>>> to
>>>>>>>>> debug
>>>>>>>>> things is to put in your own color map and look at what  
>>>>>>>>> values it
>>>>>>>>> ends
>>>>>>>>> up
>>>>>>>>> with at the end of the algorithm, and possibly even to put  
>>>>>>>>> in a
>>>>>>>>> local
>>>>>>>>> color
>>>>>>>>> map that prints out when elements are changed.  That might  
>>>>>>>>> be a lot
>>>>>>>>> of
>>>>>>>>> work
>>>>>>>>> for what could end up being an obvious problem (that I just  
>>>>>>>>> don't
>>>>>>>>> know
>>>>>>>>> how
>>>>>>>>> to diagnose), though.  BTW, does the example in
>>>>>>>>> libs/graph_parallel/example/breadth_first_search.cpp work  
>>>>>>>>> for you?
>>>>>>>>> It
>>>>>>>>> appears to be doing the same thing you want to do.  If that  
>>>>>>>>> works,
>>>>>>>>> it
>>>>>>>>> could
>>>>>>>>> be a problem in your visitor.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> I derived this code from
>>>>>>>>> graph_parallel/example/breadth_first_search.cpp.
>>>>>>>>>
>>>>>>>>> The problem is that I don't understand the input and the  
>>>>>>>>> output of
>>>>>>>>> the
>>>>>>>>>
>>>>>>>> example code. It would be great if I could get an explanation  
>>>>>>>> for
>>>>>>>> the
>>>>>>>> format of the input file. Then I can transform my graph into  
>>>>>>>> that
>>>>>>>> format
>>>>>>>> and pass to the algorithm. That would be enough for my current
>>>>>>>> purpose.
>>>>>>>>
>>>>>>>> As time permits I would try out your suggestions and let know  
>>>>>>>> of
>>>>>>>> update.
>>>>>>>> In
>>>>>>>> the meantime I am hoping that I would get input from other  
>>>>>>>> relevant
>>>>>>>> authors.
>>>>>>>>
>>>>>>>>
>>>>>>>> This is what I could tell from the code.
>>>>>>>
>>>>>>> Input:
>>>>>>> http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/ 
>>>>>>> >
>>>>>>> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>>>>
>>>>>>> metis_graph.html<
>>>>>>> http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Output:
>>>>>>> http://www.graphviz.org/doc/info/lang.html
>>>>>>>
>>>>>>>
>>>>>>> Thanks Jeremiah. The link was helpful. I understood the input  
>>>>>>> graph
>>>>>>> format.
>>>>>>> Its for undirected graph only. However the BFS output is still  
>>>>>>> coming
>>>>>>> out
>>>>>>> to
>>>>>>> be  incorrect. I  tried with  a sample line graph  of 4 nodes  
>>>>>>> and it
>>>>>>> exhibits the same problem as before.
>>>>>>>
>>>>>>> The distances of nodes on process 2 is not getting updated. On  
>>>>>>> the
>>>>>>> other
>>>>>>>
>>>>>> hand dijkstra shortest paths example is working correctly.
>>>>>>
>>>>>> Thanks
>>>>>> Sandeep
>>>>>>
>>>>>>
>>>>> I rewrote most of your code before I realized that you're  
>>>>> outputting all
>>>>> your distances on process 0, even for vertices process 0 doesn't  
>>>>> own.
>>>>> The
>>>>> large value you see is std::numeric_limits<distance_type>::max.  
>>>>> When
>>>>> you
>>>>> call get(distance, vertex(i, g)) for some i not owned by the  
>>>>> current
>>>>> process
>>>>> a ghost cell is created for the requested value and a request  
>>>>> sent to
>>>>> the
>>>>> owner of that vertex for the correct value.  get() then returns  
>>>>> whatever
>>>>> the
>>>>> default value is for the distance property map, which in this  
>>>>> case is
>>>>> infinity (i.e. std::numeric_limits<distance_type>::max.
>>>>>
>>>>> In some cases you may get the correct distance value because  
>>>>> process 0
>>>>> has
>>>>> previously requested that value (and it may or may not be up to  
>>>>> date).
>>>>> If
>>>>> process 0 has never requested that distance value and it doesn't  
>>>>> own the
>>>>> vertex, then you'll get infinity.
>>>>>
>>>>> You need to gather all your data before you output it from a  
>>>>> single node
>>>>> (i.e. issue a get() or request() which is a get with no return  
>>>>> value,
>>>>> for
>>>>> each data element).  If you want your code to be scalable you  
>>>>> should
>>>>> output
>>>>> your data in a distributed fashion from all nodes at once.  
>>>>> Remember
>>>>> that
>>>>> updated values won't be guaranteed to arrive until the next
>>>>> synchronization
>>>>> step.
>>>>>
>>>>> If you want the modified version of your code let me know and I'll
>>>>> finish
>>>>> it and ship it your way.
>>>>>
>>>>> -Nick
>>>>>
>>>>>
>>>>> Hi Nick,
>>>>>
>>>>>  Thanks so much for looking into this. Sorry, I couldn't get to it
>>>> earlier
>>>> due to other concerns. I corrected the mistake you mentioned and  
>>>> I don't
>>>> get
>>>> numeric_limit<>::max() for any nodes anymore.
>>>>
>>>> I believe the graph/distributed/graphviz.hpp was outputting the  
>>>> distance
>>>> in
>>>> correct fashion.
>>>>
>>>> Unfortunately, the output is still coming out to be incorrect.
>>>> It was also the case with output from graphviz.hpp.
>>>>
>>>> For the test graph that we mentioned before, essentially
>>>> 0 --> 1 --> 2 --> 3,
>>>> 0 --> 4 --> 3
>>>>
>>>> the distance output is as follows:
>>>> global node-id : distance
>>>> 0 : 0
>>>> 1 : 1
>>>> 2 : 2
>>>> 3 : 1            //(wrong: should be 2)
>>>> 4 :  0          // should be 1
>>>>
>>>> If possible can you send me your version of the code. Let me know  
>>>> if you
>>>> need mine (the updated version).
>>>>
>>>
>>>
>>> Given the description of your problem above, and assuming you're  
>>> using a
>>> block distribution with 8 vertices, it sounds like you're  
>>> initializing the
>>> distance to the first vertex on *each* process to 0, as opposed to  
>>> only the
>>> distance to the source.  The vertex with global index 4 is  
>>> actually local
>>> index 0 on process one using the above distribution.  If you  
>>> initialize the
>>> distances to the vertices with global indices 0 and 4 to 0, then  
>>> your
>>> results make sense.  Let me know if that's not the case, but I  
>>> surmise that
>>> it is.
>>>
>>>  Very much so :-). Thanks for getting me started with by catching  
>>> these
>> minor but fatal mis-understandings with PBFS code. I understood  
>> that call
>> vertex(i,g) creates a descriptor for ith global vertex.
>>
>> Also there's a problem in your depth labeling visitor.  In the case  
>> of
>>> cross-processor edges the process that owns the target of the edge  
>>> doesn't
>>> necessarily have the distance to the source of the edge available  
>>> locally.
>>> This will lead to incorrect distance labels even though tree and  
>>> non-tree
>>> edges will still be correctly recognized since the BFS is
>>> level-synchronized.  The fastest way to handle this is to modify  
>>> the BFS
>>> queue to also pass distance data (which is how the shortest paths  
>>> algorithms
>>> do it).  You could also send the data separately and probe for it  
>>> on the
>>> receiving side.  Check out the distributed betweenness centrality  
>>> code for
>>> how to create a distributed queue which contains tuples of data  
>>> one element
>>> of which is a vertex (in order to know where to route the data).
>>> Integrating this type of vertex queue (i.e. one that contains a data
>>> payload) with BFS basically just requires handling the data  
>>> payload on the
>>> receiving side.
>>>
>>> I would try this out. So basically the default call
>>
>> boost::breadth_first_search
>>     (g, start,
>> boost
>> ::visitor(boost::make_bfs_visitor(boost::record_distances(distance,
>> boost::on_tree_edge()))));
>>
>> wouldn't work.  I assumed that distributed BFS implementation did  
>> exactly
>> what you mentioned.
>> Although I would write my own, parallel  visitor as well per your
>> suggestions.
>>
>> thanks
>> Sandeep
>>
>>
>>
>>   Let me also add that I did modified code that initializes only the
> distance to 0th vertex of processor 0. In this case i am facing the  
> dilemma
> of what should I pass as start vertex for processes > 0. I can't  
> pass the
> global start vertex (probably the type won't be acceptable to
> breadth_first_search.
>
> I will dig further into the betweeness centrality and dijkstra code to
> figure this out. Appreciate your input.

The short answer is, just pass the same source vertex on all processors.

Explanation: Each processor will push the source vertex on the  
distributed queue but all the non-local pushes end up being no-ops  
since the source vertex is black at the end of the first BFS level  
when the messages arrive.  The source vertex just has to be  
graph_traits<Graph>::vertex_descriptor, which you can construct using  
vertex() call if you want to generate it from a global vertex index.  
The fact that all processors push the source vertex is an artifact of  
reusing the sequential BFS code, it could be changed but I haven't  
found it to be an issue thus far.

This actually brings up an interesting feature of BFS, its possible to  
start a BFS from multiple source vertices by passing a different  
source on each processor (you can also pass a queue containing  
additional starting vertices if you need > num_procs sources).  The  
strongly connected components algorithm uses this approach to run many  
BFSs on disconnected subgraphs in parallel.

One last note on your visitor, my statement was incorrect, sorry.  I  
was looking at some other code and confused it with yours, your depth  
labeling visitor will work fine because it 'pushes' distance labels.  
Basically it writes the distance to the vertex it pushes onto the  
queue into the distributed property map at the same time (actually  
immediately before).  This means that at the next synchronization step  
both the distance and the vertex descriptor will arrive, in fact the  
ordering of the messages insures that the distance will arrive prior  
to the vertex on the queue.  Sorry about that, I was looking at  
another visitor that was 'pulling' data, which is much more problematic.

Hopefully that solves all your problems and my apologies again on  
leading you to believe there was something wrong with your visitor.

The data model is a little tricky to wrap your head around, but once  
you've written some code it should become more intuitive.

Cheers,
Nick
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

[sansanx]

On Wed, Nov 4, 2009 at 3:39 PM, Nick Edmonds <ngedmond@...>wrote:

>
> On Nov 4, 2009, at 6:22 PM, Sandeep Gupta wrote:
>
>  On Wed, Nov 4, 2009 at 3:11 PM, Sandeep Gupta <gupta.sandeep@...
>> >wrote:
>>
>>
>>>
>>> On Wed, Nov 4, 2009 at 12:18 PM, Nick Edmonds <ngedmond@...
>>> >wrote:
>>>
>>>
>>>> On Nov 3, 2009, at 10:44 PM, Sandeep Gupta wrote:
>>>>
>>>> On Mon, Nov 2, 2009 at 12:43 PM, Nick Edmonds <ngedmond@...
>>>>
>>>>> wrote:
>>>>>>
>>>>>
>>>>>
>>>>>  On Oct 31, 2009, at 1:00 AM, Sandeep Gupta wrote:
>>>>>>
>>>>>> On Fri, Oct 30, 2009 at 6:41 AM, Jeremiah Willcock <
>>>>>> jewillco@...
>>>>>>
>>>>>>  wrote:
>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>>>
>>>>>>>
>>>>>>>> On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <
>>>>>>>> jewillco@...
>>>>>>>>
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>  On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>  On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <
>>>>>>>>>> gupta.sandeep@...
>>>>>>>>>>
>>>>>>>>>> wrote:
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <
>>>>>>>>>>>
>>>>>>>>>>>  jewillco@...
>>>>>>>>>>>>
>>>>>>>>>>>> wrote:
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> The error snippet regarding  predecessor map:
>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>>>>> int>&)'
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>>>>>>>>>>> error: no match for call to
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>>>>>>>>>>> (const boost::detail::parallel::global_descriptor<unsigned
>>>>>>>>>>>>>>> int>&,
>>>>>>>>>>>>>>> boost::detail::error_property_not_found&, const
>>>>>>>>>>>>>>> boost::detail::error_property_not_found&)'
>>>>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note:
>>>>>>>>>>>>>>> candidates
>>>>>>>>>>>>>>> are:
>>>>>>>>>>>>>>> T
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>>>>>>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>>>>>>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>>>>>>>>>>> T
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>>>>>>>>>>> T, T) const [with T =
>>>>>>>>>>>>>>> boost::detail::error_property_not_found]
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Jeremiah, Do you think that I should file a bug report for
>>>>>>>>>>>>>>> this.
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> Although I was hoping (and actually needed quite urgently)
>>>>>>>>>>>>>>> that
>>>>>>>>>>>>>>> it
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>> would
>>>>>>>>>>>>>>>
>>>>>>>>>>>>>>>  be
>>>>>>>>>>>>>> minor issue and get fixed quickly.
>>>>>>>>>>>>>>
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> You need to pass a predecessor map to the algorithm as one of
>>>>>>>>>>>>>> the
>>>>>>>>>>>>>>
>>>>>>>>>>>>>> parameters
>>>>>>>>>>>>>>
>>>>>>>>>>>>> (or put it as a part of your graph but making an external
>>>>>>>>>>>>> property
>>>>>>>>>>>>> map
>>>>>>>>>>>>> to
>>>>>>>>>>>>> give
>>>>>>>>>>>>> to the algorithm is easier).
>>>>>>>>>>>>>
>>>>>>>>>>>>> Hi Jeremy,
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> It took me a while but I finally figure out how to pass the
>>>>>>>>>>>>>
>>>>>>>>>>>>>  predecessor
>>>>>>>>>>>>
>>>>>>>>>>>> map. Unfortunately it doesn't have any effect. Also, I might be
>>>>>>>>>>>>
>>>>>>>>>>>>  wrong
>>>>>>>>>>>>> but I
>>>>>>>>>>>>> don't see any logical reason why predecessor map should have
>>>>>>>>>>>>> any
>>>>>>>>>>>>> bearing
>>>>>>>>>>>>> on
>>>>>>>>>>>>> the correctness of the depth. I have attached the new code.  I
>>>>>>>>>>>>> am
>>>>>>>>>>>>> not
>>>>>>>>>>>>> able
>>>>>>>>>>>>> to print out the predecessor because I am not able to figure
>>>>>>>>>>>>> out
>>>>>>>>>>>>> its
>>>>>>>>>>>>> type.
>>>>>>>>>>>>> Maybe you could help me resolve this.
>>>>>>>>>>>>>
>>>>>>>>>>>>>
>>>>>>>>>>>>> It would be nice to have this code running. I need to profile
>>>>>>>>>>>>> graph
>>>>>>>>>>>>>
>>>>>>>>>>>>> performance on a new machine by tomorrow. Again, thanks for you
>>>>>>>>>>>>>
>>>>>>>>>>>> patience
>>>>>>>>>>>> and
>>>>>>>>>>>> time. I really appreciate you looking into this.
>>>>>>>>>>>>
>>>>>>>>>>>> Hi Jeremiah,
>>>>>>>>>>>>
>>>>>>>>>>>> Was just wondering if you had time to look into this or any
>>>>>>>>>>>> suggestion
>>>>>>>>>>>>
>>>>>>>>>>>> on
>>>>>>>>>>>>
>>>>>>>>>>>>  how further proceed. I can get you the output of predecessor
>>>>>>>>>>> map if
>>>>>>>>>>> that
>>>>>>>>>>> would help.
>>>>>>>>>>> Just that I haven't be been able to figure out what the is type
>>>>>>>>>>> of
>>>>>>>>>>> the
>>>>>>>>>>> property map returned by make_distributed_property_map.
>>>>>>>>>>> Please let me know your thoughts.
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> The person who really knows this library is not around as far as
>>>>>>>>>>> I
>>>>>>>>>>>
>>>>>>>>>>>  know;
>>>>>>>>>> he
>>>>>>>>>> might be on vacation.  The type returned from
>>>>>>>>>> make_distributed_property_map
>>>>>>>>>> is documented on <URL:
>>>>>>>>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/
>>>>>>>>>> distributed_property_map.html>.  One thing that you could do to
>>>>>>>>>> debug
>>>>>>>>>> things is to put in your own color map and look at what values it
>>>>>>>>>> ends
>>>>>>>>>> up
>>>>>>>>>> with at the end of the algorithm, and possibly even to put in a
>>>>>>>>>> local
>>>>>>>>>> color
>>>>>>>>>> map that prints out when elements are changed.  That might be a
>>>>>>>>>> lot
>>>>>>>>>> of
>>>>>>>>>> work
>>>>>>>>>> for what could end up being an obvious problem (that I just don't
>>>>>>>>>> know
>>>>>>>>>> how
>>>>>>>>>> to diagnose), though.  BTW, does the example in
>>>>>>>>>> libs/graph_parallel/example/breadth_first_search.cpp work for you?
>>>>>>>>>> It
>>>>>>>>>> appears to be doing the same thing you want to do.  If that works,
>>>>>>>>>> it
>>>>>>>>>> could
>>>>>>>>>> be a problem in your visitor.
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> I derived this code from
>>>>>>>>>> graph_parallel/example/breadth_first_search.cpp.
>>>>>>>>>>
>>>>>>>>>> The problem is that I don't understand the input and the output of
>>>>>>>>>> the
>>>>>>>>>>
>>>>>>>>>>  example code. It would be great if I could get an explanation for
>>>>>>>>> the
>>>>>>>>> format of the input file. Then I can transform my graph into that
>>>>>>>>> format
>>>>>>>>> and pass to the algorithm. That would be enough for my current
>>>>>>>>> purpose.
>>>>>>>>>
>>>>>>>>> As time permits I would try out your suggestions and let know of
>>>>>>>>> update.
>>>>>>>>> In
>>>>>>>>> the meantime I am hoping that I would get input from other relevant
>>>>>>>>> authors.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> This is what I could tell from the code.
>>>>>>>>>
>>>>>>>>
>>>>>>>> Input:
>>>>>>>> http://people.sc.fsu.edu/~burkardt/data/metis_graph/<http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>>>>> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>>>>> <http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/>
>>>>>>>>
>>>>>>>> metis_graph.html<
>>>>>>>>
>>>>>>>> http://people.sc.fsu.edu/%7Eburkardt/data/metis_graph/metis_graph.html
>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>> Output:
>>>>>>>> http://www.graphviz.org/doc/info/lang.html
>>>>>>>>
>>>>>>>>
>>>>>>>> Thanks Jeremiah. The link was helpful. I understood the input graph
>>>>>>>> format.
>>>>>>>> Its for undirected graph only. However the BFS output is still
>>>>>>>> coming
>>>>>>>> out
>>>>>>>> to
>>>>>>>> be  incorrect. I  tried with  a sample line graph  of 4 nodes and it
>>>>>>>> exhibits the same problem as before.
>>>>>>>>
>>>>>>>> The distances of nodes on process 2 is not getting updated. On the
>>>>>>>> other
>>>>>>>>
>>>>>>>>  hand dijkstra shortest paths example is working correctly.
>>>>>>>
>>>>>>> Thanks
>>>>>>> Sandeep
>>>>>>>
>>>>>>>
>>>>>>>  I rewrote most of your code before I realized that you're outputting
>>>>>> all
>>>>>> your distances on process 0, even for vertices process 0 doesn't own.
>>>>>> The
>>>>>> large value you see is std::numeric_limits<distance_type>::max.  When
>>>>>> you
>>>>>> call get(distance, vertex(i, g)) for some i not owned by the current
>>>>>> process
>>>>>> a ghost cell is created for the requested value and a request sent to
>>>>>> the
>>>>>> owner of that vertex for the correct value.  get() then returns
>>>>>> whatever
>>>>>> the
>>>>>> default value is for the distance property map, which in this case is
>>>>>> infinity (i.e. std::numeric_limits<distance_type>::max.
>>>>>>
>>>>>> In some cases you may get the correct distance value because process 0
>>>>>> has
>>>>>> previously requested that value (and it may or may not be up to date).
>>>>>> If
>>>>>> process 0 has never requested that distance value and it doesn't own
>>>>>> the
>>>>>> vertex, then you'll get infinity.
>>>>>>
>>>>>> You need to gather all your data before you output it from a single
>>>>>> node
>>>>>> (i.e. issue a get() or request() which is a get with no return value,
>>>>>> for
>>>>>> each data element).  If you want your code to be scalable you should
>>>>>> output
>>>>>> your data in a distributed fashion from all nodes at once.  Remember
>>>>>> that
>>>>>> updated values won't be guaranteed to arrive until the next
>>>>>> synchronization
>>>>>> step.
>>>>>>
>>>>>> If you want the modified version of your code let me know and I'll
>>>>>> finish
>>>>>> it and ship it your way.
>>>>>>
>>>>>> -Nick
>>>>>>
>>>>>>
>>>>>> Hi Nick,
>>>>>>
>>>>>>  Thanks so much for looking into this. Sorry, I couldn't get to it
>>>>>>
>>>>> earlier
>>>>> due to other concerns. I corrected the mistake you mentioned and I
>>>>> don't
>>>>> get
>>>>> numeric_limit<>::max() for any nodes anymore.
>>>>>
>>>>> I believe the graph/distributed/graphviz.hpp was outputting the
>>>>> distance
>>>>> in
>>>>> correct fashion.
>>>>>
>>>>> Unfortunately, the output is still coming out to be incorrect.
>>>>> It was also the case with output from graphviz.hpp.
>>>>>
>>>>> For the test graph that we mentioned before, essentially
>>>>> 0 --> 1 --> 2 --> 3,
>>>>> 0 --> 4 --> 3
>>>>>
>>>>> the distance output is as follows:
>>>>> global node-id : distance
>>>>> 0 : 0
>>>>> 1 : 1
>>>>> 2 : 2
>>>>> 3 : 1            //(wrong: should be 2)
>>>>> 4 :  0          // should be 1
>>>>>
>>>>> If possible can you send me your version of the code. Let me know if
>>>>> you
>>>>> need mine (the updated version).
>>>>>
>>>>>
>>>>
>>>> Given the description of your problem above, and assuming you're using a
>>>> block distribution with 8 vertices, it sounds like you're initializing
>>>> the
>>>> distance to the first vertex on *each* process to 0, as opposed to only
>>>> the
>>>> distance to the source.  The vertex with global index 4 is actually
>>>> local
>>>> index 0 on process one using the above distribution.  If you initialize
>>>> the
>>>> distances to the vertices with global indices 0 and 4 to 0, then your
>>>> results make sense.  Let me know if that's not the case, but I surmise
>>>> that
>>>> it is.
>>>>
>>>>  Very much so :-). Thanks for getting me started with by catching these
>>>>
>>> minor but fatal mis-understandings with PBFS code. I understood that call
>>> vertex(i,g) creates a descriptor for ith global vertex.
>>>
>>> Also there's a problem in your depth labeling visitor.  In the case of
>>>
>>>> cross-processor edges the process that owns the target of the edge
>>>> doesn't
>>>> necessarily have the distance to the source of the edge available
>>>> locally.
>>>> This will lead to incorrect distance labels even though tree and
>>>> non-tree
>>>> edges will still be correctly recognized since the BFS is
>>>> level-synchronized.  The fastest way to handle this is to modify the BFS
>>>> queue to also pass distance data (which is how the shortest paths
>>>> algorithms
>>>> do it).  You could also send the data separately and probe for it on the
>>>> receiving side.  Check out the distributed betweenness centrality code
>>>> for
>>>> how to create a distributed queue which contains tuples of data one
>>>> element
>>>> of which is a vertex (in order to know where to route the data).
>>>> Integrating this type of vertex queue (i.e. one that contains a data
>>>> payload) with BFS basically just requires handling the data payload on
>>>> the
>>>> receiving side.
>>>>
>>>> I would try this out. So basically the default call
>>>>
>>>
>>> boost::breadth_first_search
>>>    (g, start,
>>> boost::visitor(boost::make_bfs_visitor(boost::record_distances(distance,
>>> boost::on_tree_edge()))));
>>>
>>> wouldn't work.  I assumed that distributed BFS implementation did exactly
>>> what you mentioned.
>>> Although I would write my own, parallel  visitor as well per your
>>> suggestions.
>>>
>>> thanks
>>> Sandeep
>>>
>>>
>>>
>>>  Let me also add that I did modified code that initializes only the
>>>
>> distance to 0th vertex of processor 0. In this case i am facing the
>> dilemma
>> of what should I pass as start vertex for processes > 0. I can't pass the
>> global start vertex (probably the type won't be acceptable to
>> breadth_first_search.
>>
>> I will dig further into the betweeness centrality and dijkstra code to
>> figure this out. Appreciate your input.
>>
>
> The short answer is, just pass the same source vertex on all processors.
>
> Explanation: Each processor will push the source vertex on the distributed
> queue but all the non-local pushes end up being no-ops since the source
> vertex is black at the end of the first BFS level when the messages arrive.
>  The source vertex just has to be graph_traits<Graph>::vertex_descriptor,
> which you can construct using vertex() call if you want to generate it from
> a global vertex index.  The fact that all processors push the source vertex
> is an artifact of reusing the sequential BFS code, it could be changed but I
> haven't found it to be an issue thus far.
>
> This actually brings up an interesting feature of BFS, its possible to
> start a BFS from multiple source vertices by passing a different source on
> each processor (you can also pass a queue containing additional starting
> vertices if you need > num_procs sources).  The strongly connected
> components algorithm uses this approach to run many BFSs on disconnected
> subgraphs in parallel.
>
> One last note on your visitor, my statement was incorrect, sorry.  I was
> looking at some other code and confused it with yours, your depth labeling
> visitor will work fine because it 'pushes' distance labels.  Basically it
> writes the distance to the vertex it pushes onto the queue into the
> distributed property map at the same time (actually immediately before).
>  This means that at the next synchronization step both the distance and the
> vertex descriptor will arrive, in fact the ordering of the messages insures
> that the distance will arrive prior to the vertex on the queue.  Sorry about
> that, I was looking at another visitor that was 'pulling' data, which is
> much more problematic.
>
> Hopefully that solves all your problems and my apologies again on leading
> you to believe there was something wrong with your visitor.
>
> The data model is a little tricky to wrap your head around, but once you've
> written some code it should become more intuitive.
>
>
> Hi Nick,
>

  Thanks for the explanation of the distributed BFS. This is indeed quite
helpful. Especially at later stages.  I haven't gotten to a point to comment
on the data model but the current architecture is swell from what I can
judge.

 I hesitate to ask explanation at every minor detail but I now confused
about passing the same vertex descriptor. Specifically I didn't quite grasp
the statement  "source vertex just has to be
graph_traits<Graph>::vertex_descriptor, which you can construct using
vertex() call if you want to generate it from a global vertex index".
The source vertex has to graph_traits<Graph>::vertex_descriptor which I
takes two arguments the index and the graph --these two parameters can only
identify local vertices. For global vertices we need global descriptors
which also require the owner.

Appreciate your help in clarifying this.

Thanks
Sandeep
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost