Package ghidra.graph.algo

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

java.lang.Object
ghidra.graph.algo.GraphNavigator<V,E>
Type Parameters:
V - the vertex type
E - the edge type
public class GraphNavigator<V,E extends GEdge<V>> extends 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 Details

    • 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 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 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 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 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 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 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