T
- the type of all nodes in the Graph
public class Coverage<T>
extends java.lang.Object
Graph
instances.
Finds all Graph
nodes that a GraphAgent
can reach by any movement path that
starts on a specified node, and whose total cost does not exceed a specified maximum cost.
The total path cost is defined as the sum of all GraphAgent.getStepCost(T, T)
results
for each movement step between two adjacent path nodes. Only nodes for which GraphAgent.canOccupy(T)
succeeds are considered reachable.
Caution: Multi-step movements are problematic when the GraphAgent
uses a
non-trivial GraphAgent.canOccupy(T)
condition. After a successful path search, all
found nodes()
are valid end points for a single-step movement. However, attempting
to reach any nodes()
element with multiple movement steps may prove impossible.
Since the algorithm does not know whether a given intermediate path node will be occupied
permanently or merely traversed, the path by which a nodes()
element was reached may
contain many intermediate nodes for which GraphAgent.canOccupy(T)
fails.
Modifier and Type | Field and Description |
---|---|
Graph<T> |
graph
The
Graph on which all searches are performed. |
Modifier and Type | Method and Description |
---|---|
GraphAgent<T> |
agent()
Gets the
GraphAgent for the last search. |
boolean |
findReachable(GraphAgent<T> agent,
T source,
double maxCost)
Finds all
graph nodes that the specified GraphAgent can reach
from the specified source node within the specified maximum path cost. |
java.util.List<T> |
nodes()
Gets all
graph nodes that were reached by the last successful search. |
public boolean findReachable(GraphAgent<T> agent, T source, double maxCost)
graph
nodes that the specified GraphAgent
can reach
from the specified source node within the specified maximum path cost.
Returns false
if graph
does not contain source
,
or if there are no nodes reachable from source
whose total path cost
is equal to or less than the specified maxCost
.
Otherwise, returns true
and sets nodes()
to the result of the
path search. nodes()
contains only those reachable nodes for which
GraphAgent.canOccupy(T)
has succeeded.
If GraphAgent.relaxedRange()
is true
for agent
, nodes()
includes those nodes whose total path cost exceeds maxCost
, but which can be
reached from a neighbor whose total path cost is strictly less than maxCost
.
These nodes are considered reachable regardless of their actual step costs.
agent
- the GraphAgent
that performs the movementsource
- the source node within graph
where the movement startsmaxCost
- the maximum total cost of the best path from source
to any reachable graph
nodetrue
if one or more graph
nodes could be reached
from source
within maxCost
, else false
java.lang.IllegalArgumentException
- if maxCost
is equal to or less than zerojava.lang.NullPointerException
- if agent
or source
is null
public GraphAgent<T> agent()
GraphAgent
for the last search.GraphAgent
that was supplied to the last findReachable(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, double)
call, or null
if the method has not yet been calledpublic java.util.List<T> nodes()
graph
nodes that were reached by the last successful search.
Returns an empty collection if the last findReachable(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, double)
call returned
false
, or if the method has not yet been called.List
containing all graph
nodes that were reached
by the last successful findReachable(org.kynosarges.tektosyne.graph.GraphAgent<T>, T, double)
call, not including the source node