00001 #ifndef METRO_GRAPH_H_INCLUDED
00002 #define METRO_GRAPH_H_INCLUDED
00003
00004 #include <boost/graph/graph_traits.hpp>
00005 #include <boost/graph/adjacency_list.hpp>
00006 #include <boost/graph/dijkstra_shortest_paths.hpp>
00007 #include <boost/format.hpp>
00008
00009 #include <iostream>
00010 #include <fstream>
00011
00012 namespace metro
00013 {
00014
00019 template<typename sommet>
00020 class Graph
00021 {
00022 typedef boost::adjacency_list< boost::listS
00023 , boost::vecS
00024 , boost::undirectedS
00025 , boost::no_property
00026 , boost::property<boost::edge_weight_t, int>
00027 > graph_t;
00028
00029 typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
00030
00031 typedef boost::graph_traits<graph_t>::edge_descriptor edge_descriptor;
00032
00033 typedef std::pair<sommet, sommet> edge_t;
00034
00035 typedef std::list<edge_t> list_edge_t;
00036 typedef std::list<int> list_weight_t;
00037
00038 list_edge_t m_edges;
00039 list_weight_t m_weigths;
00040 size_t m_nbSommets;
00041
00042 public:
00043 typedef std::list< std::pair<sommet, size_t> > solution_t;
00044
00045 Graph()
00046 : m_nbSommets(0)
00047 {
00048 }
00049
00050 ~Graph()
00051 {
00052 }
00053
00059 void add_edge(sommet s1, sommet s2, int weight)
00060 {
00061 m_edges.push_back(edge_t(s1, s2));
00062 m_weigths.push_back(weight);
00063 }
00064
00065 void set_nb_sommets(size_t nbSommets)
00066 {
00067 m_nbSommets = nbSommets;
00068 }
00069
00070 bool find_way(sommet s1, sommet s2, solution_t& trajet)
00071 {
00072 assert(m_edges.size() == m_weigths.size());
00073
00074
00075 graph_t g(m_edges.begin(), m_edges.end(), m_weigths.begin(), m_nbSommets);
00076 boost::property_map<graph_t, boost::edge_weight_t>::type weightmap = boost::get(boost::edge_weight, g);
00077
00078
00079 std::vector<vertex_descriptor> precedents(num_vertices(g));
00080 std::vector<int> distances(num_vertices(g));
00081 vertex_descriptor s = vertex(s1, g);
00082
00083
00084 boost::dijkstra_shortest_paths( g
00085 , s
00086 , boost::predecessor_map(&precedents[0]).distance_map(&distances[0])
00087 );
00088
00089
00090 trajet.push_front(std::make_pair(s2, distances[s2]));
00091 sommet cur = s2;
00092 sommet prec = 0;
00093 do {
00094 prec = precedents[cur];
00095 if (prec == cur) {
00096 return false;
00097 }
00098 else if (prec != s1) {
00099 trajet.push_front(std::make_pair(prec, distances[prec]));
00100 cur = prec;
00101 }
00102 }
00103 while (prec != s1);
00104 return true;
00105 }
00106
00107 };
00108
00109 }
00110
00111 #endif // METRO_GRAPH_H_INCLUDED