Package com.amalgamasimulation.graphagent

Class GraphEnvironment<N extends AgentGraphNode,A extends AgentGraphArc,K>

java.lang.Object
com.amalgamasimulation.graphagent.GraphEnvironment<N,A,K>
Direct Known Subclasses:
LongAgentsEnvironment
public class GraphEnvironment<N extends AgentGraphNode,A extends AgentGraphArc,K> extends Object

  • Field Details

  • Constructor Details

    • GraphEnvironment

      public GraphEnvironment()
      Creates a new instance of graph environment with these default settings:

    • GraphEnvironment

      public GraphEnvironment(boolean collisionsTrackingEnabled, boolean callbackPositionsEnabled, boolean pathsCacheEnabled, boolean minTreeCacheEnabled, boolean barrierArcsEnabled)
      Creates a new instance of graph environment with the specified settings.
      Parameters:
      collisionsTrackingEnabled - whether or not to enable tracking collisions of agents. Enabling this option can result in some loss of computational performance but would allow to use GraphAgent.onOtherAgentReached(GraphAgent, boolean) method to determine the collisions of agents
      callbackPositionsEnabled - whether or not to enable callback positions. Callback positions allow to track the events of agents reaching certain positions in the graph. This functionality can slightly decrease computational performance in some cases so this parameter can be switched off if callback positions are not needed
      pathsCacheEnabled - whether or not to allow caching of shortest paths. Enabling caching significantly improves computational performance of big models so switching on this option is recommended in majority of cases. Users might wish to switch off this option if the weight of nodes and arcs change very often and there is little value in caching the shortest paths
      minTreeCacheEnabled - whether or not to use the advanced cache based on keeping the minimal spanning trees of all shortest path searches. Might result in increase in performance in certain cases
      barrierArcsEnabled - whether or not to use the barrier arcs

  • Method Details

    • getArcWeight

      public double getArcWeight(A arcValue, K weightKey)
      Returns the weight of the specified arc used when calculating the shortest paths for agents' movements. Can be overridden in subclasses. The default implementation returns the length of the specified arc, i.e.:

      return arcValue.getLength();

      Parameters:
      arcValue - specified arc
      weightKey - an additional parameter used to parameterize the calculation if necessary. For example, can be agent if the paths should be calculated differently for each agent
      Returns:
      weight of this arc, must be non-negative

    • getNodeWeight

      public double getNodeWeight(N nodeValue, K weightKey)
      Returns the weight of the specified node used when calculating the shortest path for agents' movements. Can be overridden in subclasses. The default implementation returns 0, so by default nodes do not contribute to paths' weights.

      The default implementation is to return zero, i.e.:

      return 0;

      Parameters:
      nodeValue - specified node
      weightKey - an additional parameter used to parameterize the calculation if necessary. For example, can be agent if the paths should be calculated differently for each agent
      Returns:
      weight of this node, must be non-negative

    • getPartialArcWeight

      public double getPartialArcWeight(A arcValue, double startAbsOffset, double endAbsOffset, double startRelOffset, double endRelOffset, K weightKey)
      Returns the weight of the fragment of the specified arc. The fragment of the arc is defined by absolute and relative offsets of its beginning and end.

      Overriding this method allows users, for example, to make certain fragments of arcs less preferable or forbidden for use in path finding.

      The default implementation is to return the weight of the fragment, i.e.:

      return getArcWeight(arcValue, weightKey) * Utils.zidz(endAbsOffset - startAbsOffset, arcValue.getLength());

      For more information about absolute and relative offsets, see documentation of Polyline class. See how the total weight of the arc is calculated:

      Parameters:
      arcValue - specified arc
      startAbsOffset - absolute offset of the fragment's beginning
      endAbsOffset - absolute offset of the fragment's end
      startRelOffset - relative offset of the fragment's beginning
      endRelOffset - relative offset of the fragment's end
      weightKey - an additional parameter used to parameterize the calculation if necessary. For example, can be agent if the paths should be calculated differently for each agent
      Returns:
      weight of the fragment of the specified arc, must be non-negative

    • pathsCacheEnabled

      public boolean pathsCacheEnabled()
      Checks whether caching of the paths is enabled. Enabling paths cache increases the speed of modeling but must be used with caution when the weight of nodes or arcs change as the simulation time goes. In this case, it is still possible to use paths caching but clearCache() method must be called when the weights of nodes or arcs change.

      Paths cache can be enabled or disabled in constructor of this class.

      Returns:
      true if caching of the paths is enabled, false otherwise

    • weightKey

      public K weightKey(GraphAgent<N,A> agent)
      Returns the key that is used as additional parameter when calculating weights of nodes and arcs for the purposes of shortest paths calculation for the specified agent. Can be overridden in subclasses. Default implementation returns null, so all the agents have the same context while calculating their paths.

      An example of weight key can be some type of agent if paths need to be calculated differently for agent of different types

      Parameters:
      agent - specified agent
      Returns:
      weight key

    • addNode

      public Graph<N,A>.Node addNode(N nodeValue)
      Creates a new graph node with the specified node value and adds it to the graph.
      Parameters:
      nodeValue - value of the node being added
      Returns:
      Graph.Node instance that was created and added to the graph

    • addArc

      public Graph<N,A>.Arc addArc(N sourceNodeValue, N destNodeValue, A arcValue)
      Creates a new graph arc between the nodes with the specified values. Assigns the specified value to the created arc and adds it to the graph.
      Parameters:
      sourceNodeValue - value of the source node
      destNodeValue - value of the destination node
      arcValue - value of the arc being added
      Returns:
      Graph.Arc instance that was created and added to the graph, or null if no source or destination node with the specified values were found

    • getNodes

      public List<Graph<N,A>.Node> getNodes()
      Returns an unmodifiable list of all graph nodes. The nodes are sorted according to the order they were added to the graph
      Returns:
      unmodifiable list of Graph.Node instances

    • getNodeValues

      public List<N> getNodeValues()
      Returns an unmodifiable list of all graph node values.
      Returns:
      unmodifiable list of graph node values

    • getArcs

      public List<Graph<N,A>.Arc> getArcs()
      Returns an unmodifiable list of all graph arcs. The arc are sorted according to the order they were added to the graph
      Returns:
      unmodifiable list of Graph.Arc instances

    • getArcValues

      public List<A> getArcValues()
      Returns an unmodifiable list of all graph arc values.
      Returns:
      unmodifiable list of graph arc values

    • getAgents

      public List<GraphAgent<N,A>> getAgents()
      Returns an unmodifiable list of all agents currently living in this environment.
      Returns:
      unmodifiable list of all agents currently living in this environment

    • addArc

      public Pair<Graph<N,A>.Arc,Graph<N,A>.Arc> addArc(N sourceNodeValue, N destNodeValue, A arcValue, A reverseArcValue)
      Creates two new graph arcs (one forward and one backward) between the nodes with the specified values. Assigns the specified values to the created arcs and adds them to the graph.
      Parameters:
      sourceNodeValue - value of the source node of the forward arc
      destNodeValue - value of the destination node of the forward arc
      arcValue - value of the forward arc being added
      reverseArcValue - value of the reverse arc being added
      Returns:
      a Pair of Graph.Arc instances that were created and added to the graph, or null if no source or destination node with the specified values were found

    • getGraph

      public Graph<N,A> getGraph()
      Returns the graph of this graph environment.
      Returns:
      instance of Graph

    • getShortestPathToClosest

      public AgentGraphPath<N,A> getShortestPathToClosest(GeometricGraphPosition<N,A> sourcePosition, List<GeometricGraphPosition<N,A>> destPositions, GraphAgent<N,A> agent)
      Returns the shortest path from the specified source position to the closest one of the specified destination positions for the specified agent, or null if neither of the specified destination positions is reachable from the source position.

      Shortest paths and "closeness" of the positions are determined using the weights provided in the methods:

      The default implementation of these methods returns simple distance-based weights, however these methods can be overridden to customize the path finding logic.

      Parameters:
      sourcePosition - the origin of path finding
      destPositions - the list of possible destination positions
      agent - the agent for which the path is being searched
      Returns:
      an instance of AgentGraphPath representing the shortest path, or null

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(GeometricGraphPosition<N,A> sourcePosition, GeometricGraphPosition<N,A> destPosition, GraphAgent<N,A> agent)
      Returns the shortest path from the specified source position to the specified destination position for the specified agent, or null if no such path exists.

      Shortest path is determined using the weights provided in the methods:

      The default implementation of these methods returns simple distance-based weights, however these methods can be overridden to customize the path finding logic.

      Parameters:
      sourcePosition - the origin of path finding
      destPosition - the destination of path finding
      agent - the agent for which the path is being searched
      Returns:
      an instance of AgentGraphPath representing the shortest path, or null

    • getSourcesAndWeights

      protected List<Pair<GeometricGraphPosition<N,A>,Double>> getSourcesAndWeights(GeometricGraphPosition<N,A> sourcePosition, K weightKey)

    • getDestsAndWeights

      protected List<Pair<GeometricGraphPosition<N,A>,Double>> getDestsAndWeights(GeometricGraphPosition<N,A> destPosition, K weightKey)

    • tryGetZeroLengthPathBetweenAdjacentPositions

      protected AgentGraphPath<N,A> tryGetZeroLengthPathBetweenAdjacentPositions(GeometricGraphPosition<N,A> sourcePosition, GeometricGraphPosition<N,A> destPosition)
      Tries to find and return a zero-length path between the two adjacent positions. Note that there can still be a non-zero-lenght path between the two positions, in such case this method will return null as it only searches for zero-length paths.
      Parameters:
      sourcePosition - source adjacent position
      destPosition - destination adjacent position
      Returns:
      Found zero-length path, or null, if no zero-length path exists.

    • getSameOrReverseArcPath

      protected AgentGraphPath<N,A> getSameOrReverseArcPath(GeometricGraphPosition<N,A> sourcePosition, GeometricGraphPosition<N,A> destPosition, GraphAgent<N,A> agent)

    • calculatePathWeight

      protected double calculatePathWeight(GraphPath<N,A> path, GraphAgent<N,A> agent)

    • getGraphArc

      public Graph<N,A>.Arc getGraphArc(A arcValue)
      Returns graph arc (an instance of Graph.Arc) containing the specified value.

      Parameters:
      arcValue - value for which to return the graph node
      Returns:
      graph arc containing the specified value, null if there is no such graph arc

    • getGraphNode

      public Graph<N,A>.Node getGraphNode(N nodeValue)
      Returns graph node (an instance of Graph.Node) containing the specified value.

      Parameters:
      nodeValue - value for which to return the graph node
      Returns:
      graph node containing the specified value, null if there is no such graph node.

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(GeometricGraphPosition<N,A> sourcePosition, Predicate<Graph<N,A>.Node> destNodeIndicator, GraphAgent<N,A> agent)
      Returns the shortest path from the specified source position to the closest node on which the specified predicate returns true, or null if no such path exists or the predicate returns false for all nodes reachable from the source position. The path is searched for the specified agent.

      Shortest path is determined using the weights provided in the methods:

      The default implementation of these methods returns simple distance-based weights, however these methods can be overridden to customize the path finding logic.

      Parameters:
      sourcePosition - the origin of path finding
      destNodeIndicator - the Predicate which must return true to indicate that a node is a valid destination
      agent - the agent for which the path is being searched
      Returns:
      an instance of AgentGraphPath representing the shortest path, or null

    • clearCache

      public void clearCache()

    • getCurrentCacheFactor

      public double getCurrentCacheFactor()

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(Graph<N,A>.Node sourceNode, Predicate<Graph<N,A>.Node> destNodeIndicator, double range, GraphAgent<N,A> agent)
      Returns the nodes for which the specified predicate returns true located within the specified range from the specified source node. For every node, returns the weight of the shortest path from the specified source node to this node.

      The result is returned as a List of Pairs. The first element of each pair is the node, and the second element is its weight. The elements in the returned list are sorted by weights in ascending order.

      The search is made with respect to the specified agent.

      Note that the range is expressed in arcs' and nodes' weights, not just in distance along the graph. This means that the weight of the shortest path from the source node to any of the returned nodes is less than or equal to the specified range.

      "Closeness" is determined using the weights provided in the methods:

      The default implementation of these methods returns simple distance-based weights, however these methods can be overridden to customize the path finding logic.

      Parameters:
      sourceNode - source node
      destNodeIndicator - predicate that must return true for the node to be included into the result
      range - range (in in arcs' and nodes' weights) that limits the search
      agent - the agent for which the search is performed
      Returns:
      List of Pair, possibly empty

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(Graph<N,A>.Node sourceNode, Graph<N,A>.Node destNode, GraphAgent<N,A> agent)
      Returns the shortest path from the specified source node to the specified destination node for the specified agent, or null if no such path exists.

      Shortest path is determined using the weights provided in the methods:

      The default implementation of these methods returns simple distance-based weights, however these methods can be overridden to customize the path finding logic.

      Parameters:
      sourceNode - the origin of path finding
      destNode - the destination of path finding
      agent - the agent for which the path is being searched
      Returns:
      an instance of AgentGraphPath representing the shortest path, or null

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(N sourceNodeValue, N destNodeValue, GraphAgent<N,A> agent)
      Returns the shortest path from the specified source node to the specified destination node for the specified agent, or null if no such path exists. The nodes are specified by their values.

      Shortest path is determined using the weights provided in the methods:

      The default implementation of these methods returns simple distance-based weights, however these methods can be overridden to customize the path finding logic.

      Parameters:
      sourceNodeValue - the value of the node which is the origin of path finding
      destNodeValue - the value of the node which is the destination of path finding
      agent - the agent for which the path is being searched
      Returns:
      an instance of AgentGraphPath representing the shortest path, or null

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(GeometricGraphPosition<N,A> sourcePosition, GeometricGraphPosition<N,A> destPosition)

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(GeometricGraphPosition<N,A> sourcePosition, Predicate<Graph<N,A>.Node> destNodeIndicator)

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(Graph<N,A>.Node sourceNode, Graph<N,A>.Node destNode)

    • getShortestPath

      public AgentGraphPath<N,A> getShortestPath(N sourceNodeValue, N destNodeValue)

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(Graph<N,A>.Node sourceNode, Predicate<Graph<N,A>.Node> destNodeIndicator, double range)

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(Graph<N,A>.Node sourceNode, Predicate<Graph<N,A>.Node> destNodeIndicator, double range, int maxNodesCount)

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(GeometricGraphPosition<N,A> sourcePosition, Predicate<Graph<N,A>.Node> destNodeIndicator, double range)

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(GeometricGraphPosition<N,A> sourcePosition, Predicate<Graph<N,A>.Node> destNodeIndicator, double range, int maxNodesCount)

    • onArcWeightChanged

      public void onArcWeightChanged(A arcValue)

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(Graph<N,A>.Node sourceNode, Predicate<Graph<N,A>.Node> destNodeIndicator, double range, Map<Graph<N,A>.Node,Double> outNodeWeights, Set<Graph<N,A>.Arc> outArcsVisited)

    • getCurrentDijsktraFactor

      public double getCurrentDijsktraFactor()

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(Graph<N,A>.Node sourceNode, Predicate<Graph<N,A>.Node> destNodeIndicator, double range, GraphAgent<N,A> agent, Map<Graph<N,A>.Node,Double> outNodeWeights, Set<Graph<N,A>.Arc> outArcsVisited)

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(Graph<N,A>.Node sourceNode, Predicate<Graph<N,A>.Node> destNodeIndicator, double range, GraphAgent<N,A> agent, BiFunction<A,K,Double> arcWeighter, BiFunction<N,K,Double> nodeWeighter)

    • getClosestNodes

      public List<Pair<Graph<N,A>.Node,Double>> getClosestNodes(Graph<N,A>.Node sourceNode, Predicate<Graph<N,A>.Node> destNodeIndicator, double range, GraphAgent<N,A> agent, BiFunction<A,K,Double> arcWeighter, BiFunction<N,K,Double> nodeWeighter, int maxNodesCount)

    • isCollisionsTrackingEnabled

      public boolean isCollisionsTrackingEnabled()

    • isCallbackPositionsEnabled

      public boolean isCallbackPositionsEnabled()

    • getShortestPathBetweenNodesInternal

      protected GraphPath<N,A> getShortestPathBetweenNodesInternal(Graph<N,A> graph, Graph<N,A>.Node sourceNode, Graph<N,A>.Node destNode, Function<Graph<N,A>.Arc,Double> arcWeighter, Function<Graph<N,A>.Node,Double> nodeWeighter, Map<Graph<N,A>.Node,Double> nodeWeights, Set<Graph<N,A>.Arc> arcsVisited, GraphAgent<N,A> agent)

    • addAgentInternal

      protected void addAgentInternal(GraphAgent<N,A> agent)

    • removeAgentInternal

      protected void removeAgentInternal(GraphAgent<N,A> agent)