graph_extended_clustering.cc 5.92 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
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 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.

// based on code written by Alexandre Hannud Abdo <abdo@member.fsf.org>

#include <algorithm>
#include <tr1/unordered_set>
#include <boost/lambda/bind.hpp>
#include <boost/graph/breadth_first_search.hpp>

#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;


// filters out a single vertex
template <class Vertex>
struct single_vertex_filter 
{
    single_vertex_filter() {}
    single_vertex_filter(Vertex v):_v(v) {}

45
    bool operator()(Vertex v) const { return v != _v; }
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

    Vertex _v;
};

class bfs_stop_exception {};

// this will abort the BFS search when no longer useful

template <class TargetSet, class DistanceMap>
struct bfs_max_depth_watcher 
{
    typedef on_tree_edge event_filter;

    bfs_max_depth_watcher(TargetSet& targets, size_t max_depth, DistanceMap distance)
	: _targets(targets), _max_depth(max_depth), _distance(distance) {}
    
    template <class Graph>
    void operator()(typename graph_traits<Graph>::edge_descriptor e, const Graph& g) 
    {
	typename graph_traits<Graph>::vertex_descriptor v = target(e,g);
	if (get(_distance, v) > _max_depth)
	    throw bfs_stop_exception();
	if (_targets.find(v) != _targets.end())
	    _targets.erase(v);
	if (_targets.empty())
	    throw bfs_stop_exception();
    }
    
    TargetSet& _targets;
    size_t _max_depth;
    DistanceMap _distance;
};


struct get_extended_clustering
{
    template <class Graph, class IndexMap, class ClusteringMap>
    void operator()(Graph& g, IndexMap vertex_index, vector<ClusteringMap>& cmaps) const
    {	
	typename graph_traits<Graph>::vertex_iterator v, v_end;
	for (tie(v,v_end) = vertices(g); v != v_end; ++v) 
	{	    
	    // We must disconsider paths through the original vertex
	    typedef single_vertex_filter<typename graph_traits<Graph>::vertex_descriptor> filter_t;
	    typedef filtered_graph<Graph, keep_all, filter_t> fg_t;
	    fg_t fg(g, keep_all(), filter_t(*v));

	    typedef DescriptorHash<IndexMap> hasher_t;
	    typedef tr1::unordered_set<typename graph_traits<Graph>::vertex_descriptor,hasher_t> neighbour_set_t;
	    neighbour_set_t neighbours(0, hasher_t(vertex_index));
96
97
	    neighbour_set_t neighbours2(0, hasher_t(vertex_index));
	    neighbour_set_t targets(0, hasher_t(vertex_index));
98
	    
99
	    // collect the targets
100
101
102
	    typename graph_traits<Graph>::adjacency_iterator a, a_end;
	    for(tie(a, a_end) = adjacent_vertices(*v, g); a != a_end; ++a)
		if (*a != *v) // no self-loops
103
104
		    targets.insert(*a);
	    size_t k = targets.size();
105
106
107
108

	    // And now we setup and start the BFS bonanza
	    for(tie(a, a_end) = adjacent_vertices(*v, g); a != a_end; ++a)
	    {
109
110
111
112
		if (neighbours.find(*a) != neighbours.end()) // avoid parallel edges
		    continue;
		neighbours.insert(*a);

113
114
115
116
117
118
119
120
121
122
		typedef tr1::unordered_map<typename graph_traits<Graph>::vertex_descriptor,size_t,DescriptorHash<IndexMap> > dmap_t;
		dmap_t dmap(0, DescriptorHash<IndexMap>(vertex_index));
		InitializedPropertyMap<dmap_t> distance_map(dmap, numeric_limits<size_t>::max());

		typedef tr1::unordered_map<typename graph_traits<Graph>::vertex_descriptor,default_color_type,DescriptorHash<IndexMap> > cmap_t;
		cmap_t cmap(0, DescriptorHash<IndexMap>(vertex_index));
		InitializedPropertyMap<cmap_t> color_map(cmap, color_traits<default_color_type>::white());
		
		try
		{
123
		    distance_map[*a] = 0;
124
125
126
		    neighbour_set_t specific_targets = targets;
		    specific_targets.erase(*a);
		    bfs_max_depth_watcher<neighbour_set_t,InitializedPropertyMap<dmap_t> > watcher(specific_targets, cmaps.size(), distance_map);
127
128
129
130
131
		    breadth_first_visit(fg, *a, visitor(make_bfs_visitor(make_pair(record_distances(distance_map, boost::on_tree_edge()),watcher))).
					color_map(color_map));
		}
		catch(bfs_stop_exception) {}

132
		neighbours2.clear();
133
134
135
		typename graph_traits<Graph>::adjacency_iterator a2;
		for(a2 = adjacent_vertices(*v, g).first ; a2 != a_end ; ++a2) 
		{
136
		    if (*a2 == *v || *a2 == *a) // no self-loops
137
			continue;
138
139
140
		    if (neighbours2.find(*a2) != neighbours2.end()) // avoid parallel edges
			continue;
		    neighbours2.insert(*a2);
141
142
		    if (distance_map[*a2] <= cmaps.size())
			cmaps[distance_map[*a2]-1][*v] += 1.0/(k*(k-1));
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
		}
	    }
	}
    }
};


void GraphInterface::SetExtendedClusteringToProperty(string property_prefix, size_t max_depth)
{
    typedef HashedDescriptorMap<vertex_index_map_t,double> cmap_t;
    vector<cmap_t> cmaps(max_depth);
    for (size_t i = 0; i < cmaps.size(); ++i)
	cmaps[i] = cmap_t(_vertex_index);

    bool directed = _directed;
    _directed = false;
    check_filter(*this, bind<void>(get_extended_clustering(), _1, _vertex_index, var(cmaps)), reverse_check(), always_undirected()); 
    _directed = directed;

    for (size_t i = 0; i < cmaps.size(); ++i)
    {
	string name = property_prefix + lexical_cast<string>(i);
	try
	{
	    find_property_map(_properties, name, typeid(graph_traits<multigraph_t>::vertex_descriptor));
	    RemoveVertexProperty(name);
	}
	catch (property_not_found) {}

	_properties.property(name, cmaps[i]);
    }
}