Package oracle.spatial.network.lod

Class NetworkSearch

java.lang.Object

oracle.spatial.network.lod.NetworkSearch

Direct Known Subclasses:

BreadthFirstSearch

public class NetworkSearch
extends java.lang.Object

Since:

release specific (what release of product did this appear in)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	NetworkSearch.MatchedPoint
protected static class	NetworkSearch.NetworkSearchTree
protected static class	NetworkSearch.NodeLinkIds
protected static class	NetworkSearch.PartialLinkElement
protected static class	NetworkSearch.PointOnNetWithLink
protected static class	NetworkSearch.SameLinkMatchedPointPair
protected static class	NetworkSearch.Statistics
protected static class	NetworkSearch.TmpSearchData

Field Summary

Fields

Modifier and Type	Field	Description
protected NetworkAnalyst	analyst
protected LODAnalysisInfo	initialAnalysisInfo
protected static int	initialCapacity
protected LinkCostCalculator[]	lccs
protected LinkLevelSelector	lls
protected NodeCostCalculator[]	nccs
protected NetworkExplorer	ne
protected PriorityQueue<VisitedNode>	queue

Constructor Summary

Constructors

Constructor	Description
NetworkSearch()
NetworkSearch(NetworkExplorer ne, LinkCostCalculator[] lccs, NodeCostCalculator[] nccs, LinkLevelSelector lls, PriorityQueue<VisitedNode> queue)

Method Summary

Modifier and Type	Method	Description
protected static java.util.HashMap<java.lang.Long,java.util.HashSet<HeavyPointOnNet[]>>	buildNodeToEndPointsMap(HeavyPointOnNet[][] heavyEndPoints)
protected double	computeNextElementCost(VisitedNode currElem, double currNodeCost, double nextLinkCost)	Returns the cost of the next element.
protected static double[]	copy(double[] array)
protected VisitedNode	createInitialElement(long id, HeavyPointOnNet startPoint, HeavyPointOnNet[] endPoints, double[] costs, double[] costsAtNode, long prevLink, VisitedNode prevNode, int depth, int linkLevel, int partitionId)
protected VisitedNode	createNextElement(VisitedNode minElem, LODAnalysisInfo analysisInfo, java.lang.Object nextUserObject, double newCost, double costAtCurrNode, int linkLevel, int partitionId, HeavyPointOnNet[] endPoints, int direction)
protected LogicalNetNode	expand(VisitedNode minElem, HeavyPointOnNet[] startPoints, HeavyPointOnNet[] endPoints, LongHashMap<VisitedNode> fullyExpandedNodes, int[] userDataCategories, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, double costBound, LongHashMap<java.util.ArrayList<NetworkSearch.PartialLinkElement>> partialLinks, NetworkBuffer buffer, LODNetworkConstraint constraint, int direction, NetworkSearch.Statistics stat, oracle.spatial.network.lod.NetworkSearch.FeatureBundle featureBundle, double[] currMaxCost, boolean boundaryPointsOnly, boolean markExpandedNodes)	This expands a node, i.e., processes the links connected to the node.
protected int	findConnectedComponentsInPartition(int partitionId, int linkLevel, int startComponentId, java.util.ArrayList<oracle.spatial.network.lod.AnalysisUtility.NodeComponent> nodeComponentArray)	Find the connected components within a partition, with all the external nodes and boundary links included.
Feature[]	findConnectedFeatures(PointOnNet[] startPoints, int[] featureLayers, LODNetworkConstraint constraint, FeatureFilter featureFilter, int direction)	Returns the features within the given cost and the paths to/from them.
protected OrderedLongSet	findConnectedNodes(PointOnNet[] startPoints, int direction, boolean includeSourceNode, LODNetworkConstraint constraint, LODGoalNode goalNode)	Returns the nodes connected to startNodeId in the specified direction
protected OrderedLongSet	findConnectedNodes(PointOnNet[] sourcePoints, LODNetworkConstraint constraint, LODGoalNode goalNode)
protected LongHashMap<HeavyPointOnNet>	getAdjacentNodes(HeavyPointOnNet[] points)
protected LogicalNetLink	getCurrentLink(VisitedNode minElem, LogicalBasicNetwork part)
protected LogicalPartition	getElementPartition(VisitedNode elem, int[] userDataCategories, int[] featureLayers)
protected VisitedNode	getExpandedNode(long nodeId)
protected int[]	getFeatureLayerIds(oracle.spatial.network.lod.NetworkSearch.FeatureBundle featureBundle)
LinkCostCalculator[]	getLinkCostCalculators()
LinkLevelSelector	getLinkLevelSelector()
protected java.util.List<NetworkSearch.MatchedPoint>	getMatchedEndPoints(java.util.HashSet<HeavyPointOnNet[]> pointsSet, VisitedNode elem, int[] userDataCategories, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, LODNetworkConstraint constraint, int direction)	Returns the matched end point among members of the heavy point array.
protected LogicalNetLink[]	getNextLinks(LogicalNetNode currNode, int direction)
protected LogicalNetNode	getNextNode(LogicalNetNode currNode, LogicalNetLink nextLink, VisitedNode minElem, int direction, int[] userDataCategories, int[] featureLayers)
protected VisitedNode	getNextNodeToExpand()
NodeCostCalculator[]	getNodeCostCalculators()
protected int[]	getUserDataCategories()	Returns null.
java.lang.String	getXMLSchema()
void	init(org.w3c.dom.Element parameter)
protected void	initialize(HeavyPointOnNet[] startPoints, HeavyPointOnNet[] endPoints, int[] userDataCategories, int[] featureLayers, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, LODNetworkConstraint constraint, double cutoffCost, LongHashMap<java.util.ArrayList<NetworkSearch.PartialLinkElement>> partialLinkMap, NetworkBuffer buffer, int direction)
NetworkSearch.TmpSearchData	initSearch(PointOnNet[] startPoints, PointOnNet[] endPoints, LODNetworkConstraint constraint, int direction)
protected boolean	isConstraintSatisfied(HeavyPointOnNet endPoint, VisitedNode elem, LogicalPartition part, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, LODNetworkConstraint constraint, int[] userDataCategories, int[] featureLayers)
protected void	logExpandedNode(java.lang.Object minNodeId, int direction)
protected static java.lang.String	pointArrayToString(PointOnNet[] points)
static PathFeature	preparePathFeature(LogicalSubPath subPath, long pathId)
protected VisitedNode	relax(VisitedNode minElem, LogicalNetLink nextLink, LogicalNetNode currNode, LogicalNetNode nextNode, HeavyPointOnNet[] startPoints, HeavyPointOnNet[] endPoints, LongHashMap<VisitedNode> fullyExpandedNodes, int[] userDataCategories, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, double costBound, LongHashMap<java.util.ArrayList<NetworkSearch.PartialLinkElement>> partialLinkMap, NetworkBuffer buffer, LODNetworkConstraint constraint, int direction, oracle.spatial.network.lod.NetworkSearch.FeatureBundle featureBundle, double[] currMaxCost, boolean boundaryPointsOnly, boolean markExpandedNodes)	This processes one link from the node currently being expanded.
protected java.util.List<NetworkSearch.MatchedPoint>	removeMatchedEndPoints(java.util.HashMap<java.lang.Long,java.util.HashSet<HeavyPointOnNet[]>> nodeToEndPoints, VisitedNode elem, int[] userDataCategories, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, LODNetworkConstraint constraint, int direction)
void	reset()
protected void	setAnalysisInfoForCurrNode(VisitedNode minElem, LogicalNetLink currLink, LogicalNetNode currNode, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, LODNetworkConstraint constraint)
protected void	setAnalysisInfoForNextNode(LogicalNetLink nextLink, LogicalNetNode nextNode, LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo)
protected void	setCurrentAnalysisInfo(LogicalPartition partition, LogicalNetNode node, LongHashMap<VisitedNode> visitedNodes, LODAnalysisInfo ai, LODNetworkConstraint constraint, int[] userDataCategories, int[] featureLayers)
protected void	setCurrLinkNodeAnalysisInfo(LODAnalysisInfo currAnalysisInfo, LODAnalysisInfo combinedAnalysisInfo, LogicalNetNode currNode, VisitedNode minElem, LogicalPartition part, LODNetworkConstraint constraint)
void	setInitialAnalysisInfo(LODAnalysisInfo analysisInfo)
void	setLinkCostCalculators(LinkCostCalculator[] lccs)
void	setLinkLevelSelector(LinkLevelSelector lls)
void	setNetworkAnalyst(NetworkAnalyst analyst)
void	setNetworkExplorer(NetworkExplorer ne)
void	setNodeCostCalculators(NodeCostCalculator[] nccs)

Methods inherited from class java.lang.Object

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

Field Detail

initialCapacity

protected static final int initialCapacity

See Also:

Constant Field Values

lccs

protected LinkCostCalculator[] lccs

nccs

protected NodeCostCalculator[] nccs

ne

protected NetworkExplorer ne

lls

protected LinkLevelSelector lls

initialAnalysisInfo

protected LODAnalysisInfo initialAnalysisInfo

queue

protected PriorityQueue<VisitedNode> queue

analyst

protected NetworkAnalyst analyst

Constructor Detail

NetworkSearch

public NetworkSearch()

NetworkSearch

public NetworkSearch(NetworkExplorer ne,
                     LinkCostCalculator[] lccs,
                     NodeCostCalculator[] nccs,
                     LinkLevelSelector lls,
                     PriorityQueue<VisitedNode> queue)

Method Detail

init

public void init(org.w3c.dom.Element parameter)

getXMLSchema

public java.lang.String getXMLSchema()

setNetworkExplorer

public void setNetworkExplorer(NetworkExplorer ne)

setAnalysisInfoForCurrNode

protected void setAnalysisInfoForCurrNode(VisitedNode minElem,
                                          LogicalNetLink currLink,
                                          LogicalNetNode currNode,
                                          LODAnalysisInfo currAnalysisInfo,
                                          LODAnalysisInfo combinedAnalysisInfo,
                                          LODNetworkConstraint constraint)

setAnalysisInfoForNextNode

protected void setAnalysisInfoForNextNode(LogicalNetLink nextLink,
                                          LogicalNetNode nextNode,
                                          LODAnalysisInfo currAnalysisInfo,
                                          LODAnalysisInfo combinedAnalysisInfo)

setInitialAnalysisInfo

public void setInitialAnalysisInfo(LODAnalysisInfo analysisInfo)

pointArrayToString

protected static java.lang.String pointArrayToString(PointOnNet[] points)

initSearch

public NetworkSearch.TmpSearchData initSearch(PointOnNet[] startPoints,
                                              PointOnNet[] endPoints,
                                              LODNetworkConstraint constraint,
                                              int direction)
                                       throws LODNetworkException

Throws:

LODNetworkException

initialize

protected void initialize(HeavyPointOnNet[] startPoints,
                          HeavyPointOnNet[] endPoints,
                          int[] userDataCategories,
                          int[] featureLayers,
                          LODAnalysisInfo currAnalysisInfo,
                          LODAnalysisInfo combinedAnalysisInfo,
                          LODNetworkConstraint constraint,
                          double cutoffCost,
                          LongHashMap<java.util.ArrayList<NetworkSearch.PartialLinkElement>> partialLinkMap,
                          NetworkBuffer buffer,
                          int direction)
                   throws LODNetworkException

Parameters:

startPoints -

endPoints -

userDataCategories -

featureLayers -

currAnalysisInfo -

combinedAnalysisInfo -

constraint -

cutoffCost -

partialLinkMap - if not null, handle trace in/out analysis

buffer -

direction -

Throws:

LODNetworkException

isConstraintSatisfied

protected boolean isConstraintSatisfied(HeavyPointOnNet endPoint,
                                        VisitedNode elem,
                                        LogicalPartition part,
                                        LODAnalysisInfo currAnalysisInfo,
                                        LODAnalysisInfo combinedAnalysisInfo,
                                        LODNetworkConstraint constraint,
                                        int[] userDataCategories,
                                        int[] featureLayers)
                                 throws LODNetworkException

Throws:

LODNetworkException

getUserDataCategories

protected int[] getUserDataCategories()

Returns null. Subclasses should overide this method to return the user data categories required by the algorithm used in the subclass.

Returns:

getElementPartition

protected LogicalPartition getElementPartition(VisitedNode elem,
                                               int[] userDataCategories,
                                               int[] featureLayers)
                                        throws LODNetworkException

Throws:

LODNetworkException

getExpandedNode

protected VisitedNode getExpandedNode(long nodeId)

getNextNodeToExpand

protected VisitedNode getNextNodeToExpand()

logExpandedNode

protected void logExpandedNode(java.lang.Object minNodeId,
                               int direction)

getFeatureLayerIds

protected int[] getFeatureLayerIds(oracle.spatial.network.lod.NetworkSearch.FeatureBundle featureBundle)

getNextLinks

protected LogicalNetLink[] getNextLinks(LogicalNetNode currNode,
                                        int direction)

getNextNode

protected LogicalNetNode getNextNode(LogicalNetNode currNode,
                                     LogicalNetLink nextLink,
                                     VisitedNode minElem,
                                     int direction,
                                     int[] userDataCategories,
                                     int[] featureLayers)
                              throws LODNetworkException

Throws:

LODNetworkException

setCurrLinkNodeAnalysisInfo

protected void setCurrLinkNodeAnalysisInfo(LODAnalysisInfo currAnalysisInfo,
                                           LODAnalysisInfo combinedAnalysisInfo,
                                           LogicalNetNode currNode,
                                           VisitedNode minElem,
                                           LogicalPartition part,
                                           LODNetworkConstraint constraint)

expand

protected LogicalNetNode expand(VisitedNode minElem,
                                HeavyPointOnNet[] startPoints,
                                HeavyPointOnNet[] endPoints,
                                LongHashMap<VisitedNode> fullyExpandedNodes,
                                int[] userDataCategories,
                                LODAnalysisInfo currAnalysisInfo,
                                LODAnalysisInfo combinedAnalysisInfo,
                                double costBound,
                                LongHashMap<java.util.ArrayList<NetworkSearch.PartialLinkElement>> partialLinks,
                                NetworkBuffer buffer,
                                LODNetworkConstraint constraint,
                                int direction,
                                NetworkSearch.Statistics stat,
                                oracle.spatial.network.lod.NetworkSearch.FeatureBundle featureBundle,
                                double[] currMaxCost,
                                boolean boundaryPointsOnly,
                                boolean markExpandedNodes)
                         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

relax

protected VisitedNode relax(VisitedNode minElem,
                            LogicalNetLink nextLink,
                            LogicalNetNode currNode,
                            LogicalNetNode nextNode,
                            HeavyPointOnNet[] startPoints,
                            HeavyPointOnNet[] endPoints,
                            LongHashMap<VisitedNode> fullyExpandedNodes,
                            int[] userDataCategories,
                            LODAnalysisInfo currAnalysisInfo,
                            LODAnalysisInfo combinedAnalysisInfo,
                            double costBound,
                            LongHashMap<java.util.ArrayList<NetworkSearch.PartialLinkElement>> partialLinkMap,
                            NetworkBuffer buffer,
                            LODNetworkConstraint constraint,
                            int direction,
                            oracle.spatial.network.lod.NetworkSearch.FeatureBundle featureBundle,
                            double[] currMaxCost,
                            boolean boundaryPointsOnly,
                            boolean markExpandedNodes)
                     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

getCurrentLink

protected LogicalNetLink getCurrentLink(VisitedNode minElem,
                                        LogicalBasicNetwork part)

createInitialElement

protected VisitedNode createInitialElement(long id,
                                           HeavyPointOnNet startPoint,
                                           HeavyPointOnNet[] endPoints,
                                           double[] costs,
                                           double[] costsAtNode,
                                           long prevLink,
                                           VisitedNode prevNode,
                                           int depth,
                                           int linkLevel,
                                           int partitionId)

createNextElement

protected VisitedNode createNextElement(VisitedNode minElem,
                                        LODAnalysisInfo analysisInfo,
                                        java.lang.Object nextUserObject,
                                        double newCost,
                                        double costAtCurrNode,
                                        int linkLevel,
                                        int partitionId,
                                        HeavyPointOnNet[] endPoints,
                                        int direction)

computeNextElementCost

protected double computeNextElementCost(VisitedNode currElem,
                                        double currNodeCost,
                                        double nextLinkCost)

Returns the cost of the next element.

Parameters:

currElem -

currNodeCost -

nextLinkCost -

Returns:

getLinkLevelSelector

public LinkLevelSelector getLinkLevelSelector()

setLinkLevelSelector

public void setLinkLevelSelector(LinkLevelSelector lls)

getLinkCostCalculators

public LinkCostCalculator[] getLinkCostCalculators()

setLinkCostCalculators

public void setLinkCostCalculators(LinkCostCalculator[] lccs)

getNodeCostCalculators

public NodeCostCalculator[] getNodeCostCalculators()

setNodeCostCalculators

public void setNodeCostCalculators(NodeCostCalculator[] nccs)

getMatchedEndPoints

protected java.util.List<NetworkSearch.MatchedPoint> getMatchedEndPoints(java.util.HashSet<HeavyPointOnNet[]> pointsSet,
                                                                         VisitedNode elem,
                                                                         int[] userDataCategories,
                                                                         LODAnalysisInfo currAnalysisInfo,
                                                                         LODAnalysisInfo combinedAnalysisInfo,
                                                                         LODNetworkConstraint constraint,
                                                                         int direction)

Returns the matched end point among members of the heavy point array.

Parameters:

pointsSet - end points to choose from

elem - node being expanded

userDataCategories -

currAnalysisInfo -

combinedAnalysisInfo -

constraint -

Returns:

removeMatchedEndPoints

protected java.util.List<NetworkSearch.MatchedPoint> removeMatchedEndPoints(java.util.HashMap<java.lang.Long,java.util.HashSet<HeavyPointOnNet[]>> nodeToEndPoints,
                                                                            VisitedNode elem,
                                                                            int[] userDataCategories,
                                                                            LODAnalysisInfo currAnalysisInfo,
                                                                            LODAnalysisInfo combinedAnalysisInfo,
                                                                            LODNetworkConstraint constraint,
                                                                            int direction)
                                                                     throws LODNetworkException

Throws:

LODNetworkException

preparePathFeature

public static PathFeature preparePathFeature(LogicalSubPath subPath,
                                             long pathId)
                                      throws LODNetworkException

Throws:

LODNetworkException

setNetworkAnalyst

public void setNetworkAnalyst(NetworkAnalyst analyst)

findConnectedComponentsInPartition

protected int findConnectedComponentsInPartition(int partitionId,
                                                 int linkLevel,
                                                 int startComponentId,
                                                 java.util.ArrayList<oracle.spatial.network.lod.AnalysisUtility.NodeComponent> nodeComponentArray)
                                          throws LODNetworkException

Find the connected components within a partition, with all the external nodes and boundary links included. This method writes the node id - component id assignment information into the input array, and returns the maximum component ID that has been used so far.

Parameters:

partitionId - ID of the partition in which the connected component is computed

linkLevel - link level on which the connected component is computed

startComponentId - start component ID to be used. All component IDs being assigned to the nodes in the partition must be no smaller than the start component ID.

nodeComponentArray - empty list where the result node ID - component ID pair is written into

Returns:

Throws:

LODNetworkException

findConnectedNodes

protected OrderedLongSet findConnectedNodes(PointOnNet[] sourcePoints,
                                            LODNetworkConstraint constraint,
                                            LODGoalNode goalNode)
                                     throws LODNetworkException

Throws:

LODNetworkException

findConnectedNodes

protected OrderedLongSet findConnectedNodes(PointOnNet[] startPoints,
                                            int direction,
                                            boolean includeSourceNode,
                                            LODNetworkConstraint constraint,
                                            LODGoalNode goalNode)
                                     throws LODNetworkException

Returns the nodes connected to startNodeId in the specified direction

Parameters:

startPoints -

direction - 0: both from and to nodeId
1: from nodeId
2: to nodeId

Returns:

nodes connected to startNodeId in the specified direction

Throws:

LODNetworkException

setCurrentAnalysisInfo

protected void setCurrentAnalysisInfo(LogicalPartition partition,
                                      LogicalNetNode node,
                                      LongHashMap<VisitedNode> visitedNodes,
                                      LODAnalysisInfo ai,
                                      LODNetworkConstraint constraint,
                                      int[] userDataCategories,
                                      int[] featureLayers)
                               throws LODNetworkException

Throws:

LODNetworkException

getAdjacentNodes

protected LongHashMap<HeavyPointOnNet> getAdjacentNodes(HeavyPointOnNet[] points)
                                                 throws LODNetworkException

Throws:

LODNetworkException

reset

public void reset()

buildNodeToEndPointsMap

protected static java.util.HashMap<java.lang.Long,java.util.HashSet<HeavyPointOnNet[]>> buildNodeToEndPointsMap(HeavyPointOnNet[][] heavyEndPoints)

findConnectedFeatures

public Feature[] findConnectedFeatures(PointOnNet[] startPoints,
                                       int[] featureLayers,
                                       LODNetworkConstraint constraint,
                                       FeatureFilter featureFilter,
                                       int direction)
                                throws LODNetworkException

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

Parameters:

startPoints -

featureLayers -

direction -

constraint -

featureFilter -

Returns:

Throws:

LODNetworkException

copy

protected static double[] copy(double[] array)