7 Replies - 3169 Views - Last Post: 11 September 2012 - 10:43 AM Rate Topic: -----

#1 vikrantiitr_1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 11-July 12

Shortest path using BFS in graph

Posted 11 September 2012 - 09:07 AM

I was trying to find shortest path using modern adjacency list graph data structure and BFS algorithm. I am not getting any output after passing required inputs and it is still running. This usually happens when the loop don't terminate but I am not able to figure it out here....
#include<iostream>
using namespace std;

class vertex;
class Graph;

void BFS(Graph,int);



struct Edge{
      int E_num;
      vertex*first;
      vertex*second;
      Edge*enext;
};

struct node{
       Edge*data;          // node of edgelist inside a vertex
       node*next;          // Here we can also store vertex numbers to get adjacent vertices quickly.
};

class vertex{
      public:
       int V_num;
       node*E_in_front;
       node*E_in_rear;
       node*E_out_front;
       node*E_out_rear;
       vertex*vnext;
       int color;
       int label;
       int parent;
       
       
       vertex(){
                E_in_front = E_in_rear = NULL;
                E_out_front = E_out_rear = NULL;
                color = 0; // initially white.
                label = -1;
                parent = -1;
               }
               
       void insert_node_vin(Edge*x)
       {
            node*temp = new node;
            temp->data = x;
            temp->next = NULL;
            if(E_in_front == NULL)
            { 
              E_in_front = E_in_rear = temp;
              return;
            }
            E_in_rear->next = temp;
            E_in_rear = temp;
       }
       
       void insert_node_vout(Edge*x)
       {
            node*temp = new node;
            temp->data = x;
            temp->next = NULL;
            if(E_out_front == NULL)
            { 
              E_out_front = E_out_rear = temp;
              return;
            }
            E_out_rear->next = temp;
            E_out_rear = temp;
       }
       
       
       
};


       
class Graph{
      
  public:
         
  Edge*E_front;
  Edge*E_rear;
  vertex*V_front;
  vertex*V_rear;
  
  
      Graph(){
              E_front = E_rear = NULL;
              V_front = V_rear = NULL;
              }  
              
      void insert_edge(int v1, int v2, int num) // num = edge number input by user.
      {
           if(ispresent(v1))
           { 
             if(ispresent(v2))
             { // just create an edge with starting vertex v1 and ending v2.
               Edge*temp = new Edge;
               temp->E_num = num;
               vertex*temp1 = V_front;
               vertex*temp2 = V_front;
               while(temp1 != NULL)
               {
                 if(temp1->V_num == v1)
                 break;
                 temp1 = temp1->vnext;
               }
               while(temp2 != NULL)
               {
                 if(temp2->V_num == v2)
                 break;
                 temp2 = temp2->vnext;
               }
               E_rear->enext = temp;
               temp->enext = NULL;
               E_rear =  temp;
               temp1->insert_node_vout(temp);
               temp2->insert_node_vin(temp);
               
               temp->first = temp1;
               temp->second = temp2;
             }
             else
             {
                 Edge*temp = new Edge;
                 temp->E_num = num;
                 vertex*temp1 = V_front;
                 while(temp1 != NULL)
                 {
                 if(temp1->V_num == v1)
                 break;
                 temp1 = temp1->vnext;
                 }
                 E_rear->enext = temp;
                 temp->enext = NULL;
                 E_rear =  temp;
                 vertex*temp2 = new vertex;
                 temp2->V_num = v2;
                 V_rear->vnext = temp2;
                 temp2->vnext = NULL;
                 V_rear = temp2;
                 
                 temp1->insert_node_vout(temp);
                temp2->insert_node_vin(temp);
               
                temp->first = temp1;
                temp->second = temp2;
               }
             }
             else // if v1 is not present.
             {
                 if(ispresent(v2))
                 {
                 Edge*temp = new Edge;
                 temp->E_num = num;
                 vertex*temp2 = V_front;
                 while(temp2 != NULL)
                 {
                 if(temp2->V_num == v2)
                 break;
                 temp2 = temp2->vnext;
                 }
                 E_rear->enext = temp;
                 temp->enext = NULL;
                 E_rear =  temp;
                 vertex*temp1 = new vertex;
                 temp1->V_num = v1;
                 V_rear->vnext = temp1;
                 temp1->vnext = NULL;
                 V_rear = temp1;
                 
                 temp1->insert_node_vout(temp);
                 temp2->insert_node_vin(temp);
               
                 temp->first = temp1;
                 temp->second = temp2;
                 }
               else  // both v1 and v2 are not present. It means either there are no elements in graph or only v1 & v2 are not present.
               {
                 Edge*temp = new Edge;
                 temp->E_num = num;
                 if(E_front  == NULL)
                 {
                   E_front = E_rear = temp;
                   temp->enext = NULL;
                 }
                 else
                 {
                    E_rear->enext = temp;
                    temp->enext = NULL;
                    E_rear =  temp; 
                 }
                 vertex*temp1 = new vertex;
                 temp1->V_num = v1;
                 vertex*temp2 = new vertex;
                 temp2->V_num = v2;
                 if(V_front  == NULL)
                 {
                   V_front = V_rear = temp1;
                   temp1->vnext = temp2;
                   temp2->vnext = NULL;
                   V_rear = temp2;
                 }
                 else
                 {
                     V_rear->vnext = temp1;
                     temp1->vnext = temp2;
                     temp2->vnext = NULL;
                     V_rear = temp2;
                 }
                 
                 temp1->insert_node_vout(temp);
                 temp2->insert_node_vin(temp);
               
                 temp->first = temp1;
                 temp->second = temp2;
               }
             }
           }                                    // End void insert_edge(v1,v2,num).
           
           bool ispresent(int v)
           {
                if(V_front == NULL)
                return false;
                
                vertex*temp = V_front;
                while(temp != NULL)
                {
                  if(temp->V_num == v)
                  return true;
                  temp = temp->vnext;
                }
                return false;
           }
           
           int label_vertex(int v)
           {
               vertex*temp = V_front;
               while(temp != NULL)
               {
                if(temp->V_num == v)
                return temp->label;
                temp = temp->vnext;
               }
               
               return 0;
           }
};                                               // END OF CLASS GRAPH.
         
int main()
{
    Graph G;
    int v1=-1,v2,edgenum;
    cin>>v1>>v2>>edgenum;
    while(v1 != -1)
    {
      G.insert_edge(v1,v2,edgenum);
      cin>>v1;
      if(v1==-1)
      break;
      cin>>v2>>edgenum;
    }
    /* Now we have to define three arrays:- color, label, parent. For that either of steps can be taken:
       i) use a data member size in class graph and increment with each vertex addition
       ii)use three more data member inside vertex class ,namely color, label, parent.
       We will be using ii) case as it is more complex to implement.
    */
    cout<<"Enter the vertices between whom shortest distance is to be find out: ";
    cin>>v1>>v2;
    /* Here we will label all the vertex to practice.Otherwise there is no need of this because start BFS from v1 and when we get v2 print its
       label & also no need of taking "label" as data member because we have to just ++ a variable initialise to 0 whenever we pop-out of 
       queue and no need of labelling all intermediate vertices.But we do it here.
    */
     
    BFS(G,v1); // as discussed above this would change to BFS(G,v1,v2) and just return shortest distance directly.
    
    int shortest_path = G.label_vertex(v2) - G.label_vertex(v2);
    
    cout<<"Shortest path between "<<v1<<" and "<<v2<<" is : "<<shortest_path<<endl;
    // WE CAN ALSO STATE THE PATH TAKEN.
    system("pause");
    return 0;
}

struct queuenode{
       vertex*vpointer;
       queuenode*next;
};

class queue{
      public:
      queuenode*front;
      queuenode*rear;
      int length;
      
      queue(){ front = NULL;
               rear = NULL;
               length = 0;
      }
      
      void enqueue(vertex*x)
      {
           queuenode*newnode = new queuenode;
           newnode->vpointer = x;
           newnode->next = NULL;
           if(length==0)
           {
             front = rear = newnode;
             length++;
             return;
           }
           
           rear->next = newnode;
           length++;
           rear = newnode;
      }
             
      void dequeue(){
           if(front == NULL)
           return;
           
           queuenode*temp = front;
           front = front->next;
           delete temp;
           length--;
      }
};


void BFS(Graph G, int v)
{
  vertex*temp = G.V_front;         // Here we have taken "." instead of "->" in G.V_front.This is because "->" is taken only when object 
  while(temp->V_num != v)          // is of pointer type, like Graph*G.Thanks!! 
  temp = temp->vnext;
  
  queue q;
  q.enqueue(temp);
  temp->color = 1;  // gray- visited once and push in queue.
  temp->label = 0;  // level of that element.
  while(q.length != 0)  // queue is not empty.
  {   
      queuenode*temp1 = q.front;
      node*temp2 = temp->E_out_front;
      while(temp2 != NULL)
      {
        q.enqueue(temp2->data->second);
        temp2->data->second->label = temp1->vpointer->label + 1;
        temp2->data->second->color = 1;
        temp2->data->second->parent = temp1->vpointer->V_num;
        temp2 = temp2->next;
      }
      q.dequeue();
      temp1->vpointer->color = 2;
  }  
         
}


here inputs can be given like this:-
1 2 1
and give v1=-1 to stop inputs.

has anyone caught the bugs??

Is This A Good Question/Topic? 0
  • +

Replies To: Shortest path using BFS in graph

#2 jimblumberg  Icon User is online

  • member icon


Reputation: 4018
  • View blog
  • Posts: 12,402
  • Joined: 25-December 09

Re: Shortest path using BFS in graph

Posted 11 September 2012 - 09:13 AM

You may want to add some prompts to your inputs. After entering enough inputs this program seems to seg fault. You may want to run the program through your debugger and try to find where the crash happens and the cause.

Jim
Was This Post Helpful? 1
  • +
  • -

#3 vikrantiitr_1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 11-July 12

Re: Shortest path using BFS in graph

Posted 11 September 2012 - 09:20 AM

View Postjimblumberg, on 11 September 2012 - 09:13 AM, said:

You may want to add some prompts to your inputs. After entering enough inputs this program seems to seg fault. You may want to run the program through your debugger and try to find where the crash happens and the cause.

Jim


can you figure out any one??
Was This Post Helpful? 0
  • +
  • -

#4 jimblumberg  Icon User is online

  • member icon


Reputation: 4018
  • View blog
  • Posts: 12,402
  • Joined: 25-December 09

Re: Shortest path using BFS in graph

Posted 11 September 2012 - 09:30 AM

First add prompts for your inputs so you know what you are inputting where. Then run the program through your debugger. Your debugger will show you where it detects the problem.

Jim
Was This Post Helpful? 1
  • +
  • -

#5 vikrantiitr_1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 11-July 12

Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:31 AM

View Postjimblumberg, on 11 September 2012 - 09:30 AM, said:

First add prompts for your inputs so you know what you are inputting where. Then run the program through your debugger. Your debugger will show you where it detects the problem.

Jim


Finally....finally it works...this technique of detecting faults using prompts is awesome and give bit-to-bit explanation of what's happening around. Thanks Jim for telling this technique!! It detected lots of bugs.
Final code:- http://ideone.com/TKUD2.
It's working on my test cases now, if anyone finds test cases where it fails, please post!!thanks..:)

sorry.. remove "." in above url... its

http://ideone.com/TKUD2
Was This Post Helpful? 0
  • +
  • -

#6 jimblumberg  Icon User is online

  • member icon


Reputation: 4018
  • View blog
  • Posts: 12,402
  • Joined: 25-December 09

Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:35 AM

Why not just post your code in your post, inside code tags?

Spoiler


Jim

This post has been edited by jimblumberg: 11 September 2012 - 10:35 AM

Was This Post Helpful? 0
  • +
  • -

#7 vikrantiitr_1  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 11-July 12

Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:37 AM

i am not getting edit option...where is it??
Was This Post Helpful? 0
  • +
  • -

#8 jimblumberg  Icon User is online

  • member icon


Reputation: 4018
  • View blog
  • Posts: 12,402
  • Joined: 25-December 09

Re: Shortest path using BFS in graph

Posted 11 September 2012 - 10:43 AM

You need a few more posts before you can edit your posts. I did add your code to my last post, click on the spoiler button.

Jim
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1