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 typeE
- 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.
-
-
-
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 graphv
- 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 graphv
- 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 graphv
- 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
-
-