Results 1 to 5 of 5
  1. #1
    daxter is offline Member
    Join Date
    May 2011
    Posts
    3
    Rep Power
    0

    Default Graph Problem Java Directed

    I have a problem of creating Data structers ,about directed graph

    The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.

    Input: A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.

    Output: For test input 1 through 5, if no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).

    1. The distance of the route A-B-C.
    2. The distance of the route A-D.
    3. The distance of the route A-D-C.
    4. The distance of the route A-E-B-C-D.
    5. The distance of the route A-E-D.
    6. The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
    7. The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
    8. The length of the shortest route (in terms of distance to travel from A to C.
    9. The length of the shortest route (in terms of distance to travel from B to B.
    10. The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.

    Test Input:

    For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.

    Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

    Expected Output:

    Output #1: 9
    Output #2: 5
    Output #3: 13
    Output #4: 22
    Output #5: NO SUCH ROUTE
    Output #6: 2
    Output #7: 3
    Output #8: 9
    Output #9: 9
    Output #10: 7


    Please send me source code (How to solve this problem in Java)

  2. #2
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,641
    Rep Power
    7

    Default

    Please send me source code
    Dumping a homework assignment then asking for a solution won't get you much help here (or in life), and isn't the purpose of these forums. Make an effort, post what you've done (preferably as an SSCCE within the code tags)with precise questions about your issue

  3. #3
    daxter is offline Member
    Join Date
    May 2011
    Posts
    3
    Rep Power
    0

    Default

    Thanks for you reply

    public class GraphRepresentation {

    private final List<Vertex> vertexes;
    private final List<Edge> edges;

    public GraphRepresentation(List<Vertex> vertexes, List<Edge> edges) {
    this.vertexes = vertexes;
    this.edges = edges;
    }

    public List<Vertex> getVertexes() {
    return vertexes;
    }

    public List<Edge> getEdges() {
    return edges;
    }


    }


    this is my graph class which add the list of vertex and edged between them

    private final int MAX_VERTS = 20;

    private final int INFINITY = 1000000;

    private final String NO_SUCH_ROUTE = "NO SUCH ROUTE";

    // list of vertices
    private Vertex vertexList[];

    // adjacency matrix
    private int adjMat[][];

    // current number of vertices
    private int numberOfVertex;

    // number of verts in tree
    private int numberOfVertexInTree;

    // array for shortest−calculateDistance data
    private DistPar sPath[];

    // current vertex
    private int currentVertex;

    // distance to currentVertex
    private int startToCurrent;

    public Graph() {

    vertexList = new Vertex[MAX_VERTS];
    // adjacency matrix
    adjMat = new int[MAX_VERTS][MAX_VERTS];
    numberOfVertex = 0;
    numberOfVertexInTree = 0;

    for (int j = 0; j < MAX_VERTS; j++) { // set adjacency
    for (int k = 0; k < MAX_VERTS; k++) { // matrix
    adjMat[j][k] = INFINITY; // to infinity
    }
    }
    sPath = new DistPar[MAX_VERTS]; // shortest paths
    }


    public void addVertex(char label) {
    vertexList[numberOfVertex++] = new Vertex(label);
    }

    public void addEdge(int start, int end, int weight) {
    adjMat[start][end] = weight; // (directed)
    }

    /*
    this method find all shortest calculateDistance
    */
    public void calculateDistance() {

    int startTree = 0; // start at vertex 0

    vertexList[startTree].isInTree = true;

    numberOfVertexInTree = 1; // put it in tree

    // transfer row of distances from adjMat to sPath
    for (int j = 0; j < numberOfVertex; j++) {
    int tempDist = adjMat[startTree][j];
    sPath[j] = new DistPar(startTree, tempDist);
    }

    // until all vertices are in the tree
    while (numberOfVertexInTree < numberOfVertex) {
    int indexMin = getMin(); // get minimum from sPath
    int minDist = sPath[indexMin].distance;

    if (minDist == INFINITY) // if all infinite
    { // or in tree,
    System.out.println("There are unreachable vertices");
    break; // sPath is complete
    } else { // reset currentVertex
    currentVertex = indexMin; // to closest vert
    startToCurrent = sPath[indexMin].distance;
    // minimum distance from startTree is
    // to currentVertex, and is startToCurrent
    }
    // put current vertex in tree
    vertexList[currentVertex].isInTree = true;
    numberOfVertexInTree++;
    adjust_sPath(); // update sPath[] array
    } // end while(numberOfVertexInTree<numberOfVertex)

    displayPaths(); // display sPath[] contents


    }





    public int getMin()
    {
    // with minimum distance
    int minDist = INFINITY; // assume minimum
    int indexMin = 0;

    for (int j = 1; j < numberOfVertex; j++) // for each vertex,
    {
    if (!vertexList[j].isInTree && sPath[j].distance < minDist) {
    minDist = sPath[j].distance;
    indexMin = j;
    }
    }
    return indexMin;
    }

    public void adjust_sPath() {
    //adjust values in shortest−calculateDistance array sPath
    int column = 1; // skip starting vertex

    while (column < numberOfVertex) // go across columns
    {
    // if this columns vertex already in tree, skip it
    if (vertexList[column].isInTree) {
    column++;
    continue;
    }
    // calculate distance for one sPath entry
    // get edge from currentVertex to column
    int currentToFringe = adjMat[currentVertex][column];
    // add distance from start
    int startToFringe = startToCurrent + currentToFringe;
    // get distance of current sPath entry
    int sPathDist = sPath[column].distance;
    // compare distance from start with sPath entry
    if (startToFringe < sPathDist) // if shorter,
    { // update sPath
    sPath[column].parentVertex = currentVertex;
    sPath[column].distance = startToFringe;
    }
    column++;
    }
    }

    public void displayPaths() {

    for (int j = 0; j < numberOfVertex; j++) // display contents of sPath[]
    {
    System.out.print(vertexList[j].label + " ="); // B=

    if (sPath[j].distance == INFINITY) {
    System.out.print(NO_SUCH_ROUTE);
    } else {
    System.out.print(sPath[j].distance); // 5
    }

    char parent = vertexList[sPath[j].parentVertex].label;
    System.out.print("(" + parent + ")"); // (A)
    }

    numberOfVertexInTree = 0; // clear tree
    for (int j = 0; j < numberOfVertex; j++) {
    vertexList[j].isInTree = false;
    }
    System.out.println("");
    }


    public void displayPaths(int startVertex ,int endVertex) {


    for (int j = 0; j < numberOfVertex; j++) {
    if(startVertex<endVertex){

    if(j == startVertex) {
    System.out.print(vertexList[j].label);
    } else if(j== endVertex){
    System.out.print(" - "+vertexList[j].label);
    System.out.print(" = "+sPath[j].distance);

    }
    } else {
    if(j== endVertex){
    System.out.print(vertexList[j].label);

    } else if(j == startVertex) {
    System.out.print(" - "+ vertexList[j].label);
    System.out.print(" = "+sPath[j].distance);
    }
    }

    }

    numberOfVertexInTree = 0; // clear tree
    for (int j = 0; j < numberOfVertex; j++) {
    vertexList[j].isInTree = false;
    }
    System.out.println("");
    }



    /*
    this method find all shortest calculateDistance
    */
    public void calculateDistance(int startVertex, int endVertex) {

    int startTree = 0; // start at vertex 0

    vertexList[startTree].isInTree = true;

    numberOfVertexInTree = 1; // put it in tree

    // transfer row of distances from adjMat to sPath
    for (int j = 0; j < numberOfVertex; j++) {
    int tempDist = adjMat[startTree][j];
    sPath[j] = new DistPar(startTree, tempDist);
    }

    // until all vertices are in the tree
    while (numberOfVertexInTree < numberOfVertex) {
    int indexMin = getMin(); // get minimum from sPath
    int minDist = sPath[indexMin].distance;

    if (minDist == INFINITY) // if all infinite
    { // or in tree,
    System.out.println("There are unreachable vertices");
    break; // sPath is complete
    } else { // reset currentVertex
    currentVertex = indexMin; // to closest vert
    startToCurrent = sPath[indexMin].distance;
    // minimum distance from startTree is
    // to currentVertex, and is startToCurrent
    }
    // put current vertex in tree
    vertexList[currentVertex].isInTree = true;
    numberOfVertexInTree++;
    adjust_sPath(); // update sPath[] array
    } // end while(numberOfVertexInTree<numberOfVertex)

    displayPaths(startVertex,endVertex); // display sPath[] contents

    numberOfVertexInTree = 0; // clear tree
    for (int j = 0; j < numberOfVertex; j++) {
    vertexList[j].isInTree = false;
    }
    }

    }

    this is the class which represent the distance from parent

    public class DistPar {

    // distance from start to this vertex
    public int distance;

    // current parent of this vertex
    public int parentVertex;

    public DistPar(int pv, int d) // constructor
    {
    distance = d;
    parentVertex = pv;
    }
    }



    My question is I neeed to write public void displayPaths(int startVertex ,int endVertex) method to full fill my test scenario

    PLease help me for this

    this is my test cases class

    public class PathApp {

    public static void main(String[] args) {
    Graph theGraph = new Graph();
    theGraph.addVertex('A'); // 0 (start)
    theGraph.addVertex('B'); // 1
    theGraph.addVertex('C'); // 2
    theGraph.addVertex('D'); // 3
    theGraph.addVertex('E'); // 4

    theGraph.addEdge(0, 1, 5); // AB 5
    theGraph.addEdge(1, 2, 4); // BC 4
    theGraph.addEdge(2, 3, 8); // CD 8
    theGraph.addEdge(3, 2, 8); // DC 8
    theGraph.addEdge(3, 4, 6); // DE 6
    theGraph.addEdge(0, 3, 5); // DE 6
    theGraph.addEdge(2, 4, 2); // CE 2
    theGraph.addEdge(3, 1, 3); // EB 3
    theGraph.addEdge(0, 4, 7); // AE 7

    System.out.println("shortest paths");


    //theGraph.calculateDistance();
    //A -B- C
    //theGraph.calculateDistance(0,1);
    // theGraph.calculateDistance(1,2);
    //A to D
    // theGraph.calculateDistance(0,3);
    //A-D-C
    //theGraph.calculateDistance(0,3);
    //theGraph.calculateDistance(3,2);
    //A-E-B-C-D
    theGraph.calculateDistance(0,4);
    theGraph.calculateDistance(4,1);
    theGraph.calculateDistance(1,2);
    theGraph.calculateDistance(2,3);

    //accoriding to the design this should be A-E-B-C-D ==22 but I am //getting 28

    //theGraph.(); // shortest paths


    System.out.println();
    } // end main()
    } // end class PathApp

  4. #4
    doWhile is offline Moderator
    Join Date
    Jul 2010
    Location
    California
    Posts
    1,641
    Rep Power
    7

    Default

    Like I said, preferably as an SSCCE and within the code tags. Its tough to read code without formatting such as that, especially a whopping volume of code such as that
    My question is I neeed to write public void displayPaths(int startVertex ,int endVertex) method to full fill my test scenario
    That's not a question, its a statement that is hard to address because we have no idea what that method is supposed to do, and it doesn't seem you've made an attempt (I say that based upon your statement above, as I'm not going to go through all that unformatted code to see). FWIW, I recommend reading the following link to help you receive feedback that directly addresses you needs:
    How To Ask Questions The Smart Way

  5. #5
    daxter is offline Member
    Join Date
    May 2011
    Posts
    3
    Rep Power
    0

    Default

    XML Code:
    herewith I have displayed my source code withing the code Tag
    Java Code:
    //DistPar.java
    public class DistPar {
    
        // distance from start to this vertex
        public int distance;
    
        // current parent of this vertex
        public int parentVertex;
    
        public DistPar(int pv, int d) // constructor
        {
            distance = d;
            parentVertex = pv;
        }
    }
    Java Code:
    //Vertex.java
    public class Vertex {
        public char label; 
        public boolean isInTree;
    
        public Vertex(char lab) // constructor
        {
            label = lab;
            isInTree = false;
        }
    }

    Java Code:
    public class Graph {
    
        private final int MAX_VERTS = 20;
    
        private final int INFINITY = 1000000;
    
        private final String NO_SUCH_ROUTE = "NO SUCH ROUTE";
    
        // list of vertices
        private Vertex vertexList[];
    
        // adjacency matrix
        private int adjMat[][];
    
        // current number of vertices
        private int numberOfVertex;
    
        // number of verts in tree
        private int numberOfVertexInTree;
    
        // array for shortest−calculateDistance data
        private DistPar sPath[];
    
        // current vertex
        private int currentVertex;
    
        // distance to currentVertex
        private int startToCurrent;
    
        public Graph() {
    
            vertexList = new Vertex[MAX_VERTS];
            // adjacency matrix
            adjMat = new int[MAX_VERTS][MAX_VERTS];
            numberOfVertex = 0;
            numberOfVertexInTree = 0;
    
            for (int j = 0; j < MAX_VERTS; j++) { // set adjacency
                for (int k = 0; k < MAX_VERTS; k++) { // matrix
                    adjMat[j][k] = INFINITY; // to infinity
                }
            }
            sPath = new DistPar[MAX_VERTS]; // shortest paths
        }
    
    
        public void addVertex(char label) {
            vertexList[numberOfVertex++] = new Vertex(label);
        }
    
        public void addEdge(int start, int end, int weight) {
            adjMat[start][end] = weight; // (directed)
        }
    
        /*
         this method find all shortest calculateDistance
        */
        public void calculateDistance() {
    
            int startTree = 0; // start at vertex 0
    
            vertexList[startTree].isInTree = true;
    
            numberOfVertexInTree = 1; // put it in tree
    
            // transfer row of distances from adjMat to sPath
            for (int j = 0; j < numberOfVertex; j++) {
                int tempDist = adjMat[startTree][j];
                sPath[j] = new DistPar(startTree, tempDist);
            }
    
            // until all vertices are in the tree
            while (numberOfVertexInTree < numberOfVertex) {
                int indexMin = getMin(); // get minimum from sPath
                int minDist = sPath[indexMin].distance;
    
                if (minDist == INFINITY) // if all infinite
                { // or in tree,
                    System.out.println("There are unreachable vertices");
                    break; // sPath is complete
                } else { // reset currentVertex
                    currentVertex = indexMin; // to closest vert
                    startToCurrent = sPath[indexMin].distance;
                    // minimum distance from startTree is
                    // to currentVertex, and is startToCurrent
                }
                // put current vertex in tree
                vertexList[currentVertex].isInTree = true;
                numberOfVertexInTree++;
                adjust_sPath(); // update sPath[] array
            } // end while(numberOfVertexInTree<numberOfVertex)
    
            displayPaths(); // display sPath[] contents
    
            
        }
        
        
        
        
    
        public int getMin()
        {
            // with minimum distance
            int minDist = INFINITY; // assume minimum
            int indexMin = 0;
    
            for (int j = 1; j < numberOfVertex; j++) // for each vertex,
            { 
                if (!vertexList[j].isInTree &&  sPath[j].distance < minDist) {
                    minDist = sPath[j].distance;
                    indexMin = j;
                }
            }
            return indexMin;
        }
    
        public void adjust_sPath() {
            //adjust values in shortest−calculateDistance array sPath
            int column = 1; // skip starting vertex
    
            while (column < numberOfVertex) // go across columns
            {
                // if this columns vertex already in tree, skip it
                if (vertexList[column].isInTree) {
                    column++;
                    continue;
                }
                // calculate distance for one sPath entry
                // get edge from currentVertex to column
                int currentToFringe = adjMat[currentVertex][column];
                // add distance from start
                int startToFringe = startToCurrent + currentToFringe;
                // get distance of current sPath entry
                int sPathDist = sPath[column].distance;
                // compare distance from start with sPath entry
                if (startToFringe < sPathDist) // if shorter,
                { // update sPath
                    sPath[column].parentVertex = currentVertex;
                    sPath[column].distance = startToFringe;
                }
                column++;
            }
        }
    
        public void displayPaths() {
    
            for (int j = 0; j < numberOfVertex; j++) // display contents of sPath[]
            {
                System.out.print(vertexList[j].label + " ="); // B=
    
                if (sPath[j].distance == INFINITY) {
                    System.out.print(NO_SUCH_ROUTE);
                } else {
                    System.out.print(sPath[j].distance); // 5
                }
    
                char parent = vertexList[sPath[j].parentVertex].label;
                System.out.print("(" + parent + ")"); // (A)
            }
            
            numberOfVertexInTree = 0; // clear tree
            for (int j = 0; j < numberOfVertex; j++) {
                vertexList[j].isInTree = false;
            }
            System.out.println("");
        }
    
    
        public void displayPaths(int startVertex ,int endVertex) {
    
    
          for (int j = 0; j < numberOfVertex; j++) {
            if(startVertex < endVertex){
            	
            	 if(j == startVertex) {
                    System.out.print(vertexList[j].label);
                 } else if(j== endVertex){
                    System.out.print(" - "+vertexList[j].label);
                    System.out.print(" = "+sPath[j].distance);
                            
                 }
            } else {
            	  if(j== endVertex){
                      System.out.print(vertexList[j].label);
                              
                  } else if(j == startVertex) {
                      System.out.print(" - "+ vertexList[j].label);
                      System.out.print(" = "+sPath[j].distance);
                  }
            }
       	
          }
            
            numberOfVertexInTree = 0; // clear tree
            for (int j = 0; j < numberOfVertex; j++) {
                vertexList[j].isInTree = false;
            }
            System.out.println("");
        }
    
    
    
         /*
         this method find all shortest calculateDistance
        */
        public void calculateDistance(int startVertex, int endVertex) {
    
            int startTree = 0; // start at vertex 0
    
            vertexList[startTree].isInTree = true;
    
            numberOfVertexInTree = 1; // put it in tree
    
            // transfer row of distances from adjMat to sPath
            for (int j = 0; j < numberOfVertex; j++) {
                int tempDist = adjMat[startTree][j];
                sPath[j] = new DistPar(startTree, tempDist);
            }
    
            // until all vertices are in the tree
            while (numberOfVertexInTree < numberOfVertex) {
                int indexMin = getMin(); // get minimum from sPath
                int minDist = sPath[indexMin].distance;
    
                if (minDist == INFINITY) // if all infinite
                { // or in tree,
                    System.out.println("There are unreachable vertices");
                    break; // sPath is complete
                } else { // reset currentVertex
                    currentVertex = indexMin; // to closest vert
                    startToCurrent = sPath[indexMin].distance;
                    // minimum distance from startTree is
                    // to currentVertex, and is startToCurrent
                }
                // put current vertex in tree
                vertexList[currentVertex].isInTree = true;
                numberOfVertexInTree++;
                adjust_sPath(); // update sPath[] array
            } // end while(numberOfVertexInTree<numberOfVertex)
    
            displayPaths(startVertex,endVertex); // display sPath[] contents
    
            numberOfVertexInTree = 0; // clear tree
            for (int j = 0; j < numberOfVertex; j++) {
                vertexList[j].isInTree = false;
            }
        }
    }


    Java Code:
    //this is the main class for test Problem
    
    public class PathApp {
    
        public static void main(String[] args) {
            Graph theGraph = new Graph();
            theGraph.addVertex('A'); // 0 (start)
            theGraph.addVertex('B'); // 1
            theGraph.addVertex('C'); // 2
            theGraph.addVertex('D'); // 3
            theGraph.addVertex('E'); // 4
    
            //AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7
            theGraph.addEdge(0, 1, 5); // AB 5
            theGraph.addEdge(1, 2, 4); // BC 4
            theGraph.addEdge(2, 3, 8); // CD 8
            theGraph.addEdge(3, 2, 8); // DC 8
            theGraph.addEdge(3, 4, 6); // DE 6
            theGraph.addEdge(0, 3, 5); // AD 6
            theGraph.addEdge(2, 4, 2); // CE 2
            theGraph.addEdge(4, 1, 3); // EB 3
            theGraph.addEdge(0, 4, 7); // AE 7
    
            System.out.println("shortest paths");
    
    
            //theGraph.calculateDistance();
            //A -B- C
            //theGraph.calculateDistance(0,1);
           // theGraph.calculateDistance(1,2);
            //A to D
           // theGraph.calculateDistance(0,3);
            //A-D-C
            //theGraph.calculateDistance(0,3);
            //theGraph.calculateDistance(3,2);
            //A-E-B-C-D
            theGraph.calculateDistance(0,4);
            theGraph.calculateDistance(4,1);
            theGraph.calculateDistance(1,2);
            theGraph.calculateDistance(2,3);
            
          //A-E-D 0-4-3
            theGraph.calculateDistance(0,4);
            theGraph.calculateDistance(4,3);
    
            //theGraph.(); // shortest paths
    
    
            System.out.println();
        } // end main()
    } // end class PathApp

    XML Code:
    I need to write public void displayPaths(int startVertex ,int endVertex) to display path with edges to full fill my test scenario
    
    PLease help me for this

Similar Threads

  1. how can I display more then one Java Graph
    By santana in forum New To Java
    Replies: 2
    Last Post: 10-29-2009, 11:22 AM
  2. Self-directed learning
    By Mr.Beans in forum Forum Lobby
    Replies: 3
    Last Post: 05-05-2009, 11:40 PM
  3. How to treverse a Directed Acyclic Graph
    By TalhaS in forum New To Java
    Replies: 0
    Last Post: 03-19-2008, 09:28 PM
  4. How to insert graph in java
    By valery in forum Advanced Java
    Replies: 1
    Last Post: 08-06-2007, 09:38 PM

Posting Permissions

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