package it.univr.di.cstnu.util;

import it.unimi.dsi.fastutil.objects.*;
import it.univr.di.Debug;
import it.univr.di.cstnu.algorithms.STN;
import it.univr.di.cstnu.graph.Edge;
import it.univr.di.cstnu.graph.LabeledNode;
import it.univr.di.cstnu.graph.STNEdge;
import it.univr.di.cstnu.graph.TNGraph;
import it.univr.di.labeledvalue.Constants;
import org.apache.commons.lang3.tuple.Triple;

import javax.annotation.Nonnull;
import javax.annotation.Nullable;
import java.util.Collection;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 * Utility class containing some graph algorithm implementations.
 */
public interface GraphAlgs {
	/**
	 * Logger for the default method
	 */
	Logger LOG = Logger.getLogger(GraphAlgs.class.getName());

	/**
	 * Determines the minimal distance between all pairs of nodes (all-pair-shortest-paths (APSP)) using the Floyd-Warshall algorithm.
	 * <p>
	 * If the graph contains a negative cycle, it returns false, and the graph contains the edges that form the negative cycle.
	 *
	 * @param <E>          the kind of edge
	 * @param graph        the graph to complete
	 * @param checkStatus1 possible status to fill during the computation.
	 *
	 * @return true if the graph is consistent, false otherwise. If the response is false, the edges do not represent the minimal distance between nodes.
	 */
	@SuppressWarnings("StaticMethodOnlyUsedInOneClass")
	static <E extends STNEdge> boolean APSP_FloydWarshall(final TNGraph<E> graph, final STN.STNCheckStatus checkStatus1) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("APSP_FloydWarshall started");
			}
		}
		final LabeledNode[] node = graph.getVerticesArray();
		final int n = node.length;
		LabeledNode iV, jV, kV;
		E ik, kj, ij;
		int v;

		for (int k = 0; k < n; k++) {
			kV = node[k];
			for (int i = 0; i < n; i++) {
				iV = node[i];
				for (int j = 0; j < n; j++) {
					if ((k == i) || (k == j)) {
						continue;
					}
					jV = node[j];

					ik = graph.findEdge(iV, kV);
					kj = graph.findEdge(kV, jV);
					if ((ik == null) || (kj == null)) {
						continue;
					}
					v = Constants.sumWithOverflowCheck(ik.getValue(), kj.getValue());

					if (i == j) {
						if (v < 0) {
							// check negative cycles
							LOG.info("Found a negative cycle on node %s\nDetails: ik=%s, kj=%s,  v=%d".formatted(iV.getName(), ik, kj, v));
							if (checkStatus1 != null) {
								checkStatus1.consistency = false;
								checkStatus1.finished = true;
							}
							return false;
						}
						continue;
					}

					ij = graph.findEdge(iV, jV);
					int old = Constants.INT_POS_INFINITE;
					if (ij == null) {
						ij = graph.makeNewEdge(node[i].getName() + "-" + node[j].getName(), Edge.ConstraintType.derived);
						graph.addEdge(ij, iV, jV);
						if (Debug.ON) {
							if (LOG.isLoggable(Level.FINEST)) {
								LOG.finest("Added edge " + ij);
							}
						}
					} else {
						if (Debug.ON) {
							old = ij.getValue();
						}
					}
					if (ij.updateValue(v)) {
						if (checkStatus1 != null) {
							checkStatus1.propagationCalls++;
						}
						if (Debug.ON) {
							if (LOG.isLoggable(Level.FINEST)) {
								LOG.finest("Edge " + ij.getName() + ": " + Constants.formatInt(old) + " --> " + Constants.formatInt(v) + " because result of " + ik + " + " + kj);
							}
						}
					}
				}
			}
			if (checkStatus1 != null) {
				checkStatus1.cycles++;
			}
		}
		if (checkStatus1 != null) {
			checkStatus1.consistency = true;
			checkStatus1.finished = true;
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("APSP_FloydWarshall finished.");
			}
		}
		return true;
	}

	/**
	 * Determines the minimal distance between all pairs of nodes (all-pair-shortest-paths (APSP)) using the Johnson algorithm.
	 *
	 * @param graphDistances input GraphDistances. It must not be null, and it is updated with the new distances.
	 * @param nodePotential  a node potential function of the input graph. If null, it is determined inside the method.
	 *
	 * @return the new graph distances if all distances have been determined, null if a negative cycle or any other error occurred.
	 */
	@Nullable
	@SuppressWarnings("UnusedReturnValue")
	static GraphDistances APSP_Johnson(final @Nonnull GraphDistances graphDistances, Object2IntMap<LabeledNode> nodePotential) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.INFO)) {
				LOG.info("APSP_Johnson started.");
			}
		}
		if (Debug.ON) {
			LOG.finer("Determining a potential by Bellman-Ford.");
		}
		if (nodePotential == null) {
			nodePotential = GET_BellmanFord_Potential(graphDistances, null);
		}
		if (nodePotential == null) {
			if (Debug.ON) {
				LOG.finer("The distance matrix is not consistent.");
			}
			return null;
		}
		REWEIGHT_DISTANCES(graphDistances, nodePotential, true);
		final ExtendedPriorityQueue<LabeledNode> queueForDijkstra = new ExtendedPriorityQueue<>();
		for (final LabeledNode source : graphDistances.getNodes()) {
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINEST)) {
					LOG.finest("\nDetermining the distances considering node " + source.getName() + " as source node using Dijkstra.");
				}
			}
			// Dijkstra determines distances from the source
			if (!GET_SSSP_Dijkstra(graphDistances, source, queueForDijkstra)) {
				throw new IllegalStateException("Dijkstra cannot find distances from the source " + source);
			}
		}
		REWEIGHT_DISTANCES(graphDistances, nodePotential, false);
		if (Debug.ON) {
			if (LOG.isLoggable(Level.INFO)) {
				LOG.info("APSP_Johnson finished.");
			}
		}
		return graphDistances;
	}

	/**
	 * Determines the minimal distance between all pairs of nodes (all-pair-shortest-paths (APSP)) using the Johnson algorithm. The minimal distance between a node {@code X} and a node {@code Y} is saved as the value of the edge {@code (X, Y)}. If {@code Y} is not reachable from  {@code X}, the edge {@code (X, Y)} is null.
	 * <p>
	 * This method was built to determine the APSP very quickly. Don't use this graph in the {@link it.univr.di.cstnu.visualization.TNEditor} because it does not allow the editing of node or edge attributes.
	 *
	 * @param <E>         the kind of edges
	 * @param tnGraph     input graph. It must not be null. It will be completed with all the minimal distances.
	 * @param checkStatus status to update with statistics of the algorithm. It can be null.
	 *
	 * @return true if all distances have been determined, false if a negative cycle or any other error occurred.
	 *
	 * @see #APSP_Johnson(TNGraph, Object2IntMap, STN.STNCheckStatus)
	 */
	@SuppressWarnings("UnusedReturnValue")
	static <E extends STNEdge> boolean APSP_Johnson(final TNGraph<E> tnGraph, final STN.STNCheckStatus checkStatus) {
		return APSP_Johnson(tnGraph, null, 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 {@link STNEdge#getValue()} and set by the method {@link STNEdge#setValue(int)}.
	 * <p>
	 * The minimal distance between a node {@code X} to a node {@code Y} is saved as the value of the edge {@code (X, Y)}.
	 * <b>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.</b> If {@code Y} is not reachable from  {@code X}, the edge  {@code (X, Y)} is null.
	 * <p>
	 * This method was built to determine the APSP relatively quickly. Don't use this graph in the {@link it.univr.di.cstnu.visualization.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 {@link #APSP_Johnson(GraphDistances, Object2IntMap)}.
	 *
	 * @param <E>           the kind of edges
	 * @param tnGraph       input graph. It must not be null. It will be completed with all the minimal distances.
	 * @param nodePotential a node potential function of the input graph. If null, it is determined inside the method.
	 * @param checkStatus   status to update with statistics of the algorithm. It can be null.
	 *
	 * @return true if all distances have been determined, false if a negative cycle or any other error occurred.
	 */
	@SuppressWarnings("UnusedReturnValue")
	static <E extends STNEdge> boolean APSP_Johnson(final TNGraph<E> tnGraph, Object2IntMap<LabeledNode> nodePotential, final STN.STNCheckStatus checkStatus) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("APSP_Johnson started.");
			}
		}
		final TNGraph<E> finalG = new TNGraph<>(tnGraph, tnGraph.getEdgeImplClass(), true, true);

		if (Debug.ON) {
			LOG.finer("Determining a potential by Bellman-Ford.");
		}
		if (nodePotential == null) {
			nodePotential = GET_BellmanFord_Potential(tnGraph, STNEdge::getValue, checkStatus);
		}
		if (nodePotential == null) {
			if (Debug.ON) {
				LOG.finer("The STN is not consistent.");
			}
			return false;
		}
		if (Debug.ON) {
			LOG.finest("Re-weighting all edges.");
		}
		REWEIGHT_EDGES(tnGraph, nodePotential);

		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINEST)) {
				LOG.finest("Re-weighted graph: " + tnGraph);
			}
		}

		// Determine the distances from each node, updating the edge in the finalG
		Object2IntMap<LabeledNode> nodeDistanceFromSource;
		int newEdgeSDValue;
		E edgeSD;
		for (final LabeledNode source : tnGraph.getVertices()) {
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINEST)) {
					LOG.finest("\nDetermining the distances considering node " + source.getName() + " as source node using Dijkstra.");
				}
			}
			// Dijkstra determines distances from the source
			nodeDistanceFromSource = GET_SSSP_Dijkstra(tnGraph, source, checkStatus);
			if (nodeDistanceFromSource == null) {
				throw new IllegalStateException("Dijkstra cannot find distances from the source " + source);
			}

			// for each other node reachable from source, adjust the minimal distance from source in finalG
			for (final LabeledNode d : nodeDistanceFromSource.keySet()) {
				if (d == source) {
					continue;
				}
				// a new potential value is the value of the edge in Dijkstra plus the difference between the original destination potential and the source:
				// DijkstraDistance + (d - s)
				newEdgeSDValue = Constants.sumWithOverflowCheck(nodeDistanceFromSource.getInt(d), Constants.sumWithOverflowCheck(nodePotential.getInt(d), -nodePotential.getInt(source)));
				if (newEdgeSDValue == Constants.INT_POS_INFINITE) {
					continue;//the node is not reachable
				}
				// D is reachable from S, but there is no direct edge.
				// Johnson assumes to save the value of the edge... so we add it as internal.
				edgeSD = finalG.makeNewEdge(source.getName() + "-" + d.getName(), Edge.ConstraintType.derived);
				finalG.addEdgeWithoutCheck(edgeSD, source.getName(), d.getName());

				edgeSD.setValue(newEdgeSDValue);
				if (Debug.ON) {
					if (LOG.isLoggable(Level.FINEST)) {
						LOG.finest("Adding edge " + edgeSD);
					}
				}
			}
		}
		tnGraph.takeFrom(finalG);
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("APSP_Johnson finished.");
			}
		}
		return true;
	}

	/**
	 * Determines the potential of nodes considering a virtual source node using the Bellman-Ford algorithm.
	 * <p>
	 * 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 {@code edgeValue} parameter. In this way, all nodes not reachable from others have a potential equal to 0.
	 * <p>
	 * The potential is returned as a map (node, value). If the graph contains a negative cycle, it returns null.
	 *
	 * @param graphDistances input GraphDistances.
	 * @param 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.
	 *
	 * @return the map of pairs (node, distanceFromSource) if the graph is consistent; otherwise, it is null.
	 */
	@Nullable
	static Object2IntMap<LabeledNode> GET_BellmanFord_Potential(final @Nonnull GraphDistances graphDistances, final @Nullable LabeledNode source) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.INFO)) {
				LOG.info("GET_BellmanFord_Potential started.");
			}
		}

		final ObjectSet<LabeledNode> nodes = graphDistances.getNodes();
		final int n = nodes.size();
		final Object2IntMap<LabeledNode> solution = new Object2IntOpenHashMap<>(n);
		solution.defaultReturnValue(0);
		// defaultReturnValue is not enough because some nodes can be only the source of edges, so they are never modified after.
		// Initialize all nodes to 0 potential
		nodes.forEach((node) -> solution.put(node, 0)); // Initialize all nodes to 0 potential

		boolean nodesUpdated;
		for (int i = 1; i < n; i++) {// n-1 rounds at most
			nodesUpdated = false;
			for (final LabeledNode s : nodes) {
				for (final Object2IntMap.Entry<LabeledNode> adjEntry : graphDistances.getReachable(s).object2IntEntrySet()) {
					final LabeledNode d = adjEntry.getKey();
					// make sure that the edge has a significant value
					final int sdDistance = adjEntry.getIntValue();
					if (sdDistance == Constants.INT_POS_INFINITE) {
						continue;
					}
					/* Such a method was initially thought to find the minimal distance between nodes connected by paths having all negative edges (no cycles). So, we update the potential of the source instead of the destination because we like positive values instead of negative ones. :-)
					 * If (X, -3, Y) is the edge and X and Y potentials are both 0,
					 * using the standard approach: Y:= X+v = X-3 = 0-3 = -3
					 * using the equivalent inverted update: X:= Y-v = 0+3 = 3
					 */
					final int v = Constants.sumWithOverflowCheck(solution.getInt(d), -sdDistance);// -sdDistance because we sum using destination potential
					final int sDistance = solution.getInt(s);
					if (sDistance < v) {
						if (Debug.ON) {
							if (LOG.isLoggable(Level.FINEST)) { // Log the potential update
								LOG.finest("Potential on node " + s.getName() + " from " + Constants.formatInt(sDistance) + " to " + Constants.formatInt(v));
							}
						}
						solution.put(s, v);
						nodesUpdated = true;
					}
				}
			}
			if (!nodesUpdated) { // If no update occurred, the algorithm has converged
				if (Debug.ON) {
					if (LOG.isLoggable(Level.INFO)) {
						LOG.info("GET_BellmanFord_Potential finished.");
					}
				}
				return solution;
			}
		}
		// check if a negative cycle is present
		for (final LabeledNode s : nodes) { // Iterate through all nodes to check for negative cycles
			for (final Object2IntMap.Entry<LabeledNode> adjEntry : graphDistances.getReachable(s).object2IntEntrySet()) {
				final LabeledNode d = adjEntry.getKey();
				// make sure that the edge has a significant value
				final int sdDistance = adjEntry.getIntValue();
				if (sdDistance == Constants.INT_POS_INFINITE) {
					continue;
				}
				final int v = Constants.sumWithOverflowCheck(solution.getInt(d), -sdDistance);
				final int sDistance = solution.getInt(s);
				if (sDistance < v) {
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINE)) { // Log the negative cycle detection
							LOG.fine("BF inconsistency:" + s.getName() + " value from " + Constants.formatInt(sDistance) + " to " + Constants.formatInt(v));
						}
					}
					if (Debug.ON) {
						if (LOG.isLoggable(Level.INFO)) {
							LOG.info("GET_BellmanFord_Potential finished.");
						}
					}
					return null;
				}
			}
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.INFO)) {
				LOG.info("GET_BellmanFord_Potential finished.");
			}
		}
		return solution;
	}

	/**
	 * Determines the potential of nodes considering a virtual source node using the Bellman-Ford algorithm.
	 * <p>
	 * 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 {@code edgeValue} parameter determines the value of the edge. In this way, all nodes not reachable from others have a potential equal to 0.
	 * <p>
	 * The potential is returned as a map (node, value). If the graph contains a negative cycle, it returns null.
	 * <p>
	 * This method implements Algorithm 8 in the Technical Appendix of the AAAI22 paper.
	 * <p>
	 * The Technical Appendix is published at <a href="https://hdl.handle.net/11562/1045707">https://hdl.handle.net/11562/1045707</a>.</p>
	 *
	 * @param <E>         type of edge
	 * @param graph       input graph
	 * @param edgeValue   the value of each edge to be considered
	 * @param checkStatus possible status data structure where to register possible failures.
	 *
	 * @return the minimal potential if the network is consistent; otherwise, it is null.
	 */

	static <E extends STNEdge> Object2IntMap<LabeledNode> GET_BellmanFord_Potential(final TNGraph<E> graph, final STNEdge.EdgeValue<E> edgeValue, final STN.STNCheckStatus checkStatus) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.INFO)) {
				LOG.info("GET_BellmanFord_Potential started.");
			}
		}
		final Collection<LabeledNode> nodes = graph.getVertices();
		final int n = nodes.size();
		final ObjectList<Triple<LabeledNode, E, LabeledNode>> edgesAndNode = graph.getEdgesAndNodes();
		final Object2IntOpenHashMap<LabeledNode> distanceFromSource = new Object2IntOpenHashMap<>(n);
		distanceFromSource.defaultReturnValue(0);
		nodes.forEach((node) -> distanceFromSource.put(node, 0)); //It must be added to guarantee that if one lists such a map, they can meet all the nodes.

		for (int i = 1; i < n; i++) {// n-1 rounds
			boolean update = false;
			for (final Triple<LabeledNode, E, LabeledNode> entry : edgesAndNode) {
				final E e = entry.getMiddle();
				// make sure that the edge has a significant value
				final int w = edgeValue.getValue(e);
				if (w == Constants.INT_POS_INFINITE || w == Constants.INT_NULL) {// It is a useless value. This is correct because it is possible that, for example, the edge is an upper-case, and it is required to find the potential considering only ordinary values.
					continue;
				}
				final LabeledNode s = entry.getLeft();
				final LabeledNode d = entry.getRight();
				/* Such a method was initially thought to find the minimal distance between nodes connected by paths having all negative edges (no cycles).
				 * So, we update the potential of the source instead of the destination because we like positive values instead of negative ones. :-)
				 * If (X, -3, Y) is the edge and X and Y potentials are both 0,
				 * using the standard approach: Y:= X+v = X-3 = 0-3 = -3
				 * using the equivalent inverted update: X:= Y-v = 0+3 = 3
				 */
				final int v = Constants.sumWithOverflowCheck(distanceFromSource.getInt(d), -w);// -w because we sum using destination potential
				final int sDistance = distanceFromSource.getInt(s);
				if (sDistance < v) {
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINEST)) {
							assert s != null;
							LOG.finest("Potential on node " + s.getName() + " from " + Constants.formatInt(sDistance) + " to " + Constants.formatInt(v));
						}
					}
					distanceFromSource.put(s, v);
					update = true;
				}
			}
			if (!update) {
				if (Debug.ON) {
					if (LOG.isLoggable(Level.INFO)) {
						LOG.info("GET_BellmanFord_Potential finished.");
					}
				}
				return distanceFromSource;
			}
		}
		// check if a negative cycle is present
		for (final Triple<LabeledNode, E, LabeledNode> entry : edgesAndNode) {
			final E e = entry.getMiddle();
			//Make sure that the edge has a significant value
			final int w = edgeValue.getValue(e);
			if (w == Constants.INT_POS_INFINITE || w == Constants.INT_NULL) {// It is a useless value. This is correct because it is possible that, for example, the edge is an upper-case, and it is required to find the potential considering only ordinary values.
				continue;
			}
			final LabeledNode s = entry.getLeft();
			final LabeledNode d = entry.getRight();
			final int v = Constants.sumWithOverflowCheck(distanceFromSource.getInt(d), -w);
			final int sDistance = distanceFromSource.getInt(s);
			if (sDistance < v) {
				if (Debug.ON) {
					if (LOG.isLoggable(Level.FINE)) {
						assert s != null;
						LOG.fine("BF inconsistency:%s value from %s to %s".formatted(s.getName(), Constants.formatInt(sDistance), Constants.formatInt(v)));
					}
				}
				if (checkStatus != null) {
					checkStatus.consistency = false;
					checkStatus.finished = true;
				}
				if (Debug.ON) {
					if (LOG.isLoggable(Level.INFO)) {
						LOG.info("GET_BellmanFord_Potential finished.");
					}
				}
				return null;
			}
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINEST)) {
				LOG.finest("BF: potential determined: " + distanceFromSource);
			}
			if (LOG.isLoggable(Level.INFO)) {
				LOG.info("GET_BellmanFord_Potential finished.");
			}
		}
		return distanceFromSource;
	}

	/**
	 * Determines the minimal distance from the given source node to each other node (single-source-shortest-paths (SSSP)) using the Bellman-Ford algorithm.
	 * <p>
	 * The minimal distance is stored in a map {@code (node, distanceFromSource)}. If the graph contains a negative cycle, it returns null.
	 *
	 * @param <E>         the kind of edge. This method accepts any extensions of STNEdge. If {@link STNEdge#getValue()} does not return a valid value, the edge is ignored.
	 * @param graph       input graph. If it is null, the method returns false.
	 * @param 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.
	 * @param checkStatus status to update with statistics of the algorithm. It can be null.
	 *
	 * @return the map of pairs {@code (node, distanceFromSource)} if the graph is consistent, null otherwise.
	 */

	static <E extends STNEdge> Object2IntMap<LabeledNode> GET_SSSP_BellmanFord(final TNGraph<E> graph, final LabeledNode source, STN.STNCheckStatus checkStatus) {
		return GET_SSSP_BellmanFord(graph, source, false, Constants.INT_NULL, false, 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).
	 * <p>
	 * If a node is not reachable by the source node, its distance is {@link Constants#INT_POS_INFINITE}.
	 * <p>
	 * If the graph contains a negative cycle, it returns null.
	 *
	 * @param <E>              the kind of edge. This method accepts any extensions of STNEdge. If {@link STNEdge#getValue()} does not return a valid value, the edge is ignored.
	 * @param graph            input graph.
	 * @param 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.
	 * @param backward         true if the search has to be backward. If true, the source must be significant. Otherwise, it returns null.
	 * @param horizon          the maximum value for the potential. It is meaningful in the forward search to guarantee that any node is reachable from the source.
	 *                         <p>
	 *                         If it is not equal to {@link 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).
	 *                         <p>
	 *                         If it is equal to {@link Constants#INT_NULL}, the determined distances are meaningful only for reachable nodes; all other nodes are at distance {@link 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.
	 * @param setNodePotential true if also {@code node.potential} must be set.
	 * @param checkStatus      status to update with statistics of the algorithm. It can be null.
	 *
	 * @return the map of pairs (node, distanceFromSource) if the graph is consistent; otherwise, it is null.
	 */

	static <E extends STNEdge> Object2IntMap<LabeledNode> GET_SSSP_BellmanFord(final TNGraph<E> graph, final LabeledNode source, final boolean backward, int horizon, final boolean setNodePotential, final STN.STNCheckStatus checkStatus) {

		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("GET_SSSP_BellmanFord started.");
			}
		}
		final Collection<LabeledNode> nodes = graph.getVertices();
		if (source != null && !nodes.contains(source)) {
			return null;
		}
		final int n = nodes.size();
		final ObjectList<Triple<LabeledNode, E, LabeledNode>> edgesAndNode = graph.getEdgesAndNodes();
		final Object2IntMap<LabeledNode> solution = new Object2IntOpenHashMap<>();

		if (source == null) {
			horizon = 0;
			if (backward) {
				return null;
			}
		}

		if (horizon == Constants.INT_NULL) {
			horizon = Constants.INT_POS_INFINITE;
		}

		final int h = horizon;
		solution.defaultReturnValue(h);
		// defaultReturnValue is not enough because some nodes can be only the source of edges, so they are never modified after.
		nodes.forEach((node) -> {
			solution.put(node, h);
			if (setNodePotential) {
				node.setPotential(h);
			}
		});

		if (source != null) {
			if (setNodePotential) {
				source.setPotential(0);
			}
			solution.put(source, 0);
		}
		LabeledNode s, d;
		for (int i = 1; i < n; i++) {// n-1 rounds
			boolean update = false;
			for (final Triple<LabeledNode, E, LabeledNode> entry : edgesAndNode) {
				final E e = entry.getMiddle();
				// Make sure that the edge has a significant value
				final int edgeValue = e.getValue();
				if (edgeValue == Constants.INT_NULL || edgeValue == Constants.INT_POS_INFINITE) {
					continue;
				}
				if (backward) {// For the 'single sink', each edge is reversed
					d = entry.getLeft();
					s = entry.getRight();
				} else {
					s = entry.getLeft();
					d = entry.getRight();
				}
				final int v = Constants.sumWithOverflowCheck(solution.getInt(s), edgeValue);
				if (solution.getInt(d) > v) {
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINEST)) {
							assert d != null;
							LOG.finest("BF %s potential: %s --> %s".formatted(d.getName(), Constants.formatInt(solution.getInt(d)), Constants.formatInt(v)));
						}
					}
					if (setNodePotential) {
						assert d != null;
						d.setPotential(v);
					}
					solution.put(d, v);
					update = true;
					if (checkStatus != null) {
						checkStatus.propagationCalls++;
					}
				}
			}
			if (!update) {
				if (checkStatus != null) {
					checkStatus.cycles = i;
					checkStatus.consistency = true;
					checkStatus.finished = true;
				}
				return solution;
			}
		}
		// check if a negative cycle is present
		for (final Triple<LabeledNode, E, LabeledNode> entry : edgesAndNode) {
			final E e = entry.getMiddle();
			// make sure that the edge has a significant value
			final int edgeValue = e.getValue();
			if (edgeValue == Constants.INT_NULL || edgeValue == Constants.INT_POS_INFINITE) {
				continue;
			}
			if (backward) {// For the 'single sink', each edge is reversed.
				d = entry.getLeft();
				s = entry.getRight();
			} else {
				s = entry.getLeft();
				d = entry.getRight();
			}
			assert s != null;
			final int v = Constants.sumWithOverflowCheck(solution.getInt(s), edgeValue);
			final int dValue = solution.getInt(d);
			if (dValue > v) {
				if (Debug.ON) {
					if (LOG.isLoggable(Level.FINEST)) {
						assert d != null;
						LOG.finest("SSSP_BellmanFord:%s potential: %s-->%s".formatted(d.getName(), Constants.formatInt(dValue), Constants.formatInt(v)));
					}
				}
				if (checkStatus != null) {
					checkStatus.consistency = false;
					checkStatus.finished = true;
					checkStatus.negativeLoopNode = d;
				}
				return null;
			}
		}
		if (checkStatus != null) {
			checkStatus.cycles = n;
			checkStatus.consistency = true;
			checkStatus.finished = true;
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("GET_SSSP_BellmanFord finished.");
			}
		}
		return solution;
	}

	/**
	 * Determines the minimal distance between a source node and any node reachable by the source (single-source-shortest-paths (SSSP)) using the Dijkstra algorithm.
	 * <p>
	 * Minimal distances are returned as map {@code (destinationNode, distance)}.
	 * <p>
	 * If a node is not reachable from the source, its distance is +∞.
	 * <p>
	 * If the graph contains a negative edge beyond the source outgoing edges or the source is not in the graph, it returns null.
	 *
	 * @param <E>         the kind of edge
	 * @param graph       input graph. Each edge must have a positive weight, but the edges outgoing from the source can have a negative weight.
	 * @param source      the source node. It must belong to the graph.
	 * @param checkStatus status to update with statistics of the algorithm. It can be null.
	 *
	 * @return null or a non-empty map {@code (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 +∞.
	 */

	static <E extends STNEdge> Object2IntMap<LabeledNode> GET_SSSP_Dijkstra(final TNGraph<E> graph, final LabeledNode source, final STN.STNCheckStatus checkStatus) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finer("Considering source node: " + source);
			}
		}
		final Collection<LabeledNode> nodes = graph.getVertices();
		final int n = nodes.size();
		if (!nodes.contains(source)) {
			return null;
		}
		int v;

		final ExtendedPriorityQueue<LabeledNode> nodeQueue = new ExtendedPriorityQueue<>(nodes.size());
		nodeQueue.insertOrUpdate(source, 0);
		LabeledNode s, d;
		AbstractObject2IntMap.BasicEntry<LabeledNode> entry;
		int sValue, eValue;
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINEST)) {
				LOG.finest("Determining distance from the source node " + source);
			}
		}
		while (!nodeQueue.isEmpty()) {
			entry = nodeQueue.extractFirstEntry();
			s = entry.getKey();
			sValue = entry.getIntValue();
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINEST)) {
					LOG.finest("Considering node " + s.getName() + " having distance " + Constants.formatInt(sValue));
				}
			}
			for (final ObjectObjectImmutablePair<E, LabeledNode> edgeEntry : graph.getOutEdgesAndNodes(s)) {
				final E e = edgeEntry.left();
				d = edgeEntry.right();
				assert d != null;
				eValue = e.getValue();
				if (eValue == Constants.INT_NULL || eValue == Constants.INT_POS_INFINITE) {//edge is useless
					continue;
				}
				if (eValue < 0 && !s.equalsByName(source)) {// s != source is for allowing the use of Dijkstra when the
					// edges from source are negative (it is a particular use of the Dijkstra algorithm).
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINEST)) {
							LOG.finest("Edge %s has a negative value, but it shouldn't. Source is %s. Destination is %s".formatted(e, source.getName(), d.getName()));
						}
					}
					return null;
				}
				v = Constants.sumWithOverflowCheck(sValue, eValue);
				final int dPriority = nodeQueue.getPriority(d);
				if (dPriority == Constants.INT_POS_INFINITE) {
					// d is not in the queue
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINEST)) {
							LOG.finest("Adds '" + d.getName() + "' to the queue with value " + Constants.formatInt(v));
						}
					}
					nodeQueue.insertOrUpdate(d, v);
					continue;
				}
				if (dPriority > v && nodeQueue.getStatus(d) == ExtendedPriorityQueue.Status.isPresent) {
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINEST)) {
							LOG.finest("Updates '" + d.getName() + "' node potential adding edge value " + eValue + ": " + Constants.formatInt(dPriority) + " --> " + Constants.formatInt(v));
						}
					}
					nodeQueue.insertOrUpdate(d, v);
					if (checkStatus != null) {
						checkStatus.propagationCalls++;
					}
				}
			}
		}
		if (checkStatus != null) {
			checkStatus.cycles = n;
			checkStatus.consistency = true;
			checkStatus.finished = true;
		}
		final Object2IntMap<LabeledNode> result = nodeQueue.getAllDeterminedPriorities();
		result.defaultReturnValue(Constants.INT_POS_INFINITE);//if one asks the distance of a non-reached node, the answer is +∞
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINEST)) {
				LOG.finest("Determined node distances from " + source + ": " + result);
			}
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finer("GET_SSSP_Dijkstra finished.");
			}
		}
		return result;
	}


	/**
	 * Determines the minimal distance between a source node and any node reachable by the source (single-source-shortest-paths (SSSP)) using the Dijkstra algorithm.
	 * <p>
	 * Minimal distances are returned as map {@code (destinationNode, distance)}.
	 * <p>
	 * If a node is not reachable from the source, its distance is +∞.
	 * <p>
	 * Only the outgoing edges from the source can contain negative distance.
	 * </p>
	 *
	 * @param graphDistances   input GraphDistances.
	 * @param source           the source node. It must belong to the graph.
	 * @param 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.
	 *
	 * @return 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 +∞.
	 */
	static boolean GET_SSSP_Dijkstra(final @Nonnull GraphDistances graphDistances, final @Nonnull LabeledNode source, final @Nullable ExtendedPriorityQueue<LabeledNode> nodeQueueToReuse) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finer("GET_SSSP_Dijkstra (graph distances)");
			}
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finer("Considering source node: " + source);
			}
		}
		int newDistance;
		Object2IntMap<LabeledNode> adjacents;
		final ExtendedPriorityQueue<LabeledNode> nodeQueue;

		if (nodeQueueToReuse != null) {
			nodeQueue = nodeQueueToReuse;
			nodeQueue.clear();
		} else {
			nodeQueue = new ExtendedPriorityQueue<>();
		}

		nodeQueue.insertOrUpdate(source, 0);
		LabeledNode s;
		AbstractObject2IntMap.BasicEntry<LabeledNode> entry;
		int sKey, distance;
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINEST)) {
				LOG.finest("Determining distance from the source node " + source);
			}
		}
		while (!nodeQueue.isEmpty()) {
			entry = nodeQueue.extractFirstEntry();
			s = entry.getKey();
			sKey = entry.getIntValue();
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINEST)) {
					LOG.finest("Considering node " + s.getName() + " having distance " + Constants.formatInt(sKey));
				}
			}
			adjacents = graphDistances.getReachable(s);
			for (final Object2IntMap.Entry<LabeledNode> adjEntry : adjacents.object2IntEntrySet()) {
				distance = adjEntry.getIntValue();
				if (distance == Constants.INT_POS_INFINITE) {//edge is not present
					continue;
				}
				final LabeledNode d = adjEntry.getKey();
				if (distance < 0 && !s.equalsByName(source)) {// s != source is for allowing the use of Dijkstra when the
					// edges from source are negative (it is a particular use of the Dijkstra algorithm).
					if (Debug.ON) {
						if (LOG.isLoggable(Level.FINEST)) {
							LOG.finest("Edge value %d has a negative value, but it shouldn't. Source is %s. Destination is %s".formatted(distance, source.getName(), d.getName()));
						}
					}
					return false;
				}
				newDistance = Constants.sumWithOverflowCheck(sKey, distance);
				final int dPriority = nodeQueue.getPriority(d);
				if (Debug.ON) {
					if (LOG.isLoggable(Level.FINEST)) {
						LOG.finest("Adds/updates '" + d.getName() + "' to the queue from value " + Constants.formatInt(dPriority) + " to value " + Constants.formatInt(newDistance));
					}
				}
				if (newDistance < dPriority && nodeQueue.getStatus(d) == ExtendedPriorityQueue.Status.wasPresent) {
					if (Debug.ON) {
						if (LOG.isLoggable(Level.INFO)) {
							LOG.info("Updates '" + d.getName() + "' node potential adding value " + distance + " determined an error because the node was already analyzed.");
						}
					}
					return false;
				}
				nodeQueue.insertOrUpdate(d, newDistance);
				if (newDistance <= dPriority) {// DO NOT REMOVE =! It is important to store in the graph distance that the distance(x,x)=0
					//such 0 is saved only if the test is newDistance <= dPriority
					//Otherwise, distance(x,x) is not defined, and GraphDistances returns +∞ per entry not defined.
					graphDistances.putDistance(source, d, newDistance);
				}
			}
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finer("GET_SSSP_Dijkstra finished.");
			}
		}
		return true;
	}

	/**
	 * Re-weights all distances using the potential function.
	 * <p>The potential of a node is assumed to be stored in {@code bfPotential}.</p>
	 * <p>If a distance is NULL or +∞, it is ignored.</p>
	 *
	 * @param graphDistances input graphDistances
	 * @param nodePotential  potential of each node.
	 * @param 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.
	 */
	static void REWEIGHT_DISTANCES(final GraphDistances graphDistances, final Object2IntMap<LabeledNode> nodePotential, boolean toPositive) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.INFO)) {
				LOG.info("REWEIGHT_DISTANCES started.");
			}
		}
		for (final LabeledNode node : graphDistances.getNodes()) {
			final int sPot = nodePotential.getInt(node);
			final Object2IntMap<LabeledNode> adjacents = graphDistances.getReachable(node);
			for (final Object2IntMap.Entry<LabeledNode> entry : adjacents.object2IntEntrySet()) {
				final int distance = entry.getIntValue();
				if (distance == Constants.INT_POS_INFINITE || distance == Constants.INT_NULL) {
					continue;
				}
				final LabeledNode d = entry.getKey();
				final int dPot = nodePotential.getInt(d);
				// new distance := the distance - the potential difference between destination and source: e - (d - s) = e + s - d
				final int potentialSum = (toPositive) ? Constants.sumWithOverflowCheck(sPot, -dPot) : Constants.sumWithOverflowCheck(-sPot, dPot);
				final int newDistance = Constants.sumWithOverflowCheck(distance, potentialSum);
				if (toPositive && newDistance < 0) {
					throw new IllegalStateException("Error in re-weighting. " + "Re-weighting " + distance + ": Source potential: " + Constants.formatInt(sPot) + ", Destination potential: " + Constants.formatInt(dPot) + ". Distance: " + Constants.formatInt(distance) + ". New value (source+edge-destination): " + Constants.formatInt(newDistance));
				}
				entry.setValue(newDistance);
				if (Debug.ON) {
					if (LOG.isLoggable(Level.FINEST)) {
						LOG.finest("Re-weighting " + distance + ": Source potential: " + Constants.formatInt(sPot) + ", Destination potential: " + Constants.formatInt(dPot) + ". Edge value: " + Constants.formatInt(distance) + ". New value (source+edge-destination): " + Constants.formatInt(newDistance));
					}
				}
			}
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("REWEIGHT_DISTANCES finished.");
			}
		}
	}

	/**
	 * Re-weights all edge weights using the potential function.
	 * <p>The potential of a node is assumed to be stored in {@code bfPotential}.
	 * <p>If the edge has a not valid value (NULL or +∞), it is ignored.</p>
	 *
	 * @param <E>           the kind of edges.
	 * @param graph         input graph
	 * @param nodePotential potential of each node.
	 *
	 * @throws IllegalStateException it is not possible to re-weigh it because the potential values are not correct.
	 */
	static <E extends STNEdge> void REWEIGHT_EDGES(final TNGraph<E> graph, final Object2IntMap<LabeledNode> nodePotential) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("REWEIGHT_EDGES started.");
			}
		}
		final ObjectList<Triple<LabeledNode, E, LabeledNode>> edgesAndNode = graph.getEdgesAndNodes();
		for (final Triple<LabeledNode, E, LabeledNode> entry : edgesAndNode) {
			final E e = entry.getMiddle();
			// make sure that the edge has a significant value
			final int eV = e.getValue();
			if (eV == Constants.INT_POS_INFINITE || eV == Constants.INT_NULL) {
				//if the edge has an invalid value (NULL or +∞), we ignore the edge.
				continue;
			}
			final LabeledNode s = entry.getLeft();
			final LabeledNode d = entry.getRight();
			assert s != null;
			final int sPot = nodePotential.getInt(s);
			assert d != null;
			final int dPot = nodePotential.getInt(d);
			if (sPot == Constants.INT_NULL || dPot == Constants.INT_NULL || sPot == Constants.INT_POS_INFINITE || dPot == Constants.INT_POS_INFINITE) {
				throw new IllegalStateException("At least one of the following nodes has a wrong potential value: source node potential " + sPot + ", destination potential " + dPot);
			}
			// The new value of edge 'e' is the value of 'e' - the potential difference between destination and source: e - (d - s) = e + s - d
			final int newV = Constants.sumWithOverflowCheck(eV, Constants.sumWithOverflowCheck(sPot, -dPot));
			if (newV < 0) {
				throw new IllegalStateException("Error in re-weighting. " + "Re-weighting " + e.getName() + ": Source potential: " + Constants.formatInt(sPot) + ", Destination potential: " + Constants.formatInt(dPot) + ". Edge value: " + Constants.formatInt(eV) + ". New value (source+edge-destination): " + Constants.formatInt(newV));
			}
			e.setValue(newV);
			if (Debug.ON) {
				if (LOG.isLoggable(Level.FINEST)) {
					LOG.finest("Re-weighting " + e.getName() + ": Source potential: " + Constants.formatInt(sPot) + ", Destination potential: " + Constants.formatInt(dPot) + ". Edge value: " + Constants.formatInt(eV) + ". New value (source+edge-destination): " + Constants.formatInt(newV));
				}
			}
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("REWEIGHT_EDGES finished.");
			}
		}
	}

	/**
	 * Updates the 'apap' graph distances and the `nodePotential` propagating the assumed updated outgoing edges from node `A`.
	 * <p>
	 * <b>Side effects: `apsp` will be updated.</b>
	 *
	 * @param apsp          the graph with assumed updated edges out-going from node 'A'
	 * @param nodePotential out-of-date potential function of the nodes in 'apsp'.
	 * @param A             a node of 'apsp'.
	 *
	 * @return update node potential or null if an inconsistency is found.
	 */

	@SuppressWarnings("StaticMethodOnlyUsedInOneClass")
	static Object2IntMap<LabeledNode> UPDATE_DISTANCES(final GraphDistances apsp, final Object2IntMap<LabeledNode> nodePotential, final LabeledNode A) {
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("UPDATE_DISTANCES started.");
			}
			if (LOG.isLoggable(Level.FINER)) {
				LOG.finer("Considering activation node " + A);
			}
		}
		final Object2IntMap<LabeledNode> newPotential = new Object2IntOpenHashMap<>(nodePotential);
		final ExtendedPriorityQueue<LabeledNode> localMinQueue = new ExtendedPriorityQueue<>();

		localMinQueue.insertOrUpdate(A, 0);

		AbstractObject2IntMap.BasicEntry<LabeledNode> entry;
		LabeledNode V, W;
		while (!localMinQueue.isEmpty()) {
			entry = localMinQueue.extractFirstEntry();
			V = entry.getKey();
			final int keyV = entry.getIntValue();
			for (final Object2IntMap.Entry<LabeledNode> adjEntry : apsp.getReachable(V).object2IntEntrySet()) {
				final int delta = adjEntry.getIntValue();
				/* edge is (V, delta, W)*/
				if (delta == Constants.INT_POS_INFINITE) {// it is useless
					continue;
				}
				W = adjEntry.getKey();
				final int oldAWvalue = apsp.getDistance(A, W);
				final int AVvalue = (A == V) ? 0 : apsp.getDistance(A, V);
				final int newAWvalue = Constants.sumWithOverflowCheck(AVvalue, delta);
				if (oldAWvalue >= newAWvalue) {
					//'>=' because even if the edge value is already correct, it is possible that the potential is not.
					//So, I check whether the potential is necessary.
					apsp.putDistance(A, W, newAWvalue);
					//now check the potential, which could also be changed
					final int Wpot = newPotential.getInt(W);
					final int newWpot = Constants.sumWithOverflowCheck(newPotential.getInt(V), delta);
					if (Wpot > newWpot) {//i.e., d(W) > d(V) + delta
						newPotential.put(W, newWpot);
					}
					if (oldAWvalue > newAWvalue || Wpot > newWpot) {
						final int newKey = keyV + nodePotential.getInt(V) + delta - nodePotential.getInt(W);
						if (!localMinQueue.insertOrUpdate(W, newKey)) {
							return null;// there is a negative loop!
						}
					}
				}
			}
		}
		if (Debug.ON) {
			if (LOG.isLoggable(Level.FINE)) {
				LOG.fine("UPDATE_DISTANCES finished.");
			}
		}
		return newPotential;
	}


}