de.hpi.fgis.dude.postprocessor
Class WarshallTransitiveClosureGenerator

java.lang.Object
  de.hpi.fgis.dude.postprocessor.WarshallTransitiveClosureGenerator

All Implemented Interfaces:

Iterable<DuDeObjectPair>

public class WarshallTransitiveClosureGenerator
extends Object
implements Iterable<DuDeObjectPair>

WarshallTransitiveClosureGenerator implements the Warshall algorithm to calculate the transitive closure. The goal of the algorithm is to create the transitive closure of a directed graph. It creates a n x n matrix in which each element (i,j) describes whether there is an edge from element i to element j. As we have an undirected graph, we only have to save the edges in one half of the matrix. The graph can be implemented as an adjacency matrix (array of bitsets) or as an adjacency list (map of sets). The original algorithm was published in Stephen Warshall: A Theorem on Boolean Matrices. In: Journal of the ACM 9, 1962, 1, ISSN 0004-5411, S. 11–12.

Author:

Uwe Draisbach

Nested Class Summary

protected class	WarshallTransitiveClosureGenerator.AdjacencyList WarshallTransitiveClosureGenerator.AdjacencyList is the adjacency list representation of the added pairs.
protected class	WarshallTransitiveClosureGenerator.AdjacencyMatrix WarshallTransitiveClosureGenerator.AdjacencyMatrix is the matrix representation of the added pairs.
protected class	WarshallTransitiveClosureGenerator.GraphRepresentation WarshallTransitiveClosureGenerator.GraphRepresentation is an interface that should be implemented by all classes representing a graph of duplicates.
class	WarshallTransitiveClosureGenerator.IntPair WarshallTransitiveClosureGenerator.IntPair is used to create a pair of integer values.
protected class	WarshallTransitiveClosureGenerator.TransitiveClosureIterator WarshallTransitiveClosureGenerator.TransitiveClosureIterator is used to iterate over all pairs collected or generated by the WarshallTransitiveClosureGenerator.

Constructor Summary

WarshallTransitiveClosureGenerator()

Method Summary

void	add(DuDeObjectPair pair) Adds a pair to the WarshallClosureGenerator.
void	enableAdjacencyListRepresentation() Uses a WarshallTransitiveClosureGenerator.AdjacencyList to represent the graph.
void	enableAdjacencyMatrixRepresentation() Uses a WarshallTransitiveClosureGenerator.AdjacencyMatrix to represent the graph.
Iterator<DuDeObjectPair>	iterator()
void	printGraph() Prints the current graph as a matrix on the standard output
void	reset() Resets the settings of the current WarshallClosureGenerator.

Methods inherited from class java.lang.Object

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

Constructor Detail

WarshallTransitiveClosureGenerator

public WarshallTransitiveClosureGenerator()

Method Detail

add

public void add(DuDeObjectPair pair)

Adds a pair to the WarshallClosureGenerator.

Parameters:

pair - The pair that shall be added.

iterator

public Iterator<DuDeObjectPair> iterator()

Specified by:

iterator in interface Iterable<DuDeObjectPair>

enableAdjacencyMatrixRepresentation

public void enableAdjacencyMatrixRepresentation()

Uses a WarshallTransitiveClosureGenerator.AdjacencyMatrix to represent the graph.

enableAdjacencyListRepresentation

public void enableAdjacencyListRepresentation()

Uses a WarshallTransitiveClosureGenerator.AdjacencyList to represent the graph.

reset

public void reset()

Resets the settings of the current WarshallClosureGenerator.

printGraph

public void printGraph()

Prints the current graph as a matrix on the standard output