Bellman Ford parsing Source & Destination as a Character rather than an Integer

Question

I am working on a data structures assignment which requires me to read from a file which contains a source, destination & weight (e.g t,x,5) and I've used online resources such a geeksforgeeks from where I have altered my code to make it work. Although what I am currently doing is kind of a hack/workaround which reads the character and converts it to an integer which basically defeats the purpose. I want to parse the characters as is and not convert it to an integer. Reference: https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/ So basically what I doing is that i am treating {s,t,x,y,z} as {0,1,2,3,4} which basically works

if(a[0]=='s')
{
 graph->edge[index].src = 0;
}

and so on...

File that's being read

t,x,5
t,y,8
t,z,-4
x,t,-2
y,x,-3
y,z,9
z,x,7
z,s,2
s,t,6
s,y,7

And here is the working code for it

#include<bits/stdc++.h>
#include<fstream>
#include<string>

using namespace std;

struct Edge { 
  int s, d, w; 
}; 
struct Graph { 
  int V, E;  
  struct Edge* edge; 
}; 
struct Graph* createGraph(int V, int E) 
{ 
  struct Graph* graph = new Graph; 
  graph->V = V; 
  graph->E = E; 
  graph->edge = new Edge[E]; 
  return graph; 
} 

void initialize_single_source(int distance[],int V, int s)
{
  for (int i = 0; i < V; i++) 
  {
    distance[i] = INT_MAX; 
  }
  distance[s] = 0; 
}

void relax(int distance[], int u, int v, int w)
{
     if (distance[v] > distance[u] + w && distance[u] != INT_MAX)
     {
        distance[v] = distance[u] + w; 
     }
}

void display(int distance[], int n) 
{ 
    char vertex[] = {'s','t','x','y','z'};
    cout << "Vertex   Distance from Source\n";
    for (int i = 0; i < n; ++i)
    cout << vertex[i] << "\t\t" << distance[i] << "\n"; 
} 

bool bellman_ford(struct Graph* graph, int s) 
{ 
  int V = graph->V; 
  int E = graph->E; 
  int distance[V]; 

  initialize_single_source(distance,V,s);

  for (int i = 1; i <= V - 1; i++)
  { 
    for (int j = 0; j < E; j++) 
    { 
      int u = graph->edge[j].s; 
      int v = graph->edge[j].d; 
      int w = graph->edge[j].w; 
      relax(distance,u,v,w);
    } 
  } 

  for (int i = 0; i < E; i++) { 
    int u = graph->edge[i].s; 
    int v = graph->edge[i].d; 
    int w = graph->edge[i].w; 
    if (distance[v] > distance[u] + w && distance[u] != INT_MAX) 
      return false; 
  } 

  display(distance, V); 

  return true; 
} 

int main() 
{ 
  int V = 5; 
  int E = 10; 
  struct Graph* graph = createGraph(V, E); 
  int index = 0;
  string a;
  ifstream infile("adjlist.txt");
  while(getline(infile,a))
{   
  if(a[0]=='s')
    {
    graph->edge[index].s = 0;
    }
    else if(a[0]=='t')
    {
    graph->edge[index].s = 1;
    }
    else if(a[0]=='x')
    {
    graph->edge[index].s = 2;
    }
    else if(a[0]=='y')
    {
    graph->edge[index].s = 3;
    }
    else if(a[0]=='z')
    {
    graph->edge[index].s = 4;
    }

    if(a[2]=='s')
    {
    graph->edge[index].d = 0;
    }
    else if(a[2]=='t')
    {
    graph->edge[index].d = 1;
    }
    else if(a[2]=='x')
    {
    graph->edge[index].d = 2;
    }
    else if(a[2]=='y')
    {
    graph->edge[index].d = 3;
    }
    else if(a[2]=='z')
    {
    graph->edge[index].d = 4;
    }

    if(a[4]!='-')
    {
    graph->edge[index].w = a[4]-'0';
    }
    else
    {
    graph->edge[index].w = -(a[5]-'0');
    }
    index++;
}
  bellman_ford(graph, 0); 

  return 0; 
}

Output:

Vertex   Distance from Source
s        0
t        2
x        4
y        7
z        -2

brj · Answer 1 · 2019-11-01T22:20:23.990

0

One possible solution would be to rewrite Edge as follows

struct Edge { 
  char s, d;
  int w;
};

and use std::map<char, vector<char> > for representing the adjacency lists. Note that this will require you to somehow keep track of the weights and change the remaining parts of the code accordingly.

On a side note, as mentioned by @user4581301, including bits/stdc++ is bad practice. See this for more details.

edited Nov 01 '19 at 22:20

answered Nov 01 '19 at 22:14

brj

375
2
11

Hey, i tried doing that before writing the question although it doesn't solve my problem. – affanmansoor Nov 01 '19 at 22:20
Maybe because in the belmanford function int u = graph->edge[j].s; int v = graph->edge[j].d; are being accessed? I just can't seem to fix something so simple and it's been bothering me – affanmansoor Nov 01 '19 at 22:20
Please edit your question to include that code then, see [this](https://stackoverflow.com/help/how-to-ask) – brj Nov 01 '19 at 22:22

score 0 · Answer 2 · answered Nov 02 '19 at 12:42

Converting vertex labels from strings or some other sparse type to densely packed integers is actually pretty common when implementing graph algorithms and can be quite useful.

We do this so that we can use arrays or vectors to store other things corresponding to the vertexes, instead of more complex structures like maps.

The label mapping should be constructed dynamically, though, depending on what labels you actually have instead of hard-coding it. You can use a std::map<char,int> to do it like this:

int getVertexNumber(char c) {
    auto it = label_map.find(c);
    int num;
    if (it != label_map.end()) {
        // already had a mapping for this label
        num = it->second;
    } else {
        // new label, starting at 0
        num = (int)label_map.size();
        label_map[c] = num;
    }
    return num;
}

Bellman Ford parsing Source & Destination as a Character rather than an Integer

2 Answers2