Results 1 to 7 of 7
  1. #1
    SHE
    SHE is offline Member
    Join Date
    Mar 2011
    Posts
    27
    Rep Power
    0

    Default Represent adj matrix

    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.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
    Java 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
    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. #2
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,891
    Rep Power
    25

    Default

    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. #3
    SHE
    SHE is offline Member
    Join Date
    Mar 2011
    Posts
    27
    Rep Power
    0

    Default

    ,
    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 {
            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());
                }
    
    
            }
        }

  4. #4
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,891
    Rep Power
    25

    Default

    Have you written a small test program to see how the BufferedReader class works?

    Comments on your coding technique:
    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:
                tok = new StringTokenizer(infile.readLine());
                vertex = Integer.parseInt(tok.nextToken());
                adjVert = 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. #5
    SHE
    SHE is offline Member
    Join Date
    Mar 2011
    Posts
    27
    Rep Power
    0

    Default

    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. #6
    Norm's Avatar
    Norm is offline Moderator
    Join Date
    Jun 2008
    Location
    Eastern Florida
    Posts
    17,891
    Rep Power
    25

    Default

    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. #7
    SHE
    SHE is offline Member
    Join Date
    Mar 2011
    Posts
    27
    Rep Power
    0

Similar Threads

  1. Replies: 4
    Last Post: 03-23-2011, 04:35 PM
  2. help in matrix
    By Engineer in forum New To Java
    Replies: 7
    Last Post: 10-06-2010, 02:26 PM
  3. represent Double as "" instead of 0.0 in .jsp page without javascript
    By Tokajac in forum JavaServer Pages (JSP) and JSTL
    Replies: 1
    Last Post: 08-07-2008, 03:49 PM
  4. Replies: 1
    Last Post: 08-07-2007, 07:13 AM
  5. Help with matrix
    By susan in forum New To Java
    Replies: 1
    Last Post: 08-07-2007, 05:37 AM

Posting Permissions

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