fork download
copy 
  1. #include <boost/graph/graph_traits.hpp>
  2. #include <boost/graph/adjacency_list.hpp>
  3. #include <boost/graph/dijkstra_shortest_paths.hpp>
  4.  
  5. using namespace boost;
  6. using namespace std;
  7.  
  8. class GPS
  9. {
  10. public:
  11.     typedef			boost::property<boost::edge_weight_t, float>						Distance;
  12. 	typedef			adjacency_list<vecS, vecS, directedS, boost::no_property, Distance>	Graph;
  13. 	typedef			int																	Node;
  14. 	typedef			std::pair<int, int>													Edge;
  15. 	typedef			property_map<Graph, edge_weight_t>::type							weightmap_t;				
  16. 	typedef			graph_traits < Graph >::vertex_descriptor							vertex_descriptor;
  17. 	typedef			graph_traits < Graph >::edge_descriptor								edge_descriptor;
  18. private:
  19. 	vector<Edge>	Edges;
  20. 	Graph			Nodes;
  21. public:
  22. 	GPS() 
  23. 	{
  24.  
  25. 	}
  26. 	~GPS()
  27. 	{
  28.  
  29. 	}
  30. 	//returns amount of edges added: 0, 1 or 2
  31. 	char AddEdge(Node from, Node to, Distance weight = 0.0f, bool BothDirections = false)
  32. 	{
  33. 		char added = 0;
  34. 		if(add_edge(from,to,weight,Nodes).second)
  35. 			++added;
  36. 		if(BothDirections)
  37. 		{
  38. 			if(add_edge(to,from,weight,Nodes).second)
  39. 				++added;
  40. 		}
  41. 		return added;
  42. 	}
  43. 	//returns the added node, 
  44. 	//specify your own vertex identificator if wanted 
  45. 	//(for maintaining backwards compatibility with old graphs saved in gps.dat files)
  46. 	Node AddNode(int id = -1)
  47. 	{
  48. 		if(id == -1)
  49. 			return add_vertex(Nodes);
  50. 		else
  51. 			return vertex(id,Nodes);
  52. 	}
  53. 	//get the shortest path between 'from' and 'to' by adding all nodes which are traversed into &path
  54. 	void Path(Node from, Node to, vector<Node> &path)
  55. 	{
  56. 		std::vector<vertex_descriptor> p(num_vertices(Nodes));
  57. 		std::vector<int> d(num_vertices(Nodes));
  58. 		weightmap_t weightmap = get(edge_weight, Nodes);
  59. 		vertex_descriptor s = vertex(from, Nodes);
  60. 		dijkstra_shortest_paths(Nodes, s, predecessor_map(&p[0]).distance_map(&d[0]));
  61.  
  62. 		//what here, how to retrieve path between 'from' and 'to'?
  63. 	}
  64. };
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/PwWjxu
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!