Package ghidra.graph

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

java.lang.Object
ghidra.graph.GraphToTreeAlgorithm<V,E>
Type Parameters:
V - The vertex type
E - The edge type
public class GraphToTreeAlgorithm<V,E extends GEdge<V>> extends Object
This class provides an algorithm for topological graph sorting and an algorithm for using that topological sort to create a tree structure from the graph using that topological sort.

In general topological sorting and converting to a tree, require an acyclic graph. However, by supplying a root vertex, the graph can be made to be acyclic by traversing the graph from that root and discarding any edges the return to a "visited" vertex. This has a side effect of ignoring any nodes that are not reachable from the root node. Also, this algorithm class is constructed with an edge comparator which can also determine the order nodes are traversed, thereby affecting the final ordering or tree structure. Higher priority edges will be processed first, making those edges least likely to be removed as "back" edges.

To convert a general graph to a tree, some subset of the the graphs original edges are used to form the tree. There are many possible different trees that can be created in this way. This algorimth's goal is to create a tree such that if all the original "forward" edges are added back to the tree, they only flow down the tree. This is useful for creating a nicely organized layout of vertices and edges when drawn.

  • Constructor Details

    • GraphToTreeAlgorithm

      public GraphToTreeAlgorithm(GDirectedGraph<V,E> graph, Comparator<E> edgeComparator)
      Constructor.
      Parameters:
      graph - the graph from with to create a tree
      edgeComparator - provides a priority ordering of edges with higher priority edges getting first shot at claiming children for its sub-tree.

  • Method Details

    • toTree

      public GDirectedGraph<V,E> toTree(V root)
      Creates a tree graph with the given vertex as the root from this object's graph.
      Parameters:
      root - the vertex to be used as the root getting first shot at claiming children for its sub-tree.
      Returns:
      a graph with edges removed such that the graph is a tree.

    • topolocigalSort

      public List<V> topolocigalSort(V root)
      Sorts the vertices in this graph topologically.
      Parameters:
      root - the start node for traversing the graph (will always be the first node in the resulting list)
      Returns:
      a list of vertices reachable from the given root vertex, sorted topologically