00001 #ifndef SPAN_TREE_H
00002 #define SPAN_TREE_H
00003
00004 #include<scil/scil.h>
00005 #include<LEDA/graph.h>
00006
00022 namespace SCIL {
00023
00024 class SpanTree : public sym_constraint {
00025 private:
00026 LEDA::graph& G;
00027 scil_map<LEDA::edge>& VM;
00028 LEDA::graph H;
00029 LEDA::node_array<LEDA::node> GtoH;
00030 LEDA::edge_array<int> Cap;
00031 LEDA::node son;
00032 LEDA::node tan;
00033 LEDA::edge_array<LEDA::edge> GtoH1;
00034 LEDA::edge_array<LEDA::edge> GtoH2;
00035
00036 class st_cutset_inequality;
00037
00038 public:
00039
00047 SpanTree(LEDA::graph& G_, scil_map<LEDA::edge>& VM_);
00048
00052 void init(subproblem& S);
00053
00059 status separate(subproblem& S);
00060
00063 status feasible(solution& S);
00064
00065 void min_cut(LEDA::node u, LEDA::edge_array<int>& C, LEDA::edge_array<int>& F,
00066 LEDA::node_array<bool>& R, int& k);
00067 };
00068
00069
00070 }
00071 #endif
