graph_distance.cc 4.86 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// graph-tool -- a general graph modification and manipulation thingy
//
// Copyright (C) 2006  Tiago de Paula Peixoto <tiago@forked.de>
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version 2
// of the License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

#include <algorithm>
#include <tr1/unordered_set>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/lambda/bind.hpp>
24
#include <iostream>
25
26
27
28
29
30
31
32
33
34
35
36
37

#include "graph.hh"
#include "histogram.hh"
#include "graph_filtering.hh"
#include "graph_selectors.hh"
#include "graph_properties.hh"

using namespace std;
using namespace boost;
using namespace boost::lambda;
using namespace graph_tool;

//==============================================================================
38
39
// GetDistanceHistogram()
// retrieves the vertex-vertex distance histogram
40
41
42
//==============================================================================
struct no_weightS {};

43
struct get_distance_histogram
44
45
{

46
47
    template <class Graph, class IndexMap, class WeightMap, class Hist>
    void operator()(const Graph &g, IndexMap index_map, WeightMap weights, Hist& hist) const
48
    {	
49
	// select get_vertex_dists based on the existence of weights
50
	typedef typename mpl::if_<is_same<WeightMap, no_weightS>,
51
52
53
54
55
56
                     	          get_dists_bfs,
                                  get_dists_djk>::type get_vertex_dists_t;

	get_vertex_dists_t get_vertex_dists;
	typename graph_traits<Graph>::vertex_iterator v, v2, v_end;
	for (tie(v, v_end) = vertices(g); v != v_end; ++v)
57
	{
58
59
60
61
62
63
64
65
66
67
	    typedef tr1::unordered_map<typename graph_traits<Graph>::vertex_descriptor,double,DescriptorHash<IndexMap> > dmap_t;
	    dmap_t dmap(0, DescriptorHash<IndexMap>(index_map));
	    InitializedPropertyMap<dmap_t> dist_map(dmap, numeric_limits<double>::max());

	    dist_map[*v] = 0.0;
	    get_vertex_dists(g, *v, index_map, dist_map, weights);
	    for (v2 = vertices(g).first; v2 != v_end; ++v2)
		if (*v2 != *v && dist_map[*v2] != numeric_limits<double>::max())
		    hist[dist_map[*v2]]++;
	}	
68
69
70
    }

    // weighted version. Use dijkstra_shortest_paths()
71
    struct get_dists_djk
72
73
    {
	template <class Graph, class Vertex, class IndexMap, class DistanceMap, class WeightMap>
74
	void operator()(const Graph& g, Vertex s, IndexMap index_map, DistanceMap dist_map, WeightMap weights) const
75
	{
76
	    dijkstra_shortest_paths(g, s, vertex_index_map(index_map).weight_map(weights).distance_map(dist_map));  
77
78
79
80
	}
    };

    // unweighted version. Use BFS.
81
    struct get_dists_bfs
82
83
    {
	template <class Graph, class Vertex, class IndexMap, class DistanceMap>
84
	void operator()(const Graph& g, Vertex s, IndexMap index_map, DistanceMap dist_map, no_weightS) const
85
	{
86
87
88
89
90
	    typedef tr1::unordered_map<typename graph_traits<Graph>::vertex_descriptor,default_color_type,DescriptorHash<IndexMap> > cmap_t;
	    cmap_t cmap(0, DescriptorHash<IndexMap>(index_map));
	    InitializedPropertyMap<cmap_t> color_map(cmap, color_traits<default_color_type>::white());
	    	    
	    breadth_first_visit(g, s, visitor(make_bfs_visitor(record_distances(dist_map, on_tree_edge()))).color_map(color_map)); 
91
92
93
94
95
96
	}
    };

    
};

97
GraphInterface::hist_t GraphInterface::GetDistanceHistogram(string weight) const
98
{
99
    hist_t hist;
100
101
102

    if (weight == "")
    {
103
	check_filter(*this, bind<void>(get_distance_histogram(), _1, _vertex_index, no_weightS(), var(hist)),
104
105
106
107
108
109
110
111
112
113
114
		     reverse_check(), directed_check()); 
    }
    else
    {
	try 
	{
	    dynamic_property_map& weight_prop = find_property_map(_properties, weight, typeid(graph_traits<multigraph_t>::edge_descriptor));
	    try 
	    {
		vector_property_map<double, edge_index_map_t> weight_map;
		weight_map = get_static_property_map<vector_property_map<double, edge_index_map_t> >(weight_prop);
115
		check_filter(*this, bind<void>(get_distance_histogram(), _1, _vertex_index, weight_map, var(hist)),
116
117
118
119
120
			     reverse_check(), directed_check()); 
	    }
	    catch (bad_cast)
	    {
		DynamicPropertyMapWrap<double, graph_traits<multigraph_t>::edge_descriptor> weight_map(weight_prop);
121
		check_filter(*this, bind<void>(get_distance_histogram(), _1, _vertex_index, weight_map, var(hist)),
122
123
124
125
126
127
128
129
			     reverse_check(), directed_check()); 
	    }
	}
	catch (property_not_found& e)
	{
	    throw GraphException("error getting scalar property: " + string(e.what()));
	}
    }
130
    return hist;
131
}