473,326 Members | 2,113 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Need HELP in Depth-First-Iterative Graph Traversal

I was given the pseudo code.. but i still cannot figure out how to do it... how can i find if the vertices are adjacent to the vertex on stack top? I know i have to have an array of true/false (to dictate if the vertex is being visited)...
Expand|Select|Wrap|Line Numbers
  1. dfs(v)
  2. {    create a stack s to store visited notes
  3.     s.push(v)
  4.     while(!s.isEmpty())
  5.     {
  6.         if(no unvisited vertices are adjacent to the vertex on stack top)
  7.         {
  8.              //need a method to peep at the top element
  9.              s.pop() //backtrack
  10.         }
  11.         else
  12.         {
  13.              select an unvisited vertex u adjacent to the vertex on stack top
  14.              s.push(u);
  15.              mark u as visited
  16.         }
  17.     }
  18.  
  19. }
Graph.java
Expand|Select|Wrap|Line Numbers
  1. public class Graph {
  2.     int        arraySize, graphSize;
  3.     ListNode    node[];
  4.  
  5.             boolean[] visited= new boolean[arraySize];
  6.  
  7.     public Graph() {    // constructor
  8.         arraySize = 10;
  9.         graphSize = 0;
  10.         node = new ListNode[arraySize];
  11.         for (int j=0; j<arraySize; j++) node[j] = null;
  12.     }
  13.     public Graph(int size) {    // constructor
  14.         arraySize = size;
  15.         graphSize = 0;
  16.         node = new ListNode[arraySize];
  17.         for (int j=0; j<arraySize; j++) node[j] = null;
  18.     }
  19.  
  20.     public boolean isEmpty() {
  21.         return graphSize == 0;
  22.     }
  23.     public boolean isFull() {        
  24.         return graphSize == arraySize;
  25.     }
  26.     public int getArraySize() {
  27.         return arraySize;
  28.     }
  29.     public int getGraphSize() {
  30.         return graphSize;
  31.     }
  32.  
  33.     public boolean insertNode(NodeRecord r) { 
  34.         int    j;
  35.  
  36.         if (isFull()) return false;
  37.         for (j=0; j<arraySize; j++)
  38.             if (node[j]==null) 
  39.                 break;
  40.         node[j] = new ListNode(r);
  41.         graphSize++;
  42.         return true;
  43.     }
  44.  
  45. //dfs method
  46. public boolean insertEdge(int nodeID, EdgeRecord e) { 
  47.      int    j;
  48.     for (j=0; j<arraySize; j++)
  49.         if (nodeID==((NodeRecord) node[j].getItem()).getID()) 
  50.     break;
  51.      if (j>=arraySize) return false;
  52.     node[j].setNext(new ListNode(e, node[j].getNext()));
  53.     return true;
  54.     } 
  55.     public void print() {
  56.         int        j;
  57.  
  58.       ListNode    link;
  59.  
  60.           System.out.println(graphSize + " nodes read");
  61.     for (j=0; j<graphSize; j++) {
  62.         System.out.print(node[j].getItem()+"-> ");
  63.         link = node[j].getNext();
  64.         while (link!=null) {
  65.              System.out.print(link.getItem());
  66.              link = link.getNext();
  67.         }
  68.         System.out.println();
  69.     }
  70.     }
  71. }
Record.java
Expand|Select|Wrap|Line Numbers
  1. public class Record implements Comparable {
  2.     protected int        ID;
  3.     protected String    name;
  4.  
  5.     public Record(int newID) {
  6.         ID = newID;
  7.         name = "";
  8.     }
  9.     public Record(int newID, String newName) {
  10.         ID = newID;
  11.         name = newName;
  12.     }
  13.     //set and get methods
  14.     public int compareTo(Object o) {
  15.          if (!(o  instanceof  Record) throw new IllegalArgumentException("Error: non-Record type object!");
  16.         Record        c = (Record) o;        
  17.         if (ID > c.ID) return 1;
  18.         if (ID < c.ID) return -1;
  19.         return 0;
  20.     }
  21.     public String  toString() {  // add to class Circle 
  22.              return getID()+" ";
  23.     }
  24. }
NodeRecord.java
Expand|Select|Wrap|Line Numbers
  1. public class NodeRecord extends Record {
  2.     public NodeRecord(int newID) {
  3.     super(newID);
  4.     }
  5.     public NodeRecord(int newID, String otherInfo) {
  6.     super(newID, otherInfo);
  7.     }
  8.     public int compareTo(Object o) {
  9.     if (!(o  instanceof  NodeRecord)) throw new IllegalArgumentException("Error: non-NodeRecord type object!");
  10.         NodeRecord    c = (NodeRecord) o;        
  11.         if (ID > c.ID) return 1;
  12.         if (ID < c.ID) return -1;
  13.         return 0;
  14.     }
  15. }
EdgeRecord.java
Expand|Select|Wrap|Line Numbers
  1. public class EdgeRecord extends Record {
  2.     public EdgeRecord(int newconnectedTo) {
  3.         super(newconnectedTo);
  4.     }
  5.     public EdgeRecord(int newConnectedTo, String newOtherInfo) {
  6.         super(newConnectedTo, newOtherInfo);
  7.     }
  8.     public int getConnectedTo() {
  9.         return ID;
  10.     }
  11.     public String getOtherInfo() {
  12.         return name;
  13.     }
  14.     public EdgeRecord setConnectedTo(int newconnectedTo) {
  15.         ID = newconnectedTo;
  16.         return this;
  17.     }
  18.     public EdgeRecord setotherInfo(String newOtherInfo) {
  19.         name = newOtherInfo;
  20.         return this;
  21.     }
  22.      public int compareTo(Object o) {
  23.     if (!(o  instanceof  EdgeRecord)) throw new IllegalArgumentException("Error: non-EdgeRecord type object!");
  24.         EdgeRecord    c = (EdgeRecord) o;        
  25.         if (ID > c.ID) return 1;
  26.         if (ID < c.ID) return -1;
  27.         return 0;
  28.     }
  29.  
  30. }
Stack.java
Expand|Select|Wrap|Line Numbers
  1. public class Stack extends List {
  2.  
  3.     public Stack() {    
  4.         super();
  5.     }
  6.  
  7.     public boolean push(Object newItem) {
  8.         return insert(1, newItem);
  9.     }
  10.  
  11.     public Object pop() {
  12.         return remove(1);
  13.     }
  14.  
  15.         public Object peek(){
  16.  
  17.         return super.getItem(super.size());
  18.     }
  19.  
  20. }
Oct 22 '07 #1
2 2445
r035198x
13,262 8TB
Bart's article should be able to give you some valuable pointers.
Oct 22 '07 #2
I have changed my code a little.. I managed to do a little dfs.. but i am unable to get the value of the top item on the stack...

Graph.java
Expand|Select|Wrap|Line Numbers
  1. public class Graph {
  2.     int        arraySize, graphSize;
  3.         int row=0,col=0;
  4.     ListNode    node[];
  5.         int[][] matrix;
  6.  
  7.             boolean[] visited;
  8.  
  9.     public Graph() {    // constructor
  10.         arraySize = 10;
  11.         graphSize = 0;
  12.         node = new ListNode[arraySize];
  13.         for (int j=0; j<arraySize; j++) node[j] = null;
  14.  
  15.     }
  16.     public Graph(int size) {    // constructor
  17.         arraySize = size;
  18.         graphSize = 0;
  19.         node = new ListNode[arraySize];
  20.         for (int j=0; j<arraySize; j++) node[j] = null;
  21.                 row=size;col=size;
  22.                 matrix = new int[row][col];
  23.                  for(int i=0;i<row;i++)
  24.                 {
  25.                     for(int j=0;j<col;j++)
  26.                         matrix[i][j]=0;
  27.                 }
  28.     }
  29.  
  30.     public boolean isEmpty() {
  31.         return graphSize == 0;
  32.     }
  33.     public boolean isFull() {        
  34.         return graphSize == arraySize;
  35.     }
  36.     public int getArraySize() {
  37.         return arraySize;
  38.     }
  39.     public int getGraphSize() {
  40.         return graphSize;
  41.     }
  42.  
  43.     public boolean insertNode(NodeRecord r) { 
  44.         int    j;
  45.  
  46.         if (isFull()) return false;
  47.         for (j=0; j<arraySize; j++)
  48.             if (node[j]==null) 
  49.                 break;
  50.         node[j] = new ListNode(r);
  51.         graphSize++;
  52.         return true;
  53.     }
  54.  
  55.         public boolean insert(int node, int connectedNode) //using this insert method
  56.         {
  57.             if(node>matrix.length || connectedNode>matrix[node].length)
  58.                 return false;
  59.             matrix[node][connectedNode]=1;
  60.             matrix[connectedNode][node]=1;
  61.             return true;
  62.         }
  63.  
  64.         public void dfs(int nodeID)
  65.         {
  66.             int j=0;
  67.            visited = new boolean[row];
  68.             Stack s= new Stack();
  69.             for(int i=0;i<row;i++)
  70.                 visited[i]=false;
  71.          s.push(nodeID);
  72.             visited[nodeID]=true;
  73.             while(!s.isEmpty())
  74.             {
  75.  
  76.                while(j<col) 
  77.                {
  78.                  //s.peek() keep returning me 0...
  79.                    int element = Integer.parseInt(s.peek().toString());
  80.                    s.push(element);
  81.                     if(visited[j]==true && matrix[element][j]==0)
  82.                     {
  83.                        //if(j!=nodeID)
  84.                         //{
  85.                              System.out.println(element);
  86.                             s.pop();
  87.                         //}
  88.  
  89.                     }
  90.                     else
  91.                     {
  92.                         if(matrix[element][j]==1)
  93.                             s.push(j);
  94.                             visited[j]=true;
  95.  
  96.  
  97.                    }
  98.                    j++;
  99.  
  100.                }
  101.             }
  102.  
  103.         }
  104.  
  105.  
  106.     public void print() {
  107.         for(int i=0;i<row;i++)
  108.                 {
  109.                     for(int j=0;j<col;j++)
  110.                     {
  111.                         System.out.print(matrix[i][j]+" ");
  112.                     }
  113.                     System.out.println();
  114.                 }
  115.     }
  116. }
Stack.java
Expand|Select|Wrap|Line Numbers
  1. public class Stack extends List {
  2.    // int i=0;
  3.     public Stack() {    
  4.         super();
  5.     }
  6.  
  7.     public boolean push(Object newItem) {
  8.            // if(super.size()==0)
  9.         return insert(1, newItem);
  10.             //else
  11.               //  return insert(super.size()+1,newItem);
  12.  
  13.     }
  14.  
  15.     public Object pop() {
  16.         return remove(1);
  17.     }
  18.  
  19.     public Object peek()
  20.     {
  21.         //am i right here?
  22.         return super.getItem(super.size());
  23.     }
  24. }
Oct 23 '07 #3

Sign in to post your reply or Sign up for a free account.

Similar topics

2
by: Raed Sawalha | last post by:
I have following XML: How can I find the depth of XML? in other word max level of the XML <Root> ----- level 0 <Name>----- level 1 <FirstName>name</FirstName> ---- level 2...
4
by: Jani Yusef | last post by:
I want to create a tree of processes. The depth of the tree is given by the variable depth and the number of processes started by each node is given by the variable numberOfProcesses. Is the...
2
by: Michael Ramey | last post by:
Hi, Is there any easy way to get the number of nested folders for a given path. for instance I have the following (trying my best to simulate a view you would see in windows explorer) c:\temp...
4
by: David | last post by:
I have a problem that just cropped up with using an ImageList in my project I am using VB .NET 200 Problem: I have existing Form with 2 Image List controls. ImageList16 (for 16x16 Images) and...
8
by: darrel | last post by:
I've decided that instead of doing an XSLT transformation on a file, I might be better off bringing it in as a dataset and having a bit more direct control over it at that point. The question I...
6
by: datamodel | last post by:
Hello I have an XML tree of which you can see a mini-version here: http://paste.uni.cc/11838 (the tree is actually over 30,000 levels deep) How do I count the depth of a given...
5
by: Daz01 | last post by:
Hi, Ive written a program. But I want to add a class in it somehow? Is there any easy way to do it. Below is the code for the program: #include <cstdlib> #include <iostream> using...
13
by: softwaredoug | last post by:
I can't see to easily find this on google or in a newsgroup Is there a standard function/macro/whatever you can call and determine the distance in a C program how deep one is in the C call stack...
3
by: =?Utf-8?B?SmF5IFZpbnRvbg==?= | last post by:
I see general messages about how to learn .NET but I have an immediate requirement to ramp up my old skills very quickly. Can anyone recommend the FASTEST way for me to get almost-competent in...
9
by: pereges | last post by:
Hello I need some ideas for designing a recursive function for my ray tracing program. The idea behind ray tracing is to follow the electromagnetic rays from the source, as they hit the...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.