de.hpi.fgis.dude.postprocessor
Class WarshallTransitiveClosureGenerator.AdjacencyList

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

Enclosing class:

WarshallTransitiveClosureGenerator

protected class WarshallTransitiveClosureGenerator.AdjacencyList
extends WarshallTransitiveClosureGenerator.GraphRepresentation

WarshallTransitiveClosureGenerator.AdjacencyList is the adjacency list representation of the added pairs. It created a map of vertices and their connections. The list requires less space than WarshallTransitiveClosureGenerator.AdjacencyMatrix if the graph is sparse. As we are having an undirected graph, the map saves each edge only once, which cuts the required space in half.

Author:

Uwe Draisbach

Constructor Summary

WarshallTransitiveClosureGenerator.AdjacencyList(int elements)
Constructor of WarshallTransitiveClosureGenerator.AdjacencyList

Method Summary

void	calculateTransitiveClosure() Iterating over the matrix and searching for new connections between elements.
boolean	elementIsSet(int i, int j) Checks whether there is an edge between the two elements in the graph (element is already set in the matrix).
int	getSize() Returns the number of elements in the matrix.
void	set(int i, int j) Sets elements (i, j) in the matrix to true.

Methods inherited from class de.hpi.fgis.dude.postprocessor.WarshallTransitiveClosureGenerator.GraphRepresentation

populateGraph

Methods inherited from class java.lang.Object

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

Constructor Detail

WarshallTransitiveClosureGenerator.AdjacencyList

public WarshallTransitiveClosureGenerator.AdjacencyList(int elements)

Constructor of WarshallTransitiveClosureGenerator.AdjacencyList

Parameters:

elements - Number of elements (size).

Method Detail

getSize

public int getSize()

Description copied from class: WarshallTransitiveClosureGenerator.GraphRepresentation

Returns the number of elements in the matrix.

Specified by:

getSize in class WarshallTransitiveClosureGenerator.GraphRepresentation

Returns:

number of elements in the matrix

set

public void set(int i,
                int j)

Description copied from class: WarshallTransitiveClosureGenerator.GraphRepresentation

Sets elements (i, j) in the matrix to true. As the matrix handles undirected edges, also element (j, i) is set to true.

Specified by:

set in class WarshallTransitiveClosureGenerator.GraphRepresentation

Parameters:

i - Coordinate i in the matrix.

j - Coordinate j in the matrix.

elementIsSet

public boolean elementIsSet(int i,
                            int j)

Description copied from class: WarshallTransitiveClosureGenerator.GraphRepresentation

Checks whether there is an edge between the two elements in the graph (element is already set in the matrix).

Specified by:

elementIsSet in class WarshallTransitiveClosureGenerator.GraphRepresentation

Parameters:

i - The number of the first element.

j - The number of the second element.

Returns:

true, if there is an edge between the two elements; otherwise false.

calculateTransitiveClosure

public void calculateTransitiveClosure()

Description copied from class: WarshallTransitiveClosureGenerator.GraphRepresentation

Iterating over the matrix and searching for new connections between elements. For each element it is set to which other elements there is a path in the graph.

Specified by:

calculateTransitiveClosure in class WarshallTransitiveClosureGenerator.GraphRepresentation