Click here to Skip to main content
16,020,249 members
Please Sign up or sign in to vote.
1.00/5 (2 votes)
See more:
hi all , i`m trying to find all paths between two nodes in directed graph here is my code BUT it didn`t work correctly .. could any one help me to fix it
thanks in advance.


C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
//using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Collections.Specialized;
using System.Collections;

namespace Direct_Graph
{
  class Program
  {
    public class Digraph
    {
      private readonly int _v; //The number of vertices
      private int _e; //The number of edges
      private LinkedList<int>[] adj; //Use a LinkedList for the adjacency-list representation

      //Create a new directed graph with V vertices
      public Digraph(int V)
      {
        if (V < 0)
          throw new Exception("Number of vertices in a Digraph must be nonnegative");
          
        this._v = V;
        this._e = 0;
        //Create a new adjecency-list for each vertex
        adj = new LinkedList<int>[V];
        for (int v = 0; v < V; v++)
        {
          adj[v] = new LinkedList<int>();
        }
      }

      //return the number of vertices
      public int V()
      {
        return _v;
      }

      //return the number of edges
      public int E()
      {
        return _e;
      }

      //Add an edge to the directed graph from v to w
      public void AddEdge(int v, int w)
      {
        if (v < 0 || v >= _v) 
          throw new Exception("vertex " + v + " is not between 0 and " + (_v - 1));
        if (w < 0 || w >= _v)
          throw new Exception("vertex " + w + " is not between 0 and " + (_v - 1));
        
        adj[v].AddFirst(w);
        _e++;
      }

      /*
        * Return the adjacency-list for vertex v, which
        * are the vertices connected to v pointing from v
      * */
      public LinkedList<int> Adj(int v)
      {
        if (v < 0 || v >= _v) 
          throw new Exception();
      
        return adj[v];
      }

       //Return the directed graph as a string
       public String toString()
       {
         StringBuilder s = new StringBuilder();
         String NEWLINE = Environment.NewLine;
         //s.Append(_v + " vertices, " + _e + " edges " + NEWLINE);
         for (int v = 0; v < _v; v++)
         {
           s.Append(String.Format("{0:d}: ", v));
           foreach (int w in adj[v])
           {
             s.Append(String.Format("{0:d} ", w));
           }
           s.Append(NEWLINE);
         }
         return s.ToString();
       }
     }
  
    public class Search
    {
      int START;
      int END;

      public void DepthFirstSearch(Digraph graph, LinkedList<int> visited)
      {
        // int v = visited.Last();
                
        LinkedList<int> nodes = graph.Adj(visited.Last());
               
        // examine adjacent nodes
        foreach (int node in nodes)
        {
          if (visited.Contains(node))
            continue;

          if (node == END)
          {
            visited.AddFirst(node);
            printPath(visited);
            visited.RemoveLast();
            break;
          }
        }

        // in breadth-first, recursion needs to come after visiting adjacent nodes
        foreach (int node in nodes)
        {
          if (visited.Contains(node) || node == END)
            continue;
 
          visited.AddLast(node);
          DepthFirstSearch(graph, visited);
          visited.RemoveLast();
        }
      }

      public void printPath(LinkedList<int> visited)
      {
        foreach (int node in visited)
        {
          Console.Write(node);
          Console.Write(" ");
        }
        Console.WriteLine();
      }
    }

    static void Main(string[] args)
    {
      int START = 3;
      int END = 8;

      Digraph dg = new Digraph(30);

      dg.AddEdge(3, 4);
      dg.AddEdge(4, 8);
      dg.AddEdge(4, 11);
      dg.AddEdge(11, 14);
      dg.AddEdge(11, 17);
      dg.AddEdge(11, 8);
      dg.AddEdge(14, 8);
      dg.AddEdge(14, 17);
      dg.AddEdge(14, 25);
      dg.AddEdge(17, 22);
      dg.AddEdge(17, 25);
      dg.AddEdge(25, 8);
      dg.AddEdge(22, 25);
             
      LinkedList<int> visited = new LinkedList<int>();
      visited.AddFirst(START);
      Search s = new Search();
      s.DepthFirstSearch(dg, visited);
      s.printPath(visited);
    }
  }
}
Posted
Updated 5-Jul-14 16:50pm
v2
Comments
George Jonsson 5-Jul-14 22:53pm    
What is not working?
You need to give more information and tell us where it goes wrong.
George Jonsson 5-Jul-14 23:30pm    
One pointer.
public class Search
{
int START; // Should be initialized
int END; // Should be initialized
Member 10926769 6-Jul-14 19:22pm    
the problem is that it should give the following paths as output
3 4 8 , 3 4 11 8 , 3 4 11 14 17 22 25 8 ,3 4 11 14 25 8 , 3 4 11 17 22 25 8
3 4 11 14 17 25 8 , 3 4 11 17 25 8 , 3 4 11 14 8

BUT it ONLY give the start value 3
George Jonsson 6-Jul-14 23:00pm    
Use your debugger and you will see that you will never enter this code.
if (node == END)
{
visited.AddFirst(node);
printPath(visited);
visited.RemoveLast();
break;
}
What should be the initial value of END?
(And is homework done via Codeproject these dayas?)
Member 10926769 7-Jul-14 19:59pm    
it is not homework .. i`m making a project and need graph as input ... and i want to know how to find all paths between 2 graph nodes.
i`m asking for help because i use my debugger but didn`t recognize where is the error ... i don`t know why it works in wrong manner . can you help me in finding the error(why it didn`t return all paths).

 
Share this answer
 
v2
Comments
George Jonsson 6-Jul-14 23:04pm    
I suspect this is homework, so he has to fix the code at hand.
i`ve fixed the error .. Thank you all for trying to help me .
 
Share this answer
 
Comments
George Jonsson 7-Jul-14 23:39pm    
Would be nice to know what the problem was.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900