implement in c++ The graph contains 10000 vertices. Each vertex is given an x y

Question

implement in c++

The graph contains 10000 vertices. Each vertex is given an x y z coordinate value. For example

VERTEX2 28 5.298951 3.084083 1.732966

This line from the file declares the 28th vertex and its respective x y and z coordinates.

The rest of the file contains the edges in the graph. We are only going to be concerned the out vertex and the in vertex. Which is the first two numbers for each edge. We will ignore the rest. For example.

EDGE2 3 4 1.038045 0.003036 0.011663 44.447240 -0.955703 371.210835 9770.758221 0.000000 0.000000

Simply states that there is an edge from vertex 3 to vertex 4. We will not be using the rest of the data in the file and will be weighting the edges with the distance between the two vertices. (Use the 3 dimensional distance function).

Produce a program with the following capabilities. The program will prompt for the start- ing vertex in the range of 0-9999. The program will then prompt for a different vertex in the range of 0-9999. The program will then execute a shortest path algorithm (Dijkstra’s is fine but you are welcome to use a different one). If a path does exist between the two vertices it will

1

output the sequence of vertices in the shortest path, as well as the total weight of the entire path between the two vertices.

this link should work

https://dl.dropboxusercontent.com/u/4309261/site%20links/datasets/datasets%20backup/M10000_P_toro.graph

here is simple code.

Explanation / Answer

Program:

The graph contains 10000 vertices. Each vertex is given an x y z coordinate value. For example

VERTEX2 28 5.298951 3.084083 1.732966.

This line from the file declares the 28th vertex and its respective x y and z coordinates.

The rest of the file contains the edges in the graph. We are only going to be concerned the out vertex and the in vertex. Which is the first two numbers for each edge. We will ignore the rest

#include <boost/config.hpp>

#include <iostream>

#include <fstream>

#include <boost/graph/graph_traits.hpp>

#include <boost/graph/adjacency_list.hpp>

#include <boost/graph/dijkstra_shortest_paths.hpp>

#include <boost/property_map/property_map.hpp>

using namespace boost;

int

main(int, char *[])

{

typedef adjacency_list < listS, vecS, directedS,

    no_property, property < edge_weight_t, int > > graph_t;

typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;

typedef std::pair<int, int> Edge;

const int num_nodes = 5;

enum nodes { A, B, C, D, E };

char name[] = "ABCDE";

Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),

    Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)

};

int weights[] = { 1, 5, 85, 12, 27, 83, 19, 1, 1 };

int num_arcs = sizeof(edge_array) / sizeof(Edge);

graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);

property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight, g);

std::vector<vertex_descriptor> p(num_vertices(g));

std::vector<int> d(num_vertices(g));

vertex_descriptor s = vertex(A, g);

dijkstra_shortest_paths(g, s,

                          predecessor_map(boost::make_iterator_property_map(p.begin(), get(boost::vertex_index, g))).

                          distance_map(boost::make_iterator_property_map(d.begin(), get(boost::vertex_index, g))));

std::cout << "distances and parents:" << std::endl;

graph_traits < graph_t >::vertex_iterator vi, vend;

for (boost::tie(vi, vend) = vertices(g); vi != vend; ++vi) {

    std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";

    std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::

      endl;

}

std::cout << std::endl;

return EXIT_SUCCESS;

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.