Print all path between given vertices

Print all path between given vertices

Here given code implementation process.

//C Program 
//Print all path between given vertices in a directed graph
//Start with Source and end with Destination node
#include <stdio.h>
#include <stdlib.h>

struct AjlistNode
{
  int vId;//Vertices id
  struct AjlistNode*next;
};

struct Graph
{
  int data; //node key value
  struct AjlistNode*next;
};

struct Stack
{
  int data;
  struct Stack*next;
};

int size; //number of nodes

//set node key value
void setData(struct Graph*node)
{
  if(node!=NULL && size>0)
  {
    int index=0;
    for(index;index<size;index++)
    {
      //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }else
  {
    printf("Vertic Node is Empty");
  }
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
  if(V<size && E <size)
  {
      //first create Adjacency node
    struct AjlistNode *newEdge=(struct AjlistNode*)malloc(
      sizeof(struct AjlistNode)
      );
    if(newEdge!=NULL)
    {

      newEdge->next=NULL;
      newEdge->vId=E;

      struct AjlistNode *temp=node[V].next;

      if(temp==NULL)
      {
        node[V].next=newEdge;

      }else
      {
          //Add node at last
        while(temp->next!=NULL)
        {
          temp=temp->next;
        }      
        temp->next=newEdge;          
      }
    }
    else
    {
      printf("\n Memory overflow");
    }
  }else
  {
      //not valid Vertices
    printf("Invalid Node Vertices %d  %d", V,E);
  }
}
//Display Adjacency list of vertex
void printGraph(struct Graph*node)
{
  if(node!=NULL)
  {
    struct AjlistNode *temp=NULL;
    for(int index=0;index<size;index++)
    {
      printf("\n Adjacency list of vertex %d  :",index);
      temp=node[index].next;
      while(temp!=NULL)
      {
        //temp->vId is graph node vertices
        //in this case temp->vId is same as 
        //node[temp->vId].data

        printf("  %d",node[temp->vId].data);
        temp=temp->next;
      }
    }
  }
  else
  {
    printf("Empty Graph");
  }
}
void push(struct Stack**root, int data)
{
  struct Stack *element=(struct Stack*)malloc(
    sizeof(struct Stack)
    );

  if(element!=NULL)
  {
    element->data=data;
    element->next=*root;
    *root=element;
  }
}
void pop(struct Stack**root)
{
  if(*root==NULL) return; //already empty
  struct Stack *temp=*root;
  *root=temp->next;
  temp->next=NULL;
  free(temp);
  temp=NULL;
}

//Display Path from source to destination
void printPath(struct Stack*temp)
{
  if(temp==NULL)
  {
    return;
  }
  printPath(temp->next);
  printf(" %d ",temp->data );
}



void showPath(int start,int end,int *visit,struct Graph*node,struct Stack**output){

 if(start >size 
  || end >size 
  || start<0 
  || end<0 
  || node==NULL)
 {
    //invalid input
  return ;
}


if(visit[start]==1)
{
    //base case
  return;

}else
{
    //add element into stack
  push(output,start);
}
if(start==end)
{
  printf("\n Node Path (");
  printPath(*output);
  printf(")");
}
visit[start]=1;

struct AjlistNode *temp=node[start].next;

while(temp!=NULL)
{
  showPath(temp->vId,end,visit,node,output); 

  temp=temp->next;
}
  //remove top element
pop(output);
  //reset the  value of visited node
visit[start]=0;

}


int main(){

  size=6;
  struct Graph*node=NULL;



  int *visit=(int*)calloc(size,sizeof(int));
  node=(struct Graph*)malloc(sizeof(struct Graph)*size);

  if(node==NULL)
  {
    printf("\n Memory overflow");
  }
  else
  {
    //First set node keys
    setData(node); 
    struct Stack*root=NULL;

    //Connected two node with Edges

    addEdge(node,0, 4); 
    addEdge(node,0, 3); 
    addEdge(node,1, 0); 
    addEdge(node,1, 2); 
    addEdge(node,1, 4); 
    addEdge(node,2, 4); 
    addEdge(node,2, 5); 
    addEdge(node,3, 4);
    addEdge(node,5, 4); 
    printGraph(node);

    //source 1
    //destination 4
    showPath(1,4,visit,node,&root);
  }  
  return 0;
}

Output

Adjacency list of vertex 0  :  4  3
 Adjacency list of vertex 1  :  0  2  4
 Adjacency list of vertex 2  :  4  5
 Adjacency list of vertex 3  :  4
 Adjacency list of vertex 4  :
 Adjacency list of vertex 5  :  4
 Node Path ( 1  0  4 )
 Node Path ( 1  0  3  4 )
 Node Path ( 1  2  4 )
 Node Path ( 1  2  5  4 )
 Node Path ( 1  4 )
//C++ program
//Print all path between given vertices in a directed graph
//Start with Source and end with Destination node
#include <iostream>
using namespace std;

struct AjlistNode
{
  int vId;//Vertices id
  struct AjlistNode*next;
};

struct Vertices
{
  int data; //node key value
  struct AjlistNode*next;
};
struct Stack
{
  int data;
  struct Stack*next;
};
class Graph
{
  Vertices *node;
  int size;//number of 
public:
  Graph(int);
  void set_data();
  void add_edge(int,int);
  void print_graph();
  void connect(int ,int );
  void push( Stack**, int );
  void display_path( Stack*);
  void show_path(int ,int ,int *, Stack**);
  void pop( Stack**);
  void all_paths(int ,int );
};
Graph::Graph(int size)
{
  this->size = size;
    //set number of nodes
  node = new Vertices[size];
}
//set node key value
void Graph:: set_data()
{
  if(node!=NULL)
  {
    int index=0;

    for(index;index<size;index++)
    {
      //set vertic node data
      node[index].data=index;//set node key
      //Initial no AjlistNode
      //set NULL Value
      node[index].next=NULL;
    }
  }
  else
  {
    cout<<"Vertic Node is Empty"<<endl;
  }
}
//Add Edge from Two given Nodes
void Graph ::connect(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
    //first create Adjacency node
  AjlistNode *newEdge=new AjlistNode;

  if(newEdge!=NULL)
  {

    newEdge->next=NULL;
    newEdge->vId=E;

    AjlistNode *temp=node[V].next;

    if(temp==NULL)
    {
      node[V].next=newEdge;
    }else
    {
            //Add node at last
      while(temp->next!=NULL)
      {
        temp=temp->next;
      }      
      temp->next=newEdge;          
    }
  }

}


void Graph ::add_edge(int V ,int E)
{
    //add edge form V to E
    //V and E is Node location
  if(V<size && E <size)
  {
    connect(V,E);

  }else
  {
        //not valid Vertices
    cout<<"Invalid Node Vertices "<< V<<" "<<E;
  }
}

//Display Adjacency list of vertex
void Graph::print_graph()
{
  if(node!=NULL)
  {
    AjlistNode *temp=NULL;
    for(int index=0; index < size; index++)
    {
      cout<<"\n Adjacency list of vertex "<<index<<" :";
      temp=node[index].next;
      while(temp!=NULL)
      {
        //temp->vId is graph node vertices
        //in this case temp->vId is same as 
        //node[temp->vId].data

        cout<<" "<<node[temp->vId].data;
        temp=temp->next;
      }
    }
  }else
  {
    cout<<"Empty Graph"<<endl;
  }
}

void Graph:: push( Stack**root, int data)
{
  Stack *element= new Stack();
  if(element!=NULL)
  {
    element->data=data;
    element->next=*root;
    *root=element;
  }
}

void Graph:: pop( Stack**root)
{
  if(*root==NULL)
  {
    return; //already empty
  }
  Stack *temp=*root;
  *root=temp->next;
  delete(temp);
  temp=NULL;
}
//Display Path from source to destination
void Graph:: display_path( Stack*temp)
{
  if(temp==NULL)
  {
    return;
  }
  display_path(temp->next);
  cout<<"  "<<temp->data;
}
void Graph:: show_path(int start,int end,int *visit, Stack**output)
{
  if(start >size 
    || end >size 
    || start<0 
    || end<0 
    || node==NULL)
  {
       //invalid input
    return ;
  }
  if(visit[start]==1)
  {
      //base case
    return;
  }else
  {
    //add element into stack
    push(output,start);
  }
  if(start==end)
  {
    cout<<("\n Node Path (");
    display_path(*output);
    cout<<(")");
  }
  visit[start]=1;
  AjlistNode *temp=node[start].next;

  while(temp!=NULL)
  {
    show_path(temp->vId,end,visit,output); 

    temp=temp->next;
  }
  //remove top element
  pop(output);
  //reset the  value of visited node
  visit[start]=0;
}

void Graph:: all_paths(int source,int destination)
{
  if(node==NULL)
  {
    return;
  }
  int *visit=new int[size];
  Stack*root=NULL;
  for (int i = 0; i < size; ++i)
  {
    visit[i]=0;
  }
  show_path(source,destination,visit,&root);
  delete visit;
  visit=NULL;
}
int main()
{
  //Create Object
  Graph g=Graph(6);
  //First set node keys
  g.set_data();

  g.add_edge(0, 4); 
  g.add_edge(0, 3); 
  g.add_edge(1, 0); 
  g.add_edge(1, 2); 
  g.add_edge(1, 4); 
  g.add_edge(2, 4); 
  g.add_edge(2, 5); 
  g.add_edge(3, 4);
  g.add_edge(5, 4); 
  g.print_graph();
  g.all_paths(1,4);

  return 0;
}

Output

 Adjacency list of vertex 0  :  4  3
 Adjacency list of vertex 1  :  0  2  4
 Adjacency list of vertex 2  :  4  5
 Adjacency list of vertex 3  :  4
 Adjacency list of vertex 4  :
 Adjacency list of vertex 5  :  4
 Node Path ( 1  0  4 )
 Node Path ( 1  0  3  4 )
 Node Path ( 1  2  4 )
 Node Path ( 1  2  5  4 )
 Node Path ( 1  4 )
//Java program
//Print all path between given vertices in a directed graph
//Start with Source and end with Destination node
public class MyGraph
{

  static class AjlistNode
  {
    int id;//Vertices node key
    AjlistNode next;
  }
  static class Vertices
  {
    int data;
    AjlistNode next;
  }
  static class Stack
  {
    int data;
    Stack next;
  };

  //number of Vertices
  public  int size;
  public Stack output;
  public Vertices []node;

  MyGraph(int size)
  {
        //set value
    this.size = size;
    output=null;
    node = new Vertices[size];

  }

    //set initial node value
  public void set_data()
  {
    if(node == null)
    {
      System.out.println("\nEmpty Graph");
    }else
    {
      for(int index = 0; index < size; index++)
      {
                // avoid java.lang.nullPointerException
        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null;
      }
    }
  }
    //connect two nodes
  public void connect(int start,int end)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    if(node[start].next==null)
    {
      node[start].next=newEdge;
    }else
    {
      AjlistNode temp=node[start].next;

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=newEdge;
    }
  }
    //Add edge at the end
  public void add_edge(int start,int end)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end);

    }
    else{
      System.out.println("\nInvalid nodes "+start+" "+end);
    }
  }

  public void print_graph()
  {

    if(size>0 && node!=null)
    {
      for(int index=0;index<size;index++)
      {
        System.out.print("\nAdjacency list of vertex "+index+" :");

        AjlistNode temp=node[index].next;

        while(temp!=null)
        {
          System.out.print(" "+node[temp.id].data);

          temp=temp.next;
        }
      }
    }
  }

public void  push(int data)
{
  Stack  element= new Stack();
  if(element!=null)
  {
    element.data=data;
    element.next= output;
    output=element;
  }
}

public void pop()
{
  if( output==null)
  {
    return; //already empty
  }
  Stack  temp= output;
  output=temp.next;
  temp=null;
}
//Display Path from source to destination
public void  display_path( Stack temp)
{
  if(temp==null)
  {
    return;
  }
  display_path(temp.next);
  System.out.print("  "+temp.data);
}
public void  show_path(int start,int end,boolean  []visit)
{
  if(start >size 
    || end >size 
    || start<0 
    || end<0 
    || node==null)
  {
       //invalid input
    return ;
  }
  if(visit[start]==true)
  {
    //base case
    return;
  }
  else
  {
    //add element into stack
    push(start);
  }
  if(start==end)
  {
    System.out.print("\n Node Path (");
    display_path( output);
    System.out.print(")");
  }
  visit[start]=true;
  AjlistNode temp=node[start].next;

  while(temp!=null)
  {
    show_path(temp.id,end,visit); 

    temp=temp.next;
  }
  //remove top element
  pop();
  //reset the  value of visited node
  visit[start]=false;
}

public void  all_paths(int source,int destination)
{
  if(node==null)
  {
    return;
  }
  boolean  []visit=new boolean[size];
  //stack result
  output=null;

  for (int i = 0; i < size; ++i)
  {
    visit[i]=false;
  }
  show_path(source,destination,visit);
  
}


  public static void main(String[] args) 
  {
    int totalNode=6;

    MyGraph g=new MyGraph(totalNode);
    g.set_data();


    g.add_edge(0, 4); 
    g.add_edge(0, 3); 
    g.add_edge(1, 0); 
    g.add_edge(1, 2); 
    g.add_edge(1, 4); 
    g.add_edge(2, 4); 
    g.add_edge(2, 5); 
    g.add_edge(3, 4);
    g.add_edge(5, 4); 
    g.print_graph();
    g.all_paths(1,4);

  }
}

Output

Adjacency list of vertex 0 : 4 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 4 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Node Path (  1  0  4)
 Node Path (  1  0  3  4)
 Node Path (  1  2  4)
 Node Path (  1  2  5  4)
 Node Path (  1  4)
#Python program
#Print all path between given vertices in a directed graph
#Start with Source and end with Destination node

class AjLinkeNode:
  def __init__(self,data):
    self.key=data
    self.next=None

class Vertices:
  def __init__(self,data):
    self.data=data
    self.next=None

class Stack:
  def __init__(self,data):
    self.data=data
    self.next=None

    
class Graph:

  def __init__(self,size):
    self.size=size
    self.node=[]
    self.output = None
    

  def set_data(self):
    if(self.size>0 and self.node!=None):
      index=0
      while(index<self.size):
        self.node.append(Vertices(index))
        index+=1


  #connect two node with  edge
  def connect(self,start,end):
    new_edge=AjLinkeNode(end)
    if(self.node[start].next==None):
      self.node[start].next=new_edge
    else:
      temp=self.node[start].next
      while(temp.next!=None):
        temp=temp.next
      temp.next=new_edge  

  #add edge
  def add_edge(self,start,end):

    #start,end is two nodes
    if(self.size>start and self.size>start):
      
      self.connect(start,end)
  
    else:
      print("Invalid nodes")


  def print_graph(self):

    if(self.size>0 and self.node!=None):

      index=0

      while(index<self.size):

        print("\nAdjacency list of vertex  {0} :".format(index),end=" ")
        
        temp=self.node[index].next
        
        while temp!=None:

          print(" {0}".format(temp.key),end=" ")

          temp=temp.next

        index+=1

  
 
  def  push(self,data) :

    element= Stack(data)
    if(element!=None) :

      element.next=self.output
      self.output= element
  def  pop(self) :

    if(self.output==None) :

      return# already empty
    temp=self.output
    self.output= temp.next
    temp=None
  #Display Path from source to destination
  def  display_path(self,temp) :

    if(temp==None) :

      return
    self.display_path(temp.next)
    print (temp.data, end=" ")
  def  show_path(self,start,end,visit) :

    if(start>self.size 
      or  end>self.size 
      or  start<0 
      or  end<0 
      or  self.node==None) :

      #invalid input
      return 
    if(visit[start]==True) :

      #base case
      return
    else :

      #add element into stack
      self.push(start)
    if(start==end) :

      print ("\n Node Path(",end=" ")
      self.display_path(self.output)
      print (")")
    visit[start]=True
    temp= self.node[start].next
    while(temp!=None) :

      self.show_path(temp.key,end,visit) 
      temp=temp.next
    #remove top element
    self.pop()
    #reset the  value of visited node
    visit[start]=False
  def  all_paths(self,source,destination) :

    if(self.node==None) :

      return
    visit=[False]*self.size
    self.output=None
    self.show_path(source,destination,visit)
    visit=None

def main():
  g=Graph(6)

  #First set node keys
  g.set_data()
  g.add_edge(0, 4) 
  g.add_edge(0, 3) 
  g.add_edge(1, 0) 
  g.add_edge(1, 2) 
  g.add_edge(1, 4) 
  g.add_edge(2, 4) 
  g.add_edge(2, 5) 
  g.add_edge(3, 4)
  g.add_edge(5, 4) 
  g.print_graph()
  g.all_paths(1,4)

if __name__=="__main__":
    main()

Output

Adjacency list of vertex  0 :  4  3 
Adjacency list of vertex  1 :  0  2  4 
Adjacency list of vertex  2 :  4  5 
Adjacency list of vertex  3 :  4 
Adjacency list of vertex  4 : 
Adjacency list of vertex  5 :  4 
 Node Path( 1 0 4 )

 Node Path( 1 0 3 4 )

 Node Path( 1 2 4 )

 Node Path( 1 2 5 4 )

 Node Path( 1 4 )
//C# program
//Print all path between given vertices in a directed graph
//Start with Source and end with Destination node
using System;
public class AjlistNode
{
  public int id;//Vertices node key
  public AjlistNode next;
}
public class Vertices
{
  public int data;
  public AjlistNode next;
}
public class Stack
{
  public int data;
  public Stack next;
};
public class MyGraph
{



  //number of Vertices
  public  int size;
  public Stack output;
  public Vertices []node;

  MyGraph(int size)
  {
    //set value
    this.size = size;
    output=null;
    node = new Vertices[size];

  }

  //set initial node value
  public void set_data()
  {
    if(node == null)
    {
      Console.WriteLine("\nEmpty Graph");
    }else
    {
      for(int index = 0; index < size; index++)
      {
        // avoid java.lang.nullPointerException
        node[index]=new Vertices(); 
        node[index].data=index;//set your data
        node[index].next=null;
      }
    }
  }
  //connect two nodes
  public void connect(int start,int end)
  {
    AjlistNode newEdge=new AjlistNode();
    newEdge.id=end;//end node
    newEdge.next=null;
    if(node[start].next==null)
    {
      node[start].next=newEdge;
    }else
    {
      AjlistNode temp=node[start].next;

      while(temp.next!=null)
      {
        temp=temp.next;
      }
      temp.next=newEdge;
    }
  }
  //Add edge at the end
  public void add_edge(int start,int end)
  {
    if(start < size && end < size && node != null)
    {
      connect(start,end);

    }
    else{
      Console.WriteLine("\nInvalid nodes "+start+" "+end);
    }
  }

  public void print_graph()
  {

    if(size>0 && node!=null)
    {
      for(int index=0;index<size;index++)
      {
        Console.Write("\nAdjacency list of vertex "+index+" :");

        AjlistNode temp=node[index].next;

        while(temp!=null)
        {
          Console.Write(" "+node[temp.id].data);

          temp=temp.next;
        }
      }
    }
  }

  public void  push(int data)
  {
    Stack  element= new Stack();
    if(element!=null)
    {
      element.data=data;
      element.next= output;
      output=element;
    }
  }

  public void pop()
  {
    if( output==null)
    {
      return; //already empty
    }
    Stack  temp= output;
    output=temp.next;
    temp=null;
  }
  //Display Path from source to destination
  public void  display_path( Stack temp)
  {
    if(temp==null)
    {
      return;
    }
    display_path(temp.next);
    Console.Write("  "+temp.data);
  }
  public void  show_path(int start,int end,Boolean  []visit)
  {
    if(start >size 
      || end >size 
      || start<0 
      || end<0 
      || node==null)
    {
      //invalid input
      return ;
    }
    if(visit[start]==true)
    {
      //base case
      return;
    }
    else
    {
      //add element into stack
      push(start);
    }
    if(start==end)
    {
      Console.Write("\n Node Path (");
      display_path( output);
      Console.Write(")");
    }
    visit[start]=true;
    AjlistNode temp=node[start].next;

    while(temp!=null)
    {
      show_path(temp.id,end,visit); 

      temp=temp.next;
    }
    //remove top element
    pop();
    //reset the  value of visited node
    visit[start]=false;
  }

  public void  all_paths(int source,int destination)
  {
    if(node==null)
    {
      return;
    }
    Boolean  []visit=new Boolean[size];
    //stack result
    output=null;

    for (int i = 0; i < size; ++i)
    {
      visit[i]=false;
    }
    show_path(source,destination,visit);

  }


  public static void Main(String[] args) 
  {
    int totalNode=6;

    MyGraph g=new MyGraph(totalNode);
    g.set_data();


    g.add_edge(0, 4); 
    g.add_edge(0, 3); 
    g.add_edge(1, 0); 
    g.add_edge(1, 2); 
    g.add_edge(1, 4); 
    g.add_edge(2, 4); 
    g.add_edge(2, 5); 
    g.add_edge(3, 4);
    g.add_edge(5, 4); 
    g.print_graph();
    g.all_paths(1,4);

  }
}

Output

Adjacency list of vertex 0 : 4 3
Adjacency list of vertex 1 : 0 2 4
Adjacency list of vertex 2 : 4 5
Adjacency list of vertex 3 : 4
Adjacency list of vertex 4 :
Adjacency list of vertex 5 : 4
 Node Path (  1  0  4)
 Node Path (  1  0  3  4)
 Node Path (  1  2  4)
 Node Path (  1  2  5  4)
 Node Path (  1  4)
<?php 
/*
* PHP Program 
* Print all path between given vertices in a directed graph
* Start with Source and end with Destination node
*/

class AjlistNode
{
  public $key;
  public $next;
  function __construct($key)
  {
    $this->key=$key;
    $this->next=NULL;
  }
}
class Stack
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data=$data;
    $this->next=NULL;

  }
}
class Node
{
  public $data;
  public $next;
  function __construct($data)
  {
    $this->data=$data;
    $this->next=NULL;

  }
}
class MyGraph
{

  public $node;
  public $size;
  public $output;
  function __construct($size)
  {
    $this->size=$size;
    $this->node=[];  //empty array
    $this->output=NULL;
  }
  public function set_data()
  {
    if($this->size>0)
    {
      for($index=0;$index<$this->size;$index++)
      {
        $this->node[$index]=new Node($index);
      }

    }
  }
  public function connect($start,$end)
  {
    $newEdge=new AjlistNode($end);
    if($this->node[$start]->next==NULL)
    {
      $this->node[$start]->next=$newEdge;
    }
    else
    {

      $temp=$this->node[$start]->next;
      while($temp->next!=NULL)
      {
        $temp=$temp->next;
      }
      $temp->next= $newEdge;
    }
  }
  public function add_edge($start,$end)
  {
    if($this->size > $start && $this->size>$end)
    {
      $this->connect($start,$end);

    }
    else
    {
      echo "\n Invalid node";
    }
  }
  public function print_graph()
  {
    if($this->size>0 && count($this->node)>0 && $this->node!=NULL)
    {
      for($index=0;$index<$this->size;$index++)
      {
        echo ("\nAdjacency list of vertex ".$index." : ");
        $temp=$this->node[$index]->next;
        while($temp!=NULL)
        {
          echo (" ".$this->node[$temp->key]->data);
          $temp=$temp->next;
        }
      }
    }
  }


  
  public function push($data)
  {
    $element= new  Stack($data);
    if($element!=NULL)
    {
      $element->next=$this->output;
      $this->output= $element;
    }
  }
  
  public function pop()
  {
    if($this->output==NULL)
    {
      return;// $already $empty
    }
    $temp=$this->output;
    $this->output= $temp->next;

    $temp=NULL;
  }
//Display Path from source to destination
  public function display_path($temp)
  {
    if($temp==NULL)
    {
      return;
    }
    $this->display_path($temp->next);
    echo " ".$temp->data;
  }
  public function show_path($start,$end,&$visit)
  {
    if($start>$this->size 
     || $end>$this->size 
     || $start<0 
     || $end<0 
     || $this->node==NULL)
    {
       //invalid input
      return ;
    }
    if($visit[$start]==1)
    {
      //base case
      return;
    }else
    {
    //add element into stack
      $this->push($start);
    }
    if($start==$end)
    {
      echo ("\n Node Path(");
      $this->display_path($this->output);
      echo (")");
    }
    $visit[$start]=1;
    $temp= $this->node[$start]->next;

    while($temp!=NULL)
    {
      $this->show_path($temp->key,$end,$visit); 

      $temp=$temp->next;
    }
    //remove top element
    $this->pop();
    //reset the  value of visited node
    $visit[$start]=false;
  }
  
  public function all_paths($source,$destination)
  {
    if($this->node==NULL)
    {
      return;
    }
    $visit=array_fill(0, $this->size, false);
    $this->output=NULL;

    $this->show_path($source,$destination,$visit);
    $visit=NULL;
  }
}


function main()
{
    //create object
  $g=new MyGraph(6);
  //First set node keys
  $g->set_data();

  $g->add_edge(0, 4); 
  $g->add_edge(0, 3); 
  $g->add_edge(1, 0); 
  $g->add_edge(1, 2); 
  $g->add_edge(1, 4); 
  $g->add_edge(2, 4); 
  $g->add_edge(2, 5); 
  $g->add_edge(3, 4);
  $g->add_edge(5, 4); 
  $g->print_graph();
  $g->all_paths(1,4);


}
main();
?>

Output

Adjacency list of vertex 0 :  4 3
Adjacency list of vertex 1 :  0 2 4
Adjacency list of vertex 2 :  4 5
Adjacency list of vertex 3 :  4
Adjacency list of vertex 4 : 
Adjacency list of vertex 5 :  4
 Node Path( 1 0 4)
 Node Path( 1 0 3 4)
 Node Path( 1 2 4)
 Node Path( 1 2 5 4)
 Node Path( 1 4)


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved