I am so stuck, I would really appreciate help. I am currently studying algorithms, but I do not know where to start.
I was recently given code (we just made a theory, so when I saw that the code scared me to my core). And I was tasked with changing this code to get the details from a text file and put it in a graph, the text file is similar to this one.
Trout is-a fish Fish has gills Fish has fins Fish is food Fish is-an animal
Just a lot more. I'm just curious. How would I start doing this? There are a million questions that I should ask, but it seems to me that I could understand them only if I knew how to assign Vertices using a text file? The code that was provided to me and which needs to be changed is given below. Any help would be great, just click in the right direction if you want.
(Also, what is this weight in the addEdge class? I know what the "cost" of moving the edge is, but how do I set the weight?)
Thanks!
public class Graph { private final int MAX_VERTS = 20; private final int INFINITY = 1000000; private Vertex vertexList[]; // list of vertices private int adjMat[][]; // adjacency matrix private int nVerts; // current number of vertices private int nTree; // number of verts in tree private DistPar sPath[]; // array for shortest-path data private int currentVert; // current vertex private int startToCurrent; // distance to currentVert // ------------------------------------------------------------- public Graph() // constructor { vertexList = new Vertex[MAX_VERTS]; // adjacency matrix adjMat = new int[MAX_VERTS][MAX_VERTS]; nVerts = 0; nTree = 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 } // end constructor // ------------------------------------------------------------- public void addVertex(char lab) { vertexList[nVerts++] = new Vertex(lab); } // ------------------------------------------------------------- public void addEdge(int start, int end, int weight) { adjMat[start][end] = weight; // (directed) } // ------------------------------------------------------------- public void path() // find all shortest paths { int startTree = 0; // start at vertex 0 vertexList[startTree].isInTree = true; nTree = 1; // put it in tree // transfer row of distances from adjMat to sPath for(int j=0; j<nVerts; j++) { int tempDist = adjMat[startTree][j]; sPath[j] = new DistPar(startTree, tempDist); } // until all vertices are in the tree while(nTree < nVerts) { 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 currentVert currentVert = indexMin; // to closest vert startToCurrent = sPath[indexMin].distance; // minimum distance from startTree is // to currentVert, and is startToCurrent } // put current vertex in tree vertexList[currentVert].isInTree = true; nTree++; adjust_sPath(); // update sPath[] array } // end while(nTree<nVerts) displayPaths(); // display sPath[] contents nTree = 0; // clear tree for(int j=0; j<nVerts; j++) vertexList[j].isInTree = false; } // end path() // ------------------------------------------------------------- public int getMin() // get entry from sPath { // with minimum distance int minDist = INFINITY; // assume minimum int indexMin = 0; for(int j=1; j<nVerts; j++) // for each vertex, { // if it's in tree and if( !vertexList[j].isInTree && // smaller than old one sPath[j].distance < minDist ) { minDist = sPath[j].distance; indexMin = j; // update minimum } } // end for return indexMin; // return index of minimum } // end getMin() // ------------------------------------------------------------- public void adjust_sPath() { // adjust values in shortest-path array sPath int column = 1; // skip starting vertex while(column < nVerts) // go across columns { // if this column's vertex already in tree, skip it if( vertexList[column].isInTree ) { column++; continue; } // calculate distance for one sPath entry // get edge from currentVert to column int currentToFringe = adjMat[currentVert][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].parentVert = currentVert; sPath[column].distance = startToFringe; } column++; } // end while(column < nVerts) } // end adjust_sPath() // ------------------------------------------------------------- public void displayPaths() { for(int j=0; j<nVerts; j++) // display contents of sPath[] { System.out.print(vertexList[j].label + "="); // B= if(sPath[j].distance == INFINITY) System.out.print("inf"); // inf else System.out.print(sPath[j].distance); // 50 char parent = vertexList[ sPath[j].parentVert ].label; System.out.print("(" + parent + ") "); // (A) } System.out.println(""); } // ------------------------------------------------------------- } // end class Graph
source share