org.hypergraphdb.algorithms

Class GraphClassics

java.lang.Object

org.hypergraphdb.algorithms.GraphClassics

public class GraphClassics
extends Object

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

Author:

Borislav Iordanov

Constructor Summary

Constructors

Constructor and Description
GraphClassics()

Method Summary

Methods

Modifier and Type	Method and Description
void	a_star()
void	bellman_ford()
static 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 Double	dijkstra(HGHandle start, HGHandle goal, HGALGenerator adjacencyGenerator, Mapping<HGHandle,Double> weight, Map<HGHandle,Double> distanceMatrix, Map<HGHandle,HGHandle> predecessorMatrix) Implements Dijkstra's algorithm for finding the shortest path between two nodes (i.e.
void	floyd_warshall()
static boolean	hasCycles(HGHandle root, HGALGenerator adjencyGenerator) Detect whether a sub-graph has cycles.
void	johnson()
void	kruskall(Iterator<HGHandle> links, Mapping<HGHandle,Double> weight, Map<HGHandle,HGHandle> parentMatrix)
void	prim(HGHandle start, HGALGenerator adjencyGenerator, Mapping<HGHandle,Double> weight, Map<HGHandle,HGHandle> parentMatrix)

Methods inherited from class java.lang.Object

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

Constructor Detail

GraphClassics

public GraphClassics()

Method Detail

hasCycles

public static boolean hasCycles(HGHandle root,
                HGALGenerator adjencyGenerator)

Detect whether a sub-graph has cycles. Links are specified through an HGALGenerator as usual.

Parameters:

root - The starting point for sub-graph exploration.

adjencyGenerator - Generator for atoms adjacent to the current node being examined.

Returns:

true if the sub-graph has cycles and false otherwise.

dijkstra

public static 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 Double dijkstra(HGHandle start,
              HGHandle goal,
              HGALGenerator adjacencyGenerator,
              Mapping<HGHandle,Double> weight,
              Map<HGHandle,Double> distanceMatrix,
              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 and 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 that 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 -

adjacencyGenerator -

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 computed 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,Double> weight,
        Map<HGHandle,HGHandle> parentMatrix)

kruskall

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