NationalSecurityAgency/ghidra · warning · SorterException

Not a total order: {} ?? {}

Error message

Not a total order: {} ?? {}

What it means

Thrown by TopologicalSorter.checkTotal() (a checked SorterException) when the graph being sorted is not a total order: it computes all-pairs shortest paths and, for two vertices v1/v2, finds neither is reachable from the other (distF == null && distR == null). A total order requires every pair to be comparable, so two mutually-unreachable vertices mean the topological order is not unique/total. This is a structural validity check on the input graph, not a runtime fault.

Source

Thrown at Ghidra/Debug/ProposedUtils/src/main/java/ghidra/graph/algo/TopologicalSorter.java:103

			visit(n);
		}
	}

	/**
	 * Check that the solution is unique
	 * 
	 * @throws SorterException if the solution is not unique
	 */
	protected void checkTotal() throws SorterException {
		// This is probably not the most efficient, but this should only be once per message type
		DijkstraShortestPathsAlgorithm<V, E> dijkstra =
			new DijkstraShortestPathsAlgorithm<>(graph, GEdgeWeightMetric.unitMetric());
		for (V v1 : graph.getVertices()) {
			for (V v2 : graph.getVertices()) { // Maybe look into spliterator? to avoid double check
				Double distF = dijkstra.getDistancesFromSource(v1).get(v2);
				Double distR = dijkstra.getDistancesFromSource(v2).get(v1);
				if (distF == null && distR == null) {
					throw new SorterException("Not a total order", v1, v2);
				}
			}
		}
	}

	/**
	 * Visit a vertex
	 * 
	 * @param n the vertex
	 * @throws SorterException if a cycle is detected
	 */
	protected void visit(V n) throws SorterException {
		visit(n, new LinkedList<>());
	}

	/**
	 * Visit a vertex, checking for a cycle
	 *

View on GitHub (pinned to d5f144c24d)

Solutions

  1. Verify every vertex pair is comparable before calling sort; if incomparable pairs are acceptable, use a partial-order / non-unique sorter instead of one that calls checkTotal().
  2. Add explicit ordering edges between the two reported vertices (or their components) so a directed path exists at least one way.
  3. Remove disconnected vertices/components from the graph before sorting if they are irrelevant to the ordering.
  4. Catch SorterException (it is checked) and fall back to a non-total ordering strategy for that subgraph.

Example fix

// before
TopologicalSorter<V,E> s = new TopologicalSorter<>(graph);
s.sort(); // throws if two vertices are incomparable

// after: ensure every pair is comparable, or tolerate a partial order
try {
    TopologicalSorter<V,E> s = new TopologicalSorter<>(graph);
    s.sort();
} catch (SorterException e) {
    // graph is only partially ordered; use a non-total topological order here
    List<V> order = new DijkstraFiniteLoopGraphAlgorithm<>(graph).computeTopoOrder();
}
Defensive patterns

Strategy: validation

Validate before calling

// Before sorting, verify every pair is comparable (total order)
DijkstraShortestPathsAlgorithm<V,E> d = new DijkstraShortestPathsAlgorithm<>(graph, GEdgeWeightMetric.unitMetric());
for (V v1 : graph.getVertices()) {
    for (V v2 : graph.getVertices()) {
        if (d.getDistancesFromSource(v1).get(v2) == null && d.getDistancesFromSource(v2).get(v1) == null) {
            // incomparable pair: not a total order; do not call checkTotal()/sort
        }
    }
}

Try / catch

try {
    List<V> order = new TopologicalSorter<V,E>(graph).sort();
} catch (SorterException e) { // checked
    // graph is not a total order; use a partial-order fallback
}

Prevention

When it happens

Trigger: Invoking the sorter on a directed graph that has at least one pair of vertices with no directed path in either direction — e.g. disconnected components, two parallel branches that never rejoin, or sibling nodes with no ordering edge between them. checkTotal() is only meaningful when the caller requires a unique total order (see Javadoc 'if the solution is not unique').

Common situations: Building a dependency/ordering graph from program data (block ordering, instruction ordering) where some elements are genuinely incomparable; merging graphs from independent subtrees; feeding a DAG with multiple roots that never connect; expecting uniqueness from a graph that only admits a partial order.

Related errors

AI-assisted analysis of NationalSecurityAgency/ghidra@d5f144c24d (2026-08-14). Data as JSON: /api/errors/88e01ab9b05783d1. Report an issue: GitHub.