Package com.amalgamasimulation.graph

Interface Algorithm

public interface Algorithm
This interface consists exclusively of static methods that operate on graphs.
Author:
Andrey Malykhanov, Vitaliy Chernenko, Andrey Korotin

  • Method Details

    • getFirstPath

      static <A, B> GraphPath<A,B> getFirstPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Graph<A,B>.Node destNode)
      Returns the first found, not necessarily the shortest one, path between the specified source and destination nodes in the given graph.

      If the source and destination nodes are the same, a single node path is returned. If no path exists, the method returns null.

      Parameters:
      graph - The graph containing the nodes
      sourceNode - The starting node of the path
      destNode - The target node of the path
      Returns:
      the first found path from sourceNode to destNode, or null if no path exists

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Graph<A,B>.Node destNode, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter)
      Returns shortest path between the two specified graph nodes. If such path does not exist, returns null If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNode - Destination node of the path being searched
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Graph<A,B>.Node destNode, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, double range)
      Returns shortest path between the two specified graph nodes if the total weight of such path does not exceed the specified range. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNode - Destination node of the path being searched
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      range - Total weight that the returned path must not exceed
      Returns:
      Shortest path between the two specified graph nodes not exceeding the specified weight, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Graph<A,B>.Node destNode, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited)
      Returns shortest path between the two specified graph nodes. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNode - Destination node of the path being searched
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      outNodeWeights - Map containing weights of nodes of the minimal spanning tree built while finding the shortest path. This collection will be filled inside the method
      outArcsVisited - Set containing arcs of the minimal spanning tree, i.e. arcs visited while finding the shortest path. This collection will be filled inside the method
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Graph<A,B>.Node destNode, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited, double range)
      Returns shortest path between the two specified graph nodes if the total weight of such path does not exceed the specified range. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNode - Destination node of the path being searched
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      outNodeWeights - Map containing weights of nodes of the minimal spanning tree built while finding the shortest path. This collection will be filled inside the method
      outArcsVisited - Set containing arcs of the minimal spanning tree, i.e. arcs visited while finding the shortest path. This collection will be filled inside the method
      range - Total weight that the returned path must not exceed
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter)
      Returns shortest path from the specified graph node to the closest graph node satisfying the condition determined by the specified indicator. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition of destination node
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, double range)
      Returns shortest path from the specified graph node to the closest graph node satisfying the condition determined by the specified indicator if the total weight of such path does not exceed the specified range. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition of destination node
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      range - Total weight that the returned path must not exceed
      Returns:
      Shortest path between the two specified graph nodes, not exceeding the specified range, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited)
      Returns shortest path from the specified graph node to the closest graph node satisfying the condition determined by the specified indicator. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition of destination node
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      outNodeWeights - Map containing weights of nodes of the minimal spanning tree built while finding the shortest path. This collection will be filled inside the method
      outArcsVisited - Set containing arcs of the minimal spanning tree, i.e. arcs visited while finding the shortest path. This collection will be filled inside the method
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited, double range)
      Returns shortest path from the specified graph node to the closest graph node satisfying the condition determined by the specified indicator, if the total weight of such path does not exceed the specified range. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition of destination node
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      outNodeWeights - Map containing weights of nodes of the minimal spanning tree built while finding the shortest path. This collection will be filled inside the method
      outArcsVisited - Set containing arcs of the minimal spanning tree, i.e. arcs visited while finding the shortest path. This collection will be filled inside the method
      range - Total weight that the returned path must not exceed
      Returns:
      Shortest path between the two specified graph nodes, not exceeding the specified range, or null if such path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited, Set<Graph<A,B>.Arc> barrierArcs, double range)
      Returns shortest path from the specified graph node to the closest graph node satisfying the condition determined by the specified indicator. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition of destination node
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      outNodeWeights - Map containing weights of nodes of the minimal spanning tree built while finding the shortest path. This collection will be filled inside the method
      outArcsVisited - Set containing arcs of the minimal spanning tree, i.e. arcs visited while finding the shortest path. This collection will be filled inside the method
      barrierArcs - arcs that should not be traversed
      range - Total weight that the returned path must not exceed
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getMinPathWithContext

      static <A, B, T> Pair<GraphPath<A,B>,T> getMinPathWithContext(Graph<A,B> graph, Graph<A,B>.Node sourceNode, BiPredicate<Graph<A,B>.Node,T> searchSuccessPredicate, T sourceNodeContext, BiFunction<T,Graph<A,B>.Arc,T> contextProvider, Comparator<T> contextComparator)
      Returns a minimal-context path in the graph using a context-aware variant of Dijkstra’s algorithm.

      Each node holds a context value of type T, updated by contextProvider when traversing arcs. The search expands arcs in order of minimal context according to contextComparator, and stops when searchSuccessPredicate evaluates to true.

      Type Parameters:
      T - search context type (e.g., cost, distance, or state)
      Parameters:
      graph - the graph to search
      sourceNode - the starting node
      searchSuccessPredicate - predicate determining when the search stops
      sourceNodeContext - initial context at the source node
      contextProvider - function computing the next context from a source context and an arc that is added to the spanning tree
      contextComparator - comparator defining ordering of context values (lower means better)
      Returns:
      a Pair containing the resulting GraphPath and final context, or null if no path was found

    • calculateShortestPath

      static <A, B> GraphPath<A,B> calculateShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Graph<A,B>.Node destNode, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited)
      Calculates shortest path between the two specified nodes having data about nodes of the minimal spanning tree and arcs of the minimal spanning tree, i.e. arcs visited while finding the shortest path.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being calculated
      destNode - Destination node of the path being calculated
      outNodeWeights - Map containing weights of nodes of the minimal spanning tree built while finding the shortest path
      outArcsVisited - Set containing arcs of the minimal spanning tree, i.e. arcs visited while finding the shortest path
      Returns:
      Shortest path between the two specified graph nodes, or empty path if such path does not exist

    • getClosestNodes

      static <A, B> List<Pair<Graph<A,B>.Node,Double>> getClosestNodes(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, double range, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter)
      Returns list of pairs of nodes and distances to them from the specified source node satisfying the condition determined by the specified indicator. Allows to set the search range that will limit the search to the specified distance. List is sorted by distance from the source node. If there are several nodes at the same distance, their order is not guaranteed. If there are no nodes satisfying the specified indicator, empty list will be returned.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node from which the search starts
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition for nodes being searched
      range - Range that limits the search. The search is stopped if distance from the source node is more than range. If no limitation by distance is required, Double.POSITIVE_INFINITY should be specified
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getClosestNodes

      static <A, B> List<Pair<Graph<A,B>.Node,Double>> getClosestNodes(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, double range, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, int maxNodesCount)
      Returns list of pairs of nodes and distances to them from the specified source node satisfying the condition determined by the specified indicator. Allows to set the search range that will limit the search to the specified distance. List is sorted by distance from the source node. If there are several nodes at the same distance, their order is not guaranteed. If there are no nodes satisfying the specified indicator, empty list will be returned.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node from which the search starts
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition for nodes being searched
      range - Range that limits the search. The search is stopped if distance from the source node is more than range. If no limitation by distance is required, Double.POSITIVE_INFINITY should be specified
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      maxNodesCount - Maximum number of nodes to find. The search will stop after this amount of nodes is found
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getClosestNodes

      static <A, B> List<Pair<Graph<A,B>.Node,Double>> getClosestNodes(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, double range, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited)
      Returns list of pairs of nodes and distances to them from the specified source node satisfying the condition determined by the specified indicator. Allows to set the search range that will limit the search to the specified distance. List is sorted by distance from the source node. If there are several nodes at the same distance, their order is not guaranteed. If there are no nodes satisfying the specified indicator, empty list will be returned.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node from which the search starts
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition for nodes being searched
      range - Range that limits the search. The search is stopped if distance from the source node is more than range. If no limitation by distance is required, Double.POSITIVE_INFINITY should be specified
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      outNodeWeights - Mutable map of weights of nodes that are already known. Will be filled as a result of calling this method.
      outArcsVisited - Initially empty mutable set of arcs that will be visited during the search of the closest nodes. Will be filled as a result of calling this method.
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getClosestNodes

      static <A, B> List<Pair<Graph<A,B>.Node,Double>> getClosestNodes(Graph<A,B> graph, Graph<A,B>.Node sourceNode, Predicate<Graph<A,B>.Node> destNodeIndicator, double range, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter, Map<Graph<A,B>.Node,Double> outNodeWeights, Set<Graph<A,B>.Arc> outArcsVisited, int maxNodesCount)
      Returns list of pairs of nodes and distances to them from the specified source node satisfying the condition determined by the specified indicator. Allows to set the search range that will limit the search to the specified distance. List is sorted by distance from the source node. If there are several nodes at the same distance, their order is not guaranteed. If there are no nodes satisfying the specified indicator, empty list will be returned.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node from which the search starts
      destNodeIndicator - Class containing callback which will be called to check if node satisfies the condition for nodes being searched
      range - Range that limits the search. The search is stopped if distance from the source node is more than range. If no limitation by distance is required, Double.POSITIVE_INFINITY should be specified
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      outNodeWeights - Mutable map of weights of nodes that are already known. Will be filled as a result of calling this method.
      outArcsVisited - Initially empty mutable set of arcs that will be visited during the search of the closest nodes. Will be filled as a result of calling this method.
      maxNodesCount - maximum number of nodes. The search will stop after this number of nodes is found. To specify unlimited number of nodes pass Integer.MAX_VALUE to this parameter
      Returns:
      Shortest path between the two specified graph nodes, or null if path does not exist

    • getShortestPath

      static <A, B> GraphPath<A,B> getShortestPath(Graph<A,B> graph, Graph<A,B>.Node sourceNode, List<Predicate<Graph<A,B>.Node>> destNodeIndicators, Function<Graph<A,B>.Arc,Double> arcWeighter, Function<Graph<A,B>.Node,Double> nodeWeighter)
      Returns shortest path from the specified graph node through nodes specified by indicators. An indicator is a class that specifies condition according to which a node is chosen. If such path does not exist, returns null. If source node is equal to destination node, returns empty path. If there are more than 1 shortest paths, the method will always return the same path but there is no guarantee which path will be chosen.
      Parameters:
      graph - The graph containing source and destination nodes
      sourceNode - Source node of the path being searched
      destNodeIndicators - Class containing list of callbacks determining the sequence of nodes
      arcWeighter - Class containing callback which will be called to calculate weight of graph arcs
      nodeWeighter - Class containing callback which will be called to calculate weight of graph nodes
      Returns:
      Shortest path through nodes specified by indicators, or null if path does not exist

    • getTreeNodesByLevels

      static <A, B> List<List<Graph<A,B>.Node>> getTreeNodesByLevels(Graph<A,B> graph)
      Groups the nodes of the specified oriented tree by levels. A level is a group of nodes having the same distance from a root node. A distance in this case is defined as number of arcs that need to be traversed to reach the given node from a root one. There can be several root nodes in the specified graph. If the specified graph is not an oriented tree, a IllegalArgumentException will be thrown
      Parameters:
      graph - that must be an oriented tree
      Returns:
      List of lists of nodes grouped by levels

    • getInsignificantNodesAndArcs

      static <A, B> Pair<Set<Graph<A,B>.Node>,Set<Graph<A,B>.Arc>> getInsignificantNodesAndArcs(Graph<A,B> graph, Set<Graph<A,B>.Node> significantNodes)
      Returns the pair containing sets of insignificant nodes and arcs of the specified graph against the specified set of significant nodes. A node or arc is considered insignificant if it cannot be a part of any minimal path between any two significant nodes. The necessary assumption for this function is non-negative weights of all nodes and arcs which is the case in majority of real life cases.
      Parameters:
      graph - The specified graph
      significantNodes - Set of significant node in the specified graph
      Returns:
      Pair containing sets of insignificant nodes (first member of the pair) and arcs (second member of the pair). The returned pair and sets inside the pair are always non-null. Sets of insignificant arcs and nodes can be empty

    • getInsignificantNodesAndArcs

      static <A, B> Pair<Set<Graph<A,B>.Node>,Set<Graph<A,B>.Arc>> getInsignificantNodesAndArcs(Graph<A,B> graph, Set<Graph<A,B>.Node> significantNodes, Set<Graph<A,B>.Arc> barrierArcs)
      Returns the pair containing sets of insignificant nodes and arcs of the specified graph against the specified set of significant nodes. A node or arc is considered insignificant if it cannot be a part of any minimal path between any two significant nodes. The necessary assumption for this function is non-negative weights of all nodes and arcs which is the case in majority of real life cases.
      Parameters:
      graph - The specified graph
      significantNodes - Set of significant node in the specified graph
      barrierArcs - arcs that should not be traversed
      Returns:
      Pair containing sets of insignificant nodes (first member of the pair) and arcs (second member of the pair). The returned pair and sets inside the pair are always non-null. Sets of insignificant arcs and nodes can be empty

    • getBarrierArcs

      static <A, B> Set<Graph<A,B>.Arc> getBarrierArcs(Set<Graph<A,B>.Node> insignificantNodes, Set<Graph<A,B>.Arc> insignificantArcs)

    • getFirstCycle

      static <A, B> GraphPath<A,B> getFirstCycle(Graph<A,B> graph)
      Returns first found cycle in the specified graph. If there are no cycles in the graph, returns null. The function can return any cycle if there are several cycles in the graph, but for the same graph every time the same cycle will be returned.
      Parameters:
      graph - The specified graph
      Returns:
      The first found cycle in the graph, or null if there are no cycles in the graph

    • topologicalSort

      static <A, B> Map<Graph<A,B>.Node,Integer> topologicalSort(Graph<A,B> graph, Graph<A,B>.Node rootNode)
      Performs topological sorting of the graph with respect to the specified root node and returns a map containing mapping from graph nodes to integer numbers. Each number in this mapping is equal to minimum number of arcs to reach the given node from the root node.
      Parameters:
      graph - The specified graph
      rootNode - The specified root node
      Returns:
      Map containing mapping from graph nodes to integer numbers. Each number in this mapping is equal to minimum number of arcs to reach the given node from the root node. If a node cannot be reached from the source node, the mapping will contain -1 for this node.

    • topologicalSort

      static <A, B> Map<Graph<A,B>.Node,Integer> topologicalSort(Graph<A,B> graph, List<Graph<A,B>.Node> rootNodes)
      Performs topological sorting of the graph with respect to the specified root nodes and returns a map containing mapping from graph nodes to integer numbers. Each number in this mapping is equal to minimum number of arcs to reach the given node from the closest one of the root nodes.
      Parameters:
      graph - The specified graph
      rootNodes - The specified root nodes
      Returns:
      Map containing mapping from graph nodes to integer numbers. Each number in this mapping is equal to minimum number of arcs to reach the given node from the closest one of the root nodes. If a node cannot be reached from the source node, the mapping will contain -1 for this node.

    • getFragments

      static <A, B> List<Graph<A,B>> getFragments(Graph<A,B> graph)
      Returns all fragments (i.e. connected components) of the specified graph. A fragment is a fully isolated subgraph that can consist even of a single node.

      If the specified graph is a connected graph, returns a list containing only the specified graph.

      Parameters:
      graph - specified graph
      Returns:
      list containing all fragments (i.e. connected components) of the specified graph

    • traverse

      static <A, B, C> C traverse(Graph<A,B>.Node sourceNode, C sourceContext, Algorithm.GraphTraversalPredicate<A,B> traversedArcPredicate, Algorithm.GraphTraversalContextCalculator<A,B,C> recalculateNodeContext, Algorithm.GraphTraversalEndPredicate<A,B,C> endTraversalPredicate)
      Traverses the graph starting from the specified sourceNode by adding the arcs and nodes allowed by traversedArcPredicate until all reachable nodes are traversed or the specified endTraversalPredicate evaluated to true.

      A context of type C is calculated for every node being traversed. For the source node, the context is equal to the specified sourceContext. For every next node being traversed, its context is calculated by the specified recalculateNodeContext function. The result of the traversal is the last added context.

      Note that this function does not consider weights and thus does not build minimum spanning tree while traversal

      Type Parameters:
      A - type of graph node values
      B - type of graph arc values
      C - type of context, that is calculated for each node being traversed and returned as result of traversal
      Parameters:
      sourceNode - source node of the traversal
      sourceContext - context value of the specified source node
      traversedArcPredicate - predicate answering the question "Can we traverse the arc and the node adjacent to this arc?".

      Example of implementation:

      (addedArc, addedNode, addedArcDirection) -> true

      recalculateNodeContext - predicate answering the question "What must be the context of the node being added considering we know the added arc, the added node itself, and the context of the already traversed node adjacent to this arc?"

      Example of implementation for context of type Double:

      (addedArc, addedNode, addedArcDirection, prevNodeContext) -> prevNodeContext + addedArc.getValue().getLength()

      endTraversalPredicate - predicate answering the question "Must we end the traversal after we added the specific arc, node and calculated the specific node context?"

      Example of implementation for context of type Double:

      (addedArc, addedNode, addedNodeContext) -> addedNodeContext >= 100

      Returns:
      result of the traversal