Class DAG

java.lang.Object
com.thomas.graphs.DAG.DAG
public class DAG extends Object
An implemnation of a Directional acyclic graph
See Also:

  • Field Details

    • vertices

      public Map<String,Vertex> vertices
      The vertices within the graph

  • Constructor Details

    • DAG

      public DAG()
      Creates a new DAG

  • Method Details

    • addVertex

      public Vertex addVertex(String name)
      Adds a new vertex to the graph if it is not in the graph
      Parameters:
      name - The name of the Vertex
      Returns:
      The vertex

    • removeVertex

      public boolean removeVertex(String name)
      Removes the vertex with a given name from the graph, including all of it's edges
      Parameters:
      name - The name of the vertex
      Returns:
      true if the vertex was removed

    • getVertex

      public Vertex getVertex(String name)
      Gets a vertex with a given name
      Parameters:
      name - The name of the vertex
      Returns:
      The Vertex

    • getVertices

      public Collection<Vertex> getVertices()
      Gets all the vertices in the graph
      Returns:
      An unmodifiable collection of the vertices

    • addEdge

      public void addEdge(String fromName, String toName) throws IllegalArgumentException
      Creates a directional edge from fromName to toName.
      Both bertices are create automatically if they do not exist
      Parameters:
      fromName - The name of the source vertex
      toName - the name of the destination vertex
      Throws:
      IllegalArgumentException - if there is a self-loop
      IllegalArgumentException - if a cycle is created

    • removeEdge

      public boolean removeEdge(String fromName, String toName)
      Removes the directional edges from fromName to toName
      Parameters:
      fromName - The name of the source vertex
      toName - The name of the destination vertex
      Returns:
      true if the edge existed and was removed

    • hasEdge

      public boolean hasEdge(String fromName, String toName)
      Checks if fromName has an edge to toName
      Parameters:
      fromName - The source vertex
      toName - The destination vertex
      Returns:
      true if an edge exists between the vertices

    • hasCycle

      public boolean hasCycle()
      Checks for cycles in the graph
      Uses a depth-first search
      Returns:
      true if there is a cycle in the graph

    • dfsHasCycle

      public boolean dfsHasCycle(Vertex vertex, Set<Vertex> visited, Set<Vertex> inStack)
      Uses a depth-first search to check for cycles
      Parameters:
      vertex - The current vertex
      visited - The vertices that have been visited
      inStack - The current stack

    • topologicalSort

      public List<Vertex> topologicalSort() throws IllegalStateException
      Uses Kahn's alogorithm to sort the graph
      Returns:
      A sorted List of the Graph
      Throws:
      IllegalStateException - If a cycle is detected

    • printGraph

      public void printGraph()
      Prints the graph to the standard output

    • toString

      public String toString()
      Overrides:
      toString in class Object