1. Member
Join Date
Mar 2011
Posts
27
Rep Power
0

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 ]

Java 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.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
Java Code:
import java.util.Stack;

public class Graph {

private final int max_v = 20;
private Vertex vertexList[]; // list of vertices
private int nVerts; // current number of vertices
private Stack theStack;
private Queue theQueue;
// ----------------------------------------------------------- //

public Graph() // constructor
{
vertexList = new Vertex[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
{
}
}
theStack = new Stack();
}
// ----------------------------------------------------------- //

vertexList[nVerts++] = new Vertex(lab);
}
// ----------------------------------------------------------- //

public void addEdge(int start, int end) {
}
// ------------------------------------------------------------ //

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
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

for (int j = 0; j < nVerts; j++) {
if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
return j;
}
}
return -1;
// ------------------------------------------------------------ //

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
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
Java 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

2. help me to solve the " two red lines "
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.

3. Member
Join Date
Mar 2011
Posts
27
Rep Power
0
,
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 !

Java Code:
public void creatGraph() throws IOException, FileNotFoundException {
String fileName;
StringTokenizer tok;
int index;
int vertex;
if (gSize != 0) {
clearGraph();
}
System.out.print("Enter input file name");
System.out.println();
for (int i = 0; i < gSize; i++) {
vertex = Integer.parseInt(tok.nextToken());
}

}
}

4. 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.

Java Code:
vertex = Integer.parseInt(tok.nextToken());
vs
Java 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.

5. Member
Join Date
Mar 2011
Posts
27
Rep Power
0
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.

6. 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.

7. Member
Join Date
Mar 2011
Posts
27
Rep Power
0
ok i will , and i'll come back with my new try ^^
thx bro

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•