Graph Problem Java Directed

[daxter]

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)

[doWhile]

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

[daxter]

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

[doWhile]

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

[daxter]

herewith I have displayed my source code withing the code Tag

//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;
    }
}

//Vertex.java
public class Vertex {
    public char label; 
    public boolean isInTree;

    public Vertex(char lab) // constructor
    {
        label = lab;
        isInTree = false;
    }
}

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

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

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