Re: [Boost-users] Graph problem -- solvable using the Boost graph library ?

From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2005-12-19 14:13:29

>If the graph is acyclic -> it is a tree -> there is 1 and only 1 path
>between any two vertices (consequently, it is both shortest and longest).
>So you might as well perform breadth-first search from a starting vertex to
>get all paths and distances to other vertices. BFS complexity is O(|A|) where
>|A| is the number of edges in the graph.

So, how "zvrba_at_[hidden]" point out absolutly correctly the problem could be solved using BFS 
(in linear time with respect to edges number), with the following visitor

//////////////////code////////////////////
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

using namespace boost;
template < typename DistanceMap > class bfs_distance_visitor : public default_bfs_visitor {
  typedef typename property_traits < DistanceMap >::value_type T;
public:
  bfs_distance_visitor(DistanceMap dmap) : m_distances(dmap) { }
  template <typename vertex_descriptor, typename Graph> void initialize_vertex(vertex_descriptor v, Graph& g)
  {
        m_distances[v] = 0;
  }
  template < typename Edge, typename Graph >
  void tree_edge(Edge e, Graph& g)
  {
    put(m_distances, target(e, g), m_distances[source(e,g)] + get(edge_weight, g, e));
  }
  DistanceMap m_distances;
};

typedef adjacency_list <listS, vecS,  undirectedS, no_property, property<edge_weight_t, double> > graph_t;
typedef	graph_traits<graph_t>::vertex_descriptor	vertex_descriptor_t;

struct ltvertex {
         bool operator()(vertex_descriptor_t v1, vertex_descriptor_t v2) const {
                 return unsigned(v1) < unsigned(v2); 
         }
 };

template <typename TValue> struct	vertex_external_property_map {
        typedef  std::map<vertex_descriptor_t, TValue, ltvertex>	property_map_type;
};

typedef  vertex_external_property_map<double>::property_map_type distance_map_t;

int _tmain(int argc, _TCHAR* argv[])
{
        graph_t	g;
        typedef associative_property_map<distance_map_t>	T;
        T	dmap;
        bfs_distance_visitor<associative_property_map<distance_map_t> >	vis(dmap);
        //Now it would be good to read graph
        breadth_first_search(g, vertex(0, g), visitor(vis));
        return 0;
}
/////////////////////////////////////////////////////////////////////////////
If it doesn't  work then I don't know who wrote it
Ну привет,
--Дима