00001 #ifndef STEINER_ARBORESCENCE_H
00002 #define STEINER_ARBORESCENCE_H
00003
00004 #include <cstdarg>
00005 #include <boost/foreach.hpp>
00006 #include <boost/graph/adjacency_list.hpp>
00007 #include <boost/graph/adjacency_matrix.hpp>
00008 #include <boost/graph/depth_first_search.hpp>
00009 #include <boost/graph/graph_traits.hpp>
00010 #include <boost/graph/iteration_macros.hpp>
00011 #include <boost/graph/boykov_kolmogorov_max_flow.hpp>
00012 #include <boost/property_map/property_map.hpp>
00013 #include <iostream>
00014 #include <scil/scil.h>
00015
00016 using namespace boost;
00017 using namespace SCIL;
00018
00019 namespace SCIL {
00020
00024 template <typename Graph>
00025 class SteinerArborescence : public sym_constraint {
00026
00027 private:
00028
00029 typedef boost::graph_traits<Graph> GraphTraits;
00030 typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
00031 typedef typename GraphTraits::edge_descriptor edge_descriptor;
00032
00033
00034 typedef map<vertex_descriptor, int> vertex_index_map_t;
00035 typedef map<edge_descriptor, edge_descriptor> rev_edge_map_t;
00036 typedef map<edge_descriptor, int> capacity_map_t;
00037 typedef map<vertex_descriptor, default_color_type> color_map_t;
00038 typedef map<vertex_descriptor, edge_descriptor> predecessor_map_t;
00039 typedef map<vertex_descriptor, int> vdistance_map_t;
00040
00041 class dfs_visitor;
00042
00043 status separation(subproblem& S, bool separate_fast);
00044 int separate_flipped(subproblem& S);
00045
00046 Graph& G;
00047 vertex_descriptor root;
00048 std::list<vertex_descriptor>& terminals;
00049 var_map<edge_descriptor>& VM;
00050
00051 Graph Gmf;
00052 Graph Fmf;
00053 map<edge_descriptor, bool> is_original_edge_Gmf;
00054 map<edge_descriptor, bool> is_original_edge_Fmf;
00055 map<edge_descriptor, edge_descriptor> edges_GmfToG;
00056 map<edge_descriptor, edge_descriptor> edges_FmfToG;
00057 map<vertex_descriptor, vertex_descriptor> vertices_GtoGmf;
00058 map<vertex_descriptor, vertex_descriptor> vertices_GtoFmf;
00059 vertex_index_map_t vertex_index_Gmf;
00060 vertex_index_map_t vertex_index_Fmf;
00061 rev_edge_map_t rev_Gmf;
00062 rev_edge_map_t rev_Fmf;
00063
00064 public:
00066 SteinerArborescence(Graph& G_, vertex_descriptor root_,
00067 std::list<vertex_descriptor>& terminals_,
00068 var_map<edge_descriptor>& VM_);
00069
00070 void init(subproblem& S);
00071
00074 status standard_separation(subproblem& S);
00075
00078 status fast_separation(subproblem& S);
00079
00082 status feasible(solution& S);
00083
00086 void info();
00087
00088 };
00089
00090 }
00091
00092 #include "../../../src/constraints/SteinerArborescence.cc"
00093 #endif
