Package com.zybooks.dsaj.graph

Class GraphAlgorithms

java.lang.Object

com.zybooks.dsaj.graph.GraphAlgorithms

public class GraphAlgorithms
extends Object

A collection of graph algorithms.

Constructor Summary

Constructors

Constructor	Description
GraphAlgorithms()

Method Summary

Modifier and Type	Method	Description
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.
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.
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.
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.
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.
static <V> PositionalList<Edge<Integer>>	MST(Graph<V,Integer> g)	Computes a minimum spanning tree of connected, weighted graph g using Kruskal's algorithm.
static <V> Map<Vertex<V>,Integer>	shortestPathDistances(Graph<V,Integer> g, Vertex<V> src)	Computes shortest-path distances from src vertex to all reachable vertices of g.
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.
static <V, E> PositionalList<Vertex<V>>	topologicalSort(Graph<V,E> g)	Returns a list of verticies of directed acyclic graph g in topological order.
static <V, E> void	transitiveClosure(Graph<V,E> g)	Converts graph g into its transitive closure.

Methods inherited from class java.lang.Object

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

Constructor Details

GraphAlgorithms

public GraphAlgorithms()

Method Details

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).

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.

shortestPathDistances

public static <V> Map<Vertex<V>,Integer> shortestPathDistances(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).