|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object de.hpi.fgis.dude.postprocessor.WarshallTransitiveClosureGenerator.GraphRepresentation de.hpi.fgis.dude.postprocessor.WarshallTransitiveClosureGenerator.AdjacencyMatrix
protected class WarshallTransitiveClosureGenerator.AdjacencyMatrix
WarshallTransitiveClosureGenerator.AdjacencyMatrix
is the matrix representation of the added pairs. It creates an array of
bitsets. Each bit represents a possible edge between two vertices. If the bit is the, we have an edge, otherwise not. Although checking for
edges or creating edges is very cheap, the matrix requires quadratic space concerning the number of vertices. As we are having an undirected
graph, the matrix saves each edge only once, which cuts the required space in half.
Constructor Summary | |
---|---|
WarshallTransitiveClosureGenerator.AdjacencyMatrix(int elements)
Constructor of WarshallTransitiveClosureGenerator.AdjacencyMatrix |
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 |
---|
public WarshallTransitiveClosureGenerator.AdjacencyMatrix(int elements)
WarshallTransitiveClosureGenerator.AdjacencyMatrix
elements
- Number of elements (size).Method Detail |
---|
public int getSize()
WarshallTransitiveClosureGenerator.GraphRepresentation
getSize
in class WarshallTransitiveClosureGenerator.GraphRepresentation
public void set(int i, int j)
WarshallTransitiveClosureGenerator.GraphRepresentation
set
in class WarshallTransitiveClosureGenerator.GraphRepresentation
i
- Coordinate i in the matrix.j
- Coordinate j in the matrix.public boolean elementIsSet(int i, int j)
WarshallTransitiveClosureGenerator.GraphRepresentation
elementIsSet
in class WarshallTransitiveClosureGenerator.GraphRepresentation
i
- The number of the first element.j
- The number of the second element.
true
, if there is an edge between the two elements; otherwise false
.public void calculateTransitiveClosure()
WarshallTransitiveClosureGenerator.GraphRepresentation
calculateTransitiveClosure
in class WarshallTransitiveClosureGenerator.GraphRepresentation
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |