Package backend.TSP

Class Graph

java.lang.Object
backend.TSP.Graph
public class Graph extends Object
Graph wrapper used by the TSP solver. Holds nodes, edges, adjacency and cached path costs. Methods provide basic graph queries, a weighted A* search (AWAStar) and simple accessors. Note: several methods may return null to indicate absence of data (for example getCost(Long, Long) or cached entries in pathCost). Methods that require a tour id will throw IllegalArgumentException when the id is not present in the tour map.

  • Constructor Details

    • Graph

      public Graph(Map<Long,Node> nodes, List<Edge> edges, Map<Long,PointOfInterest> tour)
      Create a Graph instance.
      Parameters:
      nodes - map of node id -> Node; must not be null
      edges - list of graph edges; must not be null
      tour - list of point-of-interest; must not be null All parameters are stored by reference. Null parameters will cause a NullPointerException during construction.

  • Method Details

    • getTypePoI

      public PointOfInterest.PoIEnum getTypePoI(Long id)
      Return the PoI type for the given id.
      Parameters:
      id - id of the PoI
      Returns:
      the PoI enum type
      Throws:
      IllegalArgumentException - if the id is not present in the tour map

    • getAssociatedPoI

      public Long getAssociatedPoI(Long id)
      Return the associated PoI id for a pickup/delivery node.
      Parameters:
      id - PoI id
      Returns:
      associated PoI id, or null when the PoI is a warehouse or id is unknown

    • getBeginId

      public Long getBeginId()
      Find the first warehouse id in the tour.
      Returns:
      a warehouse id if present; otherwise null

    • getPickupPoIs

      public LinkedHashSet<Long> getPickupPoIs()
      Retrieve all the Pickup PoI in the tour
      Returns:
      a list of Pickup PoI

    • getNbNodes

      public int getNbNodes()
      Return the number of nodes held by this graph.
      Returns:
      the number of entries in all_nodes
      Throws:
      NullPointerException - if all_nodes is null

    • getCost

      public Float getCost(Long i, Long j)
      Return the direct edge cost from i to j stored in this Graph instance.

      This method looks up the cost in the internal cost table built from the edges that were provided when this Graph was created. The graph instance represents the full graph loaded into memory for this run, but it may be incomplete or sparse (not every pair of nodes has a direct edge).

      Parameters:
      i - origin node id
      j - destination node id
      Returns:
      the cost as a Float when a direct edge (i,j) is present in this graph; otherwise null when no direct edge is recorded
      Throws:
      NullPointerException - when i, j or internal maps are null

    • isEdge

      public boolean isEdge(Long i, Long j)
      Lightweight test whether two tour ids can form an edge.

      This checks only that both ids exist in the tour map and that they are not equal. It does not consult the stored cost table; therefore a true result does not guarantee that a direct edge (with a cost) is recorded in this Graph. Use getCost(java.lang.Long, java.lang.Long) or getAllCosts() to check for an actual stored edge.

      Parameters:
      i - first id
      j - second id
      Returns:
      true when both ids are present in the tour and differ; otherwise false

    • getPathCost

      public Float getPathCost(Long i, Long j)
      Return the cached cost of the optimal path between i and j in this Graph instance.

      If the cost is not cached this method triggers AWAStar(Long, Long) which computes an optimal path using the internal adjacency and cost tables belonging to this Graph object. If no path exists (according to the graph loaded in this object) the method throws IllegalArgumentException.

      Parameters:
      i - origin id
      j - destination id
      Returns:
      the Float cost of the optimal path
      Throws:
      IllegalArgumentException - when AWAStar determines there is no path
      NullPointerException - when parameters or internal maps are null

    • getNeighbors

      public Set<Long> getNeighbors(Long i)
      Return the outgoing neighbors for node i in this Graph.
      Parameters:
      i - node id
      Returns:
      a non-null Set of neighbor ids; empty when no neighbors are present Note: the returned set is the actual set stored in the adjacency map and modifying it will change this Graph's adjacency. Treat it as read-only.

    • AWAStar

      public Map<Long,Long> AWAStar(Long startId, Long endId)
      Run a weighted A* search from startId to endId using this Graph's adjacency and cost information.

      This method updates pathCost for the (startId,endId) pair with the computed Float cost when a path is found, or with null when no path exists. The returned map maps each reachable node id to its predecessor id and can be used to reconstruct the path.

      Parameters:
      startId - start node id
      endId - end node id
      Returns:
      a predecessor map (node -> predecessor) for reachable nodes, or null when startId equals endId or the search early-exits because a node has no neighbors

    • getAllEdges

      public List<Edge> getAllEdges()
      Returns:
      list of all edges (may be null if not set)

    • getAllNodes

      public Map<Long,Node> getAllNodes()
      Returns:
      map of node id -> Node (may be null if not set)

    • getAllCosts

      public Map<Pair<Long,Long>,Float> getAllCosts()
      Returns:
      map of direct edge costs (pair -> cost); entries absent when no direct edge

    • getTour

      public List<PointOfInterest> getTour()
      Returns:
      tour map of PoIs (id -> PointOfInterest)

    • getPathCostMap

      public Map<Pair<Long,Long>,Float> getPathCostMap()
      Returns:
      cached path costs computed by AWAStar

    • getAdjacency

      public Map<Long,Set<Long>> getAdjacency()
      Returns:
      adjacency map (id -> set of neighbor ids)