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
Edges have one of the states
The action itself may be suitably processed by a
VertexProcessorPrim
.
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 |
public boolean init(Vertex v)
v
is initialized
and thus not adjacent to the growing forest (state 1).v
- the vertex to be initializedpublic boolean reachable(Vertex v) throws java.lang.IllegalStateException
v
became adjacent
to a vertex that is part of the growing forest (state 2).v
- the vertex to be scannedjava.lang.IllegalStateException
- if v
is already
in state 3public boolean visit(Vertex v) throws java.lang.IllegalStateException
v
becomes part of
the growing forest (state 3).v
- the vertex to be visited, i.e. adjoint to the forestjava.lang.IllegalStateException
- if v
is still
in state 1public boolean anyEdge(Edge e) throws java.lang.IllegalStateException
e
has no special role.
In particular it is neither candidate, nor best, nor final edge
(state 1).e
- the edge currently having no special rolejava.lang.IllegalStateException
- public boolean candEdge(Edge e) throws java.lang.IllegalArgumentException, java.lang.IllegalStateException
e
becomes a candidate
for getting the best (cheapest) edge in connecting a vertex
with the growing forest (state 2).
e
is
part of the growing forest, and that e
has been
an any edge before.e
- the edge that becomes a candidate for being a best edgejava.lang.IllegalArgumentException
- if not exactly one vertex
of e
is part of the growing forestjava.lang.IllegalStateException
- if e
has not been
an any edge beforepublic boolean bestEdge(Edge e) throws java.lang.IllegalArgumentException, java.lang.IllegalStateException
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).
e
is
part of the growing forest, and that e
has been
a candidate edge beforee
- the edge that becomes a best edge for its unique
non-forest vertexjava.lang.IllegalArgumentException
- if not exactly one vertex
of e
is part of the growing forestjava.lang.IllegalStateException
- if e
has not been
a candidate edge beforepublic boolean treeEdge(Edge e) throws java.lang.IllegalArgumentException, java.lang.IllegalStateException
e
is an element of
the final spanning tree (state 4).
e
has been a best edge
before.e
- the edge that becomes part of the forestjava.lang.IllegalArgumentException
- if one of the vertices
is not part of the forestjava.lang.IllegalStateException
- if e
has not
been a best edge before