Package com.amalgamasimulation.graph

Class GraphPath<N,A>

java.lang.Object
com.amalgamasimulation.graph.GraphPath<N,A>
Direct Known Subclasses:
CachedShortestPath, GeometricGraphPath
public class GraphPath<N,A> extends Object
Represents a path in a graph. Path is a sequence of nodes and arcs such that each pair of subsequent nodes is adjacent. Path is a result of all path-finding algorithms. Path is not a subgraph: the same graph node or arc can be included into path several times (e.g. if path contains cycles).

Graph path always starts and ends at a node. In a non-empty path, the number of arcs always equals the number of nodes minus one.

Path can be empty (e.g. to represent a non-existent path) or consist of only one node (e.g. path from some node to this node itself).

Author:
Andrey Malykhanov

  • Constructor Details

    • GraphPath

      public GraphPath()
      Creates an empty graph path, i.e. a graph path with no nodes and arcs.

    • GraphPath

      public GraphPath(Graph<N,A>.Node node)
      Creates a graph path containing a single specified graph node.
      Parameters:
      node - specified graph node

    • GraphPath

      @SafeVarargs public GraphPath(Graph<N,A>.Arc... arcs)
      Creates a graph path consisting of the specified sequence of graph arcs and corresponding graph nodes.
      Parameters:
      arcs - sequence of graph arcs

    • GraphPath

      public GraphPath(List<Graph<N,A>.Arc> arcs)
      Creates a graph path consisting of the specified sequence of graph arcs and corresponding graph nodes.
      Parameters:
      arcs - sequence of graph arcs

    • GraphPath

      public GraphPath(GraphPath<N,A> path)
      Creates a graph path that is a copy of other specified graph path.
      Parameters:
      path - other specified graph path

  • Method Details

    • addNode

      public GraphPath<N,A> addNode(Graph<N,A>.Node node)
      Adds the specified node to this path if this path is empty, otherwise throws a IllegalArgumentException.
      Parameters:
      node - specified node
      Returns:
      reference to this instance, for convenience of building new instances

    • prependArc

      public GraphPath<N,A> prependArc(Graph<N,A>.Arc arc)
      Prepends the specified arc and its source node to this path. Destination node of the specified arc must be the same as the first node of this path, otherwise a IllegalArgumentException is thrown.

      If this arc is empty, simply adds the specified arc and both nodes to this path.

      Parameters:
      arc - arc being prepended to this path
      Returns:
      reference to this instance, for convenience of building new instances

    • appendArc

      public GraphPath<N,A> appendArc(Graph<N,A>.Arc arc)
      Appends the specified arc and its destination node to this path. Source node of the specified arc must be the same as the last node of this path, otherwise a IllegalArgumentException is thrown.

      If this arc is empty, simply adds the specified arc and both nodes to this path.

      Parameters:
      arc - arc being appended to this path
      Returns:
      reference to this instance, for convenience of building new instances

    • getNodesCount

      public int getNodesCount()
      Returns nodes count in this path.
      Returns:
      Nodes count in this path

    • getArcsCount

      public int getArcsCount()
      Returns arcs count in this path.
      Returns:
      Arcs count in this path

    • containsArc

      public boolean containsArc(A value)

    • getArc

      public Graph<N,A>.Arc getArc(A value)

    • containsNode

      public boolean containsNode(N value)
      Checks if the path contains the specified value in its nodes.
      Parameters:
      value - The specified value
      Returns:
      True if the graph contains the specified value, false otherwise

    • getNode

      public Graph<N,A>.Node getNode(N value)
      Returns a path node containing the specified value.
      Parameters:
      value - The specified value
      Returns:
      Node containing the specified value if such node exists, null otherwise

    • getFirstNode

      public Graph<N,A>.Node getFirstNode()
      Returns the first node of this path. If this path is empty, returns null.
      Returns:
      The first node of this path, or null if this path is empty

    • getLastNode

      public Graph<N,A>.Node getLastNode()
      Returns the last node of this path. If this path is empty, returns null.
      Returns:
      The last node of this path, or null if this path is empty

    • getNodes

      public List<Graph<N,A>.Node> getNodes()
      Returns an unmodifiable list of nodes of this path.
      Returns:
      Unmodifiable list of nodes

    • getLastArc

      public Graph<N,A>.Arc getLastArc()
      Returns the last arc of this path, or null if this path has no arcs.
      Returns:
      last arc of this path, or null if this path has no arcs

    • getFirstArc

      public Graph<N,A>.Arc getFirstArc()
      Returns the first arc of this path, or null if this path has no arcs.
      Returns:
      first arc of this path, or null if this path has no arcs

    • getArcs

      public List<Graph<N,A>.Arc> getArcs()
      Returns an unmodifiable list of arcs of this path.
      Returns:
      Unmodifiable list of arcs

    • getNextArc

      public Graph<N,A>.Arc getNextArc(Graph<N,A>.Node node)
      Returns the arc that follows the specified node in this path.

      Returns null in the following cases:

    • if this path does not contain the specified node
    • if the specified node is the last node of this path
      • Parameters:
      node - specified node
      Returns:
      he arc that follows the specified node, or null

    • getPrevArc

      public Graph<N,A>.Arc getPrevArc(Graph<N,A>.Node node)
      Returns the arc that precedes the specified node in this path.

      Returns null in the following cases:

    • if this path does not contain the specified node
    • if the specified node is the first node of this path
      • Parameters:
      node - specified node
      Returns:
      he arc that precedes the specified node, or null

    • append

      public GraphPath<N,A> append(GraphPath<N,A> otherPath)
      Appends the specified other path to this path. This path gets mutated as result of call to this method.

      The first node of the specified other path must be the same as the last node of this path, otherwise a IllegalArgumentException is thrown.

      Parameters:
      otherPath - other path being appended to this one
      Returns:
      reference to this instance, for convenience of building new instances

    • prepend

      public GraphPath<N,A> prepend(GraphPath<N,A> otherPath)
      Prepends the specified other path to this path. This path gets mutated as result of call to this method.

      The last node of the specified other path must be the same as the first node of this path, otherwise a IllegalArgumentException is thrown.

      Parameters:
      otherPath - other path being prepended to this one
      Returns:
      reference to this instance, for convenience of building new instances

    • getCopy

      public GraphPath<N,A> getCopy()
      Returns a copy of this path.
      Returns:
      copy of this path

    • getSubPath

      public GraphPath<N,A> getSubPath(int fromNodeIndexInclusive, int toNodeIndexInclusive)
      Returns a sub-path of this path located between the nodes with the specified indices.

      The specified indices must be non-negative and less than nodes count in this path (i.e. the result of getNodesCount() method). fromNodeIndexInclusive must be less than or equal to toNodeIndexInclusive. If any of the constraints above are violated, a IllegalArgumentException is thrown.

      If fromNodeIndexInclusive = toNodeIndexInclusive, a path containing only one node is returned.

      Parameters:
      fromNodeIndexInclusive - index of the first node of the sub-path
      toNodeIndexInclusive - index of the last node of the sub-path
      Returns:
      sub-path of this path located between the nodes with the specified indices

    • getSubPathTo

      public GraphPath<N,A> getSubPathTo(int toNodeIndexInclusive)
      Returns a sub-path of this path located between its first node and the node with the specified index.

      The specified index must be non-negative and less than nodes count in this path (i.e. the result of getNodesCount() method). If this constraint is violated, a RuntimeException is thrown.

      Parameters:
      toNodeIndexInclusive - index of the last node of the sub-path
      Returns:
      sub-path of this path located between its first node and the node with the specified index

    • getSubPathFrom

      public GraphPath<N,A> getSubPathFrom(int fromNodeIndexInclusive)
      Returns a sub-path of this path located between the node with the specified index and the last node of this path.

      The specified index must be non-negative and less than nodes count in this path (i.e. the result of getNodesCount() method). If this constraint is violated, a RuntimeException is thrown.

      Parameters:
      fromNodeIndexInclusive - index of the first node of the sub-path
      Returns:
      sub-path of this path located between the node with the specified index and the last node of this path

    • isEmpty

      public boolean isEmpty()
      Checks whether this path is empty, i.e. does not contain any nodes or arcs. Note that path with a single node is not empty.
      Returns:
      true is this path is empty, false otherwise

    • emptyPath

      public static <N, A> GraphPath<N,A> emptyPath()
      Returns an instance of an empty path, i.e. path with no arcs and nodes.
      Type Parameters:
      N - type of graph node values
      A - type of graph arc values
      Returns:
      instance of an empty path, i.e. path with no arcs and nodes

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object