Package ghidra.graph.algo

Class GraphNavigator<V,​E extends GEdge<V>>

  • Type Parameters:
    V - the vertex type
    E - the edge type
    public class GraphNavigator<V,​E extends GEdge<V>>
extends java.lang.Object
    The methods on this interface are meant to enable graph traversal in a way that allows the underlying graph to be walked from top-down or bottom-up.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      static <V,​E extends GEdge<V>>
      GraphNavigator<V,​E>      		 bottomUpNavigator()
      Creates a bottom-down navigator, which is one that traverses the graph from the sink to the source.
      java.util.Collection<E> getEdges​(GDirectedGraph<V,​E> graph, V v)
      Gets all edges leaving the given vertex, depending upon the direction of this navigator.
      V getEnd​(E e)
      Gets the vertex at the end of the given edge, where the 'end' of the edge depends on the start vertex.
      java.util.Collection<V> getPredecessors​(GDirectedGraph<V,​E> graph, V v)
      Gets all parent vertices of the given vertex, depending upon the direction of the navigator.
      java.util.Set<V> getSinks​(GDirectedGraph<V,​E> graph)
      Gets the exit vertices of the given graph.
      java.util.Set<V> getSources​(GDirectedGraph<V,​E> graph)
      Gets the root vertices of the given graph.
      java.util.Collection<V> getSuccessors​(GDirectedGraph<V,​E> graph, V v)
      Gets all child vertices of the given vertex, depending upon the direction of the navigator.
      java.util.List<V> getVerticesInPostOrder​(GDirectedGraph<V,​E> graph)
      Returns all vertices in the given graph in the depth-first order.
      boolean isTopDown()
      Returns true if this navigator processes nodes from the top down; false if nodes are processed from the bottom up.
      static <V,​E extends GEdge<V>>
      GraphNavigator<V,​E>      		 topDownNavigator()
      Creates a top-down navigator, which is one that traverses the graph from the source to the sink.

      • Methods inherited from class java.lang.Object

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

    • Method Detail

      • topDownNavigator

        public static <V,​E extends GEdge<V>> GraphNavigator<V,​E> topDownNavigator()
        Creates a top-down navigator, which is one that traverses the graph from the source to the sink.
        Returns:
        the navigator

      • bottomUpNavigator

        public static <V,​E extends GEdge<V>> GraphNavigator<V,​E> bottomUpNavigator()
        Creates a bottom-down navigator, which is one that traverses the graph from the sink to the source.
        Returns:
        the navigator

      • getEdges

        public java.util.Collection<E> getEdges​(GDirectedGraph<V,​E> graph,
                                        V v)
        Gets all edges leaving the given vertex, depending upon the direction of this navigator.
        Parameters:
        graph - the graph
        v - the vertex
        Returns:
        the edges

      • isTopDown

        public boolean isTopDown()
        Returns true if this navigator processes nodes from the top down; false if nodes are processed from the bottom up.
        Returns:
        true if this navigator processes nodes from the top down; false if nodes are processed from the bottom up.

      • getSuccessors

        public java.util.Collection<V> getSuccessors​(GDirectedGraph<V,​E> graph,
                                             V v)
        Gets all child vertices of the given vertex, depending upon the direction of the navigator.
        Parameters:
        graph - the graph
        v - the vertex
        Returns:
        the vertices

      • getPredecessors

        public java.util.Collection<V> getPredecessors​(GDirectedGraph<V,​E> graph,
                                               V v)
        Gets all parent vertices of the given vertex, depending upon the direction of the navigator.
        Parameters:
        graph - the graph
        v - the vertex
        Returns:
        the vertices

      • getEnd

        public V getEnd​(E e)
        Gets the vertex at the end of the given edge, where the 'end' of the edge depends on the start vertex.
        Parameters:
        e - the edge
        Returns:
        the vertex

      • getSources

        public java.util.Set<V> getSources​(GDirectedGraph<V,​E> graph)
        Gets the root vertices of the given graph. If this is a top-down navigator, then the sources are returned; otherwise, the sinks are returned.
        Parameters:
        graph - the graph
        Returns:
        the roots

      • getSinks

        public java.util.Set<V> getSinks​(GDirectedGraph<V,​E> graph)
        Gets the exit vertices of the given graph. If this is a top-down navigator, then the sinks are returned; otherwise, the sources are returned.
        Parameters:
        graph - the graph
        Returns:
        the exits

      • getVerticesInPostOrder

        public java.util.List<V> getVerticesInPostOrder​(GDirectedGraph<V,​E> graph)
        Returns all vertices in the given graph in the depth-first order. The order will be post-order for a top-down navigator and pre-order for a bottom-up navigator.
        Parameters:
        graph - the graph
        Returns:
        the ordered vertices