{"record":{"id":"88e01ab9b05783d1","repo":"NationalSecurityAgency/ghidra","slug":"not-a-total-order","errorCode":null,"errorMessage":"Not a total order: {} ?? {}","messagePattern":"Not a total order: (.+?) \\?\\? (.+?)","errorType":"exception","errorClass":"SorterException","httpStatus":null,"severity":"warning","filePath":"Ghidra/Debug/ProposedUtils/src/main/java/ghidra/graph/algo/TopologicalSorter.java","lineNumber":103,"sourceCode":"\t\t\tvisit(n);\n\t\t}\n\t}\n\n\t/**\n\t * Check that the solution is unique\n\t * \n\t * @throws SorterException if the solution is not unique\n\t */\n\tprotected void checkTotal() throws SorterException {\n\t\t// This is probably not the most efficient, but this should only be once per message type\n\t\tDijkstraShortestPathsAlgorithm<V, E> dijkstra =\n\t\t\tnew DijkstraShortestPathsAlgorithm<>(graph, GEdgeWeightMetric.unitMetric());\n\t\tfor (V v1 : graph.getVertices()) {\n\t\t\tfor (V v2 : graph.getVertices()) { // Maybe look into spliterator? to avoid double check\n\t\t\t\tDouble distF = dijkstra.getDistancesFromSource(v1).get(v2);\n\t\t\t\tDouble distR = dijkstra.getDistancesFromSource(v2).get(v1);\n\t\t\t\tif (distF == null && distR == null) {\n\t\t\t\t\tthrow new SorterException(\"Not a total order\", v1, v2);\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\n\t/**\n\t * Visit a vertex\n\t * \n\t * @param n the vertex\n\t * @throws SorterException if a cycle is detected\n\t */\n\tprotected void visit(V n) throws SorterException {\n\t\tvisit(n, new LinkedList<>());\n\t}\n\n\t/**\n\t * Visit a vertex, checking for a cycle\n\t * ","sourceCodeStart":85,"sourceCodeEnd":121,"githubUrl":"https://github.com/NationalSecurityAgency/ghidra/blob/d5f144c24d6bc53c9cbf4448c6d11143e7696206/Ghidra/Debug/ProposedUtils/src/main/java/ghidra/graph/algo/TopologicalSorter.java#L85-L121","documentation":"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.","triggerScenarios":"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').","commonSituations":"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.","solutions":["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().","Add explicit ordering edges between the two reported vertices (or their components) so a directed path exists at least one way.","Remove disconnected vertices/components from the graph before sorting if they are irrelevant to the ordering.","Catch SorterException (it is checked) and fall back to a non-total ordering strategy for that subgraph."],"exampleFix":"// before\nTopologicalSorter<V,E> s = new TopologicalSorter<>(graph);\ns.sort(); // throws if two vertices are incomparable\n\n// after: ensure every pair is comparable, or tolerate a partial order\ntry {\n    TopologicalSorter<V,E> s = new TopologicalSorter<>(graph);\n    s.sort();\n} catch (SorterException e) {\n    // graph is only partially ordered; use a non-total topological order here\n    List<V> order = new DijkstraFiniteLoopGraphAlgorithm<>(graph).computeTopoOrder();\n}","handlingStrategy":"validation","validationCode":"// Before sorting, verify every pair is comparable (total order)\nDijkstraShortestPathsAlgorithm<V,E> d = new DijkstraShortestPathsAlgorithm<>(graph, GEdgeWeightMetric.unitMetric());\nfor (V v1 : graph.getVertices()) {\n    for (V v2 : graph.getVertices()) {\n        if (d.getDistancesFromSource(v1).get(v2) == null && d.getDistancesFromSource(v2).get(v1) == null) {\n            // incomparable pair: not a total order; do not call checkTotal()/sort\n        }\n    }\n}","typeGuard":null,"tryCatchPattern":"try {\n    List<V> order = new TopologicalSorter<V,E>(graph).sort();\n} catch (SorterException e) { // checked\n    // graph is not a total order; use a partial-order fallback\n}","preventionTips":["Confirm the graph is connected and totally ordered before calling a total-order sorter.","Use a partial-order sorter when incomparable pairs are acceptable.","Add ordering edges between incomparable components if a unique order is required."],"tags":["graph","topological-sort","total-order","dijkstra","checked-exception"],"backgroundTag":null,"analyzedSha":"d5f144c24d6bc53c9cbf4448c6d11143e7696206","analyzedAt":"2026-08-14T01:00:57.564Z","schemaVersion":2},"datasetVersion":"2026-08-14T05:17:29.042Z"}