Package ghidra.graph.algo

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

java.lang.Object
ghidra.graph.algo.TopologicalSorter<V,E>
Type Parameters:
V - the type of vector
E - the type of edge
public class TopologicalSorter<V,E extends GEdge<V>> extends Object
Computes a topological sorting of the vertices in a directed acyclic graph (DAG)

This produces a list of vertices in the graph s.t. for every pair (v, w) where v precedes w, it can never be the case that the edge w -> v exists in the graph. Optionally, this sorter may also require that the list is unique. Here are some examples:

A-->B-->C yields simply [A, B, C]

A, B-->C yields either [A, B, C], [B, A, C], or [B, C, A] If a total ordering is required, this example causes the algorithm to fail, since the solution is not unique.

A-->B-->C-->A fails always, because the graph contains a cycle, i.e., not a DAG.

A-->B-->D, A-->C-->D yields either [A, B, C, D] or [A, C, B, D]

See Also:

  • Constructor Details

    • TopologicalSorter

      public TopologicalSorter(GDirectedGraph<V,E> graph, boolean requireTotal)
      Apply a topological sort to the given graph
      Parameters:
      graph - the graph
      requireTotal - true to require a unique solution
      Implementation Notes:
      if a unique solution is not requested, this algorithm will choose a solution arbitrarily. It does not yield all possible solutions.

  • Method Details

    • sort

      public List<V> sort() throws SorterException
      Execute the algorithm an obtain the list of vertices, in topological order
      Returns:
      the sorted list of vertices
      Throws:
      SorterException - if the graph is cyclic, or if requireTotal is set and the solution is not unique.

    • checkTotal

      protected void checkTotal() throws SorterException
      Check that the solution is unique
      Throws:
      SorterException - if the solution is not unique

    • visit

      protected void visit(V n) throws SorterException
      Visit a vertex
      Parameters:
      n - the vertex
      Throws:
      SorterException - if a cycle is detected

    • visit

      protected void visit(V n, Deque<V> temp) throws SorterException
      Visit a vertex, checking for a cycle
      Parameters:
      n - the vertex
      temp - a list of previously-visited vertices on this path
      Throws:
      SorterException - if a cycle is detected