org.hypergraphdb.algorithms
Class GraphClassics

java.lang.Object
  org.hypergraphdb.algorithms.GraphClassics

public class GraphClassics
extends java.lang.Object

A collection of classical graph algorithms implemented within the HyperGraphDB framework.

Author:

Borislav Iordanov

Constructor Summary

GraphClassics()

Method Summary

void	a_star()
void	bellman_ford()
static java.lang.Double	dijkstra(HGHandle start, HGHandle goal, HGALGenerator adjencyGenerator) Simplified interface to Dijkstra's algorithm - calls the full version with the remaining arguments set to null.
static java.lang.Double	dijkstra(HGHandle start, HGHandle goal, HGALGenerator adjencyGenerator, Mapping<HGHandle,java.lang.Double> weight, java.util.Map<HGHandle,java.lang.Double> distanceMatrix, java.util.Map<HGHandle,HGHandle> predecessorMatrix) Implements Dijkstra's algorithm for finding the shortest path between two nodes (i.e.
void	floyd_warshall()
void	johnson()
void	kruskall(java.util.Iterator<HGHandle> links, Mapping<HGHandle,java.lang.Double> weight, java.util.Map<HGHandle,HGHandle> parentMatrix)
void	prim(HGHandle start, HGALGenerator adjencyGenerator, Mapping<HGHandle,java.lang.Double> weight, java.util.Map<HGHandle,HGHandle> parentMatrix)

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphClassics

public GraphClassics()

Method Detail

dijkstra

public static java.lang.Double dijkstra(HGHandle start,
                                        HGHandle goal,
                                        HGALGenerator adjencyGenerator)

Simplified interface to Dijkstra's algorithm - calls the full version with the remaining arguments set to null.

Parameters:

start -

goal -

adjencyGenerator -

Returns:

The number of edges b/w start and goal or null if they are not connected.

dijkstra

public static java.lang.Double dijkstra(HGHandle start,
                                        HGHandle goal,
                                        HGALGenerator adjencyGenerator,
                                        Mapping<HGHandle,java.lang.Double> weight,
                                        java.util.Map<HGHandle,java.lang.Double> distanceMatrix,
                                        java.util.Map<HGHandle,HGHandle> predecessorMatrix)

Implements Dijkstra's algorithm for finding the shortest path between two nodes (i.e. atoms). The method returns the distance between start goal or null if the two atoms are not connected.

The method allows you to optionally pass your own main data structures for use in the algorithm's implementation. If you pass null as the value of a data structure, the method will create and use its own. Thus, if you care about the actual paths computed and/or all distances between nodes on those paths, you should provide your own distanceMatrix and predecessorMatrix.

The weight mapping argument represents a function the computes the weight of a given link. If you pass null, a weight of 1 will be used for all links. Note that this mapping cannot return negative values. Dijkstra's algorithms assumes non-negative weights. If the weights of your graph can be negative, use the bellman_ford instead.

Parameters:

start -

goal -

adjencyGenerator -

weight - The function that computes that weight of a link for the purposes of measuring the distance between nodes. If null, the constant function 1 will be used.

distanceMatrix - The data structure holding the computing distances between the start atom and all other atoms encountered during the search. Only put and get are used so you can provide an implementation that only implements those two methods. If null is passed, a new temporary HashMap will be instantiated and used throughout the search.

predecessorMatrix - A map storing the predecessor atoms computed during the search. Again, only put and get are used here. If null, the predecessor will not be stored anywhere.

Returns:

The distance between start and goal or null if start is unreachable from goal.

bellman_ford

public void bellman_ford()

a_star

public void a_star()

johnson

public void johnson()

floyd_warshall

public void floyd_warshall()

prim

public void prim(HGHandle start,
                 HGALGenerator adjencyGenerator,
                 Mapping<HGHandle,java.lang.Double> weight,
                 java.util.Map<HGHandle,HGHandle> parentMatrix)

kruskall

public void kruskall(java.util.Iterator<HGHandle> links,
                     Mapping<HGHandle,java.lang.Double> weight,
                     java.util.Map<HGHandle,HGHandle> parentMatrix)