I am trying to read weights from a text file but it's not giving the same output as to when I am setting them manually. This is the data present in the adjlist.txt file:
5
8
4
2
3
9
7
2
6
7
Now when I manually set these without the reading mechanism, e.g: graph->edge[0].weight = 5 and so on it gives me this output
Vertex Distance from Source
0 0
1 6
2 10
3 7
4 10
I have tried fetching the data by just printing it and it certainly is reading it correctly but isn't parsing it properly "cout << s[0] << "\n";"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include<bits/stdc++.h>
#include<fstream>
#include<string>
using namespace std;
// a structure to represent a weighted edge in graph
struct Edge
{
int src, dest, weight;
};
// a structure to represent a connected, directed and weighted graph
struct Graph
{
// V-> Number of vertices, E-> Number of edges
int V, E;
// graph is represented as an array of edges.
struct Edge* edge;
};
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));
return graph;
}
// A utility function used to print the solution
void printArr(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < n; ++i)
printf("%d \t\t %d\n", i, dist[i]);
}
void relax(struct Graph* graph, int V, int dist[], int E, int src)
{
for (int i = 1; i <= V - 1; i++)
{
for (int j = 0; j < E; j++)
{
int u = graph->edge[j].src;
int v = graph->edge[j].dest;
int weight = graph->edge[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
dist[v] = dist[u] + weight;
}
}
}
void int_source(int V,int dist[],int E,int src)
{
for (int i = 0; i < V; i++)
dist[i] = INT_MAX;
dist[src] = 0;
}
void negweight(struct Graph* graph, int V, int dist[], int E, int src)
{
for (int i = 0; i < E; i++)
{
int u = graph->edge[i].src;
int v = graph->edge[i].dest;
int weight = graph->edge[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
printf("Graph contains negative weight cycle");
}
}
// The main function that finds shortest distances from src to all other
// vertices using Bellman-Ford algorithm. The function also detects negative
// weight cycle
void BellmanFord(struct Graph* graph, int src)
{
int V = graph->V;
int E = graph->E;
int dist[V];
int_source(V,dist,E,src);
relax(graph,V,dist,E,src);
negweight(graph,V,dist,E,src);
printArr(dist, V);
return;
}
int main()
{
int V = 5; // Number of vertices in graph
int E = 10; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
string s;
cout << "Your input file contains this adjacency list\n";
ifstream infile("adjlist.txt");
while(getline(infile,s))
{
graph->edge[0].src = 1;
graph->edge[0].dest = 2;
graph->edge[0].weight = s[0]-'0';
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 1;
graph->edge[1].dest = 3;
graph->edge[1].weight = s[0]-'0';
// add edge 1-2 (or B-C in above figure)
graph->edge[2].src = 1;
graph->edge[2].dest = 4;
graph->edge[2].weight = s[0]-'0';
// add edge 1-3 (or B-D in above figure)
graph->edge[3].src = 2;
graph->edge[3].dest = 1;
graph->edge[3].weight = s[0]-'0';
// add edge 1-4 (or A-E in above figure)
graph->edge[4].src = 3;
graph->edge[4].dest = 2;
graph->edge[4].weight = s[0]-'0';
// add edge 3-2 (or D-C in above figure)
graph->edge[5].src = 3;
graph->edge[5].dest = 4;
graph->edge[5].weight = s[0]-'0';
// add edge 3-1 (or D-B in above figure)
graph->edge[6].src = 4;
graph->edge[6].dest = 2;
graph->edge[6].weight = s[0]-'0';
// add edge 4-3 (or E-D in above figure)
graph->edge[7].src = 4;
graph->edge[7].dest = 0;
graph->edge[7].weight = s[0]-'0';
// add edge 4-3 (or E-D in above figure)
graph->edge[8].src = 0;
graph->edge[8].dest = 1;
graph->edge[8].weight = s[0]-'0'; // add edge 4-3 (or E-D in above figure)
graph->edge[9].src = 0;
graph->edge[9].dest = 3;
graph->edge[9].weight = s[0]-'0';
}
BellmanFord(graph, 0);
return 0;
} `
Expected result should be
Vertex Distance from Source
0 0
1 6
2 10
3 7
4 10
Result I am getting is
Vertex Distance from Source
0 0
1 7
2 14
3 7
4 14
Take a closer look at the main parsing loop. For each line read from the file it sets the same value in the weight for all of the nodes.
Example:
graph->edge[0].src = 1;
graph->edge[0].dest = 2;
graph->edge[0].weight = s[0]-'0'; // 5
// add edge 0-2 (or A-C in above figure)
graph->edge[1].src = 1;
graph->edge[1].dest = 3;
graph->edge[1].weight = s[0]-'0'; // still five.
What you want is
int index = 0;
while(getline(infile,s))
{
graph->edge[index].src = 1;
graph->edge[index].dest = 2;
graph->edge[index].weight = s[0]-'0';
index++
}
Unfortunately this doesn't seem to fix everything. I can't see a way to enter the body of
if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
with the given inputs.