13 #ifndef VRP_BOOST_INCLUDED
14 #define VRP_BOOST_INCLUDED
25 #include <boost/graph/graphviz.hpp>
26 #include <boost/graph/graph_utility.hpp>
27 #include <boost/graph/adjacency_list.hpp>
28 #include <boost/graph/connected_components.hpp>
29 #include <boost/graph/kruskal_min_spanning_tree.hpp>
30 using namespace boost;
33 typedef property<edge_weight_t, double,
35 typedef adjacency_list<vecS, vecS, undirectedS,
43 template <
class EdgeWeight >
47 template <
class VertexOrEdge>
48 void operator()(ostream & out,
const VertexOrEdge & e)
const {
49 if(weight[e] >= 0.9999999)
50 out <<
"[style=solid]";
52 out <<
"[label=\"" << weight[e] <<
"\", stype=dashed]";
57 template <
class EdgeWeight >
71 : demand(vertex_wt) {}
72 template <
class VertexOrEdge>
73 void operator()(ostream & out,
const VertexOrEdge & v)
const {
75 out <<
" [style=filled, fillcolor=black]";
77 out <<
" [label=\"" << v <<
" : "
78 << demand[v] <<
"\" width=\"0.5\" height=\"0.5\"]";
108 const double tol = 1.0e-6){
115 property_map<Graph, edge_weight_t>::type e_weight
116 =
get(edge_weight, m_sg);
117 property_map<Graph, edge_index_t>::type e_index
118 =
get(edge_index, m_sg);
119 graph_traits<Graph>::edge_descriptor ed;
bool inserted;
123 for (c = 0; c < len; ++c) {
128 if(uv.first == 0 || uv.second == 0){
129 m_depotDegree += val[c];
132 tie(ed, inserted) = add_edge(uv.first, uv.second, m_sg);
133 e_weight[ed] = val[c];
164 const int * vertexWt,
165 const Graph & g)
const {
170 printf(
"PrintDotFile fileName = %s\n", fileName.c_str());
172 map<string, string> graph_attr, vertex_attr, edge_attr;
173 graph_attr [
"fontsize"] =
"20";
175 vertex_attr[
"fontsize"] =
"20";
176 vertex_attr[
"shape"] =
"circle";
178 edge_attr [
"style"] =
"dotted";
179 edge_attr [
"len"] =
"1.7";
180 edge_attr [
"fontsize"] =
"20";
185 write_graphviz(os, g,
188 make_graph_attributes_writer(graph_attr,
213 return connected_components(m_sg, &component[0]);
217 vector<int> & component){
218 return connected_components(g, &component[0]);
222 return degree(nodeIndex, m_sg);
226 return m_depotDegree;
void printGraph(const Graph &g) const
sg_label_writer< EdgeWeight > sg_make_label_writer(EdgeWeight e)
adjacency_list< vecS, vecS, undirectedS, no_property, edge_prop > Graph
void buildSubGraph(const int len, const double *val, const double tol=1.0e-6)
pair< int, int > UtilBothEndsU(const int index)
void printDotFile(const string &fileName, const int *vertexWt, const Graph &g) const
int findConnectedComponents(vector< int > &component)
void copyGraph(const Graph &gFrom, Graph &gTo)
void operator()(ostream &out, const VertexOrEdge &e) const
void UtilOpenFile(ifstream &fs, const char *fileName)
sg_label_writer_vertex sg_make_label_writer_vertex(const int *vertex_wt)
sg_label_writer_vertex(const int *vertex_wt)
property< edge_weight_t, double, property< edge_index_t, int > > edge_prop
int findConnectedComponents(Graph &g, vector< int > &component)
void clearSubGraph(Graph &g)
void clearVertex(const int vertex, Graph &g)
sg_label_writer(EdgeWeight e_)
void operator()(ostream &out, const VertexOrEdge &v) const
int getDegree(const int nodeIndex)