Package net.walend.digraph

This package contains a kit for working with directed graphs.

See:
Description

Interface Summary

CEDigraph	CEDigraph is an interface for representing directed graphs of nodes linked by zero or one edge.
Digraph	Digraph is a superinterface for representing directed graphs.
EdgeIterator	EdgeIterator extends EdgeNodeIterator by adding a method to get the current edge.
EdgeNodeIterator	EdgeNodeIterator is a special iterator that iterates accross the pairs of nodes that make edges in a digraph.
GEDigraph	GEDigraph is an interface for representing directed graphs of nodes linked by zero or one edge.
IndexedCEDigraph	CEDigraph methods that use indices.
IndexedDigraph	IndexedDigraph adds index methods to a Digraph.
IndexedEdgeIterator	An EdgeIterator with methods to get indicies.
IndexedEdgeNodeIterator	An EdgeNodeIterator with methods to get indicies.
IndexedGEDigraph	GEDigraph methods that use indices.
IndexedMutableCEDigraph	Indexed mutators
IndexedMutableGEDigraph	Indexed mutators
MutableCEDigraph	MutableCEDigraph adds mutators to the CEDigraph interface so that a developer can add and remove edges and nodes.
MutableGEDigraph	MutableGEDigraph adds mutators to the GEDigraph interface so that a developer can add and remove edges and nodes.
MutableUEDigraph	MutableUEDigraph adds mutators to the UEDigraph interface so that a developer can add and remove edges and nodes.
UEDigraph	UEDigraph is an interface for representing directed graphs of nodes linked by zero or one edge.

Class Summary

AbstractHashCEDigraph	This abstract class implements the CEDigraph interface using a Map and a Set.
AbstractHashGEDigraph	This abstract class implements the GEDigraph interface using two HashSets.
AbstractHashUEDigraph	This abstract class implements the UEDigraph interface using three HashMaps.
AbstractLMCEDigraph	An extension of AbstractMatrixCEDigraph that keeps an additional int[][] that shows what nodes can be reached from what other nodes.
AbstractLMGEDigraph	An extension of AbstractMatrixGEDigraph that keeps an additional int[][] that shows what nodes can be reached from what other nodes.
AbstractMatrixCEDigraph	This abstract class implements the CEDigraph interface using a Map and a Set.
AbstractMatrixGEDigraph	A GEDigraph backed by an ArrayList of nodes and a boolean[][] matrix that stores edges.
AbstractMatrixUEDigraph	This abstract class implements the UEDigraph interface using a List and a Grid.
CEDigraphAlgebra	Algebra for CEDigraph Operations.
GEDigraphAlgebra	Algebra for GEDigraph Operations.
HashCEDigraph	This class implements the CEDigraph interface using a Map and a Set.
HashGEDigraph	This class implements the GEDigraph interface using two HashMaps.
HashUEDigraph	This class implements the UEDigraph interface using three HashMaps.
ImmutableEdgeIterator	This class is an EdgeIterator for Immutables.
ImmutableEdgeNodeIterator	This class is an EdgeIterator for Immutables.
LMCEDigraph	This class implements the CEDigraph interface using a Matrix and an array to speed up some indexed operations.
LMGEDigraph	This class implements the GEDigraph interface using an ArrayList and a boolean matrix and keeps an additional int[][] that shows what nodes can be reached from what other nodes.
MatrixCEDigraph	This class implements the CEDigraph interface using a Matrix.
MatrixGEDigraph	This class implements the GEDigraph interface using an ArrayList and a boolean matrix.
MatrixUEDigraph	This class implements the UEDigraph interface using a List and a Grid.
MutableHashCEDigraph
MutableHashGEDigraph
MutableHashUEDigraph
MutableLMCEDigraph
MutableLMGEDigraph	This class implements the GEDigraph interface using an ArrayList and a boolean matrix and keeps an additional int[][] that shows what nodes can be reached from what other nodes.
MutableMatrixCEDigraph
MutableMatrixGEDigraph	A MutableGEDigraph backed by an ArrayList of nodes and a boolean[][] matrix of edges.
MutableMatrixUEDigraph
UEDigraphAlgebra	Algebra for UEDigraph Operations.

Exception Summary

DigraphException
EdgeMissingException
EdgeNotUniqueException
NodeMissingException

Package net.walend.digraph Description

This package contains a kit for working with directed graphs. It follows the same patterns as in net.walend.collection.

The main interfaces are UEDigraph, a directed graph that's edges must be unique; CEDigraph, a digraph that's edgess are objects, but are not neccessarily unique in the digraph; and GEDigraph, a digraph that's edges are not objects, but mearly a relation between nodes. Each of these is a subinterface of Digraph, which defines some methods common accross all three interpretations.

Each digraph interface has a companion mutable digraph interface that perscribes methods for changing the digraph's state. (A MutableDigraph superinterface did not prove to be useful.)

Digraphs that have no mutator methods and are final should implement the net.walend.collection.Immutable interface.

All nodes in a digraph must be unique. In UIDigraphs, edges must also be unique.

The package also includes a small hierarchy of exceptions to provide reasonable responses to corner cases.

This package currently contains both HashMap-based and and List-and-Grid-based implementations of UEDigraph, CEDigraph and GEDigraph. The hash-based approach is fine for digraphs where the number of edges varies with the number of nodes. However, digraphs with many edges may perform better with the grid-backed version.