File: hawick_circuits.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (381 lines) | stat: -rw-r--r-- 13,769 bytes parent folder | download | duplicates (13)
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
45
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
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
154
155
156
157
158
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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
// Copyright Louis Dionne 2013

// 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)

#ifndef BOOST_GRAPH_HAWICK_CIRCUITS_HPP
#define BOOST_GRAPH_HAWICK_CIRCUITS_HPP

#include <algorithm>
#include <boost/assert.hpp>
#include <boost/foreach.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/one_bit_color_map.hpp>
#include <boost/graph/properties.hpp>
#include <boost/move/utility.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/iterator.hpp>
#include <boost/tuple/tuple.hpp> // for boost::tie
#include <boost/type_traits/remove_reference.hpp>
#include <boost/utility/result_of.hpp>
#include <set>
#include <utility> // for std::pair
#include <vector>


namespace boost {
namespace hawick_circuits_detail {
//! @internal Functor returning all the vertices adjacent to a vertex.
struct get_all_adjacent_vertices {
    template <typename Sig>
    struct result;

    template <typename This, typename Vertex, typename Graph>
    struct result<This(Vertex, Graph)> {
    private:
        typedef typename remove_reference<Graph>::type RawGraph;
        typedef graph_traits<RawGraph> Traits;
        typedef typename Traits::adjacency_iterator AdjacencyIterator;

    public:
        typedef std::pair<AdjacencyIterator, AdjacencyIterator> type;
    };

    template <typename Vertex, typename Graph>
    typename result<
        get_all_adjacent_vertices(BOOST_FWD_REF(Vertex), BOOST_FWD_REF(Graph))
    >::type
    operator()(BOOST_FWD_REF(Vertex) v, BOOST_FWD_REF(Graph) g) const {
        return adjacent_vertices(boost::forward<Vertex>(v),
                                 boost::forward<Graph>(g));
    }
};

//! @internal Functor returning a set of the vertices adjacent to a vertex.
struct get_unique_adjacent_vertices {
    template <typename Sig>
    struct result;

    template <typename This, typename Vertex, typename Graph>
    struct result<This(Vertex, Graph)> {
        typedef std::set<typename remove_reference<Vertex>::type> type;
    };

    template <typename Vertex, typename Graph>
    typename result<get_unique_adjacent_vertices(Vertex, Graph const&)>::type
    operator()(Vertex v, Graph const& g) const {
        typedef typename result<
                    get_unique_adjacent_vertices(Vertex, Graph const&)
                >::type Set;
        return Set(adjacent_vertices(v, g).first,
                   adjacent_vertices(v, g).second);
    }
};

//! @internal
//! Return whether a container contains a given value.
//! This is not meant as a general purpose membership testing function; it
//! would have to be more clever about possible optimizations.
template <typename Container, typename Value>
bool contains(Container const& c, Value const& v) {
    return std::find(boost::begin(c), boost::end(c), v) != boost::end(c);
}

/*!
 * @internal
 * Algorithm finding all the cycles starting from a given vertex.
 *
 * The search is only done in the subgraph induced by the starting vertex
 * and the vertices with an index higher than the starting vertex.
 */
template <
    typename Graph,
    typename Visitor,
    typename VertexIndexMap,
    typename Stack,
    typename ClosedMatrix,
    typename GetAdjacentVertices
>
struct hawick_circuits_from {
private:
    typedef graph_traits<Graph> Traits;
    typedef typename Traits::vertex_descriptor Vertex;
    typedef typename Traits::edge_descriptor Edge;
    typedef typename Traits::vertices_size_type VerticesSize;
    typedef typename property_traits<VertexIndexMap>::value_type VertexIndex;

    typedef typename result_of<
                GetAdjacentVertices(Vertex, Graph const&)
            >::type AdjacentVertices;
    typedef typename range_iterator<AdjacentVertices const>::type AdjacencyIterator;

    // The one_bit_color_map starts all white, i.e. not blocked.
    // Since we make that assumption (I looked at the implementation, but
    // I can't find anything that documents this behavior), we're gonna
    // assert it in the constructor.
    typedef one_bit_color_map<VertexIndexMap> BlockedMap;
    typedef typename property_traits<BlockedMap>::value_type BlockedColor;

    static BlockedColor blocked_false_color()
    { return color_traits<BlockedColor>::white(); }

    static BlockedColor blocked_true_color()
    { return color_traits<BlockedColor>::black(); }

    // This is used by the constructor to secure the assumption
    // documented above.
    bool blocked_map_starts_all_unblocked() const {
        BOOST_FOREACH(Vertex v, vertices(graph_))
            if (is_blocked(v))
                return false;
        return true;
    }

    // This is only used in the constructor to make sure the optimization of
    // sharing data structures between iterations does not break the code.
    bool all_closed_rows_are_empty() const {
        BOOST_FOREACH(typename ClosedMatrix::reference row, closed_)
            if (!row.empty())
                return false;
        return true;
    }

public:
    hawick_circuits_from(Graph const& graph, Visitor& visitor,
                         VertexIndexMap const& vim,
                         Stack& stack, ClosedMatrix& closed,
                         VerticesSize n_vertices)
        : graph_(graph), visitor_(visitor), vim_(vim), stack_(stack),
          closed_(closed), blocked_(n_vertices, vim_)
        {
            BOOST_ASSERT(blocked_map_starts_all_unblocked());

            // Since sharing the data structures between iterations is
            // just an optimization, it must always be equivalent to
            // constructing new ones in this constructor.
            BOOST_ASSERT(stack_.empty());
            BOOST_ASSERT(closed_.size() == n_vertices);
            BOOST_ASSERT(all_closed_rows_are_empty());
        }

private:
    //! @internal Return the index of a given vertex.
    VertexIndex index_of(Vertex v) const {
        return get(vim_, v);
    }


    //! @internal Return whether a vertex `v` is closed to a vertex `u`.
    bool is_closed_to(Vertex u, Vertex v) const {
        typedef typename ClosedMatrix::const_reference VertexList;
        VertexList closed_to_u = closed_[index_of(u)];
        return contains(closed_to_u, v);
    }

    //! @internal Close a vertex `v` to a vertex `u`.
    void close_to(Vertex u, Vertex v) {
        BOOST_ASSERT(!is_closed_to(u, v));
        closed_[index_of(u)].push_back(v);
    }


    //! @internal Return whether a given vertex is blocked.
    bool is_blocked(Vertex v) const {
        return get(blocked_, v) == blocked_true_color();
    }

    //! @internal Block a given vertex.
    void block(Vertex v) {
        put(blocked_, v, blocked_true_color());
    }

    //! @internal Unblock a given vertex.
    void unblock(Vertex u) {
        typedef typename ClosedMatrix::reference VertexList;

        put(blocked_, u, blocked_false_color());
        VertexList closed_to_u = closed_[index_of(u)];

        while (!closed_to_u.empty()) {
            Vertex const w = closed_to_u.back();
            closed_to_u.pop_back();
            if (is_blocked(w))
                unblock(w);
        }
        BOOST_ASSERT(closed_to_u.empty());
    }

    //! @internal Main procedure as described in the paper.
    bool circuit(Vertex start, Vertex v) {
        bool found_circuit = false;
        stack_.push_back(v);
        block(v);

        // Cache some values that are used more than once in the function.
        VertexIndex const index_of_start = index_of(start);
        AdjacentVertices const adj_vertices = GetAdjacentVertices()(v, graph_);
        AdjacencyIterator const w_end = boost::end(adj_vertices);

        for (AdjacencyIterator w_it = boost::begin(adj_vertices);
             w_it != w_end;
             ++w_it)
        {
            Vertex const w = *w_it;
            // Since we're only looking in the subgraph induced by `start`
            // and the vertices with an index higher than `start`, we skip
            // any vertex that does not satisfy that.
            if (index_of(w) < index_of_start)
                continue;

            // If the last vertex is equal to `start`, we have a circuit.
            else if (w == start) {
                // const_cast to ensure the visitor does not modify the stack
                visitor_.cycle(const_cast<Stack const&>(stack_), graph_);
                found_circuit = true;
            }

            // If `w` is not blocked, we continue searching further down the
            // same path for a cycle with `w` in it.
            else if (!is_blocked(w) && circuit(start, w))
                found_circuit = true;
        }

        if (found_circuit)
            unblock(v);
        else
            for (AdjacencyIterator w_it = boost::begin(adj_vertices);
                 w_it != w_end;
                 ++w_it)
            {
                Vertex const w = *w_it;
                // Like above, we skip vertices that are not in the subgraph
                // we're considering.
                if (index_of(w) < index_of_start)
                    continue;

                // If `v` is not closed to `w`, we make it so.
                if (!is_closed_to(w, v))
                    close_to(w, v);
            }

        BOOST_ASSERT(v == stack_.back());
        stack_.pop_back();
        return found_circuit;
    }

public:
    void operator()(Vertex start) {
        circuit(start, start);
    }

private:
    Graph const& graph_;
    Visitor& visitor_;
    VertexIndexMap const& vim_;
    Stack& stack_;
    ClosedMatrix& closed_;
    BlockedMap blocked_;
};

template <
    typename GetAdjacentVertices,
    typename Graph, typename Visitor, typename VertexIndexMap
>
void call_hawick_circuits(Graph const& graph,
                          Visitor /* by value */ visitor,
                          VertexIndexMap const& vertex_index_map) {
    typedef graph_traits<Graph> Traits;
    typedef typename Traits::vertex_descriptor Vertex;
    typedef typename Traits::vertices_size_type VerticesSize;
    typedef typename Traits::vertex_iterator VertexIterator;

    typedef std::vector<Vertex> Stack;
    typedef std::vector<std::vector<Vertex> > ClosedMatrix;

    typedef hawick_circuits_from<
                Graph, Visitor, VertexIndexMap, Stack, ClosedMatrix,
                GetAdjacentVertices
            > SubAlgorithm;

    VerticesSize const n_vertices = num_vertices(graph);
    Stack stack; stack.reserve(n_vertices);
    ClosedMatrix closed(n_vertices);

    VertexIterator start, last;
    for (boost::tie(start, last) = vertices(graph); start != last; ++start) {
        // Note1: The sub algorithm may NOT be reused once it has been called.

        // Note2: We reuse the Stack and the ClosedMatrix (after clearing them)
        // in each iteration to avoid redundant destruction and construction.
        // It would be strictly equivalent to have these as member variables
        // of the sub algorithm.
        SubAlgorithm sub_algo(graph, visitor, vertex_index_map,
                              stack, closed, n_vertices);
        sub_algo(*start);
        stack.clear();
        typename ClosedMatrix::iterator row, last_row = closed.end();
        for (row = closed.begin(); row != last_row; ++row)
            row->clear();
    }
}

template <typename GetAdjacentVertices, typename Graph, typename Visitor>
void call_hawick_circuits(Graph const& graph, BOOST_FWD_REF(Visitor) visitor) {
    call_hawick_circuits<GetAdjacentVertices>(
        graph, boost::forward<Visitor>(visitor), get(vertex_index, graph)
    );
}
} // end namespace hawick_circuits_detail

//! Enumerate all the elementary circuits in a directed multigraph.
template <typename Graph, typename Visitor, typename VertexIndexMap>
void hawick_circuits(BOOST_FWD_REF(Graph) graph,
                     BOOST_FWD_REF(Visitor) visitor,
                     BOOST_FWD_REF(VertexIndexMap) vertex_index_map) {
    hawick_circuits_detail::call_hawick_circuits<
        hawick_circuits_detail::get_all_adjacent_vertices
    >(
        boost::forward<Graph>(graph),
        boost::forward<Visitor>(visitor),
        boost::forward<VertexIndexMap>(vertex_index_map)
    );
}

template <typename Graph, typename Visitor>
void hawick_circuits(BOOST_FWD_REF(Graph) graph,
                     BOOST_FWD_REF(Visitor) visitor) {
    hawick_circuits_detail::call_hawick_circuits<
        hawick_circuits_detail::get_all_adjacent_vertices
    >(boost::forward<Graph>(graph), boost::forward<Visitor>(visitor));
}

/*!
 * Same as `boost::hawick_circuits`, but duplicate circuits caused by parallel
 * edges will not be considered. Each circuit will be considered only once.
 */
template <typename Graph, typename Visitor, typename VertexIndexMap>
void hawick_unique_circuits(BOOST_FWD_REF(Graph) graph,
                            BOOST_FWD_REF(Visitor) visitor,
                            BOOST_FWD_REF(VertexIndexMap) vertex_index_map) {
    hawick_circuits_detail::call_hawick_circuits<
        hawick_circuits_detail::get_unique_adjacent_vertices
    >(
        boost::forward<Graph>(graph),
        boost::forward<Visitor>(visitor),
        boost::forward<VertexIndexMap>(vertex_index_map)
    );
}

template <typename Graph, typename Visitor>
void hawick_unique_circuits(BOOST_FWD_REF(Graph) graph,
                            BOOST_FWD_REF(Visitor) visitor) {
    hawick_circuits_detail::call_hawick_circuits<
        hawick_circuits_detail::get_unique_adjacent_vertices
    >(boost::forward<Graph>(graph), boost::forward<Visitor>(visitor));
}
} // end namespace boost

#endif // !BOOST_GRAPH_HAWICK_CIRCUITS_HPP