File: bipartite.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-- 12,960 bytes parent folder | download | duplicates (10)
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 (c) 2010 Matthias Walter (xammy@xammy.homelinux.net)
 *
 * Authors: Matthias Walter
 *
 * Distributed under 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_BIPARTITE_HPP
#define BOOST_GRAPH_BIPARTITE_HPP

#include <utility>
#include <vector>
#include <exception>
#include <boost/graph/properties.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/one_bit_color_map.hpp>
#include <boost/bind.hpp>

namespace boost {

  namespace detail {

    /**
     * The bipartite_visitor_error is thrown if an edge cannot be colored.
     * The witnesses are the edges incident vertices.
     */

    template <typename Vertex>
    struct bipartite_visitor_error: std::exception
    {
      std::pair <Vertex, Vertex> witnesses;

      bipartite_visitor_error (Vertex a, Vertex b) :
        witnesses (a, b)
      {

      }

      const char* what () const throw ()
      {
        return "Graph is not bipartite.";
      }
    };

    /**
     * Functor which colors edges to be non-monochromatic.
     */

    template <typename PartitionMap>
    struct bipartition_colorize
    {
      typedef on_tree_edge event_filter;

      bipartition_colorize (PartitionMap partition_map) :
        partition_map_ (partition_map)
      {

      }

      template <typename Edge, typename Graph>
      void operator() (Edge e, const Graph& g)
      {
        typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
        typedef color_traits <typename property_traits <PartitionMap>::value_type> color_traits;

        vertex_descriptor_t source_vertex = source (e, g);
        vertex_descriptor_t target_vertex = target (e, g);
        if (get (partition_map_, source_vertex) == color_traits::white ())
          put (partition_map_, target_vertex, color_traits::black ());
        else
          put (partition_map_, target_vertex, color_traits::white ());
      }

    private:
      PartitionMap partition_map_;
    };

    /**
     * Creates a bipartition_colorize functor which colors edges
     * to be non-monochromatic.
     *
     * @param partition_map Color map for the bipartition
     * @return The functor.
     */

    template <typename PartitionMap>
    inline bipartition_colorize <PartitionMap> colorize_bipartition (PartitionMap partition_map)
    {
      return bipartition_colorize <PartitionMap> (partition_map);
    }

    /**
     * Functor which tests an edge to be monochromatic.
     */

    template <typename PartitionMap>
    struct bipartition_check
    {
      typedef on_back_edge event_filter;

      bipartition_check (PartitionMap partition_map) :
        partition_map_ (partition_map)
      {

      }

      template <typename Edge, typename Graph>
      void operator() (Edge e, const Graph& g)
      {
        typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;

        vertex_descriptor_t source_vertex = source (e, g);
        vertex_descriptor_t target_vertex = target (e, g);
        if (get (partition_map_, source_vertex) == get (partition_map_, target_vertex))
          throw bipartite_visitor_error <vertex_descriptor_t> (source_vertex, target_vertex);
      }

    private:
      PartitionMap partition_map_;
    };

    /**
     * Creates a bipartition_check functor which raises an error if a
     * monochromatic edge is found.
     *
     * @param partition_map The map for a bipartition.
     * @return The functor.
     */

    template <typename PartitionMap>
    inline bipartition_check <PartitionMap> check_bipartition (PartitionMap partition_map)
    {
      return bipartition_check <PartitionMap> (partition_map);
    }

    /**
     * Find the beginning of a common suffix of two sequences
     * 
     * @param sequence1 Pair of bidirectional iterators defining the first sequence.
     * @param sequence2 Pair of bidirectional iterators defining the second sequence.
     * @return Pair of iterators pointing to the beginning of the common suffix.
     */

    template <typename BiDirectionalIterator1, typename BiDirectionalIterator2>
    inline std::pair <BiDirectionalIterator1, BiDirectionalIterator2> reverse_mismatch (std::pair <
        BiDirectionalIterator1, BiDirectionalIterator1> sequence1, std::pair <BiDirectionalIterator2,
        BiDirectionalIterator2> sequence2)
    {
      if (sequence1.first == sequence1.second || sequence2.first == sequence2.second)
        return std::make_pair (sequence1.first, sequence2.first);

      BiDirectionalIterator1 iter1 = sequence1.second;
      BiDirectionalIterator2 iter2 = sequence2.second;

      while (true)
      {
        --iter1;
        --iter2;
        if (*iter1 != *iter2)
        {
          ++iter1;
          ++iter2;
          break;
        }
        if (iter1 == sequence1.first)
          break;
        if (iter2 == sequence2.first)
          break;
      }

      return std::make_pair (iter1, iter2);
    }

  }

  /**
   * Checks a given graph for bipartiteness and fills the given color map with
   * white and black according to the bipartition. If the graph is not
   * bipartite, the contents of the color map are undefined. Runs in linear
   * time in the size of the graph, if access to the property maps is in
   * constant time.
   *
   * @param graph The given graph.
   * @param index_map An index map associating vertices with an index.
   * @param partition_map A color map to fill with the bipartition.
   * @return true if and only if the given graph is bipartite.
   */

  template <typename Graph, typename IndexMap, typename PartitionMap>
  bool is_bipartite (const Graph& graph, const IndexMap index_map, PartitionMap partition_map)
  {
    /// General types and variables
    typedef typename property_traits <PartitionMap>::value_type partition_color_t;
    typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;

    /// Declare dfs visitor
    //    detail::empty_recorder recorder;
    //    typedef detail::bipartite_visitor <PartitionMap, detail::empty_recorder> dfs_visitor_t;
    //    dfs_visitor_t dfs_visitor (partition_map, recorder);


    /// Call dfs
    try
    {
      depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair (
          detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map),
              put_property (partition_map, color_traits <partition_color_t>::white (), on_start_vertex ()))))));
    }
    catch (detail::bipartite_visitor_error <vertex_descriptor_t> error)
    {
      return false;
    }

    return true;
  }

  /**
   * Checks a given graph for bipartiteness.
   *
   * @param graph The given graph.
   * @param index_map An index map associating vertices with an index.
   * @return true if and only if the given graph is bipartite.
   */

  template <typename Graph, typename IndexMap>
  bool is_bipartite (const Graph& graph, const IndexMap index_map)
  {
    typedef one_bit_color_map <IndexMap> partition_map_t;
    partition_map_t partition_map (num_vertices (graph), index_map);

    return is_bipartite (graph, index_map, partition_map);
  }

  /**
   * Checks a given graph for bipartiteness. The graph must
   * have an internal vertex_index property. Runs in linear time in the
   * size of the graph, if access to the property maps is in constant time.
   *
   * @param graph The given graph.
   * @return true if and only if the given graph is bipartite.
   */

  template <typename Graph>
  bool is_bipartite (const Graph& graph)
  {
    return is_bipartite (graph, get (vertex_index, graph));
  }

  /**
   * Checks a given graph for bipartiteness and fills a given color map with
   * white and black according to the bipartition. If the graph is not
   * bipartite, a sequence of vertices, producing an odd-cycle, is written to
   * the output iterator. The final iterator value is returned. Runs in linear
   * time in the size of the graph, if access to the property maps is in
   * constant time.
   *
   * @param graph The given graph.
   * @param index_map An index map associating vertices with an index.
   * @param partition_map A color map to fill with the bipartition.
   * @param result An iterator to write the odd-cycle vertices to.
   * @return The final iterator value after writing.
   */

  template <typename Graph, typename IndexMap, typename PartitionMap, typename OutputIterator>
  OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, PartitionMap partition_map,
      OutputIterator result)
  {
    /// General types and variables
    typedef typename property_traits <PartitionMap>::value_type partition_color_t;
    typedef typename graph_traits <Graph>::vertex_descriptor vertex_descriptor_t;
    typedef typename graph_traits <Graph>::vertex_iterator vertex_iterator_t;
    vertex_iterator_t vertex_iter, vertex_end;

    /// Declare predecessor map
    typedef std::vector <vertex_descriptor_t> predecessors_t;
    typedef iterator_property_map <typename predecessors_t::iterator, IndexMap, vertex_descriptor_t,
        vertex_descriptor_t&> predecessor_map_t;

    predecessors_t predecessors (num_vertices (graph), graph_traits <Graph>::null_vertex ());
    predecessor_map_t predecessor_map (predecessors.begin (), index_map);

    /// Initialize predecessor map
    for (boost::tie (vertex_iter, vertex_end) = vertices (graph); vertex_iter != vertex_end; ++vertex_iter)
    {
      put (predecessor_map, *vertex_iter, *vertex_iter);
    }

    /// Call dfs
    try
    {
      depth_first_search (graph, vertex_index_map (index_map).visitor (make_dfs_visitor (std::make_pair (
          detail::colorize_bipartition (partition_map), std::make_pair (detail::check_bipartition (partition_map),
              std::make_pair (put_property (partition_map, color_traits <partition_color_t>::white (),
                  on_start_vertex ()), record_predecessors (predecessor_map, on_tree_edge ())))))));
    }
    catch (detail::bipartite_visitor_error <vertex_descriptor_t> error)
    {
      typedef std::vector <vertex_descriptor_t> path_t;

      path_t path1, path2;
      vertex_descriptor_t next, current;

      /// First path
      next = error.witnesses.first;
      do
      {
        current = next;
        path1.push_back (current);
        next = predecessor_map[current];
      }
      while (current != next);

      /// Second path
      next = error.witnesses.second;
      do
      {
        current = next;
        path2.push_back (current);
        next = predecessor_map[current];
      }
      while (current != next);

      /// Find beginning of common suffix
      std::pair <typename path_t::iterator, typename path_t::iterator> mismatch = detail::reverse_mismatch (
          std::make_pair (path1.begin (), path1.end ()), std::make_pair (path2.begin (), path2.end ()));

      /// Copy the odd-length cycle
      result = std::copy (path1.begin (), mismatch.first + 1, result);
      return std::reverse_copy (path2.begin (), mismatch.second, result);
    }

    return result;
  }

  /**
   * Checks a given graph for bipartiteness. If the graph is not bipartite, a
   * sequence of vertices, producing an odd-cycle, is written to the output
   * iterator. The final iterator value is returned. Runs in linear time in the
   * size of the graph, if access to the property maps is in constant time.
   *
   * @param graph The given graph.
   * @param index_map An index map associating vertices with an index.
   * @param result An iterator to write the odd-cycle vertices to.
   * @return The final iterator value after writing.
   */

  template <typename Graph, typename IndexMap, typename OutputIterator>
  OutputIterator find_odd_cycle (const Graph& graph, const IndexMap index_map, OutputIterator result)
  {
    typedef one_bit_color_map <IndexMap> partition_map_t;
    partition_map_t partition_map (num_vertices (graph), index_map);

    return find_odd_cycle (graph, index_map, partition_map, result);
  }

  /**
   * Checks a given graph for bipartiteness. If the graph is not bipartite, a
   * sequence of vertices, producing an odd-cycle, is written to the output
   * iterator. The final iterator value is returned. The graph must have an
   * internal vertex_index property. Runs in linear time in the size of the
   * graph, if access to the property maps is in constant time.
   *
   * @param graph The given graph.
   * @param result An iterator to write the odd-cycle vertices to.
   * @return The final iterator value after writing.
   */

  template <typename Graph, typename OutputIterator>
  OutputIterator find_odd_cycle (const Graph& graph, OutputIterator result)
  {
    return find_odd_cycle (graph, get (vertex_index, graph), result);
  }
}

#endif /// BOOST_GRAPH_BIPARTITE_HPP