Package org.openstreetmap.josm.data.algorithms

Class Tarjan

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private static class  Tarjan.TarjanHelper
      Helper class for storing the Tarjan algorithm runtime metadata.

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Map<Node,​java.util.List<Node>> graphMap
      Used to store the graph data as a map.
      private int index
      Used on algorithm runtime to keep track discovery progress.
      private java.util.Map<java.lang.Long,​Tarjan.TarjanHelper> registry
      Used to remember visited nodes and its metadata.
      private java.util.Collection<java.util.List<Node>> scc
      Used to store strongly connected components.
      private java.util.Deque<Node> stack
      Used on algorithm runtime to keep track discovery progress.

    • Constructor Summary

      Constructors 
      Constructor Description
      Tarjan​(NodeGraph graph)
      Initialize the Tarjan's algorithm.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.Map<Node,​java.util.List<Node>> getGraphMap()
      Returns the graph data as a map.
      java.util.Collection<java.util.List<Node>> getSCC()
      Returns the strongly connected components in the current graph.
      private java.util.List<Node> getSuccessors​(Node node)
      Returns the next direct successors from the graph of the given node.
      private void strongConnect​(Node u0)
      Calculates strongly connected components available from the given node, in an iterative fashion.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • registry

        private final java.util.Map<java.lang.Long,​Tarjan.TarjanHelper> registry
        Used to remember visited nodes and its metadata. Key is used for storing the unique ID of the nodes instead of the full data to save space.

      • graphMap

        private final java.util.Map<Node,​java.util.List<Node>> graphMap
        Used to store the graph data as a map.

      • scc

        private final java.util.Collection<java.util.List<Node>> scc
        Used to store strongly connected components. NOTE: single nodes are not stored to save memory.

      • stack

        private final java.util.Deque<Node> stack
        Used on algorithm runtime to keep track discovery progress.

      • index

        private int index
        Used on algorithm runtime to keep track discovery progress.

    • Constructor Detail

      • Tarjan

        public Tarjan​(NodeGraph graph)
        Initialize the Tarjan's algorithm.
        Parameters:
        graph - graph data in NodeGraph object format

    • Method Detail

      • getSCC

        public java.util.Collection<java.util.List<Node>> getSCC()
        Returns the strongly connected components in the current graph. Single nodes are ignored to save memory.
        Returns:
        the strongly connected components in the current graph

      • strongConnect

        private void strongConnect​(Node u0)
        Calculates strongly connected components available from the given node, in an iterative fashion.
        Parameters:
        u0 - the node to generate strongly connected components from

      • getSuccessors

        private java.util.List<Node> getSuccessors​(Node node)
        Returns the next direct successors from the graph of the given node.
        Parameters:
        node - a node to start search from
        Returns:
        direct successors of the node or an empty list, if it's a terminal node