Package squidpony.squidai.graph

Class DirectedGraphAlgorithms<V>

java.lang.Object
squidpony.squidai.graph.Algorithms<V>
squidpony.squidai.graph.DirectedGraphAlgorithms<V>
Type Parameters:
V - the vertex type; often Coord
public class DirectedGraphAlgorithms<V>
extends Algorithms<V>
Algorithms specific to directed graphs, like CostlyGraph, as well as general Algorithms. Currently, this only adds a topologicalSort() method and its overload.
Author:
earlygrey

  • Method Details

    • topologicalSort

      public boolean topologicalSort()
      Sort the vertices of this graph in topological order. That is, for every edge from vertex u to vertex v, u comes before v in the ordering. This is reflected in the iteration order of the collection returned by Graph.getVertices(). Note that the graph cannot contain any cycles for a topological order to exist. If a cycle exists, this method will do nothing.
      Returns:
      true if the sort was successful, false if the graph contains a cycle

    • topologicalSort

      public boolean topologicalSort​(ArrayList<V> sortedVertices)
      Perform a topological sort on the graph, and puts the sorted vertices in the supplied list. That is, for every edge from vertex u to vertex v, u will come before v in the supplied list. Note that the graph cannot contain any cycles for a topological order to exist. If a cycle exists, the sorting procedure will terminate and the supplied list will only contain the vertices up until the point of termination.
      Parameters:
      sortedVertices - an ArrayList of V vertices that will be cleared and modified in-place
      Returns:
      true if the sort was successful, false if the graph contains a cycle