kolmogorov_max_flow_test.cpp

来自「Boost provides free peer-reviewed portab」· C++ 代码 · 共 435 行 · 第 1/2 页

class kolmogorov_test:public detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap>
{

  typedef typename graph_traits<Graph>::edge_descriptor tEdge;
  typedef typename graph_traits<Graph>::vertex_descriptor tVertex;
  typedef typename property_traits< typename property_map<Graph, edge_capacity_t>::const_type>::value_type tEdgeVal;
  typedef typename graph_traits<Graph>::vertex_iterator tVertexIterator;
  typedef typename graph_traits<Graph>::out_edge_iterator tOutEdgeIterator;
  typedef typename property_traits<ColorMap>::value_type tColorValue;
  typedef color_traits<tColorValue> tColorTraits;
  typedef typename property_traits<DistanceMap>::value_type tDistanceVal;  
  typedef typename detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap> tSuper;
  public:
        kolmogorov_test(Graph& g, typename graph_traits<Graph>::vertex_descriptor src, typename graph_traits<Graph>::vertex_descriptor sink):
          detail::kolmogorov<Graph,EdgeCapacityMap,ResidualCapacityEdgeMap,ReverseEdgeMap,PredecessorMap,ColorMap,DistanceMap,IndexMap>
            (g, get(edge_capacity,g), get(edge_residual_capacity,g), get(edge_reverse, g), get(vertex_predecessor, g), get(vertex_color, g),
             get(vertex_distance, g),  get(vertex_index, g), src, sink){
             }

        void invariant_four(tVertex v) const{
          //passive nodes in S or T
          if(v == tSuper::m_source || v == tSuper::m_sink)
            return;
          typename std::list<tVertex>::const_iterator it = find(tSuper::m_orphans.begin(), tSuper::m_orphans.end(), v);
          // a node is active, if its in the active_list AND (is has_a_parent, or its already in the orphans_list or its the sink, or its the source)
          bool is_active = (tSuper::m_in_active_list_map[v] && (has_parent(v) || it != tSuper::m_orphans.end() ));
          if(get_tree(v) != tColorTraits::gray() && !is_active){
            typename graph_traits<Graph>::out_edge_iterator ei,e_end;
            for(tie(ei, e_end) = out_edges(v, tSuper::m_g); ei != e_end; ++ei){
              const tVertex& other_node = target(*ei, tSuper::m_g);
              if(get_tree(other_node) != get_tree(v)){
                if(get_tree(v) == tColorTraits::black())
                  BOOST_CHECK(tSuper::m_res_cap_map[*ei] == 0);
                else
                  BOOST_CHECK(tSuper::m_res_cap_map[tSuper::m_rev_edge_map[*ei]] == 0);
              }
             }
          }
        }

        void invariant_five(const tVertex& v) const{
          BOOST_CHECK(get_tree(v) != tColorTraits::gray() || tSuper::m_time_map[v] <= tSuper::m_time);
        }

        void invariant_six(const tVertex& v) const{
          if(get_tree(v) == tColorTraits::gray() || tSuper::m_time_map[v] != tSuper::m_time)
            return;
          else{
            tVertex current_node = v;
            tDistanceVal distance = 0;
            tColorValue color = get_tree(v);
            tVertex terminal = (color == tColorTraits::black()) ? tSuper::m_source : tSuper::m_sink;
            while(current_node != terminal){
              BOOST_CHECK(tSuper::has_parent(current_node));
              tEdge e = get_edge_to_parent(current_node);
              ++distance;
              current_node = (color == tColorTraits::black())? source(e, tSuper::m_g) : target(e, tSuper::m_g);
              if(distance > tSuper::m_dist_map[v])
                break;
            }
            BOOST_CHECK(distance == tSuper::m_dist_map[v]);
          }
        }

        void invariant_seven(const tVertex& v) const{
          if(get_tree(v) == tColorTraits::gray())
            return;
          else{
            tColorValue color = get_tree(v);
            long time = tSuper::m_time_map[v];
            tVertex current_node = v;
            while(tSuper::has_parent(current_node)){
              tEdge e = get_edge_to_parent(current_node);
              current_node = (color == tColorTraits::black()) ? source(e, tSuper::m_g) : target(e, tSuper::m_g);
              BOOST_CHECK(tSuper::m_time_map[current_node] >= time);
            }
          }
        }//invariant_seven

        void invariant_eight(const tVertex& v) const{
          if(get_tree(v) == tColorTraits::gray())
             return;
          else{
            tColorValue color = get_tree(v);
            long time = tSuper::m_time_map[v];
            tDistanceVal distance = tSuper::m_dist_map[v];
            tVertex current_node = v;
            while(tSuper::has_parent(current_node)){
              tEdge e = get_edge_to_parent(current_node);
              current_node = (color == tColorTraits::black()) ? source(e, tSuper::m_g) : target(e, tSuper::m_g);
              if(tSuper::m_time_map[current_node] == time)
                BOOST_CHECK(tSuper::m_dist_map[current_node] < distance);
            }
          }
        }//invariant_eight

        void check_invariants(){
          tVertexIterator vi, v_end;
          for(tie(vi, v_end) = vertices(tSuper::m_g); vi != v_end; ++vi){
            invariant_four(*vi);
            invariant_five(*vi);
            invariant_six(*vi);
            invariant_seven(*vi);
            invariant_eight(*vi);
          }
        }

        tEdgeVal test(){
          this->add_active_node(this->m_sink);
          this->augment_direct_paths();
          check_invariants();
          //start the main-loop
          while(true){
            bool path_found;
            tEdge connecting_edge;
            tie(connecting_edge, path_found) = this->grow(); //find a path from source to sink
            if(!path_found){
                //we're finished, no more paths were found
              break;
            }
            check_invariants();
            this->m_time++;
            this->augment(connecting_edge); //augment that path
            check_invariants();
            this->adopt(); //rebuild search tree structure
            check_invariants();
          }

          //check if flow is the sum of outgoing edges of src
          tOutEdgeIterator ei, e_end;
          tEdgeVal src_sum = 0; 
          for(tie(ei, e_end) = out_edges(this->m_source, this->m_g); ei != e_end; ++ei){
            src_sum += this->m_cap_map[*ei] - this->m_res_cap_map[*ei];
          }
          BOOST_CHECK(this->m_flow == src_sum);
          //check if flow is the sum of ingoing edges of sink
          tEdgeVal sink_sum = 0;
          for(tie(ei, e_end) = out_edges(this->m_sink, this->m_g); ei != e_end; ++ei){
            tEdge in_edge = this->m_rev_edge_map[*ei];
            sink_sum += this->m_cap_map[in_edge] - this->m_res_cap_map[in_edge];
          }
          BOOST_CHECK(this->m_flow == sink_sum);
          return this->m_flow;
        }
};

long test_algorithms_invariant(int n_verts, int n_edges, std::size_t seed)
{
  typedef adjacency_list_traits<vecS, vecS, directedS> tVectorTraits;
  typedef adjacency_list<vecS, vecS, directedS,
  property<vertex_index_t, long,
  property<vertex_predecessor_t, tVectorTraits::edge_descriptor,
  property<vertex_color_t, default_color_type,
  property<vertex_distance_t, long> > > >,
  property<edge_capacity_t, long,
  property<edge_residual_capacity_t, long,
  property<edge_reverse_t, tVectorTraits::edge_descriptor > > > > tVectorGraph;
  
  tVectorGraph g;
  
  graph_traits<tVectorGraph>::vertex_descriptor src, sink;
  tie(src,sink) = fill_random_max_flow_graph(g, get(edge_capacity,g), get(edge_reverse, g), n_verts, n_edges, seed);

  typedef property_map<tVectorGraph, edge_capacity_t>::type tEdgeCapMap;
  typedef property_map<tVectorGraph, edge_residual_capacity_t>::type tEdgeResCapMap;
  typedef property_map<tVectorGraph, edge_reverse_t>::type tRevEdgeMap;
  typedef property_map<tVectorGraph, vertex_predecessor_t>::type tVertexPredMap;
  typedef property_map<tVectorGraph, vertex_color_t>::type tVertexColorMap;
  typedef property_map<tVectorGraph, vertex_distance_t>::type tDistanceMap;
  typedef property_map<tVectorGraph, vertex_index_t>::type tIndexMap;
  typedef kolmogorov_test<tVectorGraph, tEdgeCapMap, tEdgeResCapMap, tRevEdgeMap, tVertexPredMap, tVertexColorMap, tDistanceMap, tIndexMap> tKolmo;
  tKolmo instance(g, src, sink);
  return instance.test();
}

int test_main(int argc, char* argv[])
{
  int n_verts = 10; 
  int n_edges = 500;
  std::size_t seed = 1;
  
  if (argc > 1) n_verts = lexical_cast<int>(argv[1]);
  if (argc > 2) n_edges = lexical_cast<int>(argv[2]);
  if (argc > 3) seed = lexical_cast<std::size_t>(argv[3]);

  //we need at least 2 vertices to create src and sink in random graphs
  //this case is also caught in kolmogorov_max_flow
  if (n_verts<2)
    n_verts = 2;

  /*
  * below are checks for different calls to kolmogorov_max_flow and different graph-types
  */
  //checks support of vecS storage
  long flow_vecS = test_adjacency_list_vecS(n_verts, n_edges, seed);
  std::cout << "vecS flow: " << flow_vecS << std::endl;
  //checks support of listS storage (especially problems with vertex indices) 
  long flow_listS = test_adjacency_list_listS(n_verts, n_edges, seed);
  std::cout << "listS flow: " << flow_listS << std::endl;
  BOOST_CHECK(flow_vecS == flow_listS);
  //checks bundled properties
  long flow_bundles = test_bundled_properties(n_verts, n_edges, seed);
  std::cout << "bundles flow: " << flow_bundles << std::endl;
  BOOST_CHECK(flow_listS == flow_bundles);
  //checks overloads
  long flow_overloads = test_overloads(n_verts, n_edges, seed);
  std::cout << "overloads flow: " << flow_overloads << std::endl;
  BOOST_CHECK(flow_bundles == flow_overloads);
  /*
  * excessive test version where kolmogorov's algorithm invariants are checked
  */
  long flow_invariants = test_algorithms_invariant(n_verts, n_edges, seed);
  std::cout << "invariants flow: " << flow_invariants << std::endl;
  BOOST_CHECK(flow_overloads == flow_invariants);
  return 0;
}