Package oracle.spatial.network.lod

Class BreadthFirstSearch

java.lang.Object

oracle.spatial.network.lod.NetworkSearch

oracle.spatial.network.lod.BreadthFirstSearch

All Implemented Interfaces:

ShortestPath

Direct Known Subclasses:

AStar, Dijkstra, KShortestPathsBfs

public class BreadthFirstSearch
extends NetworkSearch
implements ShortestPath

Network search algorithm that explores the network in breadth first manner.

Since:

11gR1

Nested Class Summary

Nested classes/interfaces inherited from class oracle.spatial.network.lod.NetworkSearch

NetworkSearch.MatchedPoint, NetworkSearch.NetworkSearchTree, NetworkSearch.NodeLinkIds, NetworkSearch.PartialLinkElement, NetworkSearch.PointOnNetWithLink, NetworkSearch.SameLinkMatchedPointPair, NetworkSearch.Statistics, NetworkSearch.TmpSearchData

Field Summary

Fields inherited from class oracle.spatial.network.lod.NetworkSearch

analyst, initialAnalysisInfo, initialCapacity, lccs, lls, nccs, ne, queue

Constructor Summary

Constructors

Constructor	Description
BreadthFirstSearch()
BreadthFirstSearch(NetworkExplorer ne, LinkCostCalculator[] lccs, NodeCostCalculator[] nccs, LinkLevelSelector lls)
BreadthFirstSearch(NetworkExplorer ne, LinkCostCalculator[] lccs, NodeCostCalculator[] nccs, LinkLevelSelector lls, PriorityQueue queue)

Method Summary

Modifier and Type	Method	Description
protected LogicalNetNode	allPathsExpand(VisitedNode minElem, HeavyPointOnNet[] startPoints, HeavyPointOnNet[] endPoints, LongHashMap<VisitedNode> fullyExpandedNodes, int[] userDataCategories, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, double costBound, LODNetworkConstraint constraint, int direction, NetworkSearch.Statistics stat, double[] currMaxCost)	This expands a node, i.e., processes the links connected to the node.
protected VisitedNode	allPathsRelax(VisitedNode minElem, LogicalNetLink nextLink, LogicalNetNode currNode, LogicalNetNode nextNode, HeavyPointOnNet[] startPoints, HeavyPointOnNet[] endPoints, LongHashMap<VisitedNode> fullyExpandedNodes, int[] userDataCategories, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, double costBound, LODNetworkConstraint constraint, int direction, double[] currMaxCost)	This processes one link from the node currently being expanded.
BreadthFirstSearch	clone()
protected LogicalSubPath	createSingleLinkSubPath(NetworkSearch.SameLinkMatchedPointPair sameLinkPoints, int[] userDataCategories, int direction)
protected LogicalSubPath[]	createSingleLinkSubPaths(NetworkSearch.SameLinkMatchedPointPair[] sameLinkPoints, int[] userDataCategories, int direction)
protected LogicalSubPath	getMinSubPath(LogicalSubPath[] subPaths)
protected HeavyPointOnNet[]	getPointsWithCommonLink(HeavyPointOnNet[] startPoints, HeavyPointOnNet[] endPoints)
FeaturePath[]	nearestFeatures(PointOnNet[] startPoints, int numberOfFeatures, int[] featureLayers, LODNetworkConstraint constraint, FeatureFilter featureFilter, int direction)
LogicalLightSubPath[]	nearestNeighbors(PointOnNet[] startPoints, int numberOfNeighbors, int direction, LODNetworkConstraint constraint, LODGoalNode goalNode, boolean returnFullPath)
PathToPoint[]	nearestPoints(PointOnNet[] startPoint, PointOnNet[][] endPoints, int k, LODNetworkConstraint constraint, int direction, boolean returnFullPath)
NetworkBuffer	networkBuffer(PointOnNet[] startPoints, double cost, int direction, LODNetworkConstraint constraint)	Returns network buffer within the specified cost.
protected NetworkSearch.SameLinkMatchedPointPair[]	removeSameLinkMatchedPoints(HeavyPointOnNet[] startPoints, java.util.HashMap<java.lang.Long,java.util.HashSet<HeavyPointOnNet[]>> nodeToEndPoints)
LogicalSubPath	shortestPath(PointOnNet[] startPoints, PointOnNet[] endPoints, LODNetworkConstraint constraint, int direction)	Returns the shortest path between a set of candidate start points and a set of end points.
LogicalSubPath[]	shortestPaths(PointOnNet[] startPoints, PointOnNet[][] endPoints, LODNetworkConstraint constraint, int direction)
LogicalLightSubPath[]	shortestPathsLight(PointOnNet[] startPoints, PointOnNet[][] endPoints, LODNetworkConstraint constraint, int direction)
LogicalLightSubPath[]	traceOut(PointOnNet[] startPoints, double cost, int direction, LODNetworkConstraint constraint, LODGoalNode goalNode, boolean returnFullPath, boolean returnBoundaryPointsOnly)
LogicalLightSubPath[]	withinCost(PointOnNet[] startPoints, double cost, int direction, LODNetworkConstraint constraint, LODGoalNode goalNode, boolean returnFullPath, boolean returnBoundaryPointsOnly)
FeaturePath[]	withinCostFeatures(PointOnNet[] startPoints, double cost, int[] featureLayers, LODNetworkConstraint constraint, FeatureFilter featureFilter, int direction)	Returns the features and the paths to/from them within the given cost.
protected PointOnNet[]	withinCostNodesAndBoundaryPoints(PointOnNet[] startPoints, double cost, int direction, LODNetworkConstraint constraint, boolean boundaryPointsOnly)	Returns all the nodes and boundary points on links within the given cost.
PathToPoint[]	withinCostPoints(PointOnNet[] startPoint, PointOnNet[][] endPoints, double maxCost, LODNetworkConstraint constraint, int direction, boolean returnFullPath)

Methods inherited from class oracle.spatial.network.lod.NetworkSearch

buildNodeToEndPointsMap, computeNextElementCost, copy, createInitialElement, createNextElement, expand, findConnectedComponentsInPartition, findConnectedFeatures, findConnectedNodes, findConnectedNodes, getAdjacentNodes, getCurrentLink, getElementPartition, getExpandedNode, getFeatureLayerIds, getLinkCostCalculators, getLinkLevelSelector, getMatchedEndPoints, getNextLinks, getNextNode, getNextNodeToExpand, getNodeCostCalculators, getUserDataCategories, getXMLSchema, init, initialize, initSearch, isConstraintSatisfied, logExpandedNode, pointArrayToString, preparePathFeature, relax, removeMatchedEndPoints, reset, setAnalysisInfoForCurrNode, setAnalysisInfoForNextNode, setCurrentAnalysisInfo, setCurrLinkNodeAnalysisInfo, setInitialAnalysisInfo, setLinkCostCalculators, setLinkLevelSelector, setNetworkAnalyst, setNetworkExplorer, setNodeCostCalculators

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface oracle.spatial.network.lod.ShortestPath

getLinkCostCalculators, getLinkLevelSelector, getNodeCostCalculators, setInitialAnalysisInfo, setLinkCostCalculators, setLinkLevelSelector, setNetworkAnalyst, setNodeCostCalculators

Constructor Detail

BreadthFirstSearch

public BreadthFirstSearch()

BreadthFirstSearch

public BreadthFirstSearch(NetworkExplorer ne,
                          LinkCostCalculator[] lccs,
                          NodeCostCalculator[] nccs,
                          LinkLevelSelector lls,
                          PriorityQueue queue)

BreadthFirstSearch

public BreadthFirstSearch(NetworkExplorer ne,
                          LinkCostCalculator[] lccs,
                          NodeCostCalculator[] nccs,
                          LinkLevelSelector lls)

Method Detail

clone

public BreadthFirstSearch clone()

Specified by:

clone in interface ShortestPath

Overrides:

clone in class java.lang.Object

nearestNeighbors

public LogicalLightSubPath[] nearestNeighbors(PointOnNet[] startPoints,
                                              int numberOfNeighbors,
                                              int direction,
                                              LODNetworkConstraint constraint,
                                              LODGoalNode goalNode,
                                              boolean returnFullPath)
                                       throws LODNetworkException

Throws:

LODNetworkException

nearestPoints

public PathToPoint[] nearestPoints(PointOnNet[] startPoint,
                                   PointOnNet[][] endPoints,
                                   int k,
                                   LODNetworkConstraint constraint,
                                   int direction,
                                   boolean returnFullPath)
                            throws LODNetworkException

Throws:

LODNetworkException

withinCostPoints

public PathToPoint[] withinCostPoints(PointOnNet[] startPoint,
                                      PointOnNet[][] endPoints,
                                      double maxCost,
                                      LODNetworkConstraint constraint,
                                      int direction,
                                      boolean returnFullPath)
                               throws LODNetworkException

Throws:

LODNetworkException

withinCost

public LogicalLightSubPath[] withinCost(PointOnNet[] startPoints,
                                        double cost,
                                        int direction,
                                        LODNetworkConstraint constraint,
                                        LODGoalNode goalNode,
                                        boolean returnFullPath,
                                        boolean returnBoundaryPointsOnly)
                                 throws LODNetworkException

Throws:

LODNetworkException

traceOut

public LogicalLightSubPath[] traceOut(PointOnNet[] startPoints,
                                      double cost,
                                      int direction,
                                      LODNetworkConstraint constraint,
                                      LODGoalNode goalNode,
                                      boolean returnFullPath,
                                      boolean returnBoundaryPointsOnly)
                               throws LODNetworkException

Throws:

LODNetworkException

networkBuffer

public NetworkBuffer networkBuffer(PointOnNet[] startPoints,
                                   double cost,
                                   int direction,
                                   LODNetworkConstraint constraint)
                            throws LODNetworkException

Returns network buffer within the specified cost.

Parameters:

startPoints -

cost -

direction -

constraint -

Returns:

Throws:

LODNetworkException

withinCostNodesAndBoundaryPoints

protected PointOnNet[] withinCostNodesAndBoundaryPoints(PointOnNet[] startPoints,
                                                        double cost,
                                                        int direction,
                                                        LODNetworkConstraint constraint,
                                                        boolean boundaryPointsOnly)
                                                 throws LODNetworkException

Returns all the nodes and boundary points on links within the given cost.

Parameters:

startPoints -

cost -

direction -

constraint -

returnBoundaryPointsOnly -

Returns:

Throws:

LODNetworkException

nearestFeatures

public FeaturePath[] nearestFeatures(PointOnNet[] startPoints,
                                     int numberOfFeatures,
                                     int[] featureLayers,
                                     LODNetworkConstraint constraint,
                                     FeatureFilter featureFilter,
                                     int direction)
                              throws LODNetworkException

Throws:

LODNetworkException

withinCostFeatures

public FeaturePath[] withinCostFeatures(PointOnNet[] startPoints,
                                        double cost,
                                        int[] featureLayers,
                                        LODNetworkConstraint constraint,
                                        FeatureFilter featureFilter,
                                        int direction)
                                 throws LODNetworkException

Returns the features and the paths to/from them within the given cost.

Parameters:

startPoints -

cost -

direction -

constraint -

featureFilter -

Returns:

Throws:

LODNetworkException

createSingleLinkSubPaths

protected LogicalSubPath[] createSingleLinkSubPaths(NetworkSearch.SameLinkMatchedPointPair[] sameLinkPoints,
                                                    int[] userDataCategories,
                                                    int direction)
                                             throws LODNetworkException

Throws:

LODNetworkException

createSingleLinkSubPath

protected LogicalSubPath createSingleLinkSubPath(NetworkSearch.SameLinkMatchedPointPair sameLinkPoints,
                                                 int[] userDataCategories,
                                                 int direction)
                                          throws LODNetworkException

Throws:

LODNetworkException

getPointsWithCommonLink

protected HeavyPointOnNet[] getPointsWithCommonLink(HeavyPointOnNet[] startPoints,
                                                    HeavyPointOnNet[] endPoints)
                                             throws LODNetworkException

Throws:

LODNetworkException

removeSameLinkMatchedPoints

protected NetworkSearch.SameLinkMatchedPointPair[] removeSameLinkMatchedPoints(HeavyPointOnNet[] startPoints,
                                                                               java.util.HashMap<java.lang.Long,java.util.HashSet<HeavyPointOnNet[]>> nodeToEndPoints)
                                                                        throws LODNetworkException

Throws:

LODNetworkException

shortestPath

public LogicalSubPath shortestPath(PointOnNet[] startPoints,
                                   PointOnNet[] endPoints,
                                   LODNetworkConstraint constraint,
                                   int direction)
                            throws LODNetworkException

Description copied from interface: ShortestPath

Returns the shortest path between a set of candidate start points and a set of end points.

Specified by:

shortestPath in interface ShortestPath

Parameters:

startPoints - start candidates

endPoints - end candidates

constraint - network constraint

direction - NetworkExplorer.DIRECTION_FORWARD or NetworkExplorer.DIRECTION_BACKWARD

Returns:

Throws:

LODNetworkException

shortestPaths

public LogicalSubPath[] shortestPaths(PointOnNet[] startPoints,
                                      PointOnNet[][] endPoints,
                                      LODNetworkConstraint constraint,
                                      int direction)
                               throws LODNetworkException

Throws:

LODNetworkException

shortestPathsLight

public LogicalLightSubPath[] shortestPathsLight(PointOnNet[] startPoints,
                                                PointOnNet[][] endPoints,
                                                LODNetworkConstraint constraint,
                                                int direction)
                                         throws LODNetworkException

Throws:

LODNetworkException

getMinSubPath

protected LogicalSubPath getMinSubPath(LogicalSubPath[] subPaths)

allPathsExpand

protected LogicalNetNode allPathsExpand(VisitedNode minElem,
                                        HeavyPointOnNet[] startPoints,
                                        HeavyPointOnNet[] endPoints,
                                        LongHashMap<VisitedNode> fullyExpandedNodes,
                                        int[] userDataCategories,
                                        LODAnalysisInfo currAnalysisInfo,
                                        LODAnalysisInfo combinedAnalysisInfo,
                                        double costBound,
                                        LODNetworkConstraint constraint,
                                        int direction,
                                        NetworkSearch.Statistics stat,
                                        double[] currMaxCost)
                                 throws LODNetworkException

This expands a node, i.e., processes the links connected to the node. In the end, returns the node that has just been expanded.

Parameters:

minElem - the element for the node to be expanded

endPoints - end points

fullyExpandedNodes - node that have been fully expanded

userDataCategories -

constraint - network constraint

currAnalysisInfo - current analysis info, i.e., analysis info in the current analysis

combinedAnalysisInfo - current analysis info combined with the initial analysis info

direction - expansion direction, forward (shortestPath, nearest neigbors, within cost, trace out analysis) or backword (nearest reaching neighbors, within reaching cost, trace in analysis)

Returns:

the node that has been expanded

Throws:

LODNetworkException

allPathsRelax

protected VisitedNode allPathsRelax(VisitedNode minElem,
                                    LogicalNetLink nextLink,
                                    LogicalNetNode currNode,
                                    LogicalNetNode nextNode,
                                    HeavyPointOnNet[] startPoints,
                                    HeavyPointOnNet[] endPoints,
                                    LongHashMap<VisitedNode> fullyExpandedNodes,
                                    int[] userDataCategories,
                                    LODAnalysisInfo currAnalysisInfo,
                                    LODAnalysisInfo combinedAnalysisInfo,
                                    double costBound,
                                    LODNetworkConstraint constraint,
                                    int direction,
                                    double[] currMaxCost)
                             throws LODNetworkException

This processes one link from the node currently being expanded. It addes or updates the element for the next node in the queue.

Parameters:

minElem - the element for the node currently being expanded

nextLink - the link to be processed

endPoints - end points

fullyExpandedNodes - node that have been fully expanded

currAnalysisInfo - current analysis info, i.e., analysis info in the current analysis

combinedAnalysisInfo - current analysis info combined with the initial analysis info

constraint - network constraint

direction - expansion direction, forward (shortestPath, nearest neigbors, within cost, trace out analysis) or backword (nearest reaching neighbors, within reaching cost, trace in analysis)

Throws:

LODNetworkException