Package it.univr.di.cstnu.util

Interface GraphAlgs

public interface GraphAlgs
Utility class containing some graph algorithm implementations.

  • Field Details

    • LOG

      static final Logger LOG
      Logger for the default method

  • Method Details

    • APSP_FloydWarshall

      static <E extends STNEdge> boolean APSP_FloydWarshall(TNGraph<E> graph, STN.STNCheckStatus checkStatus1)
      Determines the minimal distance between all pairs of nodes (all-pair-shortest-paths (APSP)) using the Floyd-Warshall algorithm.

      If the graph contains a negative cycle, it returns false, and the graph contains the edges that form the negative cycle.

      Type Parameters:
      E - the kind of edge
      Parameters:
      graph - the graph to complete
      checkStatus1 - possible status to fill during the computation.
      Returns:
      true if the graph is consistent, false otherwise. If the response is false, the edges do not represent the minimal distance between nodes.

    • APSP_Johnson

      @Nullable static GraphDistances APSP_Johnson(@Nonnull GraphDistances graphDistances, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> nodePotential)
      Determines the minimal distance between all pairs of nodes (all-pair-shortest-paths (APSP)) using the Johnson algorithm.
      Parameters:
      graphDistances - input GraphDistances. It must not be null, and it is updated with the new distances.
      nodePotential - a node potential function of the input graph. If null, it is determined inside the method.
      Returns:
      the new graph distances if all distances have been determined, null if a negative cycle or any other error occurred.

    • APSP_Johnson

      static <E extends STNEdge> boolean APSP_Johnson(TNGraph<E> tnGraph, STN.STNCheckStatus checkStatus)
      Determines the minimal distance between all pairs of nodes (all-pair-shortest-paths (APSP)) using the Johnson algorithm. The minimal distance between a node X and a node Y is saved as the value of the edge (X, Y). If Y is not reachable from X, the edge (X, Y) is null.

      This method was built to determine the APSP very quickly. Don't use this graph in the TNEditor because it does not allow the editing of node or edge attributes.

      Type Parameters:
      E - the kind of edges
      Parameters:
      tnGraph - input graph. It must not be null. It will be completed with all the minimal distances.
      checkStatus - status to update with statistics of the algorithm. It can be null.
      Returns:
      true if all distances have been determined, false if a negative cycle or any other error occurred.
      See Also:

    • APSP_Johnson

      static <E extends STNEdge> boolean APSP_Johnson(TNGraph<E> tnGraph, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> nodePotential, STN.STNCheckStatus checkStatus)
      Determines the minimal distance between all pairs of nodes (all-pair-shortest-paths (APSP)) using the Johnson algorithm. The value of an edge is given by the method STNEdge.getValue() and set by the method STNEdge.setValue(int).

      The minimal distance between a node X to a node Y is saved as the value of the edge (X, Y). Be careful: while node objects do not change, all edge objects will be replaced by new ones. Possible saved edge references will be useless after the call of this method. If Y is not reachable from X, the edge (X, Y) is null.

      This method was built to determine the APSP relatively quickly. Don't use this graph in the TNEditor because it does not allow the editing of node or edge attributes. If the graph size is more than 1000 nodes, I suggest considering APSP_Johnson(GraphDistances, Object2IntMap).

      Type Parameters:
      E - the kind of edges
      Parameters:
      tnGraph - input graph. It must not be null. It will be completed with all the minimal distances.
      nodePotential - a node potential function of the input graph. If null, it is determined inside the method.
      checkStatus - status to update with statistics of the algorithm. It can be null.
      Returns:
      true if all distances have been determined, false if a negative cycle or any other error occurred.

    • GET_BellmanFord_Potential

      @Nullable static it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_BellmanFord_Potential(@Nonnull GraphDistances graphDistances, @Nullable LabeledNode source)
      Determines the potential of nodes considering a virtual source node using the Bellman-Ford algorithm.

      The potential of a node (s) is determined as the maximum among the sums of {adjacent node potential (d) minus the edge (s--v-->d) value }. The value of the edge is determined by edgeValue parameter. In this way, all nodes not reachable from others have a potential equal to 0.

      The potential is returned as a map (node, value). If the graph contains a negative cycle, it returns null.

      Parameters:
      graphDistances - input GraphDistances.
      source - the source node. If it is null, then a virtual temporary source is added, and all nodes are initialized to 0 potential. If the value is not null and not present in the graph, the method returns null.
      Returns:
      the map of pairs (node, distanceFromSource) if the graph is consistent; otherwise, it is null.

    • GET_BellmanFord_Potential

      static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_BellmanFord_Potential(TNGraph<E> graph, STNEdge.EdgeValue<E> edgeValue, STN.STNCheckStatus checkStatus)
      Determines the potential of nodes considering a virtual source node using the Bellman-Ford algorithm.

      The potential of a node (s) is determined as the maximum among the sums of {adjacent node potential (d) minus the edge (s--v-->d) value }. The edgeValue parameter determines the value of the edge. In this way, all nodes not reachable from others have a potential equal to 0.

      The potential is returned as a map (node, value). If the graph contains a negative cycle, it returns null.

      This method implements Algorithm 8 in the Technical Appendix of the AAAI22 paper.

      The Technical Appendix is published at https://hdl.handle.net/11562/1045707.

      Type Parameters:
      E - type of edge
      Parameters:
      graph - input graph
      edgeValue - the value of each edge to be considered
      checkStatus - possible status data structure where to register possible failures.
      Returns:
      the minimal potential if the network is consistent; otherwise, it is null.

    • GET_SSSP_BellmanFord

      static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_SSSP_BellmanFord(TNGraph<E> graph, LabeledNode source, STN.STNCheckStatus checkStatus)
      Determines the minimal distance from the given source node to each other node (single-source-shortest-paths (SSSP)) using the Bellman-Ford algorithm.

      The minimal distance is stored in a map (node, distanceFromSource). If the graph contains a negative cycle, it returns null.

      Type Parameters:
      E - the kind of edge. This method accepts any extensions of STNEdge. If STNEdge.getValue() does not return a valid value, the edge is ignored.
      Parameters:
      graph - input graph. If it is null, the method returns false.
      source - the source node. If it is null, then a virtual temporary source is added to determine a virtual distance for each node (virtual distances are all non-positive). If it is not null and it is not present in the graph, the method returns null.
      checkStatus - status to update with statistics of the algorithm. It can be null.
      Returns:
      the map of pairs (node, distanceFromSource) if the graph is consistent, null otherwise.

    • GET_SSSP_BellmanFord

      static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_SSSP_BellmanFord(TNGraph<E> graph, LabeledNode source, boolean backward, int horizon, boolean setNodePotential, STN.STNCheckStatus checkStatus)
      Determines the minimal distance between the source node and any node (or any node and the sink (==source) if backward) using the Bellman-Ford algorithm. The minimal distance is stored in the returned map (and in each node in the 'potential' field if the parameter `setNodePotential` is true).

      If a node is not reachable by the source node, its distance is Constants.INT_POS_INFINITE.

      If the graph contains a negative cycle, it returns null.

      Type Parameters:
      E - the kind of edge. This method accepts any extensions of STNEdge. If STNEdge.getValue() does not return a valid value, the edge is ignored.
      Parameters:
      graph - input graph.
      source - the source node. If it is null, then a virtual temporary source is added, and the search is forced to be forward. If it is not null and it is not present in the graph, the method returns null.
      backward - true if the search has to be backward. If true, the source must be significant. Otherwise, it returns null.
      horizon - the maximum value for the potential. It is meaningful in the forward search to guarantee that any node is reachable from the source.

      If it is not equal to Constants.INT_NULL, then the source node is connected to any node by a virtual edge having horizon value (no edges are added to the graph).

      If it is equal to Constants.INT_NULL, the determined distances are meaningful only for reachable nodes; all other nodes are at distance Constants.INT_POS_INFINITE. A safe value for the horizon is the absolute greatest value present on the edges times the number of nodes. In case the source is null, the horizon is not considered because the virtual source is connected to all nodes by a virtual edge with value 0.

      setNodePotential - true if also node.potential must be set.
      checkStatus - status to update with statistics of the algorithm. It can be null.
      Returns:
      the map of pairs (node, distanceFromSource) if the graph is consistent; otherwise, it is null.

    • GET_SSSP_Dijkstra

      static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_SSSP_Dijkstra(TNGraph<E> graph, LabeledNode source, STN.STNCheckStatus checkStatus)
      Determines the minimal distance between a source node and any node reachable by the source (single-source-shortest-paths (SSSP)) using the Dijkstra algorithm.

      Minimal distances are returned as map (destinationNode, distance).

      If a node is not reachable from the source, its distance is +∞.

      If the graph contains a negative edge beyond the source outgoing edges or the source is not in the graph, it returns null.

      Type Parameters:
      E - the kind of edge
      Parameters:
      graph - input graph. Each edge must have a positive weight, but the edges outgoing from the source can have a negative weight.
      source - the source node. It must belong to the graph.
      checkStatus - status to update with statistics of the algorithm. It can be null.
      Returns:
      null or a non-empty map (node, integer) representing the distances of all nodes from the given source. Null is returned if the graph is empty, the source is not in the graph, or a negative edge beyond the source edges has been found. If a node is not reachable from the source, its distance is +∞.

    • GET_SSSP_Dijkstra

      static boolean GET_SSSP_Dijkstra(@Nonnull GraphDistances graphDistances, @Nonnull LabeledNode source, @Nullable ExtendedPriorityQueue<LabeledNode> nodeQueueToReuse)
      Determines the minimal distance between a source node and any node reachable by the source (single-source-shortest-paths (SSSP)) using the Dijkstra algorithm.

      Minimal distances are returned as map (destinationNode, distance).

      If a node is not reachable from the source, its distance is +∞.

      Only the outgoing edges from the source can contain negative distance.

      Parameters:
      graphDistances - input GraphDistances.
      source - the source node. It must belong to the graph.
      nodeQueueToReuse - if such a method is called many times, offering the same queue (that will be cleared by the method each call) could save some computation time. It could be null. In such a case, the method creates a new one each call.
      Returns:
      false if graphDistance is empty or the source is not in the graph, or a negative edge beyond source edges has been found. True if the distances of all nodes from the given source have been updated. If a node is not reachable from the source, its distance is +∞.

    • REWEIGHT_DISTANCES

      static void REWEIGHT_DISTANCES(GraphDistances graphDistances, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> nodePotential, boolean toPositive)
      Re-weights all distances using the potential function.

      The potential of a node is assumed to be stored in bfPotential.

      If a distance is NULL or +∞, it is ignored.

      Parameters:
      graphDistances - input graphDistances
      nodePotential - potential of each node.
      toPositive - true if the reweighting must transform all distances into positive values. False if the inverse transformation must be applied.
      Throws:
      IllegalStateException - it is not possible to re-weigh it because the potential values are not correct.

    • REWEIGHT_EDGES

      static <E extends STNEdge> void REWEIGHT_EDGES(TNGraph<E> graph, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> nodePotential)
      Re-weights all edge weights using the potential function.

      The potential of a node is assumed to be stored in bfPotential.

      If the edge has a not valid value (NULL or +∞), it is ignored.

      Type Parameters:
      E - the kind of edges.
      Parameters:
      graph - input graph
      nodePotential - potential of each node.
      Throws:
      IllegalStateException - it is not possible to re-weigh it because the potential values are not correct.

    • UPDATE_DISTANCES

      static it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> UPDATE_DISTANCES(GraphDistances apsp, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> nodePotential, LabeledNode A)
      Updates the 'apap' graph distances and the `nodePotential` propagating the assumed updated outgoing edges from node `A`.

      Side effects: `apsp` will be updated.

      Parameters:
      apsp - the graph with assumed updated edges out-going from node 'A'
      nodePotential - out-of-date potential function of the nodes in 'apsp'.
      A - a node of 'apsp'.
      Returns:
      update node potential or null if an inconsistency is found.