com.whitestein.lsps.common.graph

Class GraphUtils

java.lang.Object

com.whitestein.lsps.common.graph.GraphUtils

public final class GraphUtils
extends java.lang.Object

Static class for common graph manipulations.

Author:

rba

Method Summary

Modifier and Type	Method and Description
static <V> java.util.List<Edge<V>>	acyclicTransitiveReduction(DirectedGraph<V> acyclicGraph) For a given acyclic graph this method returns a list of edges that can be removed to obtain a transitive reduction of the given graph.
static <V> DirectedGraph<V>	completeGraph(java.util.Set<V> vertices) Returns complete graph over given set of vertices.
static <V> java.util.List<java.util.List<V>>	computeSCC(DirectedGraph<V> graph) Computes strongly-connected components.
static <V> java.util.List<V>	getCycle(DirectedGraph<V> graph) Returns a list of vertices forming a cycle or null if the graph is acyclic.
static <V> java.util.Set<V>	getVerticesInCycles(DirectedGraph<V> graph) Returns a set of all vertices that take part in a cycle.
static <V> java.util.List<V>	internalTopSort(DirectedGraph<V> graph) Returns topological sort of given directed graph or null if the graph is not acyclic.
static boolean	isAcyclic(DirectedGraph<?> graph) Returns true if given graph is acyclic.
static <V> DirectedGraph<V>	reverse(DirectedGraph<V> graph) Returns reverse of given graph (all edges are reversed).
static <V> DirectedGraph<V>	subgraph(DirectedGraph<V> graph, java.util.Set<V> vertices) Returns new instance of DirectedGraph induced by given set of vertices on given graph.
static <V> java.util.List<V>	topologicalSort(DirectedGraph<V> graph) Returns topological sort of given acyclic directed graph.
static void	transitiveClosure(DirectedGraph<?> graph) Adds edges to a given graph to create a transitive closure.
static <V> java.util.Set<V>	transitiveClosure(DirectedGraph<V> graph, java.util.Set<? extends V> vertices) Returns transitive closure of given vertices on given graph.

Methods inherited from class java.lang.Object

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

Method Detail

subgraph

public static <V> DirectedGraph<V> subgraph(DirectedGraph<V> graph,
                                            java.util.Set<V> vertices)

Returns new instance of DirectedGraph induced by given set of vertices on given graph. Given vertices must form a subset of the graph vertices.

Type Parameters:

V - type of graph vertex

Parameters:

vertices - set of vertices

graph - directed graph

Returns:

induced subgraph

Throws:

java.lang.NullPointerException - if any argument is null

java.lang.IllegalArgumentException - if given vertices are not a subset of this graph vertices

completeGraph

public static <V> DirectedGraph<V> completeGraph(java.util.Set<V> vertices)

Returns complete graph over given set of vertices.

Type Parameters:

V - type of vertex

Parameters:

vertices - set of vertices

Returns:

complete graph

Throws:

java.lang.NullPointerException - if argument vertices is null

transitiveClosure

public static <V> java.util.Set<V> transitiveClosure(DirectedGraph<V> graph,
                                                     java.util.Set<? extends V> vertices)

Returns transitive closure of given vertices on given graph.

Type Parameters:

V - type of vertex

Parameters:

graph - directed graph

vertices - set of vertices

Returns:

transitive closure

Throws:

java.lang.NullPointerException - if any argument is null

java.lang.IllegalArgumentException - if given vertices are not a subset of this graph vertices

transitiveClosure

public static void transitiveClosure(DirectedGraph<?> graph)

Adds edges to a given graph to create a transitive closure.

Parameters:

graph -

reverse

public static <V> DirectedGraph<V> reverse(DirectedGraph<V> graph)

Returns reverse of given graph (all edges are reversed).

Type Parameters:

V - type of vertex

Parameters:

graph - directed graph

Returns:

reverse of given graph

topologicalSort

public static <V> java.util.List<V> topologicalSort(DirectedGraph<V> graph)

Returns topological sort of given acyclic directed graph.

Type Parameters:

V - type of vertex

Parameters:

graph - acyclic directed graph

Returns:

topological sort of given acyclic directed graph

Throws:

java.lang.IllegalArgumentException - if given graph is not acyclic

internalTopSort

public static <V> java.util.List<V> internalTopSort(DirectedGraph<V> graph)

Returns topological sort of given directed graph or null if the graph is not acyclic.

IMPORTANT: the method modifies the given graph.

Type Parameters:

V - type of vertex

Parameters:

graph - directed graph (will be modified by the method)

Returns:

topological sort of given directed graph

isAcyclic

public static boolean isAcyclic(DirectedGraph<?> graph)

Returns true if given graph is acyclic.

Parameters:

graph - directed graph

Returns:

true if given graph is acyclic

getCycle

public static <V> java.util.List<V> getCycle(DirectedGraph<V> graph)

Returns a list of vertices forming a cycle or null if the graph is acyclic. The algorithm finds only one cycle, not all cycles.

Type Parameters:

V -

Parameters:

graph -

Returns:

a list of vertices forming a cycle or null if the graph is acyclic

computeSCC

public static <V> java.util.List<java.util.List<V>> computeSCC(DirectedGraph<V> graph)

Computes strongly-connected components.

Type Parameters:

V -

Parameters:

graph -

Returns:

a list of strongly-connected components

getVerticesInCycles

public static <V> java.util.Set<V> getVerticesInCycles(DirectedGraph<V> graph)

Returns a set of all vertices that take part in a cycle.

Type Parameters:

V -

Parameters:

graph -

Returns:

a set of all vertices that take part in a cycle

acyclicTransitiveReduction

public static <V> java.util.List<Edge<V>> acyclicTransitiveReduction(DirectedGraph<V> acyclicGraph)

For a given acyclic graph this method returns a list of edges that can be removed to obtain a transitive reduction of the given graph.

Type Parameters:

V -

Parameters:

acyclicGraph -

Returns:

a list of edges to be removed