Constructor Detail

• GraphAlgorithms

  public GraphAlgorithms()

Method Detail

• DFS

  public static <V,E> void DFS(Graph<V,E> g,
               Vertex<V> u,
               Set<Vertex<V>> known,
               Map<Vertex<V>,Edge<E>> forest)

  Performs depth-first search of the unknown portion of Graph g starting at Vertex u.

  Parameters:

  g - Graph instance

  u - Vertex of graph g that will be the source of the search

  known - is a set of previously discovered vertices

  forest - is a map from nonroot vertex to its discovery edge in DFS forest As an outcome, this method adds newly discovered vertices (including u) to the known set, and adds discovery graph edges to the forest.

• constructPath

  public static <V,E> PositionalList<Edge<E>> constructPath(Graph<V,E> g,
                                            Vertex<V> u,
                                            Vertex<V> v,
                                            Map<Vertex<V>,Edge<E>> forest)

  Returns an ordered list of edges comprising the directed path from u to v. If v is unreachable from u, or if u equals v, an empty path is returned.

  Parameters:

  g - Graph instance

  u - Vertex beginning the path

  v - Vertex ending the path

  forest - must be a map that resulting from a previous call to DFS started at u.

• DFSComplete

  public static <V,E> Map<Vertex<V>,Edge<E>> DFSComplete(Graph<V,E> g)

  Performs DFS for the entire graph and returns the DFS forest as a map.

  Returns:

  map such that each nonroot vertex v is mapped to its discovery edge (vertices that are roots of a DFS trees in the forest are not included in the map).

• BFS

  public static <V,E> void BFS(Graph<V,E> g,
               Vertex<V> s,
               Set<Vertex<V>> known,
               Map<Vertex<V>,Edge<E>> forest)

  Performs breadth-first search of the undiscovered portion of Graph g starting at Vertex s.

  Parameters:

  g - Graph instance

  s - Vertex of graph g that will be the source of the search

  known - is a set of previously discovered vertices

  forest - is a map from nonroot vertex to its discovery edge in DFS forest As an outcome, this method adds newly discovered vertices (including s) to the known set, and adds discovery graph edges to the forest.

• BFSComplete

  public static <V,E> Map<Vertex<V>,Edge<E>> BFSComplete(Graph<V,E> g)

  Performs BFS for the entire graph and returns the BFS forest as a map.

  Returns:

  map such that each nonroot vertex v is mapped to its discovery edge (vertices that are roots of a BFS trees in the forest are not included in the map).

• transitiveClosureIndexed

  public static <V,E> void transitiveClosureIndexed(Graph<V,E> g)

  Converts graph g into its transitive closure. This uses the Floyd-Warshall algorithm.

• transitiveClosure

  public static <V,E> void transitiveClosure(Graph<V,E> g)

  Converts graph g into its transitive closure. This uses the Floyd-Warshall algorithm.

• topologicalSort

  public static <V,E> PositionalList<Vertex<V>> topologicalSort(Graph<V,E> g)

  Returns a list of verticies of directed acyclic graph g in topological order. If graph g has a cycle, the result will be incomplete.

• shortestPathLengths

  public static <V> Map<Vertex<V>,Integer> shortestPathLengths(Graph<V,Integer> g,
                                               Vertex<V> src)

  Computes shortest-path distances from src vertex to all reachable vertices of g. This implementation uses Dijkstra's algorithm. The edge's element is assumed to be its integral weight.

• spTree

  public static <V> Map<Vertex<V>,Edge<Integer>> spTree(Graph<V,Integer> g,
                                        Vertex<V> s,
                                        Map<Vertex<V>,Integer> d)

  Reconstructs a shortest-path tree rooted at vertex s, given distance map d. The tree is represented as a map from each reachable vertex v (other than s) to the edge e = (u,v) that is used to reach v from its parent u in the tree.

• MST

  public static <V> PositionalList<Edge<Integer>> MST(Graph<V,Integer> g)

  Computes a minimum spanning tree of connected, weighted graph g using Kruskal's algorithm. Result is returned as a list of edges that comprise the MST (in arbitrary order).

• MSTPrimJarnik

  public static <V> PositionalList<Edge<Integer>> MSTPrimJarnik(Graph<V,Integer> g)

  Computes a minimum spanning tree of connected, weighted graph g using Prim-Jarnik algorithm. Result is returned as a list of edges that comprise the MST (in arbitrary order).

• main

  public static void main(String[] args)