File: tiernan_all_cycles.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 (376 lines) | stat: -rw-r--r-- 12,811 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
// (C) Copyright 2007-2009 Andrew Sutton
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

#ifndef BOOST_GRAPH_CYCLE_HPP
#define BOOST_GRAPH_CYCLE_HPP

#include <vector>

#include <boost/config.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
#include <boost/concept/assert.hpp>

#include <boost/concept/detail/concept_def.hpp>
namespace boost {
    namespace concepts {
        BOOST_concept(CycleVisitor,(Visitor)(Path)(Graph))
        {
            BOOST_CONCEPT_USAGE(CycleVisitor)
            {
                vis.cycle(p, g);
            }
        private:
            Visitor vis;
            Graph g;
            Path p;
        };
    } /* namespace concepts */
using concepts::CycleVisitorConcept;
} /* namespace boost */
#include <boost/concept/detail/concept_undef.hpp>


namespace boost
{

// The implementation of this algorithm is a reproduction of the Teirnan
// approach for directed graphs: bibtex follows
//
//     @article{362819,
//         author = {James C. Tiernan},
//         title = {An efficient search algorithm to find the elementary circuits of a graph},
//         journal = {Commun. ACM},
//         volume = {13},
//         number = {12},
//         year = {1970},
//         issn = {0001-0782},
//         pages = {722--726},
//         doi = {http://doi.acm.org/10.1145/362814.362819},
//             publisher = {ACM Press},
//             address = {New York, NY, USA},
//         }
//
// It should be pointed out that the author does not provide a complete analysis for
// either time or space. This is in part, due to the fact that it's a fairly input
// sensitive problem related to the density and construction of the graph, not just
// its size.
//
// I've also taken some liberties with the interpretation of the algorithm - I've
// basically modernized it to use real data structures (no more arrays and matrices).
// Oh... and there's explicit control structures - not just gotos.
//
// The problem is definitely NP-complete, an unbounded implementation of this
// will probably run for quite a while on a large graph. The conclusions
// of this paper also reference a Paton algorithm for undirected graphs as being
// much more efficient (apparently based on spanning trees). Although not implemented,
// it can be found here:
//
//     @article{363232,
//         author = {Keith Paton},
//         title = {An algorithm for finding a fundamental set of cycles of a graph},
//         journal = {Commun. ACM},
//         volume = {12},
//         number = {9},
//         year = {1969},
//         issn = {0001-0782},
//         pages = {514--518},
//         doi = {http://doi.acm.org/10.1145/363219.363232},
//             publisher = {ACM Press},
//             address = {New York, NY, USA},
//         }

/**
 * The default cycle visitor provides an empty visit function for cycle
 * visitors.
 */
struct cycle_visitor
{
    template <typename Path, typename Graph>
    inline void cycle(const Path& p, const Graph& g)
    { }
};

/**
 * The min_max_cycle_visitor simultaneously records the minimum and maximum
 * cycles in a graph.
 */
struct min_max_cycle_visitor
{
    min_max_cycle_visitor(std::size_t& min_, std::size_t& max_)
        : minimum(min_), maximum(max_)
    { }

    template <typename Path, typename Graph>
    inline void cycle(const Path& p, const Graph& g)
    {
        BOOST_USING_STD_MIN();
        BOOST_USING_STD_MAX();
        std::size_t len = p.size();
        minimum = min BOOST_PREVENT_MACRO_SUBSTITUTION (minimum, len);
        maximum = max BOOST_PREVENT_MACRO_SUBSTITUTION (maximum, len);
    }
    std::size_t& minimum;
    std::size_t& maximum;
};

inline min_max_cycle_visitor
find_min_max_cycle(std::size_t& min_, std::size_t& max_)
{ return min_max_cycle_visitor(min_, max_); }

namespace detail
{
    template <typename Graph, typename Path>
    inline bool
    is_vertex_in_path(const Graph&,
                        typename graph_traits<Graph>::vertex_descriptor v,
                        const Path& p)
    {
        return (std::find(p.begin(), p.end(), v) != p.end());
    }

    template <typename Graph, typename ClosedMatrix>
    inline bool
    is_path_closed(const Graph& g,
                    typename graph_traits<Graph>::vertex_descriptor u,
                    typename graph_traits<Graph>::vertex_descriptor v,
                    const ClosedMatrix& closed)
    {
        // the path from u to v is closed if v can be found in the list
        // of closed vertices associated with u.
        typedef typename ClosedMatrix::const_reference Row;
        Row r = closed[get(vertex_index, g, u)];
        if(find(r.begin(), r.end(), v) != r.end()) {
            return true;
        }
        return false;
    }

    template <typename Graph, typename Path, typename ClosedMatrix>
    inline bool
    can_extend_path(const Graph& g,
                    typename graph_traits<Graph>::edge_descriptor e,
                    const Path& p,
                    const ClosedMatrix& m)
    {
        BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
        BOOST_CONCEPT_ASSERT(( VertexIndexGraphConcept<Graph> ));
        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

        // get the vertices in question
        Vertex
            u = source(e, g),
            v = target(e, g);

        // conditions for allowing a traversal along this edge are:
        // 1. the index of v must be greater than that at which the
        //    path is rooted (p.front()).
        // 2. the vertex v cannot already be in the path
        // 3. the vertex v cannot be closed to the vertex u

        bool indices = get(vertex_index, g, p.front()) < get(vertex_index, g, v);
        bool path = !is_vertex_in_path(g, v, p);
        bool closed = !is_path_closed(g, u, v, m);
        return indices && path && closed;
    }

    template <typename Graph, typename Path>
    inline bool
    can_wrap_path(const Graph& g, const Path& p)
    {
        BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
        typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;

        // iterate over the out-edges of the back, looking for the
        // front of the path. also, we can't travel along the same
        // edge that we did on the way here, but we don't quite have the
        // stringent requirements that we do in can_extend_path().
        Vertex
            u = p.back(),
            v = p.front();
        OutIterator i, end;
        for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) {
            if((target(*i, g) == v)) {
                return true;
            }
        }
        return false;
    }

    template <typename Graph,
        typename Path,
        typename ClosedMatrix>
    inline typename graph_traits<Graph>::vertex_descriptor
    extend_path(const Graph& g,
                Path& p,
                ClosedMatrix& closed)
    {
        BOOST_CONCEPT_ASSERT(( IncidenceGraphConcept<Graph> ));
        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
        typedef typename graph_traits<Graph>::out_edge_iterator OutIterator;

        // get the current vertex
        Vertex u = p.back();
        Vertex ret = graph_traits<Graph>::null_vertex();

        // AdjacencyIterator i, end;
        OutIterator i, end;
        for(boost::tie(i, end) = out_edges(u, g); i != end; ++i) {
            Vertex v = target(*i, g);

            // if we can actually extend along this edge,
            // then that's what we want to do
            if(can_extend_path(g, *i, p, closed)) {
                p.push_back(v);         // add the vertex to the path
                ret = v;
                break;
            }
        }
        return ret;
    }

    template <typename Graph, typename Path, typename ClosedMatrix>
    inline bool
    exhaust_paths(const Graph& g, Path& p, ClosedMatrix& closed)
    {
        BOOST_CONCEPT_ASSERT(( GraphConcept<Graph> ));
        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

        // if there's more than one vertex in the path, this closes
        // of some possible routes and returns true. otherwise, if there's
        // only one vertex left, the vertex has been used up
        if(p.size() > 1) {
            // get the last and second to last vertices, popping the last
            // vertex off the path
            Vertex last, prev;
            last = p.back();
            p.pop_back();
            prev = p.back();

            // reset the closure for the last vertex of the path and
            // indicate that the last vertex in p is now closed to
            // the next-to-last vertex in p
            closed[get(vertex_index, g, last)].clear();
            closed[get(vertex_index, g, prev)].push_back(last);
            return true;
        }
        else {
            return false;
        }
    }

    template <typename Graph, typename Visitor>
    inline void
    all_cycles_from_vertex(const Graph& g,
                            typename graph_traits<Graph>::vertex_descriptor v,
                            Visitor vis,
                            std::size_t minlen,
                            std::size_t maxlen)
    {
        BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
        typedef std::vector<Vertex> Path;
        BOOST_CONCEPT_ASSERT(( CycleVisitorConcept<Visitor,Path,Graph> ));
        typedef std::vector<Vertex> VertexList;
        typedef std::vector<VertexList> ClosedMatrix;

        Path p;
        ClosedMatrix closed(num_vertices(g), VertexList());
        Vertex null = graph_traits<Graph>::null_vertex();

        // each path investigation starts at the ith vertex
        p.push_back(v);

        while(1) {
            // extend the path until we've reached the end or the
            // maxlen-sized cycle
            Vertex j = null;
            while(((j = detail::extend_path(g, p, closed)) != null)
                    && (p.size() < maxlen))
                ; // empty loop

            // if we're done extending the path and there's an edge
            // connecting the back to the front, then we should have
            // a cycle.
            if(detail::can_wrap_path(g, p) && p.size() >= minlen) {
                vis.cycle(p, g);
            }

            if(!detail::exhaust_paths(g, p, closed)) {
                break;
            }
        }
    }

    // Select the minimum allowable length of a cycle based on the directedness
    // of the graph - 2 for directed, 3 for undirected.
    template <typename D> struct min_cycles { enum { value = 2 }; };
    template <> struct min_cycles<undirected_tag> { enum { value = 3 }; };
} /* namespace detail */

template <typename Graph, typename Visitor>
inline void
tiernan_all_cycles(const Graph& g,
                    Visitor vis,
                    std::size_t minlen,
                    std::size_t maxlen)
{
    BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
    typedef typename graph_traits<Graph>::vertex_iterator VertexIterator;

    VertexIterator i, end;
    for(boost::tie(i, end) = vertices(g); i != end; ++i) {
        detail::all_cycles_from_vertex(g, *i, vis, minlen, maxlen);
    }
}

template <typename Graph, typename Visitor>
inline void
tiernan_all_cycles(const Graph& g, Visitor vis, std::size_t maxlen)
{
    typedef typename graph_traits<Graph>::directed_category Dir;
    tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value, maxlen);
}

template <typename Graph, typename Visitor>
inline void
tiernan_all_cycles(const Graph& g, Visitor vis)
{
    typedef typename graph_traits<Graph>::directed_category Dir;
    tiernan_all_cycles(g, vis, detail::min_cycles<Dir>::value,
                       (std::numeric_limits<std::size_t>::max)());
}

template <typename Graph>
inline std::pair<std::size_t, std::size_t>
tiernan_girth_and_circumference(const Graph& g)
{
    std::size_t
        min_ = (std::numeric_limits<std::size_t>::max)(),
        max_ = 0;
    tiernan_all_cycles(g, find_min_max_cycle(min_, max_));

    // if this is the case, the graph is acyclic...
    if(max_ == 0) max_ = min_;

    return std::make_pair(min_, max_);
}

template <typename Graph>
inline std::size_t
tiernan_girth(const Graph& g)
{ return tiernan_girth_and_circumference(g).first; }

template <typename Graph>
inline std::size_t
tiernan_circumference(const Graph& g)
{ return tiernan_girth_and_circumference(g).second; }

} /* namespace boost */

#endif