Interface GraphAlgs

public interface GraphAlgs
Utility class containing some graph algorithm implementations.

  • Field Details

    • LOG

      static final Logger LOG
      Logger for the default method

    • BFCT_NONE

      static final int BFCT_NONE
      The absent node in the parent and sibling arrays of the Bellman-Ford-Tarjan searches: where a null node reference used to be. It is an index and not a state, which is why it is an int and not a GraphAlgs.BFCTNodeStatus. Being a field of an interface, it is implicitly public static final.
      See Also:

  • Method Details

    • APSP_FloydWarshall

      static <E extends STNEdge> boolean APSP_FloydWarshall(TemporalConstraintGraph<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(DenseTCGraph<E> denseTCGraph, 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. Do not use this graph in the editor: it does not allow the editing of node or edge attributes. It intentionally requires the dense backend: APSP materializes up to |V| * (|V| - 1) derived edges, so a sparse graph would lose its storage advantage. When the dense backend is renamed, this signature must be renamed with it rather than generalized.

      Type Parameters:
      E - the kind of edges
      Parameters:
      denseTCGraph - 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(DenseTCGraph<E> denseTCGraph, 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. Do not use this graph in the editor: 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). It intentionally requires the dense backend because it materializes the complete APSP closure as graph edges.

      Type Parameters:
      E - the kind of edges
      Parameters:
      denseTCGraph - 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

      @Nullable static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_BellmanFord_Potential(TemporalConstraintGraph<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 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, and the cycle itself is put in STN.STNCheckStatus.negativeCycle when checkStatus is not 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.
      Implementation Note:
      The fixpoint is the same one the round-based scan used to compute -- same map, same values, same null on a negative cycle -- reached by a queue of the nodes whose potential grew, with Tarjan's subtree disassembly on top, which is the combination Cherkassky and Goldberg call BFCT. Everything is mirrored with respect to the textbook formulation, because the update here raises the SOURCE from the destination: the queue holds nodes whose potential grew, and popping one rescans the edges whose DESTINATION it is, since those are the edges that can raise a source. The parent of a node is therefore the node it took its value from, and following parent pointers walks FORWARD along edges, which is why the cycle comes out already in traversal order.

      It matters most where the network is inconsistent. There the round-based scan could not stop early -- the updates never cease, so it ran its whole budget of n rounds over m edges before answering -- while disassembly reports the cycle the moment the parent graph closes one. On the 2020 non-controllable benchmarks that is where 55% of the refusals at 1000 nodes and 68% at 2000 and 2500 come from, and there this call is the whole check: at 2000 nodes it was 45.8 ms of a 54.4 ms RUL2021 check, and the check now takes about 9 ms, six times less. On a consistent network the queue is a smaller win on the call itself and invisible end to end, the potential being about 1.6% of a RUL2021 check and 0.5% of an MDE run.

      The witness is a by-product: the parent chain already holds the cycle when the failure is detected. It is validated -- every consecutive pair must be an edge of the graph and the weights must sum negative -- and dropped if it is not, so a caller that finds STN.STNCheckStatus.negativeCycle non-null can walk it.

    • GET_NEGATIVE_CYCLE

      @Nullable static int[] GET_NEGATIVE_CYCLE(@Nonnull int[] parent)
      Extracts a cycle of the parent-pointer graph encoded in parent, the witness of the negative cycle that IS_NEGATIVE_CYCLE(int[]) only reports the presence of.

      parent is the same functional graph that method takes: parent[i] is the index of the parent of node i and index 0 is the root. Since the array is initialized to zeros, an entry equal to 0 is indistinguishable from an unset one, so, exactly as in IS_NEGATIVE_CYCLE(int[]), walking the chain stops at the root; the one case in which a cycle can run through the root is parent[0] != 0, which is handled first and on its own.

      This method does not decide consistency: it can return null where IS_NEGATIVE_CYCLE(int[]) returns true, because that method also reports parent[0] != 0 as a cycle even when the chain leaving the root does not come back to it. A caller that has to keep its verdict must therefore keep asking IS_NEGATIVE_CYCLE(int[]) for the verdict and use this method only to obtain the witness, accepting that the witness may be absent.

      Parameters:
      parent - the parent-index array; index 0 is the root
      Returns:
      the cycle as indexes following the parent chain -- for each consecutive pair, the second is the parent of the first, and the parent of the last is the first -- or null if no cycle was found

    • GET_REVERSE_POST_ORDER_VISIT

      @Nullable static <E extends STNEdge> it.unimi.dsi.fastutil.objects.ObjectList<LabeledNode> GET_REVERSE_POST_ORDER_VISIT(@CheckForNull TemporalConstraintPredecessorGraph<E> graph, @Nonnull LabeledNode root, @CheckForNull it.unimi.dsi.fastutil.objects.Object2BooleanMap<LabeledNode> isVisited)
      Determine the reverse-post-order of reachable nodes from the given root node in graph.
      Type Parameters:
      E - the kind of edges
      Parameters:
      graph - graph
      root - starting node of the visit. It must belong to the graph.
      isVisited - node visit status. It can be null or an empty map. After the call, all nodes mapped to the true value have been visited.
      Returns:
      the list of nodes in reverse-post-order if the graph is not null and the root is a node of the graph; otherwise, it is null.

    • GET_SSSP_BellmanFord

      @Nullable static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_SSSP_BellmanFord(TemporalConstraintGraph<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

      @Nullable static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_SSSP_BellmanFord(TemporalConstraintGraph<E> graph, LabeledNode source, boolean backward, int horizon, 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 (the map is the authoritative state of the computation: it was also 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.

      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

      @Nullable static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_SSSP_Dijkstra(TemporalConstraintGraph<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

      @Nullable static <E extends STNEdge> it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> GET_SSSP_Dijkstra(TemporalConstraintGraph<E> graph, LabeledNode source, STN.STNCheckStatus checkStatus, @Nullable ExtendedPriorityQueue<LabeledNode> nodeQueueToReuse)
      Same as GET_SSSP_Dijkstra(TemporalConstraintGraph, LabeledNode, STN.STNCheckStatus) but with an optional reusable queue. When the method is called many times (e.g., once per source in Johnson's APSP), passing the same queue (cleared by the method at each call) avoids reallocating it each time.
      Type Parameters:
      E - the kind of edge
      Parameters:
      graph - input graph
      source - the source node
      checkStatus - status to update; may be null
      nodeQueueToReuse - a queue to reuse (cleared by the method); may be null (a new one is created)
      Returns:
      see GET_SSSP_Dijkstra(TemporalConstraintGraph, LabeledNode, STN.STNCheckStatus)

    • 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 +∞.

    • GET_STN_PRECEDESSOR_SUBGRAPH_OPTIMIZED

      @Nullable static <E extends STNEdge> TemporalConstraintPredecessorGraph<E> GET_STN_PRECEDESSOR_SUBGRAPH_OPTIMIZED(@Nonnull TemporalConstraintGraph<E> graph, @Nonnull LabeledNode source, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> graphNodePotential, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> distanceFromSource, @Nullable TemporalConstraintPredecessorGraph<E> graphToReuse)
      Returns the predecessor graph of the given source in the given STN graph, obtaining a fresh predecessor-relation container from graph when graphToReuse is null, otherwise clearing and reusing graphToReuse itself.

      NOTE
      This method is thought to be used as a subroutine of STN.MAKE_MINIMAL_DISPATCHABLE(TemporalConstraintGraph) and STN.makeMinimalDispatchable().

      Moreover, the given STN must be consistent. Otherwise, the returned solution is not correct.

      The returned graph is an independent graph that shares nodes and edges with the input graph.

      It contains only nodes that are reachable from the source.

      The distances from the source to the nodes are stored in the given map 'distanceFromSource' (that is clear before the use).

      Invariant: this method (and FILL_STN_PREDECESSOR_SUBGRAPH_OPTIMIZED(TemporalConstraintGraph, LabeledNode, Object2IntMap, Object2IntMap, PG)) never names a concrete predecessor-graph class. It therefore works unchanged whichever TemporalConstraintGraph backend graph is.

      Performance: for graphs with thousands of nodes and tens of thousands of edges, this method is typically invoked once per node (e.g., inside STN.MAKE_MINIMAL_DISPATCHABLE(TemporalConstraintGraph)). Passing a non-null graphToReuse lets callers clear and reuse the very same predecessor-graph instance across calls instead of allocating a fresh one every time, which matters at this scale (avoids a possible out-of-memory, verified on 2022-01-09).

      Type Parameters:
      E - the kind of edges.
      Parameters:
      graph - the input graph. It will not be modified.
      source - a node of this STN.
      graphNodePotential - a solution for the STN as map (node, potential). If null, it is determined locally.
      distanceFromSource - a map that will be filled with the distances of nodes reachable from the source. If null, it is ignored.
      graphToReuse - a predecessor-graph instance to clear and reuse, or null to create a fresh one through TemporalConstraintGraph.newPredecessorInstance().
      Returns:
      the predecessor graph of node X. If the STN is consistent and X belongs to this STN, it is null otherwise.
      See Also:

    • GET_STN_PREDECESSOR_SUBGRAPH

      @Nullable static <E extends STNEdge> TemporalConstraintGraph<E> GET_STN_PREDECESSOR_SUBGRAPH(@Nonnull TemporalConstraintGraph<E> graph, @Nonnull LabeledNode source, @Nonnull it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> graphNodePotential, @Nonnull it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> distanceFromSource, @Nullable TemporalConstraintGraph<E> graphToReuse)
      Returns the predecessor graph of the given source in the given STN graph, obtaining the predecessor-graph instance either by clearing and reusing graphToReuse, or, when it is null, by calling graph.newInstance(...).

      NOTE
      Since this method is thought to be used as a subroutine of the FastDispatchMinimization algorithm. Moreover, the given STN must be consistent. Otherwise, the returned solution is not correct.
      The returned graph is an independent graph that shares nodes and edges with the input graph.
      It contains only nodes that are reachable from the source.
      The distances from the source to the nodes are stored in the given map 'distanceFromSource' (that is clear before the use).
      The Z node of the returned graph is always (re)set to graph.getZ(), including when it is null.

      Invariant: this method never names a concrete graph implementation, never casts graph or the result to one, and uses no builder: graph.newInstance(...) is enough to obtain a fresh, empty companion graph of graph's own concrete backend and edge implementation (a DenseTCGraph yields a DenseTCGraph, a SparseTCGraph yields a SparseTCGraph). It therefore works unchanged whichever TemporalConstraintGraph backend graph is.

      Performance: for graphs with thousands of nodes and tens of thousands of edges, this method is typically invoked once per node (e.g., inside STN.MAKE_MINIMAL_DISPATCHABLE(TemporalConstraintGraph)). Passing a non-null graphToReuse clears and reuses the very same graph instance across calls instead of allocating a fresh one every time, which matters at this scale (avoids a possible out-of-memory, verified on 2022-01-09).

      Precondition on graphToReuse: when non-null, it must have the very same concrete backend class as graph (e.g., both DenseTCGraph, or both SparseTCGraph); otherwise an IllegalArgumentException is thrown. This keeps the "same backend as the source" invariant that graph.newInstance(...) already provides on the fresh-build path.

      Z node: the result's Z node is always (re)set to graph.getZ(), including when it is null. This matters specifically for graphToReuse: some backends' clear() do not reset their own Z field, so without this unconditional reset a reused graph could keep a stale, previously-set Z when graph has none.

      Type Parameters:
      E - the kind of edges.
      Parameters:
      graph - the input graph. It will not be modified.
      source - a node of this STN
      graphNodePotential - a solution for the STN as map (node, potential).
      distanceFromSource - a map that will be filled with the distances of nodes reachable from the source.
      graphToReuse - a graph instance to clear and reuse, or null to build a fresh one via graph.newInstance(...). When non-null, it must have the same concrete backend class as graph. The scope of this parameter is to avoid generating new graphs when many predecessor graphs have to be generated sequentially and in a short time. Reusing one predecessor graph avoids a possible out-of-memory (verified on 2022-01-09).
      Returns:
      the predecessor graph of node X. If the STN is consistent and X belongs to this STN, it is null otherwise.
      Throws:
      IllegalArgumentException - if graphToReuse is non-null and its concrete class differs from graph's.

    • GET_STRONG_CONNECTED_COMPONENTS

      static <S extends GraphAlgs.LabeledNodeSuccessor> it.unimi.dsi.fastutil.objects.ObjectList<it.unimi.dsi.fastutil.objects.ObjectList<LabeledNode>> GET_STRONG_CONNECTED_COMPONENTS(@Nonnull LabeledNode source, @Nonnull it.unimi.dsi.fastutil.objects.Object2ObjectMap<LabeledNode, ? extends it.unimi.dsi.fastutil.objects.ObjectList<S>> adjacencyListMap)
      Determines all strongly connected components reachable from source, using the Tarjan algorithm.

      The adjacency map must return, for each node, the list of outgoing graph arcs. Every listed arc is traversed. This all-arcs version is intentionally kept separate from GET_STRONG_CONNECTED_COMPONENTS_OL(LabeledNode, Object2ObjectMap): both methods are used in hot paths that can be executed millions of times with different adjacency-entry types, and avoiding a generic extractor in the inner edge loop is relevant for performance.

      Type Parameters:
      S - the kind of successor entry
      Parameters:
      source - the source node for the SCC search
      adjacencyListMap - adjacency list indexed by node
      Returns:
      the list of SCCs reachable from source; singleton components are included

    • GET_STRONG_CONNECTED_COMPONENTS_OL

      static <E extends STNUEdge> it.unimi.dsi.fastutil.objects.ObjectList<it.unimi.dsi.fastutil.objects.ObjectList<LabeledNode>> GET_STRONG_CONNECTED_COMPONENTS_OL(@Nonnull LabeledNode source, @Nonnull it.unimi.dsi.fastutil.objects.Object2ObjectMap<LabeledNode, ? extends it.unimi.dsi.fastutil.objects.ObjectList<it.unimi.dsi.fastutil.objects.ObjectObjectImmutablePair<LabeledNode, E>>> adjacencyListMap)
      Determines all strongly connected components reachable from source, using the Tarjan algorithm.

      The adjacency map must return, for each node, the list of outgoing graph arcs encoded as (successor, edge) pairs. Edges whose ordinary/lower-case value is Constants.INT_POS_INFINITE are ignored. This OL version is intentionally kept separate from GET_STRONG_CONNECTED_COMPONENTS(LabeledNode, Object2ObjectMap): both methods are used in hot paths that can be executed millions of times with different adjacency-entry types, and avoiding a generic extractor in the inner edge loop is relevant for performance.

      Type Parameters:
      E - the kind of edge
      Parameters:
      source - the source node for the SCC search
      adjacencyListMap - adjacency list indexed by node
      Returns:
      the list of SCCs reachable from source; singleton components are included

    • GET_UNDOMINATED_EDGES

      static <E extends STNEdge> it.unimi.dsi.fastutil.objects.ObjectList<it.unimi.dsi.fastutil.Pair<LabeledNode, E>> GET_UNDOMINATED_EDGES(@Nonnull LabeledNode source, @Nonnull TemporalConstraintPredecessorGraph<E> predecessorGraph, @Nonnull it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> distanceFromSource, @Nonnull TemporalConstraintGraph<E> graph)
      Returns all undominated edges emanating from a given source in the predecessor graph without determining and storing the All-Pairs-Shortest-Paths.
      Type Parameters:
      E - the kind of edges
      Parameters:
      source - the source node in predecessorGraph.
      predecessorGraph - the predecessor graph of the source node.
      distanceFromSource - distances from the source in the predecessor graph.
      graph - graph whose edge implementation is used for the new derived edges.
      Returns:
      the list of the undominated edges emanating from source. Each edge is new, i.e., not shared with the predecessor graph. Each element of the list is a pair (Destination node name, edge object). The list is never null, but it could be empty.

    • IS_NEGATIVE_CYCLE

      static boolean IS_NEGATIVE_CYCLE(int[] parent)
      Detects whether the parent-pointer forest encoded in parent contains a cycle.

      parent represents a functional graph where parent[i] is the index of the parent of node i; the root is index 0 (with parent[0] == 0). When the array is the predecessor forest of a shortest-path computation (e.g., Bellman-Ford/Yen), a cycle here corresponds to a negative cycle in the network, hence the name. The method runs in O(n) amortized time using a per-node visit-level marking.

      Parameters:
      parent - the parent-index array; index 0 is the root and must satisfy parent[0] == 0.
      Returns:
      true if a cycle is present (i.e., parent[0] != 0 or a back-reference is found), false otherwise.

    • REMOVE_INTERNAL_EDGES_WITH_PREFIX

      static <E extends STNEdge> void REMOVE_INTERNAL_EDGES_WITH_PREFIX(TemporalConstraintGraph<E> graph, LabeledNode source, String prefix)
      Removes all (added) internal edges outgoing from the source and having a prefix in the name.
      Type Parameters:
      E - the kind of edges
      Parameters:
      graph - a not-null graph
      source - a non-null source node. If it is not in the graph, it is added.
      prefix - a non-null string representing the prefix in the name of the edge. It cannot be empty!

    • 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(TemporalConstraintGraph<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.

    • SSSP_BFCT

      static <E extends STNEdge> boolean SSSP_BFCT(@Nonnull TemporalConstraintGraph<E> g1, @Nonnull LabeledNode source, @Nullable STNEdge.EdgeValue<E> edgeValue, int horizon, @Nullable STN.STNCheckStatus checkStatus1)
      Determines the minimal distance of each node from the given source (single-source-shortest-paths (SSSP)) using the Bellman-Ford-Tarjan algorithm.
      It is the Bellman-Ford augmented by a cycle detection routine called 'Subtree disassembly' written by Tarjan.
      If the STN graph is not consistent and the checkStatus parameter is not null, then the negative cycle is stored in the field STN.STNCheckStatus.negativeCycle.
      All nodes are made reachable by Z by adding a constraint (Z, horizon, X) for each node X, where the horizon is a given parameter.

      The search state -- the predecessor of each node, the doubly-linked list of children the disassembly walks, and the reached/labeled/scanned mark -- is kept in this method, in arrays indexed by a dense node id, and not in the nodes. So two runs on the same graph cannot interfere, and a graph being drawn while a check runs never shows a half-built search tree.

      Type Parameters:
      E - the kind of edges
      Parameters:
      g1 - The STN graph
      source - the starting node
      edgeValue - the function to retrieve the correct value of the edge. If null, it is set to (e) -> e.getValue()
      horizon - the maximum value for the potential. It is meaningful in the source-node search to guarantee that any node is reachable from the source. If it is not equal to -2147483648, then the source node is connected to any node by an edge having horizon value. Otherwise, no edge is added, and if the source cannot reach any node, the determined distances are meaningful only for reachable nodes. A safe value for the horizon is the absolute greatest value present in the edges times the number of nodes.
      checkStatus1 - status to update with statistics of the algorithm. If it is null, the method does not update the statistics.
      Returns:
      false if a negative cycle was found -- and then it is in STN.STNCheckStatus.negativeCycle when checkStatus1 is not null -- true otherwise.
      See Also:

    • SSSP_BFCT

      static <E extends STNEdge> boolean SSSP_BFCT(@Nonnull TemporalConstraintGraph<E> g1, @Nonnull LabeledNode source, @Nullable STNEdge.EdgeValue<E> edgeValue, int horizon, @Nullable STN.STNCheckStatus checkStatus1, @Nullable it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> distanceOut)
      The same as SSSP_BFCT(TemporalConstraintGraph, LabeledNode, STNEdge.EdgeValue, int, STN.STNCheckStatus), with the distances handed back through distanceOut instead of being left in the nodes, which no longer carry a potential field.
      Type Parameters:
      E - the kind of edges
      Parameters:
      g1 - The STN graph
      source - the starting node
      edgeValue - the function to retrieve the correct value of the edge. If null, it is set to (e) -> e.getValue()
      horizon - the maximum value for the potential, as in the other overload
      checkStatus1 - status to update with statistics of the algorithm. If it is null, the method does not update the statistics.
      distanceOut - if not null, it is cleared and filled with the distance of each node at the moment the method returns. On a negative cycle those values are the partial ones reached when the cycle was detected, which is what the algorithm knows at that point and nothing more.
      Returns:
      false if a negative cycle was found, true otherwise
      Implementation Note:
      Measured on an STN of 2001 nodes and 6328 constraints, release build, best of six runs in a warm JVM, three alternating rounds: 8 to 10 ms. Before the search state moved from the nodes into the local arrays this method now uses, the same check took 72 to 74 ms on the same instance, so this is about eight times faster; the graph load and the other STN entry points were unaffected by that change.

      That cost is what makes the negative cycle always affordable for an STN: an algorithm that answers "not consistent" without a witness -- Floyd-Warshall, Johnson, and the two Bellman-Ford entry points, which give at most the node where they saw the network fail -- can be followed by one call to this method to obtain one, for a few milliseconds on a network of this size. For an STNU the same holds only for the cycles that do not run through a contingent link: this method finds the negative cycles of the LO graph, which on the 2020 non-controllable benchmarks is where 55% (1000 nodes) to 68% (2000 and 2500 nodes) of the refusals come from, and STNU.findSRNCycleInLOGraph uses it exactly there. A semi-reducible cycle involving contingent links is not a negative cycle of any static weighted graph and needs SRNCycleFinder.

    • UPDATE_DISTANCES

      @Nullable static it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> UPDATE_DISTANCES(GraphDistances apsp, it.unimi.dsi.fastutil.objects.Object2IntMap<LabeledNode> nodePotential, LabeledNode A)
      Updates the 'apsp' 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.

    • getDepthFirstOrder

      @Nonnull static <E> it.unimi.dsi.fastutil.objects.ObjectList<LabeledNode> getDepthFirstOrder(@Nonnull LabeledNode source, @Nonnull it.unimi.dsi.fastutil.objects.Object2ObjectMap<LabeledNode, ? extends it.unimi.dsi.fastutil.objects.ObjectList<it.unimi.dsi.fastutil.objects.ObjectObjectImmutablePair<LabeledNode, E>>> adjacencyListMap)
      Iterative method for determining a depth-first order of nodes.

      Depth-first order sorts nodes with respect to their 'finishing time' in a Depth-First-Search (DFS) (see cap. 22.3 of Cormen et al.).

      Type Parameters:
      E - the kind of edge
      Parameters:
      source - starting node of the visit. It must belong to the graph.
      adjacencyListMap - adjacency list indexed by node
      Returns:
      a list of nodes, where each node has an index equal to its 'finishing time' in a DFS.

    • getDepthFirstOrder

      @Nonnull static <E> it.unimi.dsi.fastutil.objects.ObjectList<LabeledNode> getDepthFirstOrder(@Nonnull LabeledNode source, @Nonnull it.unimi.dsi.fastutil.objects.Object2ObjectMap<LabeledNode, ? extends it.unimi.dsi.fastutil.objects.ObjectList<it.unimi.dsi.fastutil.objects.ObjectObjectImmutablePair<LabeledNode, E>>> adjacencyListMap, @Nullable it.unimi.dsi.fastutil.objects.Object2BooleanMap<LabeledNode> isVisited)
      Same as getDepthFirstOrder(LabeledNode, Object2ObjectMap), with an optional external isVisited map that lets repeated calls accumulate the visited set (needed, e.g., to peel strongly-connected components with successive reverse-post-order visits): a node already marked visited by a previous call is not traversed again, and every node finished in this call is marked visited on return. When isVisited is null, the visited set is purely internal to this call, i.e., the method behaves exactly like the two-argument overload.
      Type Parameters:
      E - the kind of edge
      Parameters:
      source - starting node of the visit. It must belong to the graph.
      adjacencyListMap - adjacency list indexed by node
      isVisited - optional external visit-status map (read and written); may be null.
      Returns:
      a list of nodes, where each node has an index equal to its 'finishing time' in a DFS.