1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/metis.hpp>
typedef boost::adjacency_list_traits<
boost::vecS, boost::vecS, boost::undirectedS, boost::listS> GraphTraits;
typedef GraphTraits::vertex_descriptor Vertex;
struct VertexProperty {
std::string name;
Vertex predecessor;
double distance;
boost::default_color_type color;
VertexProperty(const std::string& aName = "") : name(aName) { };
};
struct EdgeProperty {
double weight;
EdgeProperty(double aWeight = 0.0) : weight(aWeight) { };
};
struct do_nothing_dijkstra_visitor {
template <typename Vertex, typename Graph>
void initialize_vertex(Vertex u, const Graph& g) const { };
template <typename Vertex, typename Graph>
void examine_vertex(Vertex u, const Graph& g) const { };
template <typename Edge, typename Graph>
void examine_edge(Edge e, const Graph& g) const { };
template <typename Vertex, typename Graph>
void discover_vertex(Vertex u, const Graph& g) const { };
template <typename Edge, typename Graph>
void edge_relaxed(Edge e, const Graph& g) const { };
template <typename Edge, typename Graph>
void edge_not_relaxed(Edge e, const Graph& g) const { };
template <typename Vertex, typename Graph>
void finish_vertex(Vertex u, const Graph& g) const { };
};
int main() {
std::string tempName1;
std::string tempName2;
std::string tempString;
std::string data2;
double weight;
std::cout << "please enter the data file name: ";
char strFileName[256];
std::cin >> strFileName;
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperty, EdgeProperty> Graph;
Graph g;
// preparing the data
std::ifstream fin;
fin.open(strFileName);
if (!fin) {
std::cerr << "Can't open data file, leaving...\n";
return EXIT_FAILURE;
}
else{
std::cout << "file loaded." << std::endl << std::endl;
}
std::map<std::string, Vertex> name2v;
std::getline(fin, tempString); //Vertices:
std::getline(fin, tempString); //Location1, Location2, ...
std::stringstream tempSS(tempString);
while (std::getline(tempSS, tempName1, ',')){
name2v[tempName1] = add_vertex(VertexProperty(tempName1), g);
}
std::getline(fin, tempString); //Edges:
while (std::getline(fin, tempString)){ // (Location1, Location2, 6)
//remove parentheses
tempString.erase(tempString.begin(), tempString.begin() + tempString.find('(') + 1);
tempString.erase(tempString.begin() + tempString.find(')'), tempString.end());
std::stringstream temp_ss(tempString);
std::getline(temp_ss, tempName1, ',');
std::getline(temp_ss, tempName2, ',');
temp_ss >> weight;
add_edge(name2v[tempName1], name2v[tempName2], EdgeProperty(weight), g);
}
char x;
std::cout << std::endl << "How would you like to process your data file?" << std::endl;
std::cout << "1.) shortest path" << std::endl;
std::cout << "2.) minimum spanning tree" << std::endl;
std::cout << "3.) Travelling Salesman" << std::endl << std::endl;
returnQuestion:
std::cout << "please enter 1,2,3 or Q to quit: ";
std::cin >> x;
std::map < std::string, Vertex >;
switch (x){
case 1: //do the work for shortest path
std::cout << "please enter the node ";
dijkstra_shortest_paths(
g, start_vertex,
get(&VertexProperty::predecessor, g),
get(&VertexProperty::distance, g),
get(&EdgeProperty::weight, g),
boost::identity_property_map(), // index-map
std::less<double>(), // compare
std::plus<double>(), // combine
std::numeric_limits<double>::infinity(), // infinity
0.0, // zero
do_nothing_dijkstra_visitor(),
get(&VertexProperty::color, g));
break;
case 2: //do the work for minimum spanning
break;
case 3: //do the work for travelling salesman
break;
case 'q':
case 'Q':
return EXIT_SUCCESS;
break;
default:
goto returnQuestion;
}
std::system("pause");
}
|
