com.jgraph.algebra

Class JGraphAlgebra

public class JGraphAlgebra extends Object

A singleton class that provides algorithms for graphs. Assume the following variable for the following examples:
JGraphDistanceCostFunction(graph.getGraphLayoutCache());
JGraphFacade facade = new JGraphFacade(graph);
Object[] v = facade.getVertices().toArray();
Object[] e = facade.getEdges().toArray();
JGraphAlgebra alg = JGraphAlgebra.getSharedInstance();

Shortest Path (Dijkstra)

For example, to find the shortest path between the first and the second selected cell in a graph use the following code:

Object[] path = alg.getShortestPath(graph.getModel(), sourceVertex, targetVertex, cf, v.length, true)

Minimum Spanning Tree

This algorithm finds the set of edges with the minimal length that connect all vertices. This algorithm can be used as follows:
Prim
alg.getMinimumSpanningTree(graph.getModel(), v, cf, true))
Kruskal
alg.getMinimumSpanningTree(graph.getModel(), v, e, cf))

Connection Components

The union find may be used as follows to determine whether two cells are connected: boolean connected = uf.differ(vertex1, vertex2).

See Also: JGraphCostFunction

Field Summary
protected static JGraphAlgebrasharedInstance
Holds the shared instance of this class.
Constructor Summary
protected JGraphAlgebra()
Subclassers may override to provide special union find and priority queue datastructures.
Method Summary
protected JGraphFibonacciHeapcreatePriorityQueue()
Hook for subclassers to provide a custom fibonacci heap.
protected JGraphUnionFindcreateUnionFind(Object[] v)
Hook for subclassers to provide a custom union find structure.
JGraphUnionFindgetConnectionComponents(GraphModel model, Object[] v, Object[] e)
Returns a union find structure representing the connection components of G=(E,V).
Object[]getMinimumSpanningTree(GraphModel model, Object[] v, JGraphCostFunction cf, boolean directed)
Returns the minimum spanning tree (MST) for the graph defined by G=(E,V).
Object[]getMinimumSpanningTree(GraphModel model, Object[] v, Object[] e, JGraphCostFunction cf)
Returns the minimum spanning tree (MST) for the graph defined by G=(E,V).
static JGraphAlgebragetSharedInstance()
Object[]getShortestPath(GraphModel model, Object from, Object to, JGraphCostFunction cf, int steps, boolean directed)
Returns the shortest path between two cells or their descendants represented as an array of edges in order of traversal.
static voidsetSharedInstance(JGraphAlgebra sharedInstance)
Sets the shared instance of this class.
Listsort(Object[] cells, JGraphCostFunction cf)
Returns a sorted set for cells with respect to cf.
doublesum(Object[] cells, JGraphCostFunction cf)
Returns the sum of all cost for cells with respect to cf.

Field Detail

sharedInstance

protected static JGraphAlgebra sharedInstance
Holds the shared instance of this class.

Constructor Detail

JGraphAlgebra

protected JGraphAlgebra()
Subclassers may override to provide special union find and priority queue datastructures.

Method Detail

createPriorityQueue

protected JGraphFibonacciHeap createPriorityQueue()
Hook for subclassers to provide a custom fibonacci heap.

createUnionFind

protected JGraphUnionFind createUnionFind(Object[] v)
Hook for subclassers to provide a custom union find structure.

Parameters: v the array of all elements

Returns: Returns a union find structure for v

getConnectionComponents

public JGraphUnionFind getConnectionComponents(GraphModel model, Object[] v, Object[] e)
Returns a union find structure representing the connection components of G=(E,V).

Parameters: model the model that describes the graph v the vertices of the graph e the edges of the graph

Returns: Returns the connection components in G=(E,V)

See Also: (Object[])

getMinimumSpanningTree

public Object[] getMinimumSpanningTree(GraphModel model, Object[] v, JGraphCostFunction cf, boolean directed)
Returns the minimum spanning tree (MST) for the graph defined by G=(E,V). The MST is defined as the set of all vertices with minimal lengths that forms no cycles in G.
This implementation is based on the algorihm by Prim-Jarnik. It uses O(|E|+|V|log|V|) time when used with a Fibonacci heap and a graph whith a double linked-list datastructure, as is the case with the default implementation.

Parameters: model the model that describes the graph v the vertices of the graph cf the cost function that defines the edge length

Returns: Returns the MST as an array of edges

See Also: createPriorityQueue

getMinimumSpanningTree

public Object[] getMinimumSpanningTree(GraphModel model, Object[] v, Object[] e, JGraphCostFunction cf)
Returns the minimum spanning tree (MST) for the graph defined by G=(E,V). The MST is defined as the set of all vertices with minimal lenths that forms no cycles in G.
This implementation is based on the algorihm by Kruskal. It uses O(|E|log|E|)=O(|E|log|V|) time for sorting the edges, O(|V|) create sets, O(|E|) find and O(|V|) union calls on the union find structure, thus yielding no more than O(|E|log|V|) steps. For a faster implementatin

Parameters: model the model that describes the graph v the vertices of the graph e the edges of the graph cf the cost function that defines the edge length

Returns: Returns the MST as an array of edges

See Also: (GraphModel, Object[], JGraphCostFunction, boolean) (Object[])

getSharedInstance

public static JGraphAlgebra getSharedInstance()

Returns: Returns the sharedInstance.

getShortestPath

public Object[] getShortestPath(GraphModel model, Object from, Object to, JGraphCostFunction cf, int steps, boolean directed)
Returns the shortest path between two cells or their descendants represented as an array of edges in order of traversal.
This implementation is based on the Dijkstra algorithm.

Parameters: model the model that defines the graph structure from the source port or vertex to the target port or vertex (aka. sink) cf the cost function that defines the edge length steps the maximum number of edges to traverse directed if edge directions should be taken into account

Returns: Returns the shortest path as an array of edges

See Also: createPriorityQueue

setSharedInstance

public static void setSharedInstance(JGraphAlgebra sharedInstance)
Sets the shared instance of this class.

Parameters: sharedInstance The sharedInstance to set.

sort

public List sort(Object[] cells, JGraphCostFunction cf)
Returns a sorted set for cells with respect to cf.

Parameters: cells the cells to sort cf the cost function that defines the order

Returns: Returns an ordered set of cells wrt. cf

sum

public double sum(Object[] cells, JGraphCostFunction cf)
Returns the sum of all cost for cells with respect to cf.

Parameters: cells the cells to use for the sum cf the cost function that defines the costs

Returns: Returns the sum of all cell cost

Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.