I have been having trouble writing the following methods to implement a topologi

Question

I have been having trouble writing the following methods to implement a topological sort. Any help / advice is greatly appreciated. Thank you in advance.

A Graph object stores an ArrayList of the vertices of the graph. The Graph constructor receives the name of the input file as a parameter, opens the input file, and reads the information within the file to construct and store the graph within the Graph object. This is the statement you’ll use to open the file: FileInputStream fstream = new FileInputStream("finalAssignment.txt");

The Vertex object stores the string name and the linked list of the edges leaving it. The method addEdge adds the edge to the end of the linked list edges. The method getEdgesIterator should an iterator for the linked list edges. Nested classes cannot be added. The constructors arent an issue , its the other methods I am having a hard time with.

Writing the edge method for the edge class also has me stumped

Explanation / Answer

import java.util.LinkedList;

public class Driver {

    public static void main(String [] args) {
        String file = "myGraph.txt";
        Graph g = new Graph(file);
        LinkedList<Vertex> temp = g.topologicalSort();
        for(Vertex v: temp)
            System.out.print(v.getName());
    }

}
---------------------------------------------------------------------
import java.util.LinkedList;
import java.util.Iterator;

public class Vertex
{
    private String name;
    private LinkedList<Edge> edges;
    private boolean visited;
    private int indegree;

    public Vertex(String n)
    {
        edges = new LinkedList<>();
        name = n;
        visited = false;
        indegree = 0;
    }

    public void setName(String n)
    {
        name = n;
    }

    public String getName()
    {
        return name;
    }

    public void addEdge(Edge e)
    {
        edges.addLast(e);
    }

    public int getIndegree()
    {
        return indegree;
    }

    public void incrementIndegree() {
        indegree++;
    }

    public void setVisitedTrue()
    {
        visited = true;
    }

    public boolean isVisited()
    {
        return visited;
    }

    public Iterator<Edge> getEdgesIterator()
    {
        return edges.iterator();
    }
}
------------------------------------------------------------------------------
public class Edge
{
    private Vertex adjacentVertex;

    public Edge(Vertex v)
    {
        adjacentVertex = v;
    }

    public void setAdjacentVertex(Vertex v)
    {
        adjacentVertex = v;
    }

    public Vertex getAdjacentVertex()
    {
        return adjacentVertex;
    }
}
------------------------------------------------------------------------
import java.util.LinkedList;
import java.util.Stack;
import java.util.Iterator;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Graph
{
    private ArrayList<Vertex> vertices;

    public Graph(String filename)
    {
        vertices = new ArrayList<>();
        try{
            InputStream fstream = new FileInputStream(filename);
            BufferedReader br = new BufferedReader(new InputStreamReader(fstream));
            String line, vertexName, startVertexName, endVertexName;
            line = br.readLine();
            String [] verticesInFirstLine = line.split("\s+");
            for(String s: verticesInFirstLine) {
                vertexName = s;
                Vertex newVertex = new Vertex(vertexName);
                vertices.add(newVertex);
            }

            br.readLine();

            while((line = br.readLine()) != null) {
                String [] edges = line.split("\s+");
                startVertexName = edges[0];
                endVertexName = edges[1];
                int size = vertices.size(), startIndex, endIndex;
                for(startIndex=0;startIndex<size;startIndex++)
                    if(getVertex(startIndex).getName().equals(startVertexName)) break;
                for(endIndex=0;endIndex<size;endIndex++)
                    if(getVertex(endIndex).getName().equals(endVertexName)) break;
                Edge newEdge = new Edge(getVertex(endIndex));
                getVertex(startIndex).addEdge(newEdge);
                getVertex(endIndex).incrementIndegree();
            }
        } catch(FileNotFoundException fnf) {
            fnf.printStackTrace();
        } catch(IOException ioe) {
            ioe.printStackTrace();
        }

    }

    private Vertex getVertex(int n) {
        return vertices.get(n);
    }

    public void printAll() {
        for(Vertex v: vertices) {
            Iterator<Edge> itr = v.getEdgesIterator();
            System.out.println("The adjacent vertices of " + v.getName() + " is:");
            while(itr.hasNext())
                System.out.println(itr.next().getAdjacentVertex().getName());
        }
    }

    public LinkedList<Vertex> topologicalSort()
    {
        LinkedList<Vertex> ans = new LinkedList<>();
        for(Vertex v: vertices)
            if(v.getIndegree()==0) topologicalSort(v, ans);
        return ans;
    }

    private void topologicalSort(Vertex v, LinkedList<Vertex> list) {
        Iterator<Edge> neighbours = v.getEdgesIterator();
        while(neighbours.hasNext()) {
            Vertex next = neighbours.next().getAdjacentVertex();
            if(!next.isVisited()) topologicalSort(next,list);
        }
        v.setVisitedTrue();
        list.addFirst(v);
    }

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.