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.

Method Summary

Modifier and Type	Method and Description
boolean	topologicalSort() Sort the vertices of this graph in topological order.
boolean	topologicalSort(java.util.ArrayList<V> sortedVertices) Perform a topological sort on the graph, and puts the sorted vertices in the supplied list.

Methods inherited from class squidpony.squidai.graph.Algorithms

breadthFirstSearch, breadthFirstSearch, depthFirstSearch, depthFirstSearch, detectCycle, findMinimumDistance, findShortestPath, findShortestPath, findShortestPath, lastRunID

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

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(java.util.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