: Interface VertexPropertyItemPrim

Interface VertexPropertyItemPrim

public interface VertexPropertyItemPrim

Interface declaring required functionality for accessing the vertices of an undirected graph in a run of Prim's algorithm for finding a minimum spanning tree. The life-cycle of a vertex is

not being adjacent to the growing forest,
being adjacent to the growing forest, and
being part of the growing forest.

When a vertex is adjacent to the growing forest, then it must know the cheapest edge, as well as its weight, connecting it to a vertex of the forest.

See Also:: Edge, Iterator

Method Summary

Iterator getIterator()
          Provides the position of this item's vertex in an external data structure.

double getKey()
          Provides the key of this item's vertex, if available, that is if this vertex is in state 2 or 3.

Edge getLinkEdge()
          Provides the cheapest edge relating this item's vertex to the forest, if available, that is if this vertex is in state 2 or 3.

void intoTree()
          Tells this item that its vertex became part of the growing forest, and hereby migrates to state 3.

boolean isKeyAvailable()
          Tells whether the vertex of this item is in state 2 or 3.

boolean isTreeVertex()
          Tells whether the vertex of this item is in state 3.

void setIterator(Iterator iterator)
          Allows to set an iterator position in an external data structure for the vertex held by this item.

boolean update(Edge linkedge, double key)
          Tells this item that its vertex is linked cheapest(ly) to the forest by the given edge.

Method Detail

update

public boolean update(Edge linkedge,
                      double key)
               throws java.lang.IllegalStateException

Tells this item that its vertex is linked cheapest(ly) to the forest by the given edge. Notice that calling this method for an item storing a vertex in state 1 shifts the vertex into state 2.

Parameters:: linkedge - the edge linking this item's vertex cheapest(ly) to the forest; key - the cost of linking this vertex to the forest
Returns:: true iff the update has been effected, i.e. if this item's node is newly adjacent to the forest, or if the given key represents an improvement
Throws:: java.lang.IllegalStateException - if the vertex of this item is already part of the forest, i.e. in state 3, and thus no edge can connect it to the forest any more
See Also:: VertexPropertyItemPrim

setIterator

public void setIterator(Iterator iterator)
                 throws java.lang.IllegalArgumentException

Allows to set an iterator position in an external data structure for the vertex held by this item.

Parameters:: iterator - the position of this item's vertex in an external data structure
Throws:: java.lang.IllegalArgumentException - if the iterator pointing to this item's vertex' position in an external data structure has already been set

intoTree

public void intoTree()

Tells this item that its vertex became part of the growing forest, and hereby migrates to state 3.

See Also:: VertexPropertyItemPrim

getIterator

public Iterator getIterator()
                     throws java.util.NoSuchElementException

Provides the position of this item's vertex in an external data structure.

Returns:: the position of this item's vertex in an external data structure
Throws:: java.util.NoSuchElementException - if the iterator pointing to this item's vertex' position in an external data structure has not been set, so far
See Also:: setIterator(Iterator)

getLinkEdge

public Edge getLinkEdge()
                 throws java.util.NoSuchElementException

Provides the cheapest edge relating this item's vertex to the forest, if available, that is if this vertex is in state 2 or 3.

Returns:: the cheapest edge relating this item's vertex to the forest
Throws:: java.util.NoSuchElementException - iff isKeyAvailable()==false
See Also:: isKeyAvailable()

getKey

public double getKey()
              throws java.util.NoSuchElementException

Provides the key of this item's vertex, if available, that is if this vertex is in state 2 or 3.

Returns:: the key of this item's vertex
Throws:: java.util.NoSuchElementException - iff isKeyAvailable()==false
See Also:: isKeyAvailable()

isKeyAvailable

public boolean isKeyAvailable()

Tells whether the vertex of this item is in state 2 or 3.

Returns:: true, iff the vertex of this item is in state 2 or 3
See Also:: VertexPropertyItemPrim

isTreeVertex

public boolean isTreeVertex()

Tells whether the vertex of this item is in state 3.

Returns:: true, iff the vertex of this item is in state 3
See Also:: VertexPropertyItemPrim

Method Summary
`Iterator`	`getIterator()` Provides the position of this item's vertex in an external data structure.
`double`	`getKey()` Provides the key of this item's vertex, if available, that is if this vertex is in state 2 or 3.
`Edge`	`getLinkEdge()` Provides the cheapest edge relating this item's vertex to the forest, if available, that is if this vertex is in state 2 or 3.
`void`	`intoTree()` Tells this item that its vertex became part of the growing forest, and hereby migrates to state 3.
`boolean`	`isKeyAvailable()` Tells whether the vertex of this item is in state 2 or 3.
`boolean`	`isTreeVertex()` Tells whether the vertex of this item is in state 3.
`void`	`setIterator(Iterator iterator)` Allows to set an iterator position in an external data structure for the vertex held by this item.
`boolean`	`update(Edge linkedge, double key)` Tells this item that its vertex is linked cheapest(ly) to the forest by the given edge.