00001 #ifndef STRONGLY_CONNECTED_H
00002 #define STRONGLY_CONNECTED_H
00003
00004 #include<scil/scil.h>
00005 #include<boost/graph/strong_components.hpp>
00006 #include<boost/graph/adjacency_list.hpp>
00007 #include<boost/graph/adjacency_matrix.hpp>
00008 #include<boost/graph/boykov_kolmogorov_max_flow.hpp>
00009 #include <boost/graph/iteration_macros.hpp>
00010 #include <boost/graph/graph_traits.hpp>
00011
00012
00013 namespace SCIL {
00014
00028 template<typename Graph>
00029 class StronglyConnected : public sym_constraint {
00030 private:
00031
00032 typedef boost::graph_traits<Graph> GraphTraits;
00033 typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
00034 typedef typename GraphTraits::edge_descriptor edge_descriptor;
00035 typedef map<edge_descriptor, int> capacity_map_t;
00036 typedef map<vertex_descriptor, size_t> vertex_index_t;
00037 typedef map<edge_descriptor, edge_descriptor> edge_reverse_t;
00038
00039 Graph G;
00040 var_map<edge_descriptor> VM;
00041 edge_reverse_t edge_reverse;
00042
00043
00044 public:
00045
00046
00047
00055 StronglyConnected(Graph& G_, var_map<edge_descriptor>& VM_);
00056
00059 void min_cut(vertex_descriptor u,map<edge_descriptor, int>& C, map<edge_descriptor, int>& F,
00060 map<vertex_descriptor, bool>& R, int& k);
00061
00064 status standard_separation(subproblem& S);
00065
00068 status feasible(solution& S);
00069
00072 void info();
00073
00074 };
00075
00076 }
00077
00078 #include "../../../src/constraints/stronglyconnected.cc"
00079 #endif
