prajna.util

Class GraphUtils

java.lang.Object

prajna.util.GraphUtils

public class GraphUtils
extends java.lang.Object

This class is a set of static utility methods which operate on Graphs.

Author:

Edward Swing

Method Summary

Methods

Modifier and Type	Method and Description
static <N,E> java.util.Set<Graph<N,E>>	findClusters(Graph<N,E> graph) Find the set of clusters in the graph.
static <N,E> java.util.Set<N>	findNeighbors(Graph<N,E> graph, N node) Return all neighbors of a particular node in a graph.
static <N,E> GraphPath<N,E>	findShortestPath(Graph<N,E> graph, N startNode, N endNode) Find the shortest path from startNode to endNode.
static <N,E> GraphPath<N,E>	findShortestPath(Graph<N,E> graph, N startNode, N endNode, int maxLen) Find the shortest path from startNode to endNode.
static <N,E> Tree<N>	findSpanTree(Graph<N,E> graph, N node) Find the spanning tree for the associated graph, starting with the specified node as the root.

Methods inherited from class java.lang.Object

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

Method Detail

findClusters

public static <N,E> java.util.Set<Graph<N,E>> findClusters(Graph<N,E> graph)

Find the set of clusters in the graph. This searches through the graph to determine mutual connectivity, accumulating clusters when they can be merged by a common edge.

Type Parameters:

N - The node type for the graph

E - The edge type for the graph

Parameters:

graph - the graph to search

Returns:

A set of graph clusters.

findNeighbors

public static <N,E> java.util.Set<N> findNeighbors(Graph<N,E> graph,
                                   N node)

Return all neighbors of a particular node in a graph. This method returns all nodes which are one step away from the target node. It does not distinguish between directed and undirected graphs, returning all immediate neighbors regardless of the edge direction (if any).

Type Parameters:

N - The node type for the graph

E - The edge type for the graph

Parameters:

graph - the graph to search

node - the target node

Returns:

A set nodes which are the immediate neighbors of the target node

findShortestPath

public static <N,E> GraphPath<N,E> findShortestPath(Graph<N,E> graph,
                                    N startNode,
                                    N endNode)

Find the shortest path from startNode to endNode. Return path in a list, including startNode as the first element, and endNode as the last. If there is no path, this object is empty (and therefore not valid). If there are multiple paths, this method only returns the first one found.

Type Parameters:

N - The node type for the graph

E - The edge type for the graph

Parameters:

graph - the graph which should contain the edge

startNode - the starting node of the path

endNode - the ending node of the path

Returns:

the shortest path for the graph, or null if no such path exists.

findShortestPath

public static <N,E> GraphPath<N,E> findShortestPath(Graph<N,E> graph,
                                    N startNode,
                                    N endNode,
                                    int maxLen)

Find the shortest path from startNode to endNode. Return path in a list, including startNode as the first element, and endNode as the last. If there is no path, this object is empty (and therefore not valid). If there are multiple paths, this method only returns the first one found.

Type Parameters:

N - The node type for the graph

E - The edge type for the graph

Parameters:

graph - the graph which should contain the edge

startNode - the starting node of the path

endNode - the ending node of the path

maxLen - the maximum length for the path. The path length is the number of edge segments in the path

Returns:

the shortest path for the graph, or null if no such path exists.

findSpanTree

public static <N,E> Tree<N> findSpanTree(Graph<N,E> graph,
                         N node)

Find the spanning tree for the associated graph, starting with the specified node as the root. This algorithm adds all nodes which are connected to the root node. Each node is added at the highest (closest to root) level.

Type Parameters:

N - The node type for the graph

E - The edge type for the graph

Parameters:

graph - the graph to span

node - the node to start the span from. This becomes the root of the resulting tree.

Returns:

the spanning tree of the graph, starting at the specified node