graph_components.hh 5.4 KB
Newer Older
Tiago Peixoto's avatar
Tiago Peixoto committed
1
// Copyright (C) 2008  Tiago de Paula Peixoto <tiago@skewed.de>
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//
// 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 3
// 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, see <http://www.gnu.org/licenses/>.

#ifndef GRAPH_COMPONENTS_HH
#define GRAPH_COMPONENTS_HH

#include <boost/graph/connected_components.hpp>
#include <boost/graph/strong_components.hpp>
21
#include <boost/graph/biconnected_components.hpp>
22

23
24
25
26
27
28
29
30
31
32
33
34
35
namespace graph_tool
{
template <class PropertyMap>
class HistogramPropertyMap;
}

namespace boost
{
template <class PropertyMap>
struct property_traits<HistogramPropertyMap<PropertyMap> >:
        public property_traits<PropertyMap> {};
}

36
37
38
39
40
namespace graph_tool
{
using namespace std;
using namespace boost;

41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// this wraps an existing property map, and makes a simple histogram of the
// values (assumed to be an integer type)

template <class PropertyMap>
class HistogramPropertyMap
{
public:
    typedef typename property_traits<PropertyMap>::value_type value_type;
    typedef typename property_traits<PropertyMap>::key_type key_type;
    typedef typename property_traits<PropertyMap>::category category;

    HistogramPropertyMap(PropertyMap base_map, size_t max, vector<size_t>& hist)
        : _base_map(base_map), _max(max), _hist(hist) {}
    HistogramPropertyMap(){}

    value_type get(const key_type& k) const
    {
        return boost::get(_base_map, k);
    }

    void put(const key_type& k, const value_type& v)
    {
        boost::put(_base_map, k, v);

        vector<size_t>& h = _hist;
66
        size_t bin = v;
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
96
        if (bin > _max)
            return;
        if (bin >= h.size())
            h.resize(bin + 1);
        ++h[bin];
    }

private:
    PropertyMap _base_map;
    size_t _max;
    boost::reference_wrapper<vector<size_t> > _hist;
};

template <class PropertyMap>
typename property_traits<PropertyMap>::value_type
get(const HistogramPropertyMap<PropertyMap>& pmap,
    const typename property_traits<PropertyMap>::key_type& k)
{
    return pmap.get(k);
}

template <class PropertyMap>
void put(HistogramPropertyMap<PropertyMap> pmap,
         const typename property_traits<PropertyMap>::key_type& k,
         const typename property_traits<PropertyMap>::value_type& val)
{
    pmap.put(k, val);
}


97
// this will label the components of a graph to a given vertex property, from
98
99
// [0, number of components - 1], and keep an histogram. If the graph is
// directed the strong components are used.
100
101
102
struct label_components
{
    template <class Graph, class CompMap>
103
104
    void operator()(const Graph& g, CompMap comp_map, vector<size_t>& hist)
        const
105
106
107
    {
        typedef typename graph_traits<Graph>::directed_category
            directed_category;
108
109
        HistogramPropertyMap<CompMap> cm(comp_map, num_vertices(g), hist);
        get_components(g, cm,
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
                       typename is_convertible<directed_category,
                                               directed_tag>::type());
    }

    template <class Graph, class CompMap>
    void get_components(const Graph& g, CompMap comp_map,
                        boost::true_type is_directed) const
    {
        strong_components(g, comp_map);
    }

    template <class Graph, class CompMap>
    void get_components(const Graph& g, CompMap comp_map,
                        boost::false_type is_directed) const
    {
        connected_components(g, comp_map);
    }
};

129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
struct label_biconnected_components
{
    template <class ArtMap>
    class vertex_inserter
    {
    public:
        vertex_inserter(ArtMap art_map): _art_map(art_map) {}

        vertex_inserter& operator++() { return *this; }
        vertex_inserter& operator++(int) { return *this; }
        vertex_inserter& operator*() { return *this; }

        vertex_inserter& operator=
        (const typename property_traits<ArtMap>::key_type& e)
        {
            put(_art_map, e, 1);
            return *this;
        }

    private:
        ArtMap _art_map;
    };

    template <class Graph, class CompMap, class ArtMap>
    void operator()(const Graph& g, CompMap comp_map, ArtMap art_map,
154
                    vector<size_t>& hist) const
155
    {
156
157
        HistogramPropertyMap<CompMap> cm(comp_map, num_edges(g), hist);
        biconnected_components(g, cm,
158
                               vertex_inserter<ArtMap>(art_map));
159
160
161
162
    }
};


163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
struct label_out_component
{
    template <class CompMap>
    class marker_visitor: public bfs_visitor<>
    {
    public:
        marker_visitor() { }
        marker_visitor(CompMap comp) : _comp(comp) { }

        template <class Vertex, class Graph>
        void discover_vertex(Vertex u, const Graph& g)
        {
            _comp[u] = true;
        }
    private:
        CompMap _comp;
    };

    template <class Graph, class CompMap>
    void operator()(const Graph& g, CompMap comp_map, size_t root) const
    {
        marker_visitor<CompMap> marker(comp_map);
        breadth_first_search(g, vertex(root, g), visitor(marker));
    }
};


190
191
192
} // graph_tool namespace

#endif // GRAPH_COMPONENTS_HH