Hierarchical Index

00001 #ifndef MAX_CUT_H
00002 #define MAX_CUT_H
00003 
00004 #include <algorithm>
00005 #include <boost/foreach.hpp>
00006 #include <boost/graph/adjacency_list.hpp>
00007 #include <boost/graph/adjacency_matrix.hpp>
00008 #include <boost/graph/breadth_first_search.hpp>
00009 #include <boost/graph/dijkstra_shortest_paths.hpp>
00010 #include <boost/graph/graph_traits.hpp>
00011 #include <boost/graph/iteration_macros.hpp>
00012 #include <boost/graph/kruskal_min_spanning_tree.hpp>
00013 #include <boost/graph/connected_components.hpp>
00014 #include <boost/graph/visitors.hpp>
00015 #include <boost/property_map/property_map.hpp>
00016 #include <boost/tuple/tuple.hpp>
00017 #include <boost/type_traits/is_base_and_derived.hpp>
00018 #include <boost/type_traits/is_same.hpp>
00019 #include <cstdarg>
00020 #include <iostream>
00021 #include <list>
00022 #include <string>
00023 #include <scil/core/var_map.h>
00024 #include <scil/global.h>
00025 #include <scil/scil.h>
00026 #include <boost/unordered_map.hpp>
00027 
00028 using namespace boost;
00029 using namespace std;
00030 
00031 namespace SCIL {
00032 
00033 //class primal_heuristic;
00034 template <typename Graph, typename vertex_descriptor, typename edge_descriptor>
00035 bool color_graph(Graph& H, vertex_descriptor& r, 
00036                  map<edge_descriptor,double>& cut, 
00037                  map<vertex_descriptor, bool>& color);
00038 
00043 template <typename Graph>
00044 class CUT : public sym_constraint { 
00045 
00046    private:
00047 
00048       typedef boost::graph_traits<Graph> GraphTraits;
00049       typedef typename GraphTraits::vertex_descriptor vertex_descriptor;
00050       typedef typename GraphTraits::edge_descriptor edge_descriptor;
00051 
00052       class bfs_dist_visitor;
00053 
00054       Graph &G;               
00055       row_map<edge_descriptor> &VM;      
00056       list<vertex_descriptor> conf;
00057       list<vertex_descriptor> tconf;
00058       bool updateConfiguration;     
00059       int nc;
00060 
00062       Graph G1;
00063       map<vertex_descriptor, vertex_descriptor> GtoG1a;
00064       map<vertex_descriptor, vertex_descriptor> GtoG1b;
00065       map<edge_descriptor, edge_descriptor> back;
00066       map<vertex_descriptor, vertex_descriptor> G1toG;
00067       map<edge_descriptor, bool> isCrossEdge;
00068 
00069       list<Graph> graph_components;
00070       list<row_map<edge_descriptor> > VML;
00071 
00072       bool initialized;
00073 
00074       void initAuxGraph(solution S);
00075 
00076       void undirected_bfs(Graph &H, vertex_descriptor r, 
00077          map<vertex_descriptor, int> &dst, 
00078          map<vertex_descriptor, edge_descriptor> &pred);
00079 
00080    public:
00088       CUT(Graph &G_, row_map<edge_descriptor> &VM_, int nc_ = -1);
00089 
00090       void init(subproblem& S);
00091 
00092       int generate_triangle_inequalities(subproblem& S);
00093 
00096       status standard_separation(subproblem& S);
00097 
00100       status fast_separation(subproblem& S);
00101 
00104       status feasible(solution& S);
00105 
00111       int exactCycleSeparation(solution& S, int maxnum, 
00112          std::list<cons_obj*>& newCons);
00113 
00116       int forestCycleSeparation(solution& S, int maxnum,
00117          std::list<cons_obj*>& newCons);
00118 
00121       list<vertex_descriptor> getConfiguration(solution& S);
00122 
00125       void info();
00126 };
00127 }
00128 #include "../../../src/constraints/cut.cc"
00129 #endif
cut.h
