push_relabel_max_flow.hpp

来自「CGAL is a collaborative effort of severa」· HPP 代码 · 共 743 行 · 第 1/2 页

      //=======================================================================
      // cleanup beyond the gap
      void gap(distance_size_type empty_distance)
      {
        ++gap_count;

        distance_size_type r; // distance of layer before the current layer
        r = empty_distance - 1;

        // Set the distance for the vertices beyond the gap to "infinity".
        for (layer_iterator l = layers.begin() + empty_distance + 1;
             l < layers.begin() + max_distance; ++l) {
          list_iterator i;
          for (i = l->inactive_vertices.begin(); 
               i != l->inactive_vertices.end(); ++i) {
            distance[*i] = n;
            ++gap_node_count;
          }
          l->inactive_vertices.clear();
        }
        max_distance = r;
        max_active = r;
      }

      //=======================================================================
      // This is the core part of the algorithm, "phase one".
      FlowValue maximum_preflow()
      {
        work_since_last_update = 0;

        while (max_active >= min_active) { // "main" loop

          Layer& layer = layers[max_active];
          list_iterator u_iter = layer.active_vertices.begin();

          if (u_iter == layer.active_vertices.end())
            --max_active;
          else {
            vertex_descriptor u = *u_iter;
            remove_from_active_list(u);
            
            discharge(u);

            if (work_since_last_update * global_update_frequency() > nm) {
              global_distance_update();
              work_since_last_update = 0;
            }
          }
        } // while (max_active >= min_active)

        return excess_flow[sink];
      } // maximum_preflow()

      //=======================================================================
      // remove excess flow, the "second phase"
      // This does a DFS on the reverse flow graph of nodes with excess flow.
      // If a cycle is found, cancel it.
      // Return the nodes with excess flow in topological order.
      //
      // Unlike the prefl_to_flow() implementation, we use
      //   "color" instead of "distance" for the DFS labels
      //   "parent" instead of nl_prev for the DFS tree
      //   "topo_next" instead of nl_next for the topological ordering
      void convert_preflow_to_flow()
      {
        vertex_iterator u_iter, u_end;
        out_edge_iterator ai, a_end;

        vertex_descriptor r, restart, u;

        std::vector<vertex_descriptor> parent(n);
        std::vector<vertex_descriptor> topo_next(n);

        vertex_descriptor tos(parent[0]), 
          bos(parent[0]); // bogus initialization, just to avoid warning
        bool bos_null = true;

        // handle self-loops
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
          for (tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai)
            if (target(*ai, g) == *u_iter)
              residual_capacity[*ai] = capacity[*ai];

        // initialize
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          u = *u_iter;
          color[u] = ColorTraits::white();
          parent[u] = u;
          current[u] = out_edges(u, g).first;
        }
        // eliminate flow cycles and topologically order the vertices
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          u = *u_iter;
          if (color[u] == ColorTraits::white() 
              && excess_flow[u] > 0
              && u != src && u != sink ) {
            r = u;
            color[r] = ColorTraits::gray();
            while (1) {
              for (; current[u] != out_edges(u, g).second; ++current[u]) {
                edge_descriptor a = *current[u];
                if (capacity[a] == 0 && is_residual_edge(a)) {
                  vertex_descriptor v = target(a, g);
                  if (color[v] == ColorTraits::white()) {
                    color[v] = ColorTraits::gray();
                    parent[v] = u;
                    u = v;
                    break;
                  } else if (color[v] == ColorTraits::gray()) {
                    // find minimum flow on the cycle
                    FlowValue delta = residual_capacity[a];
                    while (1) {
                      BOOST_USING_STD_MIN();
                      delta = min BOOST_PREVENT_MACRO_SUBSTITUTION(delta, residual_capacity[*current[v]]);
                      if (v == u)
                        break;
                      else
                        v = target(*current[v], g);
                    }
                    // remove delta flow units
                    v = u;
                    while (1) {
                      a = *current[v];
                      residual_capacity[a] -= delta;
                      residual_capacity[reverse_edge[a]] += delta;
                      v = target(a, g);
                      if (v == u)
                        break;
                    }

                    // back-out of DFS to the first saturated edge
                    restart = u;
                    for (v = target(*current[u], g); v != u; v = target(a, g)){
                      a = *current[v];
                      if (color[v] == ColorTraits::white() 
                          || is_saturated(a)) {
                        color[target(*current[v], g)] = ColorTraits::white();
                        if (color[v] != ColorTraits::white())
                          restart = v;
                      }
                    }
                    if (restart != u) {
                      u = restart;
                      ++current[u];
                      break;
                    }
                  } // else if (color[v] == ColorTraits::gray())
                } // if (capacity[a] == 0 ...
              } // for out_edges(u, g)  (though "u" changes during loop)
              
              if (current[u] == out_edges(u, g).second) {
                // scan of i is complete
                color[u] = ColorTraits::black();
                if (u != src) {
                  if (bos_null) {
                    bos = u;
                    bos_null = false;
                    tos = u;
                  } else {
                    topo_next[u] = tos;
                    tos = u;
                  }
                }
                if (u != r) {
                  u = parent[u];
                  ++current[u];
                } else
                  break;
              }
            } // while (1)
          } // if (color[u] == white && excess_flow[u] > 0 & ...)
        } // for all vertices in g

        // return excess flows
        // note that the sink is not on the stack
        if (! bos_null) {
          for (u = tos; u != bos; u = topo_next[u]) {
            ai = out_edges(u, g).first;
            while (excess_flow[u] > 0 && ai != out_edges(u, g).second) {
              if (capacity[*ai] == 0 && is_residual_edge(*ai))
                push_flow(*ai);
              ++ai;
            }
          }
          // do the bottom
          u = bos;
          ai = out_edges(u, g).first;
          while (excess_flow[u] > 0) {
            if (capacity[*ai] == 0 && is_residual_edge(*ai))
              push_flow(*ai);
            ++ai;
          }
        }
        
      } // convert_preflow_to_flow()

      //=======================================================================
      inline bool is_flow()
      {
        vertex_iterator u_iter, u_end;
        out_edge_iterator ai, a_end;

        // check edge flow values
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          for (tie(ai, a_end) = out_edges(*u_iter, g); ai != a_end; ++ai) {
            edge_descriptor a = *ai;
            if (capacity[a] > 0)
              if ((residual_capacity[a] + residual_capacity[reverse_edge[a]]
                   != capacity[a] + capacity[reverse_edge[a]])
                  || (residual_capacity[a] < 0)
                  || (residual_capacity[reverse_edge[a]] < 0))
              return false;
          }
        }
        
        // check conservation
        FlowValue sum;  
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
          vertex_descriptor u = *u_iter;
          if (u != src && u != sink) {
            if (excess_flow[u] != 0)
              return false;
            sum = 0;
            for (tie(ai, a_end) = out_edges(u, g); ai != a_end; ++ai) 
              if (capacity[*ai] > 0)
                sum -= capacity[*ai] - residual_capacity[*ai];
              else
                sum += residual_capacity[*ai];

            if (excess_flow[u] != sum)
              return false;
          }
        }

        return true;
      } // is_flow()

      bool is_optimal() {
        // check if mincut is saturated...
        global_distance_update();
        return distance[src] >= n;
      }

      void print_statistics(std::ostream& os) const {
        os << "pushes:     " << push_count << std::endl
           << "relabels:   " << relabel_count << std::endl
           << "updates:    " << update_count << std::endl
           << "gaps:       " << gap_count << std::endl
           << "gap nodes:  " << gap_node_count << std::endl
           << std::endl;
      }

      void print_flow_values(std::ostream& os) const {
        os << "flow values" << std::endl;
        vertex_iterator u_iter, u_end;
        out_edge_iterator ei, e_end;
        for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
          for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
            if (capacity[*ei] > 0)
              os << *u_iter << " " << target(*ei, g) << " " 
                 << (capacity[*ei] - residual_capacity[*ei]) << std::endl;
        os << std::endl;
      }

      //=======================================================================

      Graph& g;
      vertices_size_type n;
      vertices_size_type nm;
      EdgeCapacityMap capacity;
      vertex_descriptor src;
      vertex_descriptor sink;
      VertexIndexMap index;

      // will need to use random_access_property_map with these
      std::vector< FlowValue > excess_flow;
      std::vector< list_iterator > layer_list_ptr;
      std::vector< out_edge_iterator > current;
      std::vector< distance_size_type > distance;
      std::vector< default_color_type > color;

      // Edge Property Maps that must be interior to the graph
      ReverseEdgeMap reverse_edge;
      ResidualCapacityEdgeMap residual_capacity;

      LayerArray layers;
      distance_size_type max_distance;  // maximal distance
      distance_size_type max_active;    // maximal distance with active node
      distance_size_type min_active;    // minimal distance with active node
      boost::queue<vertex_descriptor> Q;

      // Statistics counters
      long push_count;
      long update_count;
      long relabel_count;
      long gap_count;
      long gap_node_count;

      inline double global_update_frequency() { return 0.5; }
      inline vertices_size_type alpha() { return 6; }
      inline long beta() { return 12; }

      long work_since_last_update;
    };

  } // namespace detail
  
  template <class Graph, 
            class CapacityEdgeMap, class ResidualCapacityEdgeMap,
            class ReverseEdgeMap, class VertexIndexMap>
  typename property_traits<CapacityEdgeMap>::value_type
  push_relabel_max_flow
    (Graph& g, 
     typename graph_traits<Graph>::vertex_descriptor src,
     typename graph_traits<Graph>::vertex_descriptor sink,
     CapacityEdgeMap cap, ResidualCapacityEdgeMap res,
     ReverseEdgeMap rev, VertexIndexMap index_map)
  {
    typedef typename property_traits<CapacityEdgeMap>::value_type FlowValue;
    
    detail::push_relabel<Graph, CapacityEdgeMap, ResidualCapacityEdgeMap, 
      ReverseEdgeMap, VertexIndexMap, FlowValue>
      algo(g, cap, res, rev, src, sink, index_map);
    
    FlowValue flow = algo.maximum_preflow();
    
    algo.convert_preflow_to_flow();
    
    assert(algo.is_flow());
    assert(algo.is_optimal());
    
    return flow;
  } // push_relabel_max_flow()
  
  template <class Graph, class P, class T, class R>
  typename detail::edge_capacity_value<Graph, P, T, R>::type
  push_relabel_max_flow
    (Graph& g, 
     typename graph_traits<Graph>::vertex_descriptor src,
     typename graph_traits<Graph>::vertex_descriptor sink,
     const bgl_named_params<P, T, R>& params)
  {
    return push_relabel_max_flow
      (g, src, sink,
       choose_const_pmap(get_param(params, edge_capacity), g, edge_capacity),
       choose_pmap(get_param(params, edge_residual_capacity), 
                   g, edge_residual_capacity),
       choose_const_pmap(get_param(params, edge_reverse), g, edge_reverse),
       choose_const_pmap(get_param(params, vertex_index), g, vertex_index)
       );
  }

  template <class Graph>
  typename property_traits<
    typename property_map<Graph, edge_capacity_t>::const_type
  >::value_type
  push_relabel_max_flow
    (Graph& g, 
     typename graph_traits<Graph>::vertex_descriptor src,
     typename graph_traits<Graph>::vertex_descriptor sink)
  {
    bgl_named_params<int, buffer_param_t> params(0); // bogus empty param
    return push_relabel_max_flow(g, src, sink, params);
  }

} // namespace boost

#endif // BOOST_PUSH_RELABEL_MAX_FLOW_HPP