File: st_connected.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 (82 lines) | stat: -rw-r--r-- 2,514 bytes parent folder | download | duplicates (17)
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
// Copyright (C) 2006 The Trustees of Indiana University.

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

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
#ifndef BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP
#define BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/two_bit_color_map.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/pending/queue.hpp>

namespace boost { namespace graph {

template<typename Graph, typename ColorMap>
bool 
st_connected(const Graph& g, 
             typename graph_traits<Graph>::vertex_descriptor s,
             typename graph_traits<Graph>::vertex_descriptor t,
             ColorMap color)
{
  typedef typename property_traits<ColorMap>::value_type Color;
  typedef color_traits<Color> ColorTraits;
  typedef typename graph_traits<Graph>::vertex_descriptor Vertex;

  // Set all vertices to white (unvisited)
  BGL_FORALL_VERTICES_T(v, g, Graph)
    put(color, v, ColorTraits::white());

  // Vertices found from the source are grey
  put(color, s, ColorTraits::gray());

  // Vertices found from the target are greeen
  put(color, t, ColorTraits::green());
  queue<Vertex> Q;
  Q.push(s);
  Q.push(t);

  while (!Q.empty()) {
    Vertex u = Q.top(); Q.pop();
    Color u_color = get(color, u);

    BGL_FORALL_OUTEDGES_T(u, e, g, Graph) {
      Vertex v = target(e, g);
      Color v_color = get(color, v);
      if (v_color == ColorTraits::white()) {
        // We have not seen "v" before; mark it with the same color as u
        Color u_color = get(color, u);
        put(color, v, u_color);
        
        // Push it on the queue
        Q.push(v);
      } else if (v_color != ColorTraits::black() && u_color != v_color) {
        // Colors have collided. We're done!
        return true;
      }
    }
    // u is done, so mark it black
    put(color, u, ColorTraits::black());
  }

  return false;
}

template<typename Graph>
inline bool 
st_connected(const Graph& g, 
             typename graph_traits<Graph>::vertex_descriptor s,
             typename graph_traits<Graph>::vertex_descriptor t)
{
  return st_connected(g, s, t, 
                      make_two_bit_color_map(num_vertices(g),
                                             get(vertex_index, g)));
}

} } // end namespace boost::graph

#endif // BOOST_GRAPH_DISTRIBUTED_ST_CONNECTED_HPP