Interface VisitorPrim

public interface VisitorPrim

Interface declaring minimal set of actions required to record a run of Prim's algorithm for constructing a minimal spanning tree.

The life-cycle of a vertex is

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

Edges have one of the states

  1. edge not investigated so far, or that will definitively not be part of the tree
  2. candidate edge having one vertex in state 2, the other in state 3, that has to be tested if it relates its state 2 vertex newly to the forest, or at least cheaper than the unique current best edge of the state 3 vertex
  3. best edge having one vertex in state 2, the other in state 3, that connects its state 2 vertex cheapest(ly) to the growing forest; notice that every vertex in state 2 has exactly one best edge
  4. tree edge having both vertices in state 3
The following state transitions make sense:
  1. (1, 2)
  2. (2, 1)
  3. (2, 3)
  4. (3, 1)
  5. (3, 4).

The action itself may be suitably processed by a VertexProcessorPrim.

See Also:
Vertex, Edge, VertexProcessorPrim

Method Summary
 boolean anyEdge(Edge e)
          Records the fact that edge e has no special role.
 boolean bestEdge(Edge e)
          Records the fact that edge e connects its unique non-tree vertex with best cost, among the edges that have been candidates so far, to the growing forest (state 3).
 boolean candEdge(Edge e)
          Records the fact that edge e becomes a candidate for getting the best (cheapest) edge in connecting a vertex with the growing forest (state 2).
 boolean init(Vertex v)
          Records the fact that vertex v is initialized and thus not adjacent to the growing forest (state 1).
 boolean reachable(Vertex v)
          Records the fact that vertex v became adjacent to a vertex that is part of the growing forest (state 2).
 boolean treeEdge(Edge e)
          Records the fact that edge e is an element of the final spanning tree (state 4).
 boolean visit(Vertex v)
          Records the fact that vertex v becomes part of the growing forest (state 3).
 

Method Detail

init

public boolean init(Vertex v)
Records the fact that vertex v is initialized and thus not adjacent to the growing forest (state 1).
Parameters:
v - the vertex to be initialized

reachable

public boolean reachable(Vertex v)
                  throws java.lang.IllegalStateException
Records the fact that vertex v became adjacent to a vertex that is part of the growing forest (state 2).
Parameters:
v - the vertex to be scanned
Throws:
java.lang.IllegalStateException - if v is already in state 3

visit

public boolean visit(Vertex v)
              throws java.lang.IllegalStateException
Records the fact that vertex v becomes part of the growing forest (state 3).
Parameters:
v - the vertex to be visited, i.e. adjoint to the forest
Throws:
java.lang.IllegalStateException - if v is still in state 1

anyEdge

public boolean anyEdge(Edge e)
                throws java.lang.IllegalStateException
Records the fact that edge e has no special role. In particular it is neither candidate, nor best, nor final edge (state 1).
Parameters:
e - the edge currently having no special role
Throws:
java.lang.IllegalStateException -  

candEdge

public boolean candEdge(Edge e)
                 throws java.lang.IllegalArgumentException,
                        java.lang.IllegalStateException
Records the fact that edge e becomes a candidate for getting the best (cheapest) edge in connecting a vertex with the growing forest (state 2).
We may assume that exactly one vertex of e is part of the growing forest, and that e has been an any edge before.
Parameters:
e - the edge that becomes a candidate for being a best edge
Throws:
java.lang.IllegalArgumentException - if not exactly one vertex of e is part of the growing forest
java.lang.IllegalStateException - if e has not been an any edge before

bestEdge

public boolean bestEdge(Edge e)
                 throws java.lang.IllegalArgumentException,
                        java.lang.IllegalStateException
Records the fact that edge e connects its unique non-tree vertex with best cost, among the edges that have been candidates so far, to the growing forest (state 3).
We may assume that exactly one vertex of e is part of the growing forest, and that e has been a candidate edge before
Parameters:
e - the edge that becomes a best edge for its unique non-forest vertex
Throws:
java.lang.IllegalArgumentException - if not exactly one vertex of e is part of the growing forest
java.lang.IllegalStateException - if e has not been a candidate edge before

treeEdge

public boolean treeEdge(Edge e)
                 throws java.lang.IllegalArgumentException,
                        java.lang.IllegalStateException
Records the fact that edge e is an element of the final spanning tree (state 4).
We may assume that edge both vertices are part of the growing forest, and that e has been a best edge before.
Parameters:
e - the edge that becomes part of the forest
Throws:
java.lang.IllegalArgumentException - if one of the vertices is not part of the forest
java.lang.IllegalStateException - if e has not been a best edge before