• 06-06-2011, 12:33 PM
SHE
Hi ya ,
how are you !
am try to implement a Graph ! but i really faced problem .
I wanna read from file described the graph file as follow:
The first line of input contains 2 integers A and B where A is the number of nodes in the graph AND The B input lines describe the edges.

Each edge is described by two integers v and u indicating that there is an edge from node v to node u

----------------

main methods reads the data from the input file and represents the graph as an adjacency matrix, [1]
and asks the user for a starting node and then calls the next two methods to traverse the graph.
[2]

Then i have use (dfs , bfs ) methods .

the last two methods work probley if i fixed the input , i will show you my work and please will you help me to solve the " two red lines " ,

[main Class ]

Code:

```     public static void main(String[] args) { //        try {         //Scanner input = new Scanner(new File("Matrix"));         //int size = input.nextInt();         Graph theGraph = new Graph();         //System.out.printf("%d", table[i][j]); //            while(input.hasNext()) //            { //                int a = input.nextInt();         theGraph.addVertex('A'); // 0 (start for dfs)         theGraph.addVertex('B'); // 1         theGraph.addVertex('C'); // 2         theGraph.addVertex('D'); // 3         theGraph.addVertex('E'); // 4         theGraph.addEdge(0, 1); // AB         theGraph.addEdge(1, 2); // BC         theGraph.addEdge(0, 3); // AD         theGraph.addEdge(3, 4); // DE         //theGraph.displayVertex(1);         System.out.print("Visits: ");         theGraph.dfs(); // depth-first search         System.out.println();         System.out.print("Visits: ");         theGraph.bfs(); // depth-first search         System.out.println(); //        } catch (Exception e) { //            System.out.println();     }```
Graph
Code:

``` import java.util.Stack; public class Graph {     private final int max_v = 20;     private Vertex vertexList[]; // list of vertices     private int adjMat[][]; // adjacency matrix     private int nVerts; // current number of vertices     private Stack theStack;     private Queue theQueue; // ----------------------------------------------------------- //     public Graph() // constructor     {         vertexList = new Vertex[max_v]; // adjacency matrix         adjMat = new int[max_v][max_v];         nVerts = 0;         for (int j = 0; j < max_v; j++) // set adjacency         {             for (int k = 0; k < max_v; k++) // matrix to 0             {                 adjMat[j][k] = 0;             }         }         theStack = new Stack();     } // ----------------------------------------------------------- //     public void addVertex(char lab) {         vertexList[nVerts++] = new Vertex(lab);     } // ----------------------------------------------------------- //     public void addEdge(int start, int end) {         adjMat[start][end] = 1;         adjMat[end][start] = 1;     } // ------------------------------------------------------------ //     public void displayVertex(int v) {         System.out.print(vertexList[v].label);     } // ------------------------------------------------------------ //     public void dfs() // depth-first search     { // begin at vertex 0         vertexList[0].wasVisited = true; // mark it         displayVertex(0); // display it         theStack.push(0); // push it         while (!theStack.isEmpty()) // until stack empty,         { // get an unvisited vertex adjacent to stack top             int v = getAdjUnvisitedVertex((Integer) theStack.peek());             if (v == -1) // if no such vertex,             {                 theStack.pop();             } else // if it exists,             {                 vertexList[v].wasVisited = true; // mark it                 displayVertex(v); // display it                 theStack.push(v); // push it             }         } // end while // stack is empty, so we’re done         for (int j = 0; j < nVerts; j++) // reset flags         {             vertexList[j].wasVisited = false;         }     } // end dfs // ------------------------------------------------------------ // // returns an unvisited vertex adj to v     public int getAdjUnvisitedVertex(int v) {         for (int j = 0; j < nVerts; j++) {             if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {                 return j;             }         }         return -1;     } // end getAdjUnvisitedVertex() // ------------------------------------------------------------ //     public void bfs() // breadth-first search     { // begin at vertex 0         vertexList[0].wasVisited = true; // mark it         displayVertex(0); // display it         theQueue.insert(0); // insert at tail         int v2;         while (!theQueue.isEmpty()) // until queue empty,         {             int v1 = theQueue.remove(); // remove vertex at head // until it has no unvisited neighbors             while ((v2 = getAdjUnvisitedVertex(v1)) != -1) { // get one,                 vertexList[v2].wasVisited = true; // mark it                 displayVertex(v2); // display it                 theQueue.insert(v2); // insert it             } // end while(unvisited neighbors)         } // end while(queue not empty) // queue is empty, so we’re done         for (int j = 0; j < nVerts; j++) // reset flags         {             vertexList[j].wasVisited = false;         }     } // end bfs()     public void mst() // minimum spanning tree (depth first)     { // start at 0         vertexList[0].wasVisited = true; // mark it         theStack.push(0); // push it         while (!theStack.isEmpty()) // until stack empty         { // get stack top             int currentVertex = (Integer)theStack.peek(); // get next unvisited neighbor             int v = getAdjUnvisitedVertex(currentVertex);             if (v == -1) // if no more neighbors             {                 theStack.pop(); // pop it away             } else // got a neighbor             {                 vertexList[v].wasVisited = true; // mark it                 theStack.push(v); // push it // display edge                 displayVertex(currentVertex); // from currentV                 displayVertex(v); // to v                 System.out.print(""); } } // end while(stack not empty) // stack is empty, so we’re done for(int j=0; j < nVerts; j++) // reset flags         {             vertexList[j].wasVisited = false;         }     } // end mst() }```
VERTICES
Code:

``` public class Vertex { public char label; // label (e.g. ‘A’) public boolean wasVisited; public Vertex(char lab) // constructor { label = lab; wasVisited = false; }```

AND ALSO THERE IS QUEUE CLASS :)-:
• 06-06-2011, 01:43 PM
Norm
Quote:

help me to solve the " two red lines "
Quote:

reads the data from the input file and represents the graph as an adjacency matrix
What is the algorithm for doing that? Do you have a design for how to program that?
Have you written any code to implement your design?
Show what your program does now and explain what is wrong with it and show what it should be.
• 06-06-2011, 09:30 PM
SHE
,
First of all thanx for your time ,
Look , this program work as following :
it is already create the adj Matrix .. but here just for test if other method are work or not. What i have to do now is
let program read from input file :
5
1 3 6
1 4 7 ... etc
and then implement these values in adj matrix .. and print the Graph as a Matrix
so i have problem with reading file and then implement and print the graph.

i found this method in my book , but am not sure if i can use it because am used to use scanner more , and to be honest i did not use BufferedReader before !

Code:

```    public void creatGraph() throws IOException, FileNotFoundException {         BufferedReader Keyboard = new BufferedReader(new InputStreamReader(System.in));         String fileName;         StringTokenizer tok;         int index;         int vertex;         int adjVert;         if (gSize != 0) {             clearGraph();         }         System.out.print("Enter input file name");         fileName = Keyboard.readLine();         System.out.println();         BufferedReader infile = new BufferedReader(new FileReader(fileName));         gSize = Integer.parseInt(infile.readLine());         for (int i = 0; i < gSize; i++) {             tok = new StringTokenizer(infile.readLine());             vertex = Integer.parseInt(tok.nextToken());             adjVert = Integer.parseInt(tok.nextToken());             while (adjVert != -999) {                 graph[vertex].addLast(adjVert);                 adjVert = Integer.parseInt(tok.nextToken());             }         }     }```
• 06-06-2011, 09:36 PM
Norm
Have you written a small test program to see how the BufferedReader class works?

Break these statements up into single steps, vs using the return from one method the feed another.
That will allow you to print out what was read and to test if there is a next token and to see its contents before using it.

Code:

```            tok = new StringTokenizer(infile.readLine());             vertex = Integer.parseInt(tok.nextToken());             adjVert = Integer.parseInt(tok.nextToken());```
vs
Code:

```String nextLine = infile.readLine();  // get next line from the file System.out.println("nxtLn=" + nextLine + "<");  // show the line for debug tok = new StringTokenizer(nextLine);  // use the line```
Also close the file when done using it.
• 06-06-2011, 09:51 PM
SHE
Quote:

Have you written a small test program to see how the BufferedReader class works?
in fact no , am familiar more with scanner because i used all times.
• 06-06-2011, 09:54 PM
Norm
I recommend that you do write a small simple program to read a file and print out what it reads before putting the code into your larger program.
• 06-06-2011, 09:58 PM
SHE
ok i will , and i'll come back with my new try ^^
thx bro