evaluating a code of a graph [migrated]
- by mazen.r.f
This is relatively a long code,if you have the tolerance and the will to find out how to make this code work then take a look please, i will appreciate your feed back.
i have spent two days trying to come up with a code to represent a graph , then calculate the shortest path using dijkastra algorithm , but i am not able to get the right result , even the code runs without errors , but the result is not correct , always i am getting 0.
briefly,i have three classes , Vertex, Edge, Graph , the Vertex class represents the nodes in the graph and it has id and carried ( which carry the weight of the links connected to it while using dijkastra algorithm ) and a vector of the ids belong to other nodes the path will go through before arriving to the node itself , this vector is named previous_nodes.
the Edge class represents the edges in the graph it has two vertices ( one in each side ) and a wight ( the distance between the two vertices ).
the Graph class represents the graph , it has two vectors one is the vertices included in this graph , and the other is the edges included in the graph.
inside the class Graph there is a method its name shortest takes the sources node id and the destination and calculates the shortest path using dijkastra algorithm, and i think that it is the most important part of the code.
my theory about the code is that i will create two vectors one for the vertices in the graph i will name it vertices and another vector its name is ver_out it will include the vertices out of calculation in the graph, also i will have two vectors of type Edge , one its name edges for all the edges in the graph and the other its name is track to contain temporarily the edges linked to the temporarily source node in every round , after the calculation of every round the vector track will be cleared.
in main() i created five vertices and 10 edges to simulate a graph , the result of the shortest path supposedly to be 4 , but i am always getting 0 , that means i am having something wrong in my code , so if you are interesting in helping me find my mistake and how to make the code work , please take a look.
the way shortest work is as follow at the beginning all the edges will be included in the vector edges , we select the edges related to the source and put them in the vector track , then we iterate through track and add the wight of every edge to the vertex (node ) related to it ( not the source vertex ) , then after we clear track and remove the source vertex from the vector vertices and select a new source , and start over again select the edges related to the new source , put them in track , iterate over edges in tack , adding the weights to the corresponding vertices then remove this vertex from the vector vertices, and clear track , and select a new source , and so on .
here is the code.
#include<iostream>
#include<vector>
#include <stdlib.h> // for rand()
using namespace std;
class Vertex
{
private:
unsigned int id; // the name of the vertex
unsigned int carried; // the weight a vertex may carry when calculating shortest path
vector<unsigned int> previous_nodes;
public:
unsigned int get_id(){return id;};
unsigned int get_carried(){return carried;};
void set_id(unsigned int value) {id = value;};
void set_carried(unsigned int value) {carried = value;};
void previous_nodes_update(unsigned int val){previous_nodes.push_back(val);};
void previous_nodes_erase(unsigned int val){previous_nodes.erase(previous_nodes.begin() + val);};
Vertex(unsigned int init_val = 0, unsigned int init_carried = 0) :id (init_val), carried(init_carried) // constructor
{
}
~Vertex() {}; // destructor
};
class Edge
{
private:
Vertex first_vertex; // a vertex on one side of the edge
Vertex second_vertex; // a vertex on the other side of the edge
unsigned int weight; // the value of the edge ( or its weight )
public:
unsigned int get_weight() {return weight;};
void set_weight(unsigned int value) {weight = value;};
Vertex get_ver_1(){return first_vertex;};
Vertex get_ver_2(){return second_vertex;};
void set_first_vertex(Vertex v1) {first_vertex = v1;};
void set_second_vertex(Vertex v2) {second_vertex = v2;};
Edge(const Vertex& vertex_1 = 0, const Vertex& vertex_2 = 0, unsigned int init_weight = 0)
: first_vertex(vertex_1), second_vertex(vertex_2), weight(init_weight)
{
}
~Edge() {} ; // destructor
};
class Graph
{
private:
std::vector<Vertex> vertices;
std::vector<Edge> edges;
public:
Graph(vector<Vertex> ver_vector, vector<Edge> edg_vector)
: vertices(ver_vector), edges(edg_vector)
{
}
~Graph() {};
vector<Vertex> get_vertices(){return vertices;};
vector<Edge> get_edges(){return edges;};
void set_vertices(vector<Vertex> vector_value) {vertices = vector_value;};
void set_edges(vector<Edge> vector_ed_value) {edges = vector_ed_value;};
unsigned int shortest(unsigned int src, unsigned int dis) {
vector<Vertex> ver_out;
vector<Edge> track;
for(unsigned int i = 0; i < edges.size(); ++i)
{
if((edges[i].get_ver_1().get_id() == vertices[src].get_id()) || (edges[i].get_ver_2().get_id() == vertices[src].get_id()))
{
track.push_back (edges[i]);
edges.erase(edges.begin()+i);
}
};
for(unsigned int i = 0; i < track.size(); ++i)
{
if(track[i].get_ver_1().get_id() != vertices[src].get_id())
{
track[i].get_ver_1().set_carried((track[i].get_weight()) + track[i].get_ver_2().get_carried());
track[i].get_ver_1().previous_nodes_update(vertices[src].get_id());
}
else
{
track[i].get_ver_2().set_carried((track[i].get_weight()) + track[i].get_ver_1().get_carried());
track[i].get_ver_2().previous_nodes_update(vertices[src].get_id());
}
}
for(unsigned int i = 0; i < vertices.size(); ++i)
if(vertices[i].get_id() == src) vertices.erase(vertices.begin() + i); // removing the sources vertex from the vertices vector
ver_out.push_back (vertices[src]);
track.clear();
if(vertices[0].get_id() != dis) {src = vertices[0].get_id();}
else {src = vertices[1].get_id();}
for(unsigned int i = 0; i < vertices.size(); ++i)
if((vertices[i].get_carried() < vertices[src].get_carried()) && (vertices[i].get_id() != dis))
src = vertices[i].get_id();
//while(!edges.empty())
for(unsigned int round = 0; round < vertices.size(); ++round)
{
for(unsigned int k = 0; k < edges.size(); ++k)
{
if((edges[k].get_ver_1().get_id() == vertices[src].get_id()) || (edges[k].get_ver_2().get_id() == vertices[src].get_id()))
{
track.push_back (edges[k]);
edges.erase(edges.begin()+k);
}
};
for(unsigned int n = 0; n < track.size(); ++n)
if((track[n].get_ver_1().get_id() != vertices[src].get_id()) && (track[n].get_ver_1().get_carried() > (track[n].get_ver_2().get_carried() + track[n].get_weight())))
{
track[n].get_ver_1().set_carried((track[n].get_weight()) + track[n].get_ver_2().get_carried());
track[n].get_ver_1().previous_nodes_update(vertices[src].get_id());
}
else if(track[n].get_ver_2().get_carried() > (track[n].get_ver_1().get_carried() + track[n].get_weight()))
{
track[n].get_ver_2().set_carried((track[n].get_weight()) + track[n].get_ver_1().get_carried());
track[n].get_ver_2().previous_nodes_update(vertices[src].get_id());
}
for(unsigned int t = 0; t < vertices.size(); ++t)
if(vertices[t].get_id() == src) vertices.erase(vertices.begin() + t);
track.clear();
if(vertices[0].get_id() != dis) {src = vertices[0].get_id();}
else {src = vertices[1].get_id();}
for(unsigned int tt = 0; tt < edges.size(); ++tt)
{
if(vertices[tt].get_carried() < vertices[src].get_carried())
{
src = vertices[tt].get_id();
}
}
}
return vertices[dis].get_carried();
}
};
int main()
{
cout<< "Hello, This is a graph"<< endl;
vector<Vertex> vers(5);
vers[0].set_id(0);
vers[1].set_id(1);
vers[2].set_id(2);
vers[3].set_id(3);
vers[4].set_id(4);
vector<Edge> eds(10);
eds[0].set_first_vertex(vers[0]);
eds[0].set_second_vertex(vers[1]);
eds[0].set_weight(5);
eds[1].set_first_vertex(vers[0]);
eds[1].set_second_vertex(vers[2]);
eds[1].set_weight(9);
eds[2].set_first_vertex(vers[0]);
eds[2].set_second_vertex(vers[3]);
eds[2].set_weight(4);
eds[3].set_first_vertex(vers[0]);
eds[3].set_second_vertex(vers[4]);
eds[3].set_weight(6);
eds[4].set_first_vertex(vers[1]);
eds[4].set_second_vertex(vers[2]);
eds[4].set_weight(2);
eds[5].set_first_vertex(vers[1]);
eds[5].set_second_vertex(vers[3]);
eds[5].set_weight(5);
eds[6].set_first_vertex(vers[1]);
eds[6].set_second_vertex(vers[4]);
eds[6].set_weight(7);
eds[7].set_first_vertex(vers[2]);
eds[7].set_second_vertex(vers[3]);
eds[7].set_weight(1);
eds[8].set_first_vertex(vers[2]);
eds[8].set_second_vertex(vers[4]);
eds[8].set_weight(8);
eds[9].set_first_vertex(vers[3]);
eds[9].set_second_vertex(vers[4]);
eds[9].set_weight(3);
unsigned int path;
Graph graf(vers, eds);
path = graf.shortest(2, 4);
cout<< path << endl;
return 0;
}
