I'm so stuck, I would greatly appreciate some help. I'm currently learning Algorithms, but I have no idea where to start.
I was given code recently (We have only really done theory so seeing the code has scared me to my core) And I have been given the task to modify this code to take details from a text file and put it in a graph. The text file is similar to this.
Trout is-a fish
Fish has gills
Fish has fins
Fish is food
Fish is-an animal
Just a lot more in there. I am just wondering. How I would get started with this whole thing? There are a million questions I have to ask, but I feel like I could figure those out if only I knew how to assign the Vertices using the text file? The code I was supplied and have to edit is below. Any help would be great, Just a push in the right direction if you will.
(Also, What the heck is weight, in the addEdge class? I know it's the "cost" of traversing the edge, but how do I assign 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
String[MAX_VERTS]). Then whenever you see an "isa" line, like "Trout is a Fish", check whether Trout and Fish have corresponding numbers, if not add them, thenadd_edge(numberForTrout, numberForFish, 1). Edge weights should all be 1 as far as I can see. – Esmeralda