WorksComputer Science
IsaGraphLib: Formally Verified Efficient Graph Algorithms in Isabelle/HOL
Abstract
We present a library of formally verified graph algorithms in Isabelle/HOL. The library covers the main problems of combinatorial optimisation on graphs: reachability, shortest paths, minimum spanning trees, matching, maximum flow, and minimum-cost flow. The algorithms in the library use most of the standard algorithm design techniques: graph search, greedy algorithms on matroids, dynamic programming, augmenting paths, blossom contraction, blocking flows, push-relabel, scaling, the primal-dual method, randomisation, and certificate checking. The library has adaptors between different types of graphs (directed, undirected, multigraphs), which allow results to be reused. Each algorithm is verified independently of its data structures, and the main algorithms are refined to efficient imperative implementations, from which we generate code in Standard ML, Scala, and Go. We developed parts of the library with large language models (LLMs), improved the quality of their proofs with a method based on statistics of our own proofs, and labelled which parts were developed by humans, by LLMs, or collaboratively. We perform a detailed experimental analysis of representative algorithms in our library, comparing it with state-of-the-art mainstream libraries, showing that our implementations are practical.
Mohammad Abdulaziz, Thomas Ammer, Peter Lammich, and Adem Rimpapa
1 Introduction
Algorithms for combinatorial optimisation problems on graphs have influenced both the theory and the practice of computing. Theoretically, polynomial running time as the notion of efficient computation was proposed by Edmonds in his paper on matching in general graphs [27]. Practically, matching algorithms are used in kidney exchange programmes [17] and in allocating online advertisements [71], minimum-cost flow algorithms compute the cheapest way to transport goods [46], and shortest path algorithms are used in route planning [15], AI planning [19], and model checking [12]. Ensuring the correctness of implementations of these algorithms is difficult without formal verification, for two reasons.
First, their correctness arguments are mathematically involved, with many concepts and complicated constructions. Second, practical implementations employ low-level optimisations, e.g. storing graphs in the compressed sparse row (CSR) format and renumbering vertices to improve cache locality, whose correctness is hard to ensure within a large and complicated algorithm. We assume that the reader is familiar with common graph algorithms, otherwise we refer to standard literature [48, 78, 9, 85].
In this paper, we present practical formally verified (implementations of) algorithms in Isabelle/HOL [74] for most of the main combinatorial optimisation problems on graphs (Table 1). In particular: 1. we present a library of these implementations, from which we generate code in Standard ML, Scala, and Go [37, 82], 2. we describe the methodology underlying the library (§ 1), which extends that of Abdulaziz [2 Chapter 24] to substantially more involved algorithms, 3. we refine our algorithms to imperative implementations without a custom mechanism for non-determinism, which, as far as we are aware, is a first (§ 1.5), using a separation logic framework for Imperative HOL which we extended, e.g. with monadic folds and while-loops, 4. we report on developing parts of the library with large language models (LLMs) (Section 4): we label parts of the library as developed by humans, by an LLM, or collaboratively, and we restyle LLM-generated proofs using statistics of our own proofs, and 5. we evaluate the implementations of representative algorithms experimentally against LEMON [24], SciPy [84], NetworkX [83], JGraphT [72], and Sage [23] (Section 3).
| Algorithm | Proved | Lines |
| Reachability and cycle detection | ||
| Depth-first search [2] | T, C | 877 |
| Breadth-first search [2] | T, C | 1,805 |
| Cycle detection | T, C | 3,305 |
| Directed cycle detection | T, C | 697 |
| Shortest paths | ||
| BFS with distances | T, C | 2,901 |
| Bellman–Ford | C, O | 2,837 |
| Dijkstra | T, C, O | 2,865 |
| Maximum flow | ||
| Dinic | T, C, O | 1,455 |
| Blocking flow | T, C | 713 |
| DFS with backtracking | T, C | 746 |
| Push-relabel | T, C, O | 4,897 |
| Minimum-cost flow | ||
| Successive shortest paths [3] | T, C, O | 1,158 |
| Capacity scaling [3] | T, C, O | 1,785 |
| Orlin [3] | T, C, O | 12,080 |
| Network simplex | T, C, O | 7,582 |
| Acyclic flows | T, C | 10,691 |
| Spanning trees and matroids | ||
| Best-in-greedy [5] | T, C, A, O | 5,750 |
| Kruskal [5] | T, C, O | 1,559 |
| Greedoid greedy [5] | T, C, O | 2,217 |
| Jarník–Prim [5] | T, C, O | 1,277 |
| Matroid intersection [5] | T, C, O | 2,646 |
| Weighted matroid intersection | T, C, O | 5,274 |
| Matroid partitioning | C, O | 1,215 |
| Matching | ||
| Edmonds’ blossom [7] | T, C, O | 10,460 |
| Weighted blossom | C, O | 5,801 |
| Edmonds–Gallai decomposition | T, C | 5,007 |
| Hopcroft–Karp | T, C, O | 2,381 |
| Hungarian method [4] | T, C, O | 4,123 |
| Primal-dual (Egerváry) [4] | T, C, O | 1,863 |
| Online matching | ||
| RANKING [6] | A | 6,973 |
| RANKING, primal-dual [4] | A | 4,861 |
| AdWords [4] | C, A | 1,347 |
Table 1. The verified algorithms, grouped by the problems they solve. A citation marks an algorithm whose formalisation was published before; the formalisations of the other algorithms are new. Proved: termination (T), correctness (C), optimality (O), and approximation or competitive ratio (A). The Isabelle logo links to the main theorem in the formal development. Lines: the number of lines of the theories specific to the algorithm. Table 3 in Section A gives the details of the verification of every algorithm, and Table 38 in Section C shows which of them have abstract (i.e. non-executable), functional, and imperative versions. The library has about 300,000 lines of Isabelle/HOL.
Throughout the paper, the Isabelle logo and the Isabelle names in typewriter font link to the corresponding lines of our formal development (see the data availability statement).
Methodology
Our library uses Abdulaziz’s [2 Chapter 24] methodology for verifying graph algorithms: the abstract data type of graphs (specified as an Isabelle/HOL locale) and the mathematical representation of graphs as sets of edges (related to the abstract data type by an abstraction function) are both taken from that chapter. However, that chapter applies the methodology to depth-first search (DFS) and breadth-first search (BFS), while we apply it to a far larger set of algorithms [3, 5, 7, 4] whose verification is substantially more involved: our formalisation of minimum-cost flow algorithms [3], including Orlin’s algorithm, is 27,000 lines of Isabelle/HOL, that of Edmonds’ blossom algorithm [7] is about 10,000 lines, while the formalisations of DFS and BFS accompanying the chapter are about 800 and 1,500 lines, respectively.
Mathematical Models of Graphs and Reasoning Principles
An initial motivation for our library was that the Isabelle community has produced a large number of graph libraries, covering both theory and algorithms. Each of those libraries came with its own definitions of graphs and lemmas about them: in the Archive of Formal Proofs (AFP) alone, a graph is represented as a record of a vertex set, a set of arcs, and two functions mapping every arc to its tail and head [75], as a set of vertices together with a set of edges, each of which is a set of vertices [25], as a multiset of such edges [26], as a set of unordered vertex pairs [38], as a value of an abstract type of undirected graphs whose edges are given as pairs of vertices [63], and as a function mapping every pair of vertices to a capacity [64]. Every result in a given representation has to be proved again for every other representation. As we designed our library, we were aiming for results concerning graphs to be proved once and then reused by all the algorithms that need them.
Our library has two main representations, shown in Figure 1 along with the connections between them: directed graphs, i.e. sets of pairs of vertices [2 Chapter 24], and undirected graphs, i.e. sets of two-element sets of vertices [7]. Each of them has its own notions of walks, vwalk and awalk for directed graphs and walk_betw for undirected graphs. The two representations are connected by adaptors, which are theories relating the notions of one representation to those of the other, e.g. they relate paths, given as lists of vertices, of two distinct representations. For example, walk_betw_iff_vwalk_bet states that a walk in an undirected graph is a walk in the directed graph that has both orientations of every edge of , and vice versa. Thus, results proved for one representation can be used for the other. Multigraphs, whose edges have an abstract type, are an example of this reuse: a path in a multigraph, multigraph_path, is defined as a walk, awalk, over its edges mapped to vertex pairs by make_pair, so all lemmas about walks in directed graphs apply to multigraphs without being proved anew. Finally, adaptors to Noschinski’s library [75], which was developed independently of ours, prove that our definitions of arcs, reachability, walks, trails, paths, cycles, and decompositions of walks into cycles, (induced) subgraphs, connectivity, and strongly connected components of directed graphs agree with those of that library.

Figure 1. Representations of graphs in the library and the connections between them. Thick boxes are graph representations, the grey box is an external library from the AFP, plain boxes are ADTs, and dashed boxes are their implementations. Dashed double arrows are adaptors; dotted arrows are abstraction functions; solid arrows are locale imports or interpretations. Daggers mark ADTs and implementations that are only in development branches of the library. Table 4 in Section A describes the abstract data types.
Some theorems about graphs are proved by induction on the graph’s edge set. For example, component_has_path_distinct states that if every vertex of a finite graph has degree at most two, then every connected component of is the vertex set of a path without repeated vertices, and it is proved by induction on . The induction step has to know how the connected components change when an edge is added to , which is given by a case analysis in_insert_connected_componentE of Abdulaziz and Mehlhorn [7]: every connected component of the extended graph is a connected component of , the new component , the component of one endpoint extended by the other endpoint, or the union of the components of both endpoints.
The library has further reasoning principles of this kind for other concepts, none of which has been described before: (1) the same case analysis for walks, for reachability, for walks in directed graphs, and for the union of two graphs; (2) a lemma that splits reachability in the extended graph into reachability in to and from the endpoints of the new edge; (3) induction principles that build a walk one edge at a time, for walks in undirected graphs, for walks in directed graphs given as lists of vertices, extended at the start or at the end, or as lists of edges, and for paths in multigraphs; (4) induction on reachability in directed graphs, forwards from the source or backwards from the target; and (5) an induction principle that reduces a property of all walks between two vertices to the walks without repeated vertices by removing closed subwalks.
For proving algorithms correct, we need intricate graph-theoretic results, such as, for minimum-cost flows, a criterion for optimality and the preservation thereof, or Berge’s lemma for matchings. Although in this paper we clearly focus on the algorithmic side, note that our infrastructure allows formal proofs of deep graph-theoretic results that we do not use for proving algorithms correct, for example, the Tutte–Berge formula, or the Edmonds–Gallai decomposition [30, 31, 27].
Implementing Graphs
The algorithms do not operate on the mathematical representations of graphs directly, but on abstract data types (ADTs) of graphs [2 Chapter 24]. An ADT is a locale (§ 1.3) that fixes the operations of a data structure and an invariant on its values, and assumes the specification of these operations in terms of an abstraction function, which maps every value satisfying the invariant to one of the mathematical representations. For example, Pair_Graph_Specs combines a map ADT with an ADT of sets from which an element can be chosen, maps every vertex to its out-neighbourhood, and is related to directed graphs by digraph_abs. Accordingly, an algorithm is defined in terms of the ADT’s operations, and its proof uses the lemmas about the mathematical representation, which apply to the abstraction of the graph. Table 4 in Section A describes the graph ADTs of the library. The four ADTs in the main branch represent a graph as a map from every vertex to the set or list of its neighbours, which suits algorithms that look up and modify neighbourhoods, e.g. DFS and BFS. The ADTs in development branches represent multigraphs whose edges at a vertex are visited with a cursor, which suits algorithms that resume the scan of the edges of a vertex where an earlier scan stopped, e.g. Dijkstra’s algorithm.
| ADT | Graph; abstraction | Implementation | Costs | Reasons and users |
| Pair_Graph_Specs | Directed; vertex to set of out-neighbours; digraph_abs | Red-black trees | Looking up a neighbourhood, adding or deleting an edge: ; choosing a neighbour: | Purely functional; vertices of any linearly ordered type; e.g. depth-first and breadth-first search, Dinic’s algorithm, Prim’s algorithm |
| AVL trees | As for red-black trees | As for red-black trees; no algorithm in the main branch uses it | ||
| Pair_Graph_U_Specs | Undirected; both orientations of every edge; ugraph_abs | Red-black trees | As for Pair_Graph_Specs, with every edge added or deleted twice | Reuses the directed ADT and its lemmas; e.g. Kruskal’s algorithm |
| Adj_Map_Specs2 | Directed, over a map without deletion; digraph_abs | Red-black trees | Looking up a neighbourhood, adding an edge: | Requires no deletion from the map; the forest that Orlin’s algorithm maintains |
| Pair_Graph_Imperative | Directed, on the heap; vertex to list of out-neighbours; graph_assn | Array maps and lists | Looking up a neighbourhood: ; adding an edge: , since a neighbourhood is a list without duplicates | In-place updates; vertices must be numbers below a fixed bound; e.g. imperative depth-first search |
| Hash maps and lists | Looking up a neighbourhood: expected ; adding an edge: | In-place updates; vertices of any hashable type; e.g. imperative depth-first search | ||
| Multi_Graph_Specs† | Multigraph; vertex to set of its edges; multigraph_abs | Arrays (CSR) | Accessing the edges of a vertex: | Parallel edges; e.g. breadth-first search on multigraphs |
| indexed_iterable_set† | One set per index, e.g. per vertex, each with a cursor; idx_abstract | Arrays (CSR), csr_graph and, with weights, weighted_csr | Element and weight at a cursor, advancing or resetting a cursor: ; building the arrays: | A scan resumes where it stopped; the edges of a vertex are contiguous in memory, which is cache-efficient, but the graph cannot change; e.g. the Hungarian method |
| outgoing_edge_iterator, ingoing_edge_iterator† | Multigraph whose out- or in-edges at every vertex are an indexed_iterable_set; out_abstract, in_abstract | Arrays (CSR) | As for indexed_iterable_set | As for indexed_iterable_set; e.g. Dijkstra’s algorithm, the network simplex method |
Table 4. The graph ADTs of the library and their implementations. The costs are the standard bounds of the data structures, where is the number of vertices, the number of edges, and the degree of the vertex concerned; the library does not verify them. Daggers mark ADTs that are only in development branches of the library.
An implementation of an ADT is an interpretation of its locale with concrete operations, for which the locale assumptions have to be proved. The interpretation yields the definitions and theorems of every algorithm that is defined in terms of the ADT for these operations. The functional implementations use the red-black trees (RBTs) and AVL trees of the Isabelle/HOL distribution [2], both for the map from vertices to their neighbourhoods and for neighbourhoods themselves, e.g. the implementation of Pair_Graph_Specs with RBTs. The imperative implementations use the array maps or hash maps of the separation logic framework for Imperative HOL [61] for the map, and duplicate-free lists for the neighbourhoods. In development branches, the CSR representation stores the edges in one array sorted by their sources, together with an array of the positions at which the edges of every vertex begin and an array of cursors. The edges leaving a vertex are thus contiguous in memory, which makes scanning them cache-efficient, and advancing or resetting the cursor of a vertex takes constant time. Note that since the first two arrays are never modified, the CSR representation suits algorithms whose graph does not change.
Modelling Algorithms
The main mechanism we use to structure the library is Isabelle/HOL’s locales [14]. A locale is a named context that fixes a number of constants, the parameters of the locale, and states assumptions about them; definitions in the locale can refer to these constants, and theorems proved in the locale can use these assumptions. A locale can extend other locales with further constants and assumptions, and can later be instantiated by giving concrete values for its constants and proving its assumptions for these values. This yields instances of all the definitions and theorems of the locale for these values. We usually split locales modelling algorithms into a specification locale, which only fixes constants and their types, and a proof locale, which extends the former by the assumptions. For example, the specification locale multigraph_spec fixes an edge set , functions fst and snd returning an edge’s endpoints, and create_edge to construct an edge from two vertices. The proof locale multigraph assumes that is finite, that fst and snd return the vertices given to create_edge, etc. We split locales in this way because a specification locale has no assumptions and therefore admits a global interpretation for arbitrary values of its constants. Such a global interpretation is what Isabelle/HOL’s code generator needs to produce executable code from the locale definitions.
We model the algorithms following the methodology of Abdulaziz [2 Chapter 24], which was also used for the minimum-cost flow algorithms [3], the greedy and matroid intersection algorithms [5], and the Hungarian method [4]. The variables that change during a loop of an algorithm form its program state, which is modelled as a record with one field for each variable. The loop is modelled as a recursive function that maps a state to the state in which the loop stops. For instance, depth-first search, DFS, is a function on records of type DFS_state, whose fields are a stack, a set of visited vertices, and a return value. Termination is not proved when such a function is defined: instead, Isabelle/HOL’s function package [51] provides a domain predicate, e.g. DFS_dom, which holds for the states on which the function terminates, and we first prove the function partially correct for all states in its domain and only then prove that the states that satisfy the invariants are in the domain.
Locales are used in two ways when modelling algorithms. First, the data structures used by the algorithm are parameters of its locale, specified by the ADTs of § 1.2. Thus, the algorithm is defined and verified once and can be executed with every implementation of these ADTs. Second, a sub-procedure that the algorithm calls is a parameter of its locale, specified by assumptions that state what the sub-procedure computes, so that the algorithm can be verified before the sub-procedure is defined. For instance, the locale of the main loop of Edmonds’ blossom algorithm fixes a function that searches for an augmenting path and assumes that this function finds such a path whenever one exists and that every path it returns is augmenting. This is stepwise refinement [7]: the assumed sub-procedures are defined and verified in later steps, until no assumption is left that is not satisfied by a definition.
Table 1 states, for every algorithm in the library, which properties of it are proved and the size of the theories that verify it, and Table 3 in Section A also states whether its loops are modelled with the methodology of § 1.4, the number of invariants of its loops, and its main theorem.
| Algorithm | Pat. | Inv. | Proved | Main theorem | Lines |
| Graph search and shortest paths | |||||
| Depth-first search | ✓ | 5 | T, C | Finds a path from the source to the target iff one exists | 877 |
| Cycle detection | ✓ | 16 | T, C | Reports a cycle iff the graph has one | 3,305 |
| Directed cycle detection† | ✓ | 5 (1) | T, C | Reports a cycle iff the searched part has one | 697 |
| Breadth-first search | ✓ | 13 | T, C | Visits exactly the reachable vertices, along shortest paths | 1,805 |
| BFS with distances† | ✓ | 15 | T, C | Also computes distances and shortest-path parents | 2,901 |
| Bellman–Ford | − | 8 | C, O | Without negative cycles, computes shortest paths | 2,837 |
| Dijkstra† | ✓ | 14 | T, C, O | Computes shortest paths to the settled vertices | 2,865 |
| Greedy algorithms and spanning trees | |||||
| Best-in-greedy | ✓ | 4 | T, C, A, O | Rank-quotient approximation; optimal for all weights iff matroid | 5,750 |
| Kruskal | inst. | (4) | T, C, O | Computes a maximum-weight spanning forest | 1,559 |
| Greedoid greedy | − | 2 | T, C, O | Optimal for all modular weights iff strong exchange | 2,217 |
| Jarník–Prim | inst. | (2) | T, C, O | Computes a maximum-weight spanning tree | 1,277 |
| Flows | |||||
| Successive shortest paths | ✓ | 3 | T, C, O | Computes a minimum-cost flow or reports none | 1,158 |
| Capacity scaling | ✓ | 3 | T, C, O | As for successive shortest paths | 1,785 |
| Orlin | ✓ | 30 | T, C, O | As for successive shortest paths | 12,080 |
| Dinic | ✓ | 1 | T, C, O | Computes a maximum flow | 1,455 |
| Blocking flow | (✓) | 3 | T, C | Computes a blocking flow | 713 |
| DFS with backtracking | 5 | T, C | Removed edges lie on no source–target path | 746 | |
| Push-relabel† | ✓ | 7 | T, C, O | Computes a maximum flow | 4,897 |
| Network simplex† | ✓ | 7 | T, C, O | Minimum-cost flow or infinite negative cycle | 7,582 |
| Acyclic flows† | ✓ | 9 | T, C | Makes a flow acyclic, not raising its cost | 10,691 |
| Matchings | |||||
| Edmonds’ blossom | (✓) | 15 | T, C, O | Computes a maximum-cardinality matching | 10,460 |
| Weighted blossom† | (✓) | 11 | C, O | Min-weight perfect matching or reports none, if it terminates | 5,801 |
| Edmonds–Gallai decomposition† | − | 0 | T, C | Computes the decomposition from a maximum matching | 5,007 |
| Hopcroft–Karp† | ✓ | 7 | T, C, O | Computes a maximum-cardinality bipartite matching | 2,381 |
| Hungarian method | ✓ | 8 | T, C, O | Min-weight perfect matching or reports none | 4,123 |
| Primal-dual (Egerváry) | (✓) | 0 | T, C, O | Max-weight matching and an optimal dual | 1,863 |
| RANKING | − | 0 | A | Competitive ratio tending to | 6,973 |
| RANKING, primal-dual | − | 0 | A | Ratio , also vertex-weighted | 4,861 |
| AdWords | − | 0 | C, A | Ratio in terms of bids and budgets | 1,347 |
| Matroid intersection | |||||
| Matroid intersection | ✓ | 1 | T, C, O | Max-cardinality common independent set | 2,646 |
| Weighted matroid intersection† | ✓ | 1 | T, C, O | Max-weight common independent set | 5,274 |
| Matroid partitioning† | − | 0 | C, O | Optimal partition from a max-cardinality common independent set | 1,215 |
Table 3. Table 3. The verified algorithms. Pat.: loops are modelled as in Section 2.4 (✓), in part ((✓)), or not (−), or the algorithm is an instance of another one (inst.). Inv.: named invariants of the loops, without invariants of data structures; numbers in parentheses are inherited. Proved: termination (T), correctness (C), optimality (O), approximation or competitive ratio (A); running-time analyses are not included. Lines: theories specific to the algorithm, without running-time analyses, executable instances, refinements, as well as the abstract graph-theoretic reasoning. Daggers mark algorithms only in development branches. The Isabelle logo links to the main theorem in the formal development.
Proofs about Algorithms
The induction principle that the function package derives for a function modelling a loop contains the function’s entire control flow, making it hard to use in interactive proofs [2 Chapter 24]. Accordingly, for every execution path of the loop, we define a predicate stating that the path is taken and a function computing the state at the end of the path, e.g. DFS_call_1_conds and DFS_upd1 for the path that pushes an unvisited vertex onto the stack. From these definitions we prove three lemmas that characterise the function only in terms of its execution paths: (1) a case analysis, DFS_cases, stating that one of the paths is taken; (2) simplification rules, DFS_simps, stating the result of the function for each path; and (3) a computation induction principle, DFS_induct, whose induction step has one hypothesis for every recursive path, only mentioning the predicate and the update function of that path. For every path predicate, we also prove introduction and elimination rules, e.g. the elimination rule DFS_call_1_conds, which turns the predicate into the facts about the state that it implies.
Invariants are predicates on the state, and, instead of one comprehensive loop invariant, we state many separate invariants, e.g. sixteen for the search for alternating paths in Edmonds’ blossom algorithm [7], each of which is proved to be preserved assuming whatever other invariants are needed. Every invariant is first proved to be preserved by every recursive path, e.g. invar_1_holds_1, which is where the mathematical reasoning about the algorithm takes place and where the reasoning principles of § 1.1 are used. It is then lifted to the whole function by the computation induction principle, e.g. invar_1_holds. These two kinds of lemmas are combined by Isabelle/HOL’s classical reasoner and simplifier: we collect the introduction and elimination rules of the path predicates and of the invariants, and the preservation lemmas, in named collections of theorems.
They are given to the classical reasoner as introduction and elimination rules, so that e.g. the proof of invar_1_holds consists of the computation induction, the case analysis, and a single call of auto. Finally, termination is proved by a measure that decreases on every recursive path of a state that satisfies some of the invariants, and the correctness theorems, e.g. DFS_correct_1, follow from the invariants and the predicates of the paths on which the loop returns.
The loops of breadth-first search, the best-in-greedy algorithm, which yields Kruskal’s algorithm, successive shortest paths, capacity scaling, the two inner loops of Orlin’s algorithm, the Hungarian method, Dinic’s algorithm, and matroid intersection are verified in the same way, where each link points to the computation induction principle of the loop. However, Edmonds’ blossom algorithm, which was the first algorithm in the library, uses path predicates only in its search for alternating paths and reasons about its other loops with the induction principles that the function package derives.
Imperative Implementations
So far, we have described functional algorithms as locales parameterised over their data structures and operations. However, imperative implementations are much faster than functional ones: on the BFS benchmarks of § 2, the imperative export to SML is about two orders of magnitude faster than the functional one on the smallest grids, and about four orders of magnitude faster on the largest grids and on the road networks (Tables 9 and Table 12). One approach to verifying imperative code in Isabelle/HOL is Lammich’s Isabelle Refinement Framework [66] with its tool Sepref [57]. The Refinement Framework, however, requires the abstract algorithm to be stated in its non-determinism error monad. Accordingly, using it would require restating every algorithm of the library in that monad, and would give up a property of our methodology: an algorithm is a recursive function in a locale whose correctness is proved by induction. We favour this approach because reading or extending the library needs no vocabulary beyond what an average Isabelle/HOL user already knows. The problem we had to solve was thus to refine our algorithms to imperative implementations without changing the locale-based methodology. Note that the monad models non-determinism, e.g. choosing an arbitrary element from a set, and failure. We solve this problem with an intermediate functional implementation: we first instantiate the functional locale with a functional data structure, e.g. a list, which fixes the choices that the abstract algorithm leaves open, and we then refine this deterministic functional implementation to an imperative one.
| Network | SML imp. | SML func. | Scala imp. | Scala func. | Go imp. | Go func. | |
| NY | 264346 | 0.039 (1.00) | 854 (21644) | 0.761 (19.3) | TO | 4.95 (125) | TO |
| BAY | 321270 | 0.024 (1.00) | 1037 (42977) | 0.803 (33.3) | TO | 5.33 (221) | TO |
| COL | 435666 | 0.022 (1.00) | TO | 1.02 (45.8) | TO | 7.68 (346) | TO |
| FLA | 1070376 | 0.067 (1.00) | TO | 2.23 (33.3) | TO | 19.1 (285) | TO |
| NW | 1207945 | 0.075 (1.00) | TO | 2.39 (31.9) | TO | 19.9 (266) | TO |
| NE | 1524453 | 0.102 (1.00) | TO | 3.18 (31.3) | TO | OOM | TO |
| CAL | 1890815 | 0.138 (1.00) | TO | 3.85 (27.9) | TO | OOM | TO |
| LKS | 2758119 | 0.210 (1.00) | TO | 5.79 (27.5) | TO | OOM | TO |
| E | 3598623 | 0.358 (1.00) | TO | 7.51 (21.0) | TO | OOM | TO |
| W | 6262104 | 0.528 (1.00) | TO | 13.7 (25.9) | TO | OOM | TO |
| CTR | 14081816 | 1.36 (1.00) | TO | 34.2 (25.1) | TO | OOM | TO |
| USA | 23947347 | 1.85 (1.00) | TO | 56.8 (30.7) | TO | OOM | TO |
Table 12. Table 12. Breadth-first search, USA-road-t family [code 7] (, one network per size, 10 source-target pairs each, median of 3 repeats each).
We use the separation logic framework for partial correctness in Imperative HOL (SL-Framework for short), which we originally developed for total correctness and extended to partial correctness to implement a WebAssembly interpreter [87]. For this project, we improved its automation, added concepts such as monadic folds and while-loops, and proved that Hoare triples are admissible for fixed-point induction over recursive partial functions in the heap monad. We also reuse its library of imperative data structures.
Imperative HOL shallowly embeds imperative programs into a heap-error monad, from which Isabelle’s code generator produces actual imperative programs [20]. The SL-Framework adds a separation logic and a verification condition generator. Its central concept is the Hoare triple , with separation logic assertions and . It expresses partial correctness: if holds for the initial heap and returns without errors, then holds for the result and the final heap. An error means non-termination or a runtime failure, e.g. a failed bounds check.
Since we mainly verify an imperative implementation w.r.t. the functional one, all our assertions are refinement assertions. Such an assertion relates an abstract value to a concrete one that may refer to the heap. For example, is_iam m a states that points to an array on the heap that implements the map from natural numbers to values, the indices being the keys.
To refine a graph algorithm, we set up a locale that inherits from the algorithm’s functional locale and fixes imperative versions of its data structures and subroutines, assuming that they are correct. Thus, the functional locale refines abstract concepts such as sets and graphs to functional implementations, and the imperative locale refines these further to imperative ones.
In DFS, for instance, the open choice is the next successor to process, which the set ADT provides by a choice operation 🧩, and we implement vertex sets by distinct lists, which we refine differently depending on their use. Successor sets remain purely functional lists, as DFS only picks elements from them and iterates over them. The visited set, however, needs an efficient membership test, so we refine its list back to a set and then use any suitable imperative set implementation, e.g. bit-sets or hash-sets. We note that fixing an implementation, e.g. of sets using lists, is only a workaround.
Depending on the complexity of the algorithm and the intended flexibility, the imperative locale either partially instantiates the functional locale with functional data structures, or leaves all instantiations to the last step. In both cases, it is parameterised over the imperative implementations, which we choose when instantiating it. For DFS, for example, we generate one implementation with natural numbers as vertices and array-based maps and sets 🧩, and one based on hash maps and hash sets 🧩.
We define a refinement assertion for the state, typically as the product of the refinements of the state components. We then implement refinements of the functions of the functional version, i.e. some helpers and the main loop, and prove that they indeed refine their functional counterparts: on related arguments, they return related results. The loop is implemented as a partial function [50, 51] in Imperative HOL’s heap monad, and we prove by fixed-point induction that it refines the tail-recursive partial function of the functional version. For DFS, we prove 🧩 that, on implementations of a graph and a state, the imperative DFS leaves the graph unchanged and returns an implementation of the functional DFS’s result state. The proof is largely canonical: inside the induction, we unfold one step of the functional implementation and split it into its conditional branches; for each branch, we unfold the imperative implementation, eliminate its other branches, and prove the refinement with the verification condition generator. This step can be largely automated.
Finally, we combine both refinements into a Hoare triple stating that the imperative algorithm satisfies the abstract specification, again in a canonical and partially automated way. For example, from the result of the imperative DFS, we obtain a walk to the target or the absence of one.
Other Methodological Points
Algorithms on abstract structures. Some algorithms are verified on abstract combinatorial structures and then instantiated to graphs, so that one correctness proof serves several algorithms. For instance, Kruskal’s algorithm is an interpretation of the locale of the best-in-greedy algorithm on matroids, with the forests of the input graph as the independent sets, and maximum cardinality bipartite matching is computed by matroid intersection, where the independent sets of the two matroids are the sets of edges that share no vertex on the left and on the right side, respectively.
Verified algorithms as building blocks. Verified algorithms are also used as concrete sub-procedures of other algorithms, in contrast to the sub-procedures that are locale parameters (§ 1.3). For instance, the independence oracle of Kruskal’s algorithm runs the verified DFS to decide whether an edge closes a cycle in the current forest, and the proof of the oracle uses the correctness theorems of DFS.
Verified reductions. We verify reductions between problems, so that an algorithm for one problem solves another. For instance, we prove that every minimum-cost flow problem with capacities can be transformed into an uncapacitated one, such that flows of the two problems correspond, costs are preserved, and optimal flows are mapped to optimal flows. Accordingly, Orlin’s algorithm, which is verified for uncapacitated problems [3], also solves problems with capacities.
Shared optimality theorems. We prove the characterisations of optimal solutions separately from the algorithms and share them between algorithms, so that the proof of an algorithm only needs to show the condition of the characterisation. For instance, Berge’s lemma [16], i.e. that a matching has maximum cardinality if and only if there is no augmenting path, is used in the proofs of the blossom algorithm, the Hungarian method, and RANKING, and the characterisation of minimum-cost flows by the absence of augmenting cycles of negative cost is used in the proofs of successive shortest paths, capacity scaling, and Orlin’s algorithm.
Running-time analysis. We analyse running times in a locale that extends the locale of the algorithm with the costs of the ADT operations as parameters. It defines a function with the same recursion as the algorithm, which returns the time along with the result. For Orlin’s algorithm, we prove in such a locale that the time is bounded by a sum of products of the operation costs and terms in the number of vertices, and that the result is that of the algorithm 🧩. Accordingly, the algorithm and its correctness proof are not changed by the analysis.
Certification. In addition to verified algorithms, we use verified code to check, and if necessary to clean up, the output of an unverified solver, which is the approach of LEDA’s certifying algorithms [70], except that the checker itself is verified [11].
Empirical Evaluation
The library contains many verified implementations of graph algorithms and, given the space limitations, we focus on evaluating those for the main problems: 1. depth-first (DFS) and breadth-first search (BFS) for reachability, 2. Dijkstra’s algorithm for single-source shortest paths, 3. Kruskal’s algorithm [52] for minimum spanning forests, 4. push-relabel (PR) for maximum flow [34], 5. the Hungarian method (HM) [40, 53, 54] for minimum-weight perfect bipartite matching (minPBM), 6. (weighted) bipartite (-)matching, with matroid intersection (MI) [67, 29], and 7. hybrid solvers for minPBM and minimum-cost flows. Our focus is on running time: we compare the code exported from our verified implementations against unverified implementations in widely used graph libraries, such as SciPy (Cython), Sage and NetworkX [84, 23, 83] (Python), JGraphT [72] (Java), LEMON [24] (C++), which is widely recognised as one of the fastest graph libraries, and against reference solvers recommended for the DIMACS challenges, from which most of the problem families are also taken.
We export code to SML, Scala, and Go using Isabelle’s code generator [37] and its Go extension [82], which we extended to export Imperative HOL to Go. The exceptions are the hybrid solvers, whose verified part we export only to SML. We export to 32-bit integers (SML default) and compile SML with mlton with high inlining. We conduct the measurements on an AMD EPYC 7343 (Milan, Zen 3) with a timeout of 1200 s. The runs are scheduled to share the RAM but not the cache hierarchy. Because of the graphs’ sizes, we only take between 3 and 10 instances per size, run each instance 3 times, take the median for each instance, and average over all instances.
If a library can combine building data structures or graph representations with input file parsing, we count the respective time as parsing, which is excluded from the measurement. If the data representation has to be built separately from parsing, as in the case of our verified code, it is included in the measurement. Except for Kruskal’s algorithm, all our imperative implementations scan graphs by neighbourhoods, and we use the cache-efficient CSR representation. Despite the cost of CSR buildup being an additional , we generally use it since our implementations of simpler algorithms, which themselves are or close, are intended as repeatedly executed sub-procedures of more complex algorithms, which amortises the cost. Note the convention that denotes the number of vertices and denotes the number of edges in a graph.
We present plots (running time in seconds against the number of vertices on a log-log scale) and tables, with the latter in the appendix. Our code exports’ plots usually have the same slope, with the vertical shift accounting for the constant factor from language differences. SML beats Scala, which in turn beats Go, and imperative implementations beat functional ones by orders of magnitude (OoM). Imperative SML, which is always our best-performing variant and which we focus on, is plotted as •. Generally, the gap to the top-performing reference implementations (‘the libraries’) is much smaller for simple algorithms, probably because there is less room for heuristics and low-level optimisations.
DFS and BFS. We let the solvers explore all vertices reachable from a random source on three families of graphs. Figure 2 shows a performance difference of OoMs between imperative (with CSR) and purely functional (with RBTs) code exports. For DFS, we also include a semi-imperative export with an adjacency list representation, whose performance is in between but closer to CSR-based (RBT-based) on sparse (dense) graphs. For the libraries, we measure both with a native graph representation that can be built during parsing and with the more efficient CSRs. SciPy’s native representation is CSR, and here we have measurements with and without its buildup: the cost of buildup is clearly visible on dense graphs, where it is also asymptotically highest. Since the CSRs are only used once, CSR-based implementations of DFS and BFS generally perform worse in comparison to those where the representation is built during parsing. For sparse graphs, our imperative SML code with CSRs is on par with the libraries, and is within an OoM for the dense family. If the libraries are also charged with the cost of building CSRs, it seems that we can beat them by a small margin.

Figure 2. Fig. 2. ● SML CSR, ⊙ SML adjacency lists, ○ SML RBT, ■ Scala CSR, ◇ Scala adjacency lists, □ Scala RBT, ▲ Go CSR, ◆ Go adjacency lists, △ Go RBT, — LEMON CSR, * LEMON linked, ◆ JGraphT CSR, ◇ JGraphT hash, ◆ SciPy CSR, ◆ SciPy prebuilt, + NetworkX. PR: ● SML HL, ○ SML FIFO, ○ SML AFP, ◆ JGraphT, ◆ SciPy, × GC.
Dijkstra’s (DA) and Kruskal’s Algorithms (KA). Figure 2 shows that our SML is still within an OoM of the best library or narrows to it at scale. For DA, the difference is bigger for DFS and BFS, which we attribute to the higher implementation complexity of the algorithm, in particular to the priority queue. For KA, where we reuse an implementation of a union-find data structure by Stevens and Ghidini [81], our SML is also well within an OoM of the best library’s performance.
Push-Relabel (PR). Apart from the libraries, we evaluate our PR exports with highest-label (HL) and FIFO selection heuristics, an export of the older formalisation [65] (AFP) with FIFO, and Goldberg and Cherkassky’s implementation [21] (GC), which has been tuned for decades. SciPy does not offer PR, so we use its implementation of Dinic’s algorithm instead.
The algorithm has ample room for heuristics, e.g. all implementations use the gap heuristic [9, 21], and Figure 2 seemingly shows the effect: on RMF and WASH-RLG [43], JGraphT and NetworkX, both much slower for the simpler algorithms from above, beat (or start to beat at scale) both of our SML exports, which hit the timeout. In contrast to our implementation (and to LEMON), they offer an effective heuristic: BFS-based global relabelling (GL). Our two code exports offer HL and FIFO, of which HL is known to usually perform a bit better [9, 21]. GL seems to be good enough to compensate for JGraphT’s FIFO heuristic and the language difference. On RMF and WASH-RLG, we only beat the code export from the older formalisation [65]. The latter does not even work at larger sizes because of an overflow during the buildup of its memory-consuming
data structures (adjacency matrices). Our code performs asymptotically and in terms of OoM far worse than GC. By design, the AK family affects the gap heuristic [21], which interacts with GL [21], and GL seems to become much less effective, which might reduce LEMON’s disadvantage of lacking it. LEMON’s plot is parallel to those of our SML exports and two OoMs below them, which indicates a large constant factor.
We plan to add GL to our PR, leading to the combination of gap heuristic, GL and HL, which is known for its strong performance [21]. We expect a significant speedup since GL is seemingly able to make NetworkX, which is pure Python, beat compiled SML.
Hungarian method (HM). Our HM for minPBM is optimised for sparse graphs, and we borrow a few, but not all, practical optimisations from Jonker and Volgenant’s (JV) high-performing version [44]. We compare against SciPy’s JV for dense (LSA) and sparse adjacency matrices (MWFBM), JGraphT’s dense HM (KM) and sparse HM (MWBM), Goldberg and Kennedy’s CSA solver [32], and Google’s OR-Tools [76] (OR). The latter two implement cost-scaling algorithms. We use the families low-cost (LC), two-cost (TC), and geometric (GEO) [32].
In Figure 3, our HM in SML is within two OoMs of the best three solvers, and for TC, even within one, but the effect does not seem to scale for LC. We think that the smaller gap for TC is due to 1. more productive primal-dual adjustments because there are only two cost values, and 2. more scaling phases because one of the two costs is large. Our measurements for PR and HM confirm the higher difficulty of producing verified implementations of complex and heuristic-heavy algorithms, especially ones that are somewhat competitive with respected libraries that have often been tuned for decades.

Figure 3. SML, Scala, Go, SciPy LSA, SciPy MWFBM CSR, JGraphT KM, JGraphT MWBM CSR, JGraphT MWBM hash-backed, CSA CSR, OR-Tools, NetworkX wrapps Scipy, skipped. Sage (our oracle), Sage (plain).
Matroid Intersection (MI). Matroids are used to model -matching, in which every vertex can be matched up to times. The abstract algorithms obtain information about the concrete problem by oracles. One iteration of our MI takes oracle calls. We offer constant-time oracles to model bipartite matching as MI. Sage also offers unweighted and weighted MI in pure Python, though the weighted one uses a different algorithm. The pure algorithms also take oracle calls per iteration, and internal glue code adds a factor of . An oracle built from Sage’s primitives takes time, and our own customised one takes constant time, resulting in and per iteration, respectively. Bipartite matching as MI takes time, where is the time of one iteration and .
We benchmark the resulting solvers for (un-)weighted (-)matching on LC, TC, and GEO. Figure 3 shows the results (see Figure 6 in the appendix for more). The figures mostly seem to confirm the asymptotics. TC tends to be solved a bit faster than LC, which we attribute to the simpler weight structure. Unexpectedly, Sage instantiated with the faster Python oracle improves relatively for the dense GEO family, perhaps due to the weight variance. Usually, SML beats the fast Python implementation by OoMs, but for weighted matching on GEO, they are on par and SML times out for the biggest instance. However, for weighted -matching … matching (see Figure 6 in the appendix), SML changes little and Sage falls behind, which must be the effect of allowing multiple matching edges per vertex.

Figure 6. Matroid Intersection, matching, -matching and weighted -matching; on matching and -matching, LC and TC share their instances (LC/TC): SML, Scala, Go, Sage (our oracle), Sage (plain).
Hybrid Solvers. We offer certificate checking for minimum-cost flows (MCF) and weighted bipartite matching (WBM). In combination with the verified network simplex and HM, respectively, we build hybrid solvers that first let an unverified program (‘oracle’) solve the problem and generate a certificate. If the verified checker rejects the certificate, we use our verified network simplex or HM, respectively, to solve the problem. In contrast to HM, the network simplex can be warm-started, i.e. it is initialised with the unverified solver’s rejected solution. Both checkers examine a simple property of every edge, in time.
For example, by extending implementations of different algorithms from LEMON with certificate generation, we obtain four oracles for MCFs from which the user can select. The cost ratio of verification (CV) is, for the fastest oracle, the ratio between the total CPU time (which includes certificate generation and checking) and the time of the oracle’s initialisation and main loop. Table 2 shows the results. On netgen_deg, where for fixed the density grows up to , the CV increases up to 3.69. Since both oracle and checker have to deal with bigger graphs, a roughly constant CV would be expected, or even a decreasing one since no oracle’s running time is linear. These are worst-case running times, however, and we believe the CV increases because, as the graph grows, for a fixed increase in the checker’s time, the oracle has the same or better chances to route the flow. For growth in and moderate or no growth in density (netgen_lo_sr and road_paths), the CV decreases as expected. We benchmark on 18 families, and 3.69 is the highest CV that we measured for any family and size.
| Family | Size | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 12 | ||
| netgen_deg | , | 1.18 | 1.24 | 1.28 | 1.31 | 1.50 | 1.68 | 1.88 | 2.23 | 2.61 | 3.69 | ||
| netgen_lo_sr | , | 3.17 | 3.34 | 3.40 | 2.94 | 2.96 | 2.38 | 2.22 | 1.89 | 1.80 | |||
| road_paths | , | 1.91 | 1.63 | 1.40 | 1.22 | 1.29 | 1.16 | ||||||
| LC | , | 1.72 | 1.68 | 1.61 | 1.62 | 1.65 | 1.64 | 1.51 | 1.26 | ||||
| TC | , | 1.18 | 1.16 | 1.16 | 1.16 | 1.18 | 1.18 | 1.10 | 1.05 | ||||
| GEO | , | 2.21 | 2.35 | 2.43 | 2.36 | 2.13 | 1.97 | 1.69 |
Table 2. CV derived from Table 30, Table 31, Table 32, Table 35, Table 36, Table 37 in the appendix.
| deg | Alg. | Oracle | Cert. | Check | Glue | Total | Total/Oracle | |
| 2 | 8192 | NS | 7.79 | 0.021 | 0.649 | 0.697 | 9.15 | 1.18 |
| COS | 20.7 | 0.119 | 0.696 | 0.946 | 22.5 | 1.08 | ||
| CAS | 103 | 0.081 | 0.674 | 0.965 | 105 | 1.02 | ||
| SSP | 123 | 0.084 | 0.675 | 0.961 | 125 | 1.01 | ||
| 4 | 16384 | NS | 10.9 | 0.048 | 1.61 | 1.00 | 13.5 | 1.24 |
| COS | 19.3 | 0.244 | 1.72 | 1.42 | 22.7 | 1.18 | ||
| CAS | 286 | 0.198 | 1.62 | 1.47 | 290 | 1.01 | ||
| SSP | 212 | 0.195 | 1.63 | 1.46 | 215 | 1.01 | ||
| 8 | 32768 | NS | 16.8 | 0.198 | 2.10 | 2.43 | 21.6 | 1.28 |
| COS | 26.8 | 0.434 | 2.36 | 3.45 | 33.0 | 1.23 | ||
| CAS | 972 | 0.377 | 2.09 | 3.46 | 978 | 1.01 | ||
| SSP | 537 | 0.370 | 2.12 | 3.46 | 543 | 1.01 | ||
| 16 | 65536 | NS | 24.0 | 0.330 | 4.07 | 3.06 | 31.0 | 1.31 |
| COS | 38.0 | 0.803 | 4.62 | 4.80 | 48.0 | 1.27 | ||
| CAS | 3843 | 0.802 | 4.06 | 4.14 | 3852 | 1.00 | ||
| SSP | 911 | 0.720 | 4.06 | 4.76 | 921 | 1.01 | ||
| 32 | 131072 | NS | 36.0 | 0.628 | 11.5 | 6.03 | 54.0 | 1.50 |
| COS | 56.0 | 1.45 | 12.7 | 9.38 | 79.0 | 1.42 | ||
| CAS | 8854 | 1.26 | 11.5 | 10.2 | 8877 | 1.00 | ||
| SSP | 1265 | 1.12 | 11.5 | 9.39 | 1287 | 1.02 | ||
| 64 | 262144 | NS | 52.0 | 1.21 | 22.7 | 11.7 | 88.0 | 1.68 |
| COS | 94.0 | 2.67 | 25.1 | 19.3 | 141 | 1.50 | ||
| CAS | 23755 | 2.40 | 22.8 | 18.8 | 23799 | 1.00 | ||
| SSP | 1910 | 1.94 | 22.8 | 19.3 | 1954 | 1.02 | ||
| 128 | 524288 | NS | 84.0 | 2.29 | 45.3 | 26.6 | 158 | 1.88 |
| COS | 191 | 4.46 | 49.6 | 38.4 | 283 | 1.49 | ||
| CAS | 75297 | 4.21 | 45.5 | 41.3 | 75388 | 1.00 | ||
| SSP | 3335 | 3.43 | 45.2 | 40.4 | 3424 | 1.03 | ||
| 256 | 1048576 | NS | 123 | 4.20 | 89.8 | 56.9 | 274 | 2.23 |
| COS | 409 | 8.52 | 99.4 | 83.8 | 601 | 1.47 | ||
| CAS | 281740 | 8.03 | 91.1 | 90.9 | 281930 | 1.00 | ||
| SSP | 4564 | 6.09 | 89.8 | 84.1 | 4744 | 1.04 | ||
| 512 | 2097152 | NS | 190 | 8.44 | 181 | 117 | 495 | 2.61 |
| COS | 1058 | 16.0 | 197 | 182 | 1453 | 1.37 | ||
| CAS | 924820 | 15.7 | 182 | 192 | 925210 | 1.00 | ||
| SSP | 7854 | 12.7 | 179 | 186 | 8231 | 1.05 | ||
| 1024 | 4194304 | NS | 339 | 15.8 | 358 | 243 | 956 | 2.82 |
| COS | 2309 | 32.1 | 396 | 408 | 3146 | 1.36 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | 13945 | 26.2 | 357 | 390 | 14718 | 1.05 | ||
| 8388608 | NS | 575 | 29.6 | 716 | 512 | 1833 | 3.19 | |
| COS | 5100 | 56.4 | 797 | 828 | 6782 | 1.33 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | 26008 | 48.8 | 709 | 807 | 27572 | 1.06 | ||
| 16252992 | NS | 916 | 53.5 | 1489 | 919 | 3378 | 3.69 | |
| COS | 10320 | 110 | 1638 | 1501 | 13569 | 1.31 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | 51289 | 115 | 1522 | 1585 | 54511 | 1.06 |
Table 30. Hybrid min-cost flow solver, netgen_deg [code 21] family generated by [47]. A density sweep by increasing degrees at the fixed node count . The first column is the average in-degree which is equal to the out-degree and the density.
| Alg. | Oracle | Cert. | Check | Glue | Total | Total/Oracle | ||
| 256 | 4096 | NS | 0.266 | 0.010 | 0.279 | 0.287 | 0.842 | 3.17 |
| COS | 0.936 | 0.022 | 0.324 | 0.393 | 1.68 | 1.79 | ||
| CAS | 0.635 | 0.017 | 0.279 | 0.405 | 1.34 | 2.10 | ||
| SSP | 0.792 | 0.017 | 0.284 | 0.398 | 1.49 | 1.88 | ||
| 512 | 11585 | NS | 0.696 | 0.015 | 1.04 | 0.576 | 2.33 | 3.34 |
| COS | 2.60 | 0.069 | 1.16 | 0.893 | 4.72 | 1.82 | ||
| CAS | 2.09 | 0.025 | 1.04 | 0.903 | 4.06 | 1.94 | ||
| SSP | 3.11 | 0.025 | 1.03 | 0.895 | 5.06 | 1.63 | ||
| 1024 | 32768 | NS | 1.87 | 0.163 | 2.84 | 1.50 | 6.37 | 3.40 |
| COS | 7.13 | 0.337 | 3.14 | 2.35 | 13.0 | 1.82 | ||
| CAS | 7.01 | 0.244 | 2.86 | 2.42 | 12.5 | 1.79 | ||
| SSP | 10.3 | 0.248 | 2.82 | 2.37 | 15.7 | 1.53 | ||
| 92682 | NS | 6.21 | 0.352 | 7.85 | 3.84 | 18.2 | 2.94 | |
| COS | 20.4 | 0.900 | 8.70 | 6.43 | 36.4 | 1.79 | ||
| CAS | 27.7 | 0.702 | 7.89 | 6.71 | 43.0 | 1.55 | ||
| SSP | 40.0 | 0.715 | 7.95 | 6.68 | 55.3 | 1.38 | ||
| 262144 | NS | 17.8 | 1.01 | 22.5 | 11.6 | 52.9 | 2.96 | |
| COS | 62.5 | 2.65 | 25.0 | 18.8 | 109 | 1.74 | ||
| CAS | 86.5 | 1.94 | 22.6 | 19.1 | 130 | 1.50 | ||
| SSP | 145 | 1.92 | 22.5 | 19.0 | 188 | 1.30 | ||
| 741455 | NS | 58.7 | 3.06 | 43.1 | 34.7 | 140 | 2.38 | |
| COS | 203 | 6.08 | 50.2 | 57.3 | 317 | 1.56 | ||
| CAS | 278 | 4.54 | 43.1 | 59.5 | 386 | 1.39 | ||
| SSP | 562 | 4.82 | 43.2 | 60.6 | 671 | 1.19 | ||
| 2097152 | NS | 203 | 8.52 | 123 | 117 | 450 | 2.22 | |
| COS | 822 | 16.7 | 142 | 187 | 1168 | 1.42 | ||
| CAS | 1081 | 11.4 | 124 | 194 | 1411 | 1.30 | ||
| SSP | 2104 | 12.9 | 122 | 198 | 2437 | 1.16 | ||
| 5931642 | NS | 754 | 20.8 | 354 | 298 | 1427 | 1.89 | |
| COS | 2832 | 44.3 | 409 | 566 | 3851 | 1.36 | ||
| CAS | 3539 | 30.9 | 353 | 597 | 4520 | 1.28 | ||
| SSP | 7417 | 33.6 | 353 | 594 | 8397 | 1.13 | ||
| 16777216 | NS | 2822 | 54.0 | 1102 | 1102 | 5080 | 1.80 | |
| COS | 9482 | 114 | 1267 | 1731 | 12594 | 1.33 | ||
| CAS | 12679 | 104 | 1106 | 1886 | 15775 | 1.24 | ||
| SSP | 27502 | 109 | 1106 | 1899 | 30616 | 1.11 |
Table 31. Hybrid min-cost flow solver, netgen_lo_sr [code 23] family generated by NETGEN [47]. A node sweep at the density .
| Instance | Alg. | Oracle | Cert. | Check | Glue | Total | Total/Oracle | |||
| 01_DC | 9559 | 29768 | 3.11 | NS | 15.2 | 0.165 | 2.09 | 1.85 | 19.3 | 1.27 |
| COS | 31.0 | 0.415 | 2.24 | 2.54 | 36.2 | 1.17 | ||||
| CAS | 4.75 | 0.164 | 2.08 | 2.66 | 9.65 | 2.03 | ||||
| SSP | 4.73 | 0.174 | 2.08 | 2.69 | 9.67 | 2.05 | ||||
| 02_DE | 49109 | 120576 | 2.46 | NS | 143 | 1.23 | 9.11 | 8.05 | 162 | 1.13 |
| COS | 239 | 2.25 | 9.27 | 10.7 | 261 | 1.09 | ||||
| CAS | 23.2 | 0.634 | 8.63 | 11.8 | 44.3 | 1.91 | ||||
| SSP | 23.2 | 0.617 | 8.83 | 11.6 | 44.3 | 1.91 | ||||
| 03_NH | 116920 | 265402 | 2.27 | NS | 678 | 2.28 | 19.2 | 17.9 | 718 | 1.06 |
| COS | 845 | 4.13 | 20.6 | 24.1 | 894 | 1.06 | ||||
| CAS | 76.7 | 1.47 | 19.3 | 27.3 | 125 | 1.63 | ||||
| SSP | 76.9 | 1.45 | 19.2 | 26.9 | 124 | 1.62 | ||||
| 04_NV | 261155 | 620924 | 2.38 | NS | 2854 | 4.53 | 45.6 | 40.9 | 2945 | 1.03 |
| COS | 3339 | 8.91 | 49.0 | 58.0 | 3455 | 1.03 | ||||
| CAS | 280 | 2.98 | 46.0 | 63.6 | 393 | 1.40 | ||||
| SSP | 279 | 2.92 | 45.3 | 63.5 | 391 | 1.40 | ||||
| 05_WI | 519157 | 1266876 | 2.44 | NS | 9150 | 10.7 | 96.2 | 87.1 | 9344 | 1.02 |
| COS | 8859 | 19.8 | 103 | 122 | 9104 | 1.03 | ||||
| CAS | 1121 | 6.27 | 96.7 | 144 | 1368 | 1.22 | ||||
| SSP | 1116 | 5.74 | 96.6 | 142 | 1360 | 1.22 | ||||
| 06_FL | 1048506 | 2653624 | 2.53 | NS | TO | TO | TO | TO | TO | TO |
| COS | TO | TO | TO | TO | TO | TO | ||||
| CAS | 1842 | 12.5 | 211 | 309 | 2375 | 1.29 | ||||
| SSP | 1859 | 11.4 | 212 | 302 | 2384 | 1.28 | ||||
| 07_TX | 2073870 | 5156088 | 2.49 | NS | TO | TO | TO | TO | TO | TO |
| COS | TO | TO | TO | TO | TO | TO | ||||
| CAS | 6688 | 21.4 | 427 | 590 | 7727 | 1.16 | ||||
| SSP | 6665 | 24.2 | 425 | 609 | 7723 | 1.16 |
Table 32. Hybrid min-cost flow solver, road_paths [code 25] family on the road networks of [22]. US state road network (real data). The first column lists the instances, ordered by increasing number of nodes .
| Oracle | Cert. | Check | Glue | Total | Total/Oracle | ||
| 22528 | 4.89 | 0.116 | 0.041 | 0.745 | 5.79 | 1.18 | |
| 49152 | 12.2 | 0.248 | 0.092 | 1.63 | 14.2 | 1.16 | |
| 106496 | 27.5 | 0.583 | 0.198 | 3.65 | 31.9 | 1.16 | |
| 229376 | 65.6 | 1.73 | 0.471 | 8.15 | 76.0 | 1.16 | |
| 491520 | 150 | 5.23 | 1.49 | 20.3 | 177 | 1.18 | |
| 1048576 | 356 | 14.9 | 3.96 | 43.4 | 418 | 1.18 | |
| 2228224 | 1438 | 37.0 | 9.47 | 94.3 | 1579 | 1.10 | |
| 4718592 | 4362 | 114 | 22.9 | 200 | 4699 | 1.08 | |
| 9961472 | 10805 | 264 | 49.7 | 431 | 11550 | 1.07 | |
| 20971520 | 31019 | 552 | 102 | 956 | 32630 | 1.05 |
Table 36. Hybrid bipartite matching solver with CSA [code 9] as oracle, two-cost family [code 4] (10 instances per size, averaged over the medians of 3 repeats per instance). A node sweep at the density .
| Oracle | Cert. | Check | Glue | Total | Total/Oracle | ||
| 256 | 0.545 | 0.061 | 0.023 | 0.577 | 1.21 | 2.21 | |
| 512 | 2.09 | 0.410 | 0.090 | 2.31 | 4.90 | 2.35 | |
| 1024 | 8.63 | 0.749 | 0.352 | 11.2 | 21.0 | 2.43 | |
| 44.2 | 4.53 | 1.83 | 53.9 | 104 | 2.36 | ||
| 258 | 45.0 | 6.97 | 241 | 551 | 2.13 | ||
| 1348 | 171 | 34.6 | 1101 | 2654 | 1.97 | ||
| 6990 | 641 | 193 | 4000 | 11824 | 1.69 |
Table 37. Hybrid bipartite matching solver with CSA [code 9] as oracle, geometric family [code 5] (10 instances per size, averaged over the medians of 3 repeats per instance). A node sweep on complete bipartite graphs, .
Table 2 also gives the CV of the hybrid solver for minPBM that combines the CSA solver [32] with our verified certificate checker. We use the same families as for HM, in which the graphs grow in both and , and observe the same behaviour as for netgen_lo_sr and road_paths: the CV decreases at scale. For LC and TC, the certificate checker does the same amount of work, but since CSA does worse on TC, the CV is smaller. On the dense GEO family, the CV is much higher since the greater density increases the checker’s relative work.
Hybrid solvers perform almost by design well within an OoM of unverified ones but we cannot reduce the CV to 1. They are still practical, especially for dense instances, where a fully verified but slower main loop would hurt most.
AI-Assisted Development
Our verification methodology developed on a small number of algorithms: the graph representation and modelling loops as tail-recursive functions for the blossom algorithm [7], and the graph ADTs, the invariant reasoning, and the imperative refinement for depth- and breadth-first search [2]; it was then refined for minimum-cost flows [3], algorithms for matroids and greedoids [5], and primal-dual algorithms [4]. Our initial intention behind this methodology was pedagogical, e.g. using basic Isabelle/HOL formalisms like locales and recursive functions, instead of complex formalisms like non-determinism monads. It turns out that, according to our experience, LLM-generated algorithms and specifications, when done according to this methodology, are easier to read and to review than what an LLM would output by default. This mitigates the well-documented difficulty of ensuring that LLM-generated definitions, code, and theorem statements are aligned with the user’s request [90, 8, 69]. We used two methods to improve this alignment, one for definitions and specifications, and one for proofs.
The first method is standard: the LLM works in phases, and we review its design and implementation decisions, in the form of an LLM-generated plan, before it implements them [42, 13, 41, 80]. At that stage, we remove the most obvious flaws, e.g. wrong definitions or specifications, reinvented definitions, lemmas that are not reused, and deviations from our formalisation idioms.
For proofs, alignment is less a matter of correctness than of readability. This matters e.g. to understand the correctness argument when one wants to further improve an algorithm. Since in our library proofs are more than eight times as long as the definitions and specifications, reviewing all LLM-generated proofs is infeasible. Instead, we compute a statistical signature of our own proofs, e.g. the share of calls to automated Isabelle proof methods, such as auto, among all proof steps, and prompt the LLM to restyle its already working proofs towards that signature, since LLMs write verbose proofs with many low-level steps [36, 10]. For instance, in the LLM-generated proofs of the Hopcroft-Karp algorithm, auto accounts for 10.7% of the proof method calls, against 61.2% and 50.7% in our proofs of depth- and breadth-first search, and 38.0% of the lemmas have a single-step automated proof, against 76.5% and 63.1%; after restyling, 69.2% of Hopcroft-Karp’s proofs have a single-step proof (Table 39 in Section C.1). To our knowledge, this is the first use of a statistical signature of one’s own verified proofs to guide the restyling of LLM-generated proofs.
| Statistic | DFS | BFS | Before | After |
| Size | ||||
| Proof lines | 323 | 1041 | 1342 | 1055 |
| Definition and specification lines | 355 | 552 | 472 | 917 |
| Lemmas | 81 | 103 | 108 | 182 |
| of which loop-template lemmas | 65 | 83 | 3 | 92 |
| Proof form (share of lemmas) | ||||
| Single-step proofs | 76.5% | 63.1% | 38.0% | 69.2% |
| Structured (proof . . . qed) | 21.0% | 27.2% | 61.1% | 27.5% |
| With apply | 2.5% | 9.7% | 0.0% | 3.3% |
| Proof length (non-blank lines) | ||||
| Median | 1 | 2 | 8 | 2 |
| Mean | 3.7 | 9.9 | 12.0 | 5.6 |
| 90th percentile | 8 | 31 | 30 | 15 |
| Proof lines per statement line | 1.50 | 3.15 | 4.43 | 2.02 |
| Steps per structured proof | 2.4 | 8.4 | 8.7 | 4.1 |
| Handling of facts (per lemma) | ||||
| Labelled have/show/obtain | 0.01 | 0.21 | 2.29 | 0.12 |
| [OF ...] | 0.26 | 0.61 | 2.10 | 0.74 |
| using | 0.44 | 1.66 | 3.10 | 0.79 |
| Facts quoted as cartouches | 0.07 | 1.64 | 0.02 | 0.19 |
| Named assumptions | 0.00 | 0.00 | 0.51 | 0.00 |
| Proof methods (share of all method calls) | ||||
| auto | 61.2% | 50.7% | 10.7% | 40.2% |
| force + fastforce | 9.3% | 12.4% | 0.4% | 1.9% |
| simp | 2.2% | 4.3% | 29.0% | 11.6% |
| rule | 10.1% | 7.5% | 23.8% | 13.8% |
| metis + smt | 0.0% | 4.1% | 0.0% | 0.0% |
| Closing calls inside structured proofs | ||||
| by (rule ...) | 2.6% | 1.0% | 25.9% | 14.2% |
| Bare by simp/auto/blast/... | 20.5% | 21.6% | 46.4% | 34.7% |
| Method modifiers (per lemma) | ||||
| elim!: | 0.38 | 0.50 | 0.00 | 0.14 |
| intro!: | 0.46 | 0.49 | 0.00 | 0.16 |
| Statements | ||||
| Plain form [\[A; B\]] \Longrightarrow C | 79.0% | 77.7% | 57.4% | 79.1% |
| [[ per statement | 0.69 | 0.79 | 0.00 | 0.34 |
| Lemmas with an attribute | 80.2% | 67.0% | 6.5% | 45.6% |
| Layout | ||||
| by opening its own line | 100% | 95.0% | 16.8% | 100% |
| using opening its own line | 100% | 99.4% | 34.9% | 100% |
| proof-/proof( (no space) | 4/15 | 15/43 | 0/0 | 30/28 |
| proof -/proof ( (space) | 0/0 | 0/0 | 41/52 | 0/0 |
| Line length, 95th percentile | 119 | 117 | 99 | 104 |
| Definitions and program state | ||||
| State records | 1 | 1 | 0 | 2 |
| Loops as function (domintros) over one record | 1 | 1 | 0 | 2 |
| Loops written as fun | 0 | 0 | 1 | 0 |
| Executable twins (partial_function) | 1 | 1 | 1 | 2 |
| named_theorems declared | 9 | 9 | 0 | 14 |
| Untyped definitions | 22/22 | 23/23 | 24/26 | 50/50 |
| Invariants | ||||
| invar_* definitions | 5 | 13 | 0 | 8 |
| Complete families (elim., intro., per branch, loop) | 5 | 7 | 0 | 8 |
| Uses of [invar_holds_intros] | 26 | 33 | 0 | 33 |
| Naming | ||||
| Mean lemma-name length (characters) | 18.2 | 22.1 | 14.2 | 22.8 |
| Mean lemma-name parts | 4.0 | 4.5 | 3.0 | 4.0 |
| Constants with the prefix hk_ | – | – | 11 | 0 |
| Global abbreviations named with characters | 0 | 0 | 9 | 0 |
| Layering | ||||
| Interpretations in algorithm theories (global/plain) | 0/0 | 0/0 | 2/3 | 0/0 |
| Interpretations in the sub-procedure theory (global/plain) | – | 0/0 | – | 4/3a |
| Interpretations in the example theory (global/plain) | 1/0 | 2/0 | 1/1 | 1/1 |
| sublocale commands | 0 | 0 | 0 | 0 |
| Algorithm theories importing concrete data structures | 0 | 0 | 1 | 0 |
| Locales with qualified data-structure parents | 1 | 1 | 0 | 2 |
| Sub-procedure contracts in the definitions locale | – | yes | no | yes |
Table 39. All in Hopcroft_Karp_Subprocedures, a recorded deviation: the phase is implemented there at the concrete operations, since the alternating BFS and the incremental DFS of the Micali–Vazirani development are used through their concrete instances. Table 39. Style statistics of the depth- and breadth-first search theories (the ground truth) and of the Hopcroft–Karp theories before and after the restyling.
In addition to alignment, another concern we had related to using LLMs to generate proofs was attribution. We label parts of theory files at the lowest granularity we believe is practical: we label sections of Isabelle/HOL files as developed by humans, ‘collaboratively’ with an LLM, or by an LLM. We label a part as collaborative, e.g. if a human prompted the LLM in detail on how to formalise a concept, revised it, or manually formalised parts of it. Parts labelled as produced by an LLM alone are mostly auxiliary lemmas and low-level proofs. Counting the lines labelled that way, more than 55% of the lines of the library were developed purely by humans (Table 38 in Section C). This granularity gives data for further studies of the formalisation styles of LLMs and humans, something which we plan to do in the future.
| Algorithm | Abstract | Functional | Imperative |
| Graph search and shortest paths | |||
| Depth-first search | − | ✗ | (✓CSR version only) |
| Cycle detection | − | ✗ | − |
| Directed cycle detection | ✓ | ✓ | ✓ |
| Breadth-first search | − | ✗ | ✗ |
| BFS with distances | − | ✗ | − |
| Bellman–Ford | − | ✗ | − |
| Dijkstra | − | ✓ | ✓ |
| Greedy algorithms and spanning trees | |||
| Best-in-greedy | − | ✗ | ✓ |
| Kruskal | − | ✗ | ✓ |
| Greedoid greedy | − | ✗ | − |
| Jarník–Prim | − | ✗ | − |
| Flows | |||
| DFS with backtracking | − | ✗ | − |
| Blocking flow | − | ✗ | − |
| Dinic | − | ✗ | − |
| Push-relabel | − | ✓ | ✓ |
| Successive shortest paths | ✗ | − | − |
| Capacity scaling | ✗ | − | − |
| Orlin | − | ✗ | − |
| Acyclic flows | − | ✓ | ✓ |
| Network simplex | − | ✓ | ✓ |
| Matchings | |||
| Edmonds’ blossom | ✗ | ✓ | ✓ |
| Hopcroft–Karp | − | ✓ | ✓ |
| Hungarian method | − | ✗(shortcut ✓) | ✓ |
| Primal-dual (Egerváry) | ✗ | − | − |
| RANKING | ✗ | − | − |
| RANKING, primal-dual | ✗ | − | − |
| AdWords | ✗ | − | − |
| Matroids | |||
| Matroid intersection | − | ✗ | ✓ |
| Weighted matroid intersection | − | ✓ | ✓ |
| Matroid partitioning | ✓ | − | − |
Table 38. The parts of each algorithm that were developed or verified using AI. ✓means AI contribution, ✗only human contributors, and − signifies that this variant of the algorithm is not present. Readers can obtain a more fine-grained understanding of the extent of AI contribution by reading through the theory scripts, which have labels indicating human/human-AI/AI contributions.
Discussion
Graph libraries. In unverified graph libraries, such as LEDA [70], LEMON [24], Boost [79], and JGraphT [72], algorithms are written against an interface of graph operations and work with any implementation of that interface. Our ADT locales have the same role, and every interface has a specification, against which the correctness of every algorithm that uses it is proved. Algorithms in LEDA return the solution alongside a certificate that a simple checker program tests, which moves the trust to the checker, which can itself be wrong [11]. The graph library for Isabelle/HOL by Noschinski [75] and the graph theory in Lean’s mathlib [1] formalise the mathematical theory of graphs without executable algorithms. Verification, on the other hand, has mostly been applied to one or a small family of algorithms at a time, each development with its own graph theory and representation, e.g. the Ford–Fulkerson method in Mizar [68], various graph algorithms in Isabelle/HOL [65, 38, 62], and C implementations in Coq [73]. In contrast, all algorithms in our library are stated in terms of the same few representations, which are connected by adaptors (§ 1.1).
Refinement. Obtaining efficient verified implementations by stepwise refinement [88] and data refinement [39] is an established approach in Isabelle/HOL. Its most developed instance is Lammich’s Isabelle Refinement Framework [66, 55], which was used for graph algorithms, too [65, 38]. Our approach differs: 1. instead of a nondeterministic monad, we write algorithms purely functionally, 2. instead of automated data refinement to the Isabelle Collections Framework [59, 60], we apply data refinement by locale interpretations [14], and 3. the resulting functional implementation is the intermediate step from which the imperative implementation is refined (§ 1.5). Our functional implementations have to be deterministic, but we can state them as ordinary recursive functions and conduct proofs in the style of textbooks on verified functional algorithms [2]. Alternatively, others verify the low-level code that is actually run, either directly, e.g. C implementations of graph algorithms [73], or by abstracting C programs to higher-level specifications [77, 35].
LLM-based development of formal libraries. Theorem proving with LLMs has mostly been studied as proving individual theorems against a fixed library, using a variety of techniques [28, 41, 89, 86, 80, 91, 69]. Developing a library aided by AI is a different task, since much of the work is in choosing definitions, representations, and the statements of lemmas so that later developments can reuse them, and none of these choices is checked by the proof checker. In our development (§ 3), this is where the decisions of the LLM had to be reviewed, and the methodology of § 1 gave that review a fixed reference: a definition, a specification, or a proof that does not follow its idioms is easy to identify.
The restyling of LLM-generated proofs in § 3 is related to recent work on automated proof optimisation. ImProver [10] and ProofOptimizer [36] optimise Lean proofs that already check w.r.t. a single criterion, e.g. length. Our guideline is derived from a statistical signature of our own verified proofs, and the aim of the restyling is that the LLM-generated proofs match the style of those proofs, rather than that they minimise one measure. Measuring style is not new [18], but to our knowledge, it has not previously been used to guide or to evaluate LLM-generated proofs.
Conclusion. We presented a library of formally verified graph algorithms in Isabelle/HOL. For simple algorithms, we are within an order of magnitude of standard libraries such as SciPy [84] or LEMON [24], or even on par, whereas for more complex algorithms, which come with much more room for heuristics and tuning, it is harder as our code is sometimes two orders of magnitude slower. We plan to add more optimisations, which come with more low-level details, but the effort should be greatly reduced by AI. Keeping the library’s style, especially maintaining the abstraction barriers, is a challenge. Also, some of the complex implementations in the libraries we benchmarked against have been tuned for decades, whereas we started including efficient code less than a year ago.
The algorithms share one methodology, so that a lemma or a data structure developed for one algorithm is available to the others. The methodology also allowed us to develop about a third of the library collaboratively with LLMs while still being able to review what they produced. Directions for future work include: 1. proving running-time bounds for all algorithms of the library in the model of § 1.6, as we did for Orlin’s algorithm, and relating them to a concrete model of computation using our framework [45], and 2. refining the imperative implementations further to LLVM [56, 58].
Data Availability
Our formal development, the style guideline that we gave to the LLM when it restyled its proofs, the two scripts that compute the style statistics of Table 39 from the theory sources (Section C.1), and the scripts of our experiments are archived at https://doi.org/10.5281/zenodo.23805452. The library is developed further at https://github.com/mabdula/Isabelle-Graph-Library. The links to the formal development in this paper point to the version of the library in this repository that has the tag tacas27-artefact: https://github.com/mabdula/Isabelle-Graph-Library/tree/tacas27-artefact.
Verified Algorithms and Graph Data Types
Table 3 gives the details of the verification of the algorithms of Table 1, and Table 4 describes the graph ADTs of § 1.2.
Running Times
Tables 5 to 8 give the running times for depth-first search, Tables 9 to 12 those for breadth-first search, Tables 13 to 15 those for Dijkstra’s algorithm, Tables 16 to 18 those for Kruskal’s algorithm, Tables 19 to 21 those for push-relabel, Tables 22 to 24 those for the Hungarian method and Tables 25 to 28 those for matroid intersection. Each row is an instance size (a network in the road tables) and each column a solver.
An entry is the mean CPU time in seconds of the solver call over the instances of that size, where <0.001 is a mean below a millisecond. Next to it (below it in all but the matroid intersection tables), in parentheses, is that mean normalised by SML (by SML CSR in the DFS tables, by the imperative SML export in the BFS tables, by SML HL in the push-relabel tables), i.e. divided by the SML mean for the same size, so SML’s own ratio is (1.00) and a value below 1 means the solver was faster than SML. A superscript marks a mean over only the of instances that finished. TO means that no instance finished within 1200 s (larger sizes were then not run), OOM that the solver ran out of memory. OVF means that the AFP export’s integer index overflowed, n/a that the instances violate its precondition of no antiparallel arcs, and (–) that the SML mean is 0 or missing, so no ratio can be given.
Measurements in Java and Scala are done after a dummy call to the solver enforcing a JVM warm-up.
For each instance family, the table captions cite its generator or its instance files online. We use the settings prescribed by the DIMACS challenges. The only exception is the dense- family Tables 7, 11 and 18, whose random graphs come from our own instantiation of a DIMACS generator [code 6]: connect all vertices in the order of a random permutation to ensure strong connectivity. Then, for times, we randomly draw an edge, retry if a self-loop is drawn, and insert the resulting random edge into the graph. For a number of vertices , we set arcs, so the average degree grows from 64 at to 2048 at . Weights are between 0 and .
For BFS and DFS, whose graphs come with weights, the weights are ignored. We select a source randomly and explore all reachable vertices. For Dijkstra’s algorithm, we select a source randomly and search for a randomly selected target. The only exception is SciPy, which by its functionality explores the whole graph. For the reachability problems, a graph with a source and, if applicable, a target constitutes a problem instance. All solvers were given the same instance, i.e. the selected sources (and targets) are consistent among columns.
For Kruskal’s algorithm, which reuses the graphs for path search, we treat edges as undirected and the parser always picks the minimum-weight edge between two vertices.
The tables for the hybrid solvers, Tables 29 to 33 for minimum-cost flows and Tables 35 to 37 for weighted bipartite matching, use a different measurement methodology, which is described with them below.
| SML CSR | SML lists | SML RBT | Scala CSR | Scala lists | Scala RBT | Go CSR | Go lists | Go RBT | |
| 1024 | 0.0001 (1.00) | 0.0001 (1.16) | 0.011 (87.5) | 0.011 (88.1) | 0.008 (67.4) | 0.080 (653) | 0.023 (190) | 0.012 (94.9) | 0.039 (320) |
| 2025 | 0.0001 (1.00) | 0.0003 (2.58) | 0.026 (244) | 0.020 (181) | 0.016 (150) | 0.128 (1187) | 0.044 (408) | 0.022 (200) | 0.085 (791) |
| 4096 | 0.0002 (1.00) | 0.0006 (2.59) | 0.059 (273) | 0.040 (186) | 0.035 (160) | 0.201 (925) | 0.107 (494) | 0.047 (218) | 0.202 (929) |
| 8190 | 0.0004 (1.00) | 0.001 (2.55) | 0.118 (262) | 0.075 (168) | 0.079 (176) | 0.297 (660) | 0.235 (523) | 0.102 (226) | 0.446 (992) |
| 16384 | 0.001 (1.00) | 0.002 (2.43) | 0.326 (326) | 0.151 (150) | 0.152 (151) | 0.501 (500) | 0.548 (547) | 0.218 (217) | 1.04 (1037) |
| 32761 | 0.003 (1.00) | 0.005 (2.02) | 0.721 (286) | 0.294 (117) | 0.179 (71.0) | 0.912 (362) | 1.23 (487) | 0.466 (185) | 2.45 (973) |
| 65536 | 0.006 (1.00) | 0.013 (2.16) | 1.75 (301) | 0.458 (78.8) | 0.281 (48.4) | 1.95 (336) | 2.63 (453) | 1.01 (174) | 5.58 (961) |
| 131044 | 0.013 (1.00) | 0.054 (4.12) | 3.70 (284) | 0.758 (58.2) | 0.536 (41.2) | 4.00 (307) | 5.49 (421) | 2.15 (165) | 12.4 (951) |
| 262144 | 0.028 (1.00) | 0.075 (2.70) | 8.11 (293) | 1.32 (47.9) | 0.900 (32.6) | 9.03 (327) | 10.9 (396) | 4.52 (163) | 27.7 (1003) |
| 524176 | 0.061 (1.00) | 0.169 (2.75) | 17.9 (292) | 2.50 (40.8) | 1.72 (28.0) | 21.1 (344) | 21.7 (354) | 9.78 (160) | 60.5 (987) |
| 1048576 | 0.184 (1.00) | 1.42 (7.72) | 43.8 (238) | 4.98 (27.0) | 3.56 (19.3) | 49.1 (266) | OOM | 20.4 (110) | OOM |
| 2096704 | 0.729 (1.00) | 1.11 (1.53) | 101 (138) | 10.9 (15.0) | 7.27 (9.98) | 111 (152) | OOM | OOM | OOM |
| LEMON CSR [code 38] | LEMON linked [code 38] | JGraphT CSR [code 29] | JGraphT hash [code 29] | SciPy CSR [code 55] | SciPy prebuilt [code 55] | NetworkX [code 44] | |||
| 1024 | 0.0002 (1.27) | 0.0000 (0.29) | 0.0009 (7.72) | 0.001 (10.1) | 0.0004 (3.52) | 0.0001 (1.05) | 0.0006 (4.85) | ||
| 2025 | 0.0001 (1.27) | 0.0001 (0.60) | 0.002 (16.3) | 0.003 (27.3) | 0.0005 (4.81) | 0.0002 (1.42) | 0.001 (11.3) | ||
| 4096 | 0.0003 (1.30) | 0.0001 (0.62) | 0.004 (17.1) | 0.008 (34.6) | 0.0007 (3.22) | 0.0002 (1.00) | 0.003 (11.6) | ||
| 8190 | 0.0006 (1.29) | 0.0003 (0.63) | 0.008 (17.8) | 0.021 (47.9) | 0.001 (2.43) | 0.0003 (0.76) | 0.005 (11.8) | ||
| 16384 | 0.001 (1.24) | 0.0007 (0.67) | 0.019 (19.4) | 0.054 (54.1) | 0.002 (2.18) | 0.0008 (0.84) | 0.011 (10.9) | ||
| 32761 | 0.003 (1.09) | 0.001 (0.53) | 0.041 (16.1) | 0.096 (38.2) | 0.004 (1.73) | 0.002 (0.74) | 0.055 (21.9) | ||
| 65536 | 0.006 (1.03) | 0.003 (0.55) | 0.107 (18.4) | 0.141 (24.3) | 0.011 (1.82) | 0.004 (0.74) | 0.213 (36.7) | ||
| 131044 | 0.015 (1.13) | 0.007 (0.52) | 0.370 (28.4) | 0.305 (23.4) | 0.019 (1.47) | 0.009 (0.66) | 0.605 (46.4) | ||
| 262144 | 0.034 (1.21) | 0.021 (0.74) | 0.937 (33.9) | 0.946 (34.2) | 0.037 (1.34) | 0.015 (0.55) | 1.54 (55.8) | ||
| 524176 | 0.078 (1.27) | 0.058 (0.95) | 2.49 (40.7) | 2.37 (38.7) | 0.076 (1.24) | 0.040 (0.66) | 3.74 (61.0) | ||
| 1048576 | 0.203 (1.10) | 0.152 (0.83) | 5.71 (30.9) | 6.40 (34.7) | 0.156 (0.84) | 0.076 (0.41) | 7.78 (42.2) | ||
| 2096704 | 0.705 (0.97) | 0.472 (0.65) | 15.2 (20.8) | 18.0 (24.7) | 0.551 (0.76) | 0.331 (0.45) | 16.3 (22.3) |
Table 5. Depth-first search, Square-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| SML CSR | SML lists | SML RBT | Scala CSR | Scala lists | Scala RBT | Go CSR | Go lists | Go RBT | |
| 1024 | 0.0001 (1.00) | 0.0001 (2.49) | 0.023 (397) | 0.010 (182) | 0.007 (126) | 0.077 (1346) | 0.022 (387) | 0.012 (206) | 0.039 (680) |
| 0.0001 (1.00) | 0.0003 (2.54) | 0.025 (232) | 0.020 (180) | 0.016 (148) | 0.130 (1197) | 0.044 (407) | 0.022 (201) | 0.087 (802) | |
| 0.0002 (1.00) | 0.0005 (2.52) | 0.056 (257) | 0.038 (176) | 0.035 (160) | 0.190 (877) | 0.102 (472) | 0.047 (217) | 0.196 (905) | |
| 0.0004 (1.00) | 0.001 (2.57) | 0.111 (251) | 0.070 (158) | 0.076 (172) | 0.293 (663) | 0.236 (535) | 0.101 (227) | 0.439 (992) | |
| 0.0010 (1.00) | 0.002 (2.37) | 0.312 (313) | 0.150 (151) | 0.146 (147) | 0.493 (494) | 0.543 (544) | 0.216 (216) | 1.01 (1011) | |
| 0.002 (1.00) | 0.005 (2.11) | 0.684 (284) | 0.296 (123) | 0.179 (74.2) | 0.888 (369) | 1.21 (501) | 0.458 (190) | 2.31 (959) | |
| 0.006 (1.00) | 0.013 (2.22) | 1.66 (293) | 0.450 (79.3) | 0.265 (46.7) | 1.93 (340) | 2.56 (452) | 0.976 (172) | 5.44 (959) | |
| 0.013 (1.00) | 0.051 (4.05) | 3.64 (288) | 0.741 (58.7) | 0.513 (40.6) | 3.87 (307) | 5.34 (423) | 2.10 (167) | 12.2 (964) | |
| 0.027 (1.00) | 0.072 (2.71) | 8.08 (305) | 1.29 (48.7) | 0.827 (31.2) | 8.80 (332) | 10.6 (401) | 4.39 (166) | 26.6 (1005) | |
| 0.059 (1.00) | 0.173 (2.94) | 19.5 (331) | 2.48 (42.2) | 1.64 (27.9) | 20.0 (341) | 21.5 (367) | 9.52 (162) | 59.3 (1010) | |
| 0.169 (1.00) | 1.39 (8.19) | 38.3 (226) | 4.81 (28.4) | 3.33 (19.7) | 47.5 (281) | OOM | 19.7 (116) | OOM | |
| 0.708 (1.00) | 1.04 (1.47) | 98.3 (139) | 10.9 (15.4) | 6.97 (9.85) | 108 (152) | OOM | OOM | OOM |
Table 6. Table 6. Depth-first search, Long-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| LEMON CSR [code 38] | LEMON linked [code 38] | JGraphT [code 29] | JGraphT hash [code 29] | SciPy CSR [code 55] | SciPy prebuilt [code 55] | NetworkX [code 44] | |
| 1024 | 0.0001 (1.25) | 0.0000 (0.82) | 0.001 (17.9) | 0.001 (26.0) | 0.0005 (9.04) | 0.0001 (2.40) | 0.0006 (10.5) |
| 0.0001 (1.27) | 0.0001 (0.59) | 0.002 (20.5) | 0.005 (44.5) | 0.0006 (5.66) | 0.0002 (1.43) | 0.001 (11.5) | |
| 0.0003 (1.29) | 0.0001 (0.59) | 0.006 (26.2) | 0.014 (63.8) | 0.0007 (3.25) | 0.0002 (0.98) | 0.003 (11.6) | |
| 0.0006 (1.29) | 0.0003 (0.67) | 0.017 (38.0) | 0.055 (123) | 0.001 (2.54) | 0.0003 (0.78) | 0.005 (11.9) | |
| 0.001 (1.23) | 0.0006 (0.65) | 0.058 (57.7) | 0.100 (101) | 0.002 (2.12) | 0.0008 (0.79) | 0.011 (11.1) | |
| 0.003 (1.12) | 0.001 (0.59) | 0.199 (82.7) | 0.311 (129) | 0.005 (1.88) | 0.002 (0.75) | 0.049 (20.4) | |
| 0.006 (1.05) | 0.003 (0.59) | 1.06 (187) | 1.36 (240) | 0.010 (1.71) | 0.004 (0.74) | 0.203 (35.8) | |
| 0.014 (1.12) | 0.007 (0.52) | 4.56 (362) | 5.88 (466) | 0.019 (1.53) | 0.009 (0.69) | 0.488 (38.7) | |
| 0.034 (1.30) | 0.019 (0.71) | 19.5 (735) | 22.4 (846) | 0.036 (1.36) | 0.016 (0.59) | 1.21 (45.8) | |
| 0.101 (1.72) | 0.064 (1.09) | 74.5 (1268) | 83.7 (1424) | 0.074 (1.26) | 0.037 (0.62) | 2.91 (49.5) | |
| 0.246 (1.45) | 0.170 (1.00) | 296 (1746) | 373 (2202) | 0.158 (0.93) | 0.079 (0.46) | 6.53 (38.6) | |
| 0.616 (0.87) | 0.513 (0.72) | TO | TO | 0.550 (0.78) | 0.356 (0.50) | 15.0 (21.2) |
Table 6.

Figure 4. DFS: filled marks are exports over CSR arrays, half-filled marks those over adjacency lists, hollow marks those over red-black trees. SML CSR, SML lists, SML RBT, Scala CSR, Scala lists, Scala RBT, Go CSR, Go lists, Go RBT, LEMON CSR, LEMON linked, JGraphT CSR, JGraphT hash, SciPy CSR, SciPy prebuilt, NetworkX.
| SML CSR | SML lists | SML RBT | Scala CSR | Scala lists | Scala RBT | Go CSR | Go lists | Go RBT | |
| 1024 | 0.0006 (1.00) | 0.025 (39.9) | 0.399 (635) | 0.135 (215) | 0.180 (286) | 0.365 (581) | 0.496 (790) | 0.205 (327) | 0.716 (1140) |
| 0.003 (1.00) | 0.234 (89.2) | 1.47 (560) | 0.432 (165) | 0.913 (349) | 1.42 (540) | 2.37 (904) | 1.17 (447) | 3.96 (1512) | |
| 0.011 (1.00) | 3.56 (330) | 8.15 (757) | 1.08 (100) | 8.86 (823) | 8.62 (800) | 9.55 (887) | 8.51 (790) | 21.4 (1983) | |
| 0.048 (1.00) | 90.6 (1876) | 39.9 (826) | 3.79 (78.5) | 119 (2462) | 51.6 (1068) | OOM | 133 (2757) | 110 (2282) | |
| 0.335 (1.00) | 923 (2751) | 210 (626) | 17.3 (51.5) | TO | 281 (837) | OOM | OOM | OOM | |
| 1.40 (1.00) | TO | (812) | OOM | TO | TO | OOM | OOM | OOM |
| LEMON CSR [code 38] | LEMON linked [code 38] | JGraphT CSR [code 29] | JGraphT hash [code 29] | SciPy CSR [code 55] | SciPy prebuilt [code 55] | NetworkX [code 44] | |
| 1024 | 0.0008 (1.33) | 0.0008 (1.29) | 0.036 (56.9) | 0.050 (80.0) | 0.004 (6.88) | 0.0003 (0.45) | 0.003 (4.12) |
| 0.003 (1.28) | 0.004 (1.54) | 0.191 (73.0) | 0.196 (74.7) | 0.011 (4.21) | 0.001 (0.48) | 0.010 (3.85) | |
| 0.019 (1.79) | 0.024 (2.21) | 1.57 (146) | 1.90 (177) | 0.040 (3.70) | 0.003 (0.26) | 0.269 (24.9) | |
| 0.082 (1.71) | 0.379 (7.84) | 10.6 (220) | 14.1 (292) | 0.178 (3.68) | 0.014 (0.30) | 1.30 (27.0) | |
| 0.375 (1.12) | 2.69 (8.03) | 77.7 (232) | 155 (464) | 0.749 (2.23) | 0.040 (0.12) | 3.54 (10.6) | |
| 1.28 (0.92) | 12.3 (8.79) | 647 (464) | TO | 3.21 (2.30) | 0.159 (0.11) | 26.3 (18.8) |
Table 7. Depth-first search, dense connected rand. family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance). The instances are those of Table 11.
| Network | SML CSR | SML lists | SML RBT | Scala CSR | Scala lists | Scala RBT | Go CSR | Go lists | Go RBT | LEMON CSR [code 38] | LEMON linked [code 38] | JGraphT CSR [code 29] | JGraphT hash [code 29] | SciPy CSR [code 55] | SciPy prebuilt [code 55] | NetworkX [code 44] | |
| NY | 264346 | 0.025 (1.00) | 0.063 (2.48) | 5.27 (208) | 0.887 (35.0) | 0.586 (23.1) | 4.32 (171) | 7.66 (302) | 3.65 (144) | 19.7 (780) | 0.020 (0.79) | 0.013 (0.52) | 0.392 (15.5) | 0.455 (18.0) | 0.024 (0.94) | 0.010 (0.38) | 0.440 (17.4) |
| BAY | 321270 | 0.023 (1.00) | 0.072 (3.08) | 6.07 (260) | 0.967 (41.4) | 0.657 (28.2) | 5.09 (218) | 8.44 (362) | 4.42 (189) | 23.0 (985) | 0.026 (1.10) | 0.018 (0.77) | 0.353 (15.1) | 0.437 (18.7) | 0.026 (1.13) | 0.011 (0.47) | 0.526 (22.6) |
| COL | 435666 | 0.022 (1.00) | 0.112 (5.14) | 8.18 (374) | 1.21 (55.4) | 0.758 (34.7) | 6.95 (318) | 11.4 (521) | 5.77 (264) | 31.7 (1449) | 0.039 (1.80) | 0.024 (1.08) | 0.419 (19.2) | 0.656 (30.0) | 0.036 (1.65) | 0.017 (0.80) | 0.739 (33.8) |
| FLA | 1070376 | 0.057 (1.00) | 0.271 (4.72) | 22.1 (385) | 2.78 (48.4) | 1.55 (27.0) | 19.3 (337) | 28.9 (504) | 15.2 (265) | OOM | 0.089 (1.54) | 0.099 (1.73) | 1.40 (24.4) | 1.54 (26.8) | 0.093 (1.61) | 0.045 (0.78) | 1.81 (31.6) |
| NW | 1207945 | 0.064 (1.00) | 0.254 (3.95) | 24.8 (386) | 3.00 (46.7) | 1.52 (23.7) | 22.2 (345) | 30.5 (474) | 14.8 (230) | OOM | 0.110 (1.71) | 0.130 (2.01) | 1.70 (26.4) | 1.85 (28.7) | 0.103 (1.60) | 0.051 (0.79) | 1.62 (25.2) |
| NE | 1524453 | 0.099 (1.00) | 1.12 (11.4) | 31.9 (324) | 3.98 (40.4) | 1.99 (20.2) | 30.1 (306) | OOM | OOM | OOM | 0.145 (1.47) | 0.158 (1.60) | 4.34 (44.1) | 4.74 (48.1) | 0.136 (1.38) | 0.064 (0.65) | 2.76 (28.1) |
| CAL | 1890815 | 0.145 (1.00) | 1.14 (7.87) | 41.8 (290) | 5.16 (35.7) | 2.50 (17.3) | 38.1 (263) | OOM | OOM | OOM | 0.168 (1.16) | 0.232 (1.60) | 4.45 (30.8) | 4.58 (31.7) | 0.188 (1.30) | 0.092 (0.64) | 3.43 (23.7) |
| LKS | 2758119 | 0.214 (1.00) | 1.48 (6.93) | 60.2 (281) | 7.36 (34.4) | 3.78 (17.6) | 56.7 (265) | OOM | OOM | OOM | 0.257 (1.20) | 0.266 (1.24) | 8.17 (38.1) | 7.76 (36.2) | 0.276 (1.29) | 0.140 (0.65) | 5.32 (24.8) |
| E | 3598623 | 0.346 (1.00) | 0.882 (2.55) | 83.9 (242) | 9.40 (27.1) | 5.00 (14.4) | 77.0 (222) | OOM | OOM | OOM | 0.377 (1.09) | 0.382 (1.10) | 11.1 (31.9) | 15.5 (44.9) | 0.369 (1.06) | 0.198 (0.57) | 7.01 (20.2) |
| W | 6262104 | 0.469 (1.00) | 1.50 (3.19) | 151 (321) | 17.3 (36.9) | 8.53 (18.2) | 139 (296) | OOM | OOM | OOM | 0.652 (1.39) | 0.601 (1.28) | 20.3 (43.3) | 20.4 (43.4) | 0.627 (1.34) | 0.341 (0.73) | 11.9 (25.4) |
| CTR | 14081816 | 1.42 (1.00) | 3.87 (2.73) | 425 (299) | 45.3 (31.9) | 21.7 (15.3) | 425 (299) | OOM | OOM | OOM | 1.92 (1.35) | 1.55 (1.09) | 95.6 (67.3) | 185 (131) | 1.86 (1.31) | 1.09 (0.77) | 33.1 (23.3) |
| USA | 23947347 | 2.24 (1.00) | 7.39 (3.30) | 643 (287) | 78.8 (35.2) | 33.2 (14.8) | 605 (270) | OOM | OOM | OOM | 2.44 (1.09) | 2.72 (1.21) | 239 (107) | 331 (148) | 2.51 (1.12) | 1.49 (0.66) | 48.2 (21.5) |
Table 8. Table 8. Depth-first search, USA-road-t family [code 7] (2.35 2.78, one network per size, 10 sources each, median of 3 repeats each).
| SML imp. | SML func. | Scala imp. | Scala func. | Go imp. | Go func. | |
| 1024 | 0.0001 (1.00) | 0.019 (174) | 0.010 (90.8) | 0.234 (2085) | 0.027 (241) | 0.145 (1293) |
| 2025 | 0.0001 (1.00) | 0.064 (605) | 0.019 (178) | 0.473 (4462) | 0.033 (310) | 0.376 (3547) |
| 4096 | 0.0002 (1.00) | 0.230 (1105) | 0.037 (178) | 1.12 (5384) | 0.076 (366) | 1.47 (7045) |
| 8190 | 0.0004 (1.00) | 0.808 (1980) | 0.067 (164) | 3.68 (9023) | 0.174 (426) | 5.76 (14126) |
| 16384 | 0.0009 (1.00) | 3.15 (3592) | 0.134 (153) | 16.5 (18794) | 0.375 (428) | 22.7 (25969) |
| 32761 | 0.002 (1.00) | 12.3 (6453) | 0.264 (138) | 78.3 (41005) | 0.836 (438) | 92.5 (48419) |
| 65536 | 0.004 (1.00) | 53.2 (12532) | 0.421 (99.1) | 501 (118038) | 1.78 (420) | 577 (135887) |
| 131044 | 0.010 (1.00) | 200 (20687) | 0.639 (66.3) | TO | 3.71 (384) | TO |
| 262144 | 0.020 (1.00) | TO | 1.06 (52.6) | TO | 7.58 (377) | TO |
| 524176 | 0.049 (1.00) | TO | 2.03 (41.8) | TO | 15.1 (310) | TO |
| 1048576 | 0.125 (1.00) | TO | 3.91 (31.3) | TO | OOM | TO |
| 2096704 | 0.452 (1.00) | TO | 8.46 (18.7) | TO | OOM | TO |
Table 9. Breadth-first search, Square-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| LEMON CSR [code 35] | LEMON linked [code 35] | JGraphT CSR [code 28] | JGraphT hash [code 28] | SciPy CSR [code 54] | SciPy prebuilt [code 54] | NetworkX [code 43] | |
| 1024 | 0.0001 (1.24) | 0.0000 (0.23) | 0.0008 (6.82) | 0.0007 (6.01) | 0.0005 (4.50) | 0.0002 (1.45) | 0.001 (9.05) |
| 2025 | 0.0001 (1.16) | 0.0000 (0.35) | 0.001 (12.5) | 0.001 (12.9) | 0.0005 (4.66) | 0.0001 (1.26) | 0.001 (10.3) |
| 4096 | 0.0003 (1.21) | 0.0001 (0.40) | 0.003 (13.6) | 0.003 (16.1) | 0.0008 (3.62) | 0.0002 (0.88) | 0.002 (10.6) |
| 8190 | 0.0005 (1.28) | 0.0002 (0.46) | 0.006 (14.4) | 0.008 (18.6) | 0.0010 (2.35) | 0.0003 (0.61) | 0.005 (11.1) |
| 16384 | 0.001 (1.21) | 0.0004 (0.45) | 0.012 (14.2) | 0.021 (24.0) | 0.002 (2.21) | 0.0006 (0.69) | 0.009 (10.5) |
| 32761 | 0.002 (1.20) | 0.0010 (0.50) | 0.023 (11.9) | 0.046 (24.0) | 0.004 (2.05) | 0.001 (0.61) | 0.023 (11.9) |
| 65536 | 0.005 (1.15) | 0.002 (0.43) | 0.054 (12.6) | 0.071 (16.6) | 0.009 (2.17) | 0.003 (0.62) | 0.056 (13.1) |
| 131044 | 0.013 (1.30) | 0.004 (0.42) | 0.226 (23.4) | 0.127 (13.1) | 0.017 (1.74) | 0.005 (0.56) | 0.144 (15.0) |
| 262144 | 0.029 (1.47) | 0.018 (0.92) | 0.511 (25.5) | 0.460 (22.9) | 0.031 (1.55) | 0.009 (0.42) | 0.354 (17.6) |
| 524176 | 0.064 (1.32) | 0.040 (0.82) | 1.32 (27.3) | 0.854 (17.6) | 0.058 (1.20) | 0.021 (0.43) | 1.55 (32.0) |
| 1048576 | 0.152 (1.22) | 0.095 (0.76) | 3.11 (24.8) | 1.74 (13.9) | 0.118 (0.94) | 0.034 (0.28) | 2.49 (19.9) |
| 2096704 | 0.449 (0.99) | 0.331 (0.73) | 6.62 (14.6) | 3.64 (8.06) | 0.346 (0.77) | 0.134 (0.30) | 7.28 (16.1) |
Table 9 (PDF p. 34). Breadth-first search, Square-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| SML imp. | SML func. | Scala imp. | Scala func. | Go imp. | Go func. | |
| 1024 | 0.0001 (1.00) | 0.019 (371) | 0.010 (195) | 0.239 (4588) | 0.039 (743) | 0.104 (2000) |
| 0.0001 (1.00) | 0.063 (599) | 0.020 (185) | 0.438 (4136) | 0.033 (316) | 0.382 (3603) | |
| 0.0002 (1.00) | 0.226 (1126) | 0.037 (186) | 1.14 (5691) | 0.076 (380) | 1.44 (7140) | |
| 0.0004 (1.00) | 0.793 (1992) | 0.072 (181) | 3.47 (8726) | 0.169 (426) | 5.66 (14217) | |
| 0.0009 (1.00) | 3.07 (3564) | 0.138 (161) | 19.8 (22951) | 0.375 (435) | 22.1 (25582) | |
| 0.002 (1.00) | 11.9 (6241) | 0.264 (139) | 66.5 (34831) | 0.817 (428) | 91.1 (47750) | |
| 0.004 (1.00) | 51.4 (12221) | 0.437 (104) | 561 (133494) | 1.75 (416) | 549 (130735) | |
| 0.010 (1.00) | 191 (19408) | 0.648 (65.7) | TO | 3.66 (371) | TO | |
| 0.020 (1.00) | TO | 1.11 (55.6) | TO | 7.42 (371) | TO | |
| 0.045 (1.00) | TO | 2.05 (45.9) | TO | 14.9 (334) | TO | |
| 0.123 (1.00) | TO | 3.93 (31.9) | TO | OOM | TO | |
| 0.459 (1.00) | TO | 8.45 (18.4) | TO | OOM | TO |
Table 10. Breadth-first search, Long-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| LEMON CSR [code 35] | LEMON linked [code 35] | JGraphT [code 28] | JGraphT hash [code 28] | SciPy CSR [code 54] | SciPy prebuilt [code 54] | NetworkX [code 43] | |
| 1024 | 0.0001 (2.65) | 0.0000 (0.40) | 0.0008 (14.5) | 0.0007 (13.6) | 0.0004 (7.96) | 0.0001 (2.23) | 0.0006 (10.6) |
| 0.0001 (1.15) | 0.0000 (0.38) | 0.001 (13.2) | 0.002 (14.2) | 0.0005 (4.68) | 0.0001 (1.29) | 0.001 (10.4) | |
| 0.0002 (1.23) | 0.0001 (0.42) | 0.003 (13.0) | 0.003 (14.1) | 0.0007 (3.33) | 0.0002 (0.88) | 0.002 (11.0) | |
| 0.0005 (1.26) | 0.0002 (0.43) | 0.006 (14.0) | 0.007 (18.2) | 0.0010 (2.44) | 0.0003 (0.72) | 0.004 (11.2) | |
| 0.001 (1.21) | 0.0004 (0.43) | 0.012 (13.3) | 0.019 (21.7) | 0.002 (2.04) | 0.0006 (0.65) | 0.009 (10.6) | |
| 0.002 (1.17) | 0.0009 (0.45) | 0.023 (12.0) | 0.043 (22.4) | 0.004 (2.03) | 0.001 (0.63) | 0.022 (11.3) | |
| 0.005 (1.14) | 0.002 (0.41) | 0.056 (13.2) | 0.065 (15.5) | 0.008 (1.99) | 0.003 (0.61) | 0.056 (13.4) | |
| 0.012 (1.24) | 0.004 (0.42) | 0.222 (22.5) | 0.124 (12.5) | 0.016 (1.65) | 0.006 (0.56) | 0.139 (14.1) | |
| 0.029 (1.43) | 0.019 (0.93) | 0.562 (28.1) | 0.416 (20.8) | 0.031 (1.53) | 0.009 (0.46) | 0.270 (13.5) | |
| 0.087 (1.95) | 0.042 (0.95) | 1.37 (30.8) | 0.836 (18.7) | 0.058 (1.31) | 0.021 (0.46) | 0.623 (13.9) | |
| 0.168 (1.36) | 0.081 (0.66) | 3.15 (25.5) | 1.67 (13.5) | 0.114 (0.93) | 0.036 (0.29) | 1.39 (11.3) | |
| 0.393 (0.85) | 0.282 (0.61) | 6.90 (15.0) | 3.39 (7.39) | 0.358 (0.78) | 0.129 (0.28) | 3.34 (7.28) |
Table 10 (PDF p. 35). Breadth-first search, Long-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).

Figure 5. BFS: filled marks are exports over CSR arrays, hollow marks those over red-black trees. ● SML imp., ○ SML func., ■ Scala imp., □ Scala func., ▲ Go imp., △ Go func., ✚ LEMON CSR, ✣ LEMON linked, ◆ JGraphT CSR, ◇ JGraphT hash, ◆ SciPy CSR, ❖ SciPy prebuilt, ➜ NetworkX.
| SML imp. | SML func. | Scala imp. | Scala func. | Go imp. | Go func. | ||
| 1024 | 0.0006 (1.00) | 0.315 (573) | 0.109 (198) | 1.20 (2179) | 0.366 (666) | 1.81 (3297) | |
| 0.002 (1.00) | 2.27 (1040) | 0.386 (177) | 11.3 (5182) | 1.68 (769) | 19.1 (8760) | ||
| 0.009 (1.00) | 37.9 (4232) | 0.884 (98.7) | 115 (12876) | 6.85 (765) | 248 (27722) | ||
| 0.043 (1.00) | 180 (4205) | 3.04 (70.9) | 772 (18027) | OOM | TO | ||
| 0.310 (1.00) | TO | 13.7 (44.3) | TO | OOM | TO | ||
| 1.38 (1.00) | TO | OOM | TO | OOM | TO | ||
| LEMON CSR [code 35] | LEMON linked [code 35] | JGraphT CSR [code 28] | JGraphT hash [code 28] | SciPy CSR [code 54] | SciPy prebuilt [code 54] | NetworkX [code 43] | |
| 1024 | 0.002 (3.10) | 0.002 (2.80) | 0.016 (29.7) | 0.011 (19.9) | 0.002 (4.12) | 0.0003 (0.54) | 0.0007 (1.26) |
| 0.003 (1.43) | 0.004 (1.79) | 0.080 (36.6) | 0.042 (19.2) | 0.010 (4.76) | 0.001 (0.62) | 0.002 (0.74) | |
| 0.016 (1.80) | 0.026 (2.93) | 0.587 (65.6) | 0.169 (18.8) | 0.041 (4.52) | 0.003 (0.33) | 0.134 (14.9) | |
| 0.075 (1.75) | 0.359 (8.37) | 3.09 (72.2) | 0.577 (13.5) | 0.180 (4.21) | 0.016 (0.37) | 0.522 (12.2) | |
| 0.359 (1.16) | 2.06 (6.63) | 17.4 (56.0) | 2.57 (8.28) | 0.760 (2.45) | 0.046 (0.15) | 0.047 (0.15) | |
| 1.26 (0.91) | 9.22 (6.68) | 85.2 (61.8) | 12.3 (8.90) | 3.34 (2.42) | 0.228 (0.17) | 10.8 (7.86) |
Table 11. Breadth-first search, dense connected rand. family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| Network | LEMON CSR [code 35] | LEMON linked [code 35] | JGraphT CSR [code 28] | JGraphT hash [code 28] | SciPy CSR [code 54] | SciPy prebuilt [code 54] | NetworkX [code 43] | |
| NY | 264346 | 0.039 (0.99) | 0.011 (0.28) | 0.147 (3.73) | 0.188 (4.77) | 0.023 (0.60) | 0.008 (0.20) | 0.308 (7.80) |
| BAY | 321270 | 0.023 (0.97) | 0.015 (0.64) | 0.181 (7.51) | 0.261 (10.8) | 0.024 (1.01) | 0.009 (0.37) | 0.353 (14.6) |
| COL | 435666 | 0.030 (1.37) | 0.022 (0.97) | 0.308 (13.9) | 0.507 (22.9) | 0.033 (1.49) | 0.013 (0.60) | 0.514 (23.2) |
| FLA | 1070376 | 0.086 (1.29) | 0.086 (1.28) | 0.940 (14.0) | 1.06 (15.8) | 0.081 (1.21) | 0.034 (0.50) | 1.71 (25.5) |
| NW | 1207945 | 0.096 (1.28) | 0.075 (1.00) | 1.14 (15.2) | 1.20 (16.0) | 0.092 (1.23) | 0.042 (0.56) | 1.99 (26.6) |
| NE | 1524453 | 0.139 (1.37) | 0.095 (0.93) | 2.04 (20.0) | 1.50 (14.7) | 0.120 (1.19) | 0.050 (0.50) | 2.36 (23.2) |
| CAL | 1890815 | 0.164 (1.19) | 0.181 (1.31) | 2.18 (15.8) | 1.69 (12.2) | 0.173 (1.26) | 0.081 (0.59) | 3.44 (24.9) |
| LKS | 2758119 | 0.288 (1.37) | 0.226 (1.07) | 4.43 (21.0) | 2.69 (12.8) | 0.247 (1.18) | 0.113 (0.54) | 4.97 (23.6) |
| E | 3598623 | 0.376 (1.05) | 0.261 (0.73) | 6.22 (17.4) | 3.93 (11.0) | 0.307 (0.86) | 0.144 (0.40) | 7.41 (20.7) |
| W | 6262104 | 0.540 (1.02) | 0.389 (0.74) | 10.3 (19.6) | 6.41 (12.1) | 0.575 (1.09) | 0.284 (0.54) | 13.9 (26.3) |
| CTR | 14081816 | 1.43 (1.05) | 1.24 (0.91) | 32.3 (23.7) | 18.0 (13.2) | 1.40 (1.03) | 0.621 (0.46) | 57.4 (42.1) |
| USA | 23947347 | 2.26 (1.22) | 1.95 (1.05) | 45.8 (24.8) | 26.8 (14.5) | 2.22 (1.20) | 1.02 (0.55) | 67.1 (36.3) |
Table 40.
| SML | Scala | Go | LEMON CSR [code 39] | LEMON linked [code 39] | JGraphT CSR [code 30] | JGraphT hash [code 30] | SciPy CSR [code 56] | SciPy prebuilt [code 56] | NetworkX [code 47] | ||
| 1024 | 0.0004 (1.00) | 0.016 (38.1) | 0.036 (87.5) | 0.0002 (0.54) | 0.0001 (0.13) | 1024 | 0.0008 (2.01) | 0.0007 (1.79) | 0.0006 (1.56) | 0.0003 (0.71) | 0.001 (2.75) |
| 2025 | 0.0007 (1.00) | 0.023 (31.3) | 0.057 (78.1) | 0.0002 (0.23) | 0.0001 (0.07) | 2025 | 0.001 (1.81) | 0.0009 (1.27) | 0.0009 (1.19) | 0.0005 (0.68) | 0.003 (3.66) |
| 4096 | 0.002 (1.00) | 0.060 (34.9) | 0.178 (104) | 0.0004 (0.24) | 0.0002 (0.10) | 4096 | 0.003 (1.69) | 0.003 (1.75) | 0.001 (0.83) | 0.0009 (0.54) | 0.005 (3.03) |
| 8190 | 0.004 (1.00) | 0.132 (33.8) | 0.459 (118) | 0.0009 (0.23) | 0.0004 (0.11) | 8190 | 0.006 (1.49) | 0.008 (2.01) | 0.003 (0.67) | 0.002 (0.50) | 0.014 (3.52) |
| 16384 | 0.007 (1.00) | 0.220 (30.6) | 0.953 (133) | 0.002 (0.24) | 0.0008 (0.10) | 16384 | 0.012 (1.61) | 0.013 (1.76) | 0.006 (0.78) | 0.004 (0.59) | 0.032 (4.50) |
| 32761 | 0.008 (1.00) | 0.370 (47.6) | 1.97 (253) | 0.003 (0.43) | 0.002 (0.22) | 32761 | 0.024 (3.02) | 0.024 (3.03) | 0.012 (1.49) | 0.009 (1.18) | 0.068 (8.79) |
| 65536 | 0.052 (1.00) | 0.530 (10.2) | 3.85 (73.8) | 0.007 (0.13) | 0.003 (0.06) | 65536 | 0.059 (1.14) | 0.038 (0.73) | 0.025 (0.48) | 0.020 (0.38) | 0.150 (2.88) |
| 131044 | 0.063 (1.00) | 0.978 (15.4) | 11.0 (174) | 0.022 (0.34) | 0.013 (0.20) | 131044 | 0.249 (3.94) | 0.145 (2.29) | 0.056 (0.88) | 0.046 (0.72) | 1.06 (16.7) |
| 262144 | 0.100 (1.00) | 1.58 (15.9) | 18.8 (188) | 0.052 (0.52) | 0.026 (0.26) | 262144 | 0.505 (5.07) | 0.290 (2.91) | 0.127 (1.27) | 0.109 (1.09) | 1.89 (18.9) |
| 524176 | 0.216 (1.00) | 2.80 (12.9) | 32.2 (149) | 0.118 (0.55) | 0.048 (0.22) | 524176 | 1.18 (5.44) | 0.468 (2.17) | 0.343 (1.59) | 0.304 (1.40) | 3.71 (17.2) |
| 1048576 | 0.707 (1.00) | 5.02 (7.10) | OOM | 0.252 (0.36) | 0.101 (0.14) | 1048576 | 2.45 (3.47) | 0.753 (1.06) | 0.778 (1.10) | 0.736 (1.04) | 6.08 (8.60) |
| 2096704 | 1.70 (1.00) | 13.6 (8.00) | OOM | 0.691 (0.41) | 0.425 (0.25) | 2096704 | 6.65 (3.92) | 2.28 (1.35) | 1.85 (1.09) | 1.70 (1.00) | 34.1 (20.1) |
Table 13. Dijkstra’s algorithm, Square-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| SML | Scala | Go | LEMON CSR [code 39] | LEMON linked [code 39] | JGraphT CSR [code 30] | JGraphT hash [code 30] | SciPy CSR [code 56] | SciPy prebuilt [code 56] | NetworkX [code 47] | |
| 1024 | 0.0004 (1.00) | 0.015 (36.6) | 0.056 (141) | 0.0001 (0.25) | 0.0000 (0.09) | 0.0008 (2.02) | 0.0005 (1.29) | 0.0007 (1.68) | 0.0003 (0.72) | 0.001 (2.69) |
| 0.0008 (1.00) | 0.030 (36.2) | 0.071 (86.6) | 0.0002 (0.24) | 0.0001 (0.10) | 0.001 (1.65) | 0.001 (1.49) | 0.0009 (1.12) | 0.0004 (0.55) | 0.005 (6.05) | |
| 0.002 (1.00) | 0.060 (35.8) | 0.170 (102) | 0.0004 (0.23) | 0.0002 (0.09) | 0.003 (1.66) | 0.002 (1.45) | 0.001 (0.77) | 0.0008 (0.46) | 0.005 (3.23) | |
| 0.003 (1.00) | 0.112 (32.2) | 0.391 (113) | 0.0008 (0.23) | 0.0003 (0.09) | 0.006 (1.65) | 0.006 (1.80) | 0.002 (0.62) | 0.001 (0.42) | 0.015 (4.22) | |
| 0.008 (1.00) | 0.246 (31.5) | 1.04 (134) | 0.002 (0.23) | 0.0008 (0.10) | 0.011 (1.44) | 0.017 (2.22) | 0.004 (0.58) | 0.003 (0.41) | 0.064 (8.16) | |
| 0.014 (1.00) | 0.368 (26.4) | 2.08 (149) | 0.003 (0.25) | 0.002 (0.12) | 0.025 (1.77) | 0.029 (2.07) | 0.009 (0.62) | 0.006 (0.45) | 0.182 (13.0) | |
| 0.051 (1.00) | 0.565 (11.2) | 4.31 (85.2) | 0.007 (0.14) | 0.003 (0.07) | 0.059 (1.17) | 0.045 (0.88) | 0.018 (0.37) | 0.014 (0.27) | 0.727 (14.4) | |
| 0.050 (1.00) | 0.870 (17.3) | 9.01 (179) | 0.018 (0.36) | 0.008 (0.15) | 0.251 (4.98) | 0.106 (2.10) | 0.038 (0.75) | 0.029 (0.57) | 3.81 (75.8) | |
| 0.070 (1.00) | 1.28 (18.2) | 14.1 (200) | 0.039 (0.56) | 0.016 (0.22) | 0.507 (7.21) | 0.211 (3.00) | 0.088 (1.25) | 0.071 (1.01) | 5.36 (76.2) | |
| 0.202 (1.00) | 2.64 (13.1) | 31.3 (155) | 0.123 (0.61) | 0.042 (0.21) | 1.17 (5.78) | 0.488 (2.42) | 0.256 (1.27) | 0.192 (0.95) | 31.29/10 (155) | |
| 0.750 (1.00) | 5.58 (7.45) | OOM | 0.264 (0.35) | 0.121 (0.16) | 2.72 (3.63) | 1.05 (1.40) | 0.594 (0.79) | 0.449 (0.60) | 19.94/10 (26.5) | |
| 1.51 (1.00) | 11.9 (7.92) | OOM | 0.548 (0.36) | 0.344 (0.23) | 6.84 (4.53) | 2.07 (1.37) | 1.31 (0.87) | 1.17 (0.77) | OOM |
Table 14. Dijkstra’s algorithm, Long- family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| Network | SML | Scala | Go | LEMON CSR [code 39] | LEMON linked [code 39] | |
| NY | 264346 | 0.131 (1.00) | 1.15 (8.76) | 14.1 (107) | 0.061 (0.46) | 0.020 (0.15) |
| BAY | 321270 | 0.114 (1.00) | 1.45 (12.7) | 19.2 (168) | 0.039 (0.34) | 0.029 (0.25) |
| COL | 435666 | 0.115 (1.00) | 1.69 (14.7) | 21.8 (190) | 0.048 (0.42) | 0.032 (0.28) |
| FLA | 1070376 | 0.300 (1.00) | 3.93 (13.1) | 51.1 (170) | 0.134 (0.45) | 0.094 (0.31) |
| NW | 1207945 | 0.363 (1.00) | 4.93 (13.6) | 61.4 (169) | 0.168 (0.46) | 0.123 (0.34) |
| NE | 1524453 | 0.724 (1.00) | 6.63 (9.16) | 80.1 (111) | 0.233 (0.32) | 0.172 (0.24) |
| CAL | 1890815 | 0.788 (1.00) | 7.71 (9.78) | OOM | 0.289 (0.37) | 0.208 (0.26) |
| LKS | 2758119 | 1.14 (1.00) | 11.2 (9.83) | OOM | 0.415 (0.36) | 0.300 (0.26) |
| E | 3598623 | 1.54 (1.00) | 15.2 (9.91) | OOM | 0.528 (0.34) | 0.394 (0.26) |
| W | 6262104 | 2.35 (1.00) | 25.4 (10.8) | OOM | 0.870 (0.37) | 0.598 (0.25) |
| CTR | 14081816 | 7.13 (1.00) | 71.1 (9.97) | OOM | 2.67 (0.37) | 2.02 (0.28) |
| USA | 23947347 | 12.5 (1.00) | 1106/10 (8.83) | OOM | 4.13 (0.33) | 3.90 (0.31) |
| Network | JGraphT CSR [code 30] | JGraphT hash [code 30] | SciPy CSR [code 56] | SciPy prebuilt [code 56] | NetworkX [code 47] | |
| NY | 264346 | 0.175 (1.33) | 0.180 (1.38) | 0.082 (0.62) | 0.080 (0.61) | 1.08 (8.24) |
| BAY | 321270 | 0.219 (1.92) | 0.263 (2.30) | 0.094 (0.82) | 0.088 (0.77) | 2.66 (23.3) |
| COL | 435666 | 0.267 (2.33) | 0.324 (2.83) | 0.140 (1.22) | 0.128 (1.11) | 2.96 (25.8) |
| FLA | 1070376 | 0.995 (3.31) | 0.695 (2.31) | 0.384 (1.28) | 0.347 (1.16) | 8.14 (27.1) |
| NW | 1207945 | 1.22 (3.36) | 1.01 (2.78) | 0.452 (1.25) | 0.440 (1.21) | 16.2 (44.6) |
| NE | 1524453 | 1.89 (2.61) | 1.22 (1.68) | 0.586 (0.81) | 0.573 (0.79) | 19.3 (26.6) |
| CAL | 1890815 | 2.28 (2.90) | 1.28 (1.63) | 0.819 (1.04) | 0.784 (0.99) | 29.3 (37.2) |
| LKS | 2758119 | 4.22 (3.70) | 2.05 (1.80) | 1.21 (1.06) | 1.14 (1.00) | 42.9 (37.7) |
| E | 3598623 | 5.70 (3.71) | 3.02 (1.96) | 1.65 (1.07) | 1.60 (1.04) | 47.59/10 (30.9) |
| W | 6262104 | 10.4 (4.43) | 4.15 (1.77) | 2.97 (1.26) | 2.92 (1.24) | OOM |
| CTR | 14081816 | 29.0 (4.07) | 13.2 (1.85) | 8.30 (1.16) | 8.17 (1.15) | OOM |
| USA | 23947347 | 45.6 (3.66) | 24.4 (1.95) | 13.2 (1.06) | 12.9 (1.03) | OOM |
Table 15. Dijkstra’s algorithm, USA-road-t family [code 7] (, one network per size, 10 source-target pairs each, median of 3 repeats each).
| SML | Scala | Go | LEMON [code 40] | JGraphT [code 31] | SciPy [code 58] | NetworkX [code 45] | |
| 1024 | 0.0004 (1.00) | 0.014 (39.0) | 0.025 (70.3) | 0.0001 (0.31) | 0.0008 (2.13) | 0.0003 (0.91) | 0.005 (13.8) |
| 2025 | 0.0007 (1.00) | 0.048 (68.3) | 0.060 (85.6) | 0.0002 (0.33) | 0.002 (2.50) | 0.0005 (0.70) | 0.009 (12.6) |
| 4096 | 0.001 (1.00) | 0.249 (170) | 0.158 (108) | 0.0005 (0.33) | 0.004 (2.98) | 0.0009 (0.61) | 0.018 (12.3) |
| 8190 | 0.003 (1.00) | 0.746 (254) | 0.464 (158) | 0.001 (0.38) | 0.009 (2.90) | 0.002 (0.59) | 0.036 (12.3) |
| 16384 | 0.006 (1.00) | 3.86 (615) | 1.57 (250) | 0.002 (0.39) | 0.015 (2.31) | 0.004 (0.57) | 0.095 (15.1) |
| 32761 | 0.014 (1.00) | 16.1 (1125) | 5.97 (418) | 0.005 (0.36) | 0.044 (3.08) | 0.007 (0.52) | 0.204 (14.2) |
| 65536 | 0.037 (1.00) | 72.0 (1935) | 22.5 (605) | 0.011 (0.30) | 0.109 (2.94) | 0.017 (0.45) | 0.562 (15.1) |
| 131044 | 0.064 (1.00) | 303 (4708) | 85.1 (1321) | 0.024 (0.37) | 0.285 (4.42) | 0.035 (0.55) | 1.40 (21.7) |
| 262144 | 0.146 (1.00) | TO | 7288/10 (4981) | 0.056 (0.38) | 0.743 (5.08) | 0.078 (0.54) | 3.26 (22.3) |
| 524176 | 0.354 (1.00) | TO | TO | 0.129 (0.37) | 1.76 (4.98) | 0.160 (0.45) | 7.56 (21.4) |
| 1048576 | 0.765 (1.00) | TO | TO | 0.301 (0.39) | 4.06 (5.30) | 0.365 (0.48) | 15.9 (20.8) |
| 2096704 | 1.67 (1.00) | TO | TO | 0.669 (0.40) | 9.80 (5.87) | 0.882 (0.53) | 34.2 (20.5) |
Table 16. Kruskal’s algorithm, Square-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| SML | Scala | Go | LEMON [code 40] | JGraphT [code 31] | SciPy [code 58] | NetworkX [code 45] | |
| 1024 | 0.0004 (1.00) | 0.014 (39.8) | 0.025 (70.1) | 0.0001 (0.32) | 0.0008 (2.23) | 0.0003 (0.89) | 0.005 (13.7) |
| 0.0007 (1.00) | 0.063 (90.6) | 0.060 (85.3) | 0.0002 (0.33) | 0.002 (2.63) | 0.0005 (0.71) | 0.009 (12.7) | |
| 0.001 (1.00) | 0.162 (115) | 0.154 (110) | 0.0005 (0.35) | 0.004 (3.12) | 0.0009 (0.63) | 0.018 (12.7) | |
| 0.003 (1.00) | 0.919 (312) | 0.457 (155) | 0.001 (0.38) | 0.008 (2.67) | 0.002 (0.58) | 0.036 (12.1) | |
| 0.006 (1.00) | 4.15 (674) | 1.51 (246) | 0.002 (0.39) | 0.015 (2.51) | 0.004 (0.57) | 0.096 (15.5) | |
| 0.015 (1.00) | 16.6 (1121) | 5.36 (362) | 0.005 (0.34) | 0.041 (2.78) | 0.007 (0.50) | 0.216 (14.6) | |
| 0.037 (1.00) | 66.7 (1810) | 21.2 (576) | 0.011 (0.30) | 0.105 (2.86) | 0.016 (0.43) | 0.529 (14.4) | |
| 0.064 (1.00) | 282 (4373) | 81.4 (1264) | 0.023 (0.36) | 0.291 (4.52) | 0.035 (0.54) | 1.40 (21.7) | |
| 0.136 (1.00) | (8427) | 672 (4935) | 0.055 (0.40) | 0.703 (5.17) | 0.073 (0.54) | 3.29 (24.2) | |
| 0.368 (1.00) | TO | TO | 0.126 (0.34) | 1.73 (4.69) | 0.158 (0.43) | 6.79 (18.4) | |
| 0.739 (1.00) | TO | TO | 0.292 (0.39) | 3.99 (5.40) | 0.348 (0.47) | 15.5 (21.0) | |
| 1.67 (1.00) | TO | TO | 0.681 (0.41) | 9.60 (5.73) | 0.852 (0.51) | 34.2 (20.4) |
Table 17. Kruskal’s algorithm, Long-n family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| SML | Scala | Go | LEMON [code 40] | JGraphT [code 31] | SciPy [code 58] | NetworkX [code 45] | |
| 1024 | 0.012 (1.00) | 13.3 (1127) | 5.08 (429) | 0.003 (0.28) | 0.017 (1.48) | 0.005 (0.39) | 0.108 (9.09) |
| 0.061 (1.00) | 249 (4106) | 81.1 (1339) | 0.015 (0.25) | 0.099 (1.63) | 0.021 (0.34) | 0.589 (9.73) | |
| 0.291 (1.00) | TO | TO | 0.087 (0.30) | 0.698 (2.39) | 0.091 (0.31) | 2.92 (10.0) | |
| 1.26 (1.00) | TO | TO | 0.456 (0.36) | 2.88 (2.28) | 0.448 (0.35) | 14.0 (11.1) | |
| 7.23 (1.00) | TO | TO | 2.02 (0.28) | 12.9 (1.78) | 2.24 (0.31) | 67.9 (9.39) | |
| 34.1 (1.00) | TO | TO | 8.71 (0.26) | 62.9 (1.84) | 10.9 (0.32) | 324 (9.50) |
Table 18. Kruskal’s algorithm, dense connected rand. family [code 6] (, 10 instances per size, averaged over the medians of 3 repeats per instance). The instances are those of Table 11.
| SML HL | SML FIFO | SML AFP [code 27] | LEMON CSR [code 42] | LEMON linked [code 42] | JGraphT [code 34] | SciPy Dinic CSR [code 57] | SciPy Dinic prebuilt [code 57] | NetworkX [code 46] | GC [code 10] | |
| 4096 | 0.047 (1.00) | 0.056 (1.17) | n/a | 0.007 (0.15) | 0.009 (0.19) | 0.150 (3.17) | 0.081 (1.72) | 0.080 (1.69) | 0.941 (19.9) | 0.004 (0.08) |
| 9000 | 0.151 (1.00) | 0.201 (1.33) | n/a | 0.021 (0.14) | 0.034 (0.23) | 0.320 (2.12) | 0.288 (1.91) | 0.290 (1.92) | 1.98 (13.1) | 0.009 (0.06) |
| 15488 | 0.377 (1.00) | 0.714 (1.89) | n/a | 0.050 (0.13) | 0.141 (0.38) | 0.610 (1.62) | 0.816 (2.17) | 0.817 (2.17) | 3.36 (8.93) | 0.018 (0.05) |
| 30589 | 0.914 (1.00) | 2.01 (2.20) | n/a | 0.105 (0.11) | 0.240 (0.26) | 1.13 (1.24) | 1.99 (2.18) | 1.80 (1.97) | 6.77 (7.41) | 0.038 (0.04) |
| 65536 | 2.12 (1.00) | 5.63 (2.65) | n/a | 0.445 (0.21) | 1.72 (0.81) | 2.40 (1.13) | 4.61 (2.17) | 4.69 (2.21) | 20.1 (9.48) | 0.084 (0.04) |
| 130321 | 5.57 (1.00) | 14.4 (2.58) | n/a | 1.09 (0.20) | 5.15 (0.93) | 6.81 (1.22) | 12.4 (2.23) | 12.2 (2.20) | 48.6 (8.72) | 0.232 (0.04) |
| 270319 | 29.4 (1.00) | 100 (3.41) | n/a | 4.78 (0.16) | 48.6 (1.66) | 14.9 (0.51) | 44.5 (1.52) | 44.2 (1.51) | 142 (4.83) | 1.06 (0.04) |
| 527067 | 147 (1.00) | 467 (3.17) | n/a | 22.7 (0.15) | 300 (2.04) | 31.9 (0.22) | 147 (1.00) | 150 (1.02) | 358 (2.43) | 1.47 (0.01) |
| 1046528 | 509 (1.00) | TO | n/a | 51.5 (0.10) | TO | 80.4 (0.16) | 743 (1.46) | 792 (1.56) | 923 (1.82) | 4.53 (0.01) |
| 2090912 | TO | TO | n/a | 267 (–) | TO | 200 (–) | TO | TO | TO | 6.56 (–) |
| 4147200 | TO | TO | n/a | 827 (–) | TO | 469 (–) | TO | TO | TO | 19.4 (–) |
| 8444736 | TO | TO | n/a | TO | TO | TO | TO | TO | TO | 90.2 (–) |
| 16777216 | TO | TO | n/a | TO | TO | TO | TO | TO | TO | 242 (–) |
| 33460368 | TO | TO | n/a | TO | TO | TO | TO | TO | TO | 598 (–) |
| 67109224 | TO | TO | n/a | TO | TO | TO | TO | TO | TO | TO |
Table 19. Push-relabel, RMF-long family [code 1] (, 3 instances per size). Plots were cut off at . The family does not meet the structural prerequisites for SML AFP [code 27].
| SML HL | SML FIFO | SML AFP [code 27] | LEMON CSR [code 42] | LEMON linked [code 42] | JGraphT [code 34] | SciPy Dinic CSR [code 57] | SciPy Dinic prebuilt [code 57] | NetworkX [code 46] | GC [code 10] | |
| 4098 | 0.028 (1.00) | 0.027 (0.94) | 0.310 (10.9) | 0.009 (0.33) | 0.009 (0.32) | 0.117 (4.11) | 0.028 (0.99) | 0.028 (0.97) | 0.824 (29.0) | 0.005 (0.16) |
| 8194 | 0.086 (1.00) | 0.121 (1.40) | 1.23 (14.2) | 0.042 (0.48) | 0.042 (0.48) | 0.280 (3.24) | 0.097 (1.12) | 0.096 (1.11) | 1.76 (20.3) | 0.010 (0.11) |
| 16386 | 0.264 (1.00) | 0.430 (1.63) | 3.39 (12.8) | 0.116 (0.44) | 0.113 (0.43) | 0.600 (2.27) | 0.338 (1.28) | 0.339 (1.28) | 2.96 (11.2) | 0.019 (0.07) |
| 32770 | 0.889 (1.00) | 1.60 (1.80) | 10.2 (11.5) | 0.640 (0.72) | 0.599 (0.67) | 1.23 (1.38) | 1.13 (1.27) | 1.12 (1.26) | 7.09 (7.97) | 0.042 (0.05) |
| 65538 | 2.54 (1.00) | 3.67 (1.44) | OVF | 1.47 (0.58) | 1.85 (0.73) | 2.38 (0.94) | 2.69 (1.06) | 2.60 (1.02) | 14.2 (5.58) | 0.080 (0.03) |
| 131074 | 6.89 (1.00) | 8.76 (1.27) | OVF | 3.30 (0.48) | 3.05 (0.44) | 4.47 (0.65) | 8.93 (1.30) | 8.98 (1.30) | 28.8 (4.18) | 0.170 (0.02) |
| 262146 | 36.6 (1.00) | 35.8 (0.98) | OVF | 3.63 (0.10) | 3.39 (0.09) | 11.7 (0.32) | 35.5 (0.97) | 34.0 (0.93) | 64.4 (1.76) | 0.347 (0.01) |
| 524290 | 273 (1.00) | 299 (1.09) | OVF | 90.2 (0.33) | 92.9 (0.34) | 29.4 (0.11) | 130 (0.48) | 129 (0.47) | 154 (0.56) | 0.748 (0.00) |
| 1048578 | TO | TO | OVF | 139 (–) | 138 (–) | 72.4 (–) | 498 (–) | 512 (–) | 304 (–) | 1.01 (–) |
| 2097154 | TO | TO | OVF | 137 (–) | 134 (–) | 180 (–) | TO | TO | 568 (–) | 2.04 (–) |
| 4194306 | TO | TO | OVF | 350 (–) | 353 (–) | 459 (–) | TO | TO | TO | 4.69 (–) |
| 8388610 | TO | TO | OVF | TO | TO | TO | TO | TO | TO | 9.33 (–) |
| 16777218 | TO | TO | OVF | TO | TO | TO | TO | TO | TO | 17.3 (–) |
| 33554434 | TO | TO | OVF | TO | TO | TO | TO | TO | TO | 38.8 (–) |
| 67108866 | TO | TO | OVF | TO | TO | TO | TO | TO | TO | 81.4 (–) |
Table 20. Push-relabel, WASH-RLG-long family [code 2] (, 3 instances per size). Plots were cut off at .
| SML HL | SML FIFO | SML AFP [code 27] | LEMON CSR [code 42] | LEMON linked [code 42] | JGraphT [code 34] | SciPy Dinic CSR [code 57] | SciPy Dinic prebuilt [code 57] | NetworkX [code 46] | GC [code 10] | |
| 4102 | 0.120 (1.00) | 0.072 (0.60) | 0.392 (3.27) | 0.003 (0.02) | 0.006 (0.05) | 0.460 (3.84) | 0.135 (1.13) | 0.294 (2.46) | 8.81 (73.6) | 0.014 (0.11) |
| 8198 | 0.280 (1.00) | 0.273 (0.97) | 1.43 (5.11) | 0.007 (0.02) | 0.014 (0.05) | 0.930 (3.32) | 0.539 (1.92) | 1.17 (4.18) | 32.0 (114) | 0.057 (0.20) |
| 16390 | 1.61 (1.00) | 1.09 (0.68) | 3.69 (2.30) | 0.019 (0.01) | 0.047 (0.03) | 2.63 (1.64) | 2.16 (1.34) | 3.13 (1.95) | 127 (79.3) | 0.233 (0.14) |
| 32774 | 4.41 (1.00) | 3.16 (0.72) | 11.9 (2.70) | 0.058 (0.01) | 0.090 (0.02) | 7.39 (1.68) | 8.76 (1.99) | 9.63 (2.18) | 523 (119) | 0.889 (0.20) |
| 65542 | 15.0 (1.00) | 9.14 (0.61) | OVF | 0.198 (0.01) | 0.242 (0.02) | 32.5 (2.17) | 34.9 (2.33) | 35.5 (2.37) | TO | 2.19 (0.15) |
| 131078 | 55.3 (1.00) | 33.0 (0.60) | OVF | 0.730 (0.01) | 0.793 (0.01) | 392 (7.09) | 138 (2.51) | 138 (2.51) | TO | 6.96 (0.13) |
| 262150 | 222 (1.00) | 129 (0.58) | OVF | 3.41 (0.02) | 3.68 (0.02) | TO | 553 (2.49) | 553 (2.49) | TO | 28.3 (0.13) |
| 524294 | 883 (1.00) | 510 (0.58) | OVF | 11.9 (0.01) | 11.9 (0.01) | TO | TO | TO | TO | 111 (0.13) |
| 1048582 | TO | TO | OVF | 43.8 (–) | 43.0 (–) | TO | TO | TO | TO | 441 (–) |
Table 21. Push-relabel, AK family [code 8] (, 1 instance per size, median of 3 repeats).
| SML | Scala | Go | SciPy LSA [code 52] | SciPy MWFBM CSR [code 53] | |
| 0.005 (1.00) | 0.537 (102) | 4.81 (916) | 0.012 (2.32) | 0.002 (0.46) | |
| 0.016 (1.00) | 0.763 (47.9) | 13.6 (853) | 0.058 (3.62) | 0.006 (0.40) | |
| 0.054 (1.00) | 1.22 (22.5) | 40.4 (748) | 0.351 (6.50) | 0.020 (0.36) | |
| 0.163 (1.00) | 2.61 (16.0) | 137 (838) | 2.32 (14.2) | 0.069 (0.42) | |
| 0.588 (1.00) | 6.28 (10.7) | 320 (544) | 20.9 (35.5) | 0.251 (0.43) | |
| JGraphT KM with GC [code 32] | JGraphT MWBM CSR [code 33] | JGraphT MWBM hash [code 33] | CSA CSR [code 9] | OR-Tools [code 11] | |
| 2.43 (463) | 0.108 (20.5) | 0.192 (36.5) | 0.005 (0.93) | 0.009 (1.69) | |
| 23.3 (1460) | 0.288 (18.1) | 0.489 (30.7) | 0.012 (0.76) | 0.018 (1.13) | |
| 201 (3715) | 0.758 (14.0) | 1.18 (21.9) | 0.027 (0.50) | 0.042 (0.78) | |
| TO | 2.33 (14.3) | 3.11 (19.1) | 0.064 (0.39) | 0.095 (0.58) | |
| TO | 6.68 (11.4) | 9.89 (16.8) | 0.152 (0.26) | 0.218 (0.37) |
Table 23. Hungarian method, two-cost family [code 4] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| SML | Scala | Go | SciPy LSA [code 52] | SciPy MWFBM CSR [code 53] | |
| 256 | 0.005 (1.00) | 0.494 (106) | 8.20 (1766) | 0.0006 (0.13) | 0.005 (0.99) |
| 512 | 0.024 (1.00) | 1.04 (43.5) | 42.8 (1784) | 0.003 (0.11) | 0.013 (0.56) |
| 1024 | 0.143 (1.00) | 3.48 (24.4) | 279 (1953) | 0.012 (0.09) | 0.045 (0.32) |
| 0.945 (1.00) | 19.9 (21.0) | 1186/10 (1256) | 0.069 (0.07) | 0.198 (0.21) | |
| 6.03 (1.00) | 133 (22.0) | TO | 0.333 (0.06) | 0.817 (0.14) | |
| JGraphT KM with GC [code 32] | JGraphT MWBM CSR [code 33] | JGraphT MWBM hash [code 33] | CSA CSR [code 9] | OR-Tools [code 11] | |
| 256 | 0.036 (7.83) | 0.093 (19.9) | 0.105 (22.7) | 0.0006 (0.12) | 0.004 (0.88) |
| 512 | 0.321 (13.4) | 0.313 (13.0) | 0.425 (17.7) | 0.002 (0.09) | 0.009 (0.38) |
| 1024 | 2.38 (16.7) | 1.28 (8.97) | 1.49 (10.4) | 0.009 (0.06) | 0.052 (0.37) |
| 34.6 (36.6) | 9.13 (9.66) | 15.7 (16.7) | 0.046 (0.05) | 0.386 (0.41) | |
| 480 (79.7) | 50.8 (8.43) | 90.7 (15.0) | 0.300 (0.05) | 3.97 (0.66) |
Table 24. Hungarian method, geometric family [code 5] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
b-Matching. For -matching, we set the capacities , where is selected uniformly at random between 1 and 20 and is the vertex degree.
Matroid intersection, unweighted problems on the low-cost and two-cost families [code 4], which share their graphs (, 5 instances per size, run once in each family, mean over both runs).
| SML | Scala | Go | Sage (our oracle) [code 49] | Sage (plain) [code 49,50,51] | |
| Matching | |||||
| 32 | <0.001 (–) | 0.038 (–) | 0.008 (–) | 0.003 (–) | 0.021 (–) |
| 64 | <0.001 (–) | 0.068 (–) | 0.025 (–) | 0.009 (–) | 0.137 (–) |
| 128 | 0.0006 (1.00) | 0.123 (206) | 0.094 (157) | 0.053 (88.8) | 1.49 (2480) |
| 256 | 0.002 (1.00) | 0.229 (99.3) | 0.337 (146) | 0.337 (147) | 14.8 (6421) |
| 512 | 0.009 (1.00) | 0.488 (53.6) | 1.52 (167) | 4.42 (485) | 176 (19357) |
| 1024 | 0.032 (1.00) | 0.830 (26.0) | 5.70 (179) | 46.3 (1452) | TO |
| 0.146 (1.00) | 2.27 (15.5) | 28.1 (193) | TO | TO | |
| 0.394 (1.00) | 7.29 (18.5) | 116 (294) | TO | TO | |
| 1.67 (1.00) | 29.1 (17.4) | 476 (284) | TO | TO | |
| 7.93 (1.00) | 123 (15.5) | TO | TO | TO | |
| 37.0 (1.00) | 530 (14.3) | TO | TO | TO | |
| -matching | |||||
| 32 | <0.001 (–) | 0.013 (–) | 0.019 (–) | 0.011 (–) | 0.233 (–) |
| 64 | <0.001 (–) | 0.039 (–) | 0.067 (–) | 0.076 (–) | 2.56 (–) |
| 128 | 0.002 (1.00) | 0.234 (117) | 0.623 (312) | 1.63 (815) | 40.2 (20079) |
| 256 | 0.018 (1.00) | 0.614 (34.9) | 4.79 (272) | 31.2 (1775) | 591 (33606) |
| 512 | 0.121 (1.00) | 2.24 (18.5) | 30.1 (249) | 539 (4460) | TO |
| 1024 | 0.885 (1.00) | 11.8 (13.3) | 201 (227) | TO | TO |
| 4.83 (1.00) | 59.6 (12.4) | 1069 (221) | TO | TO | |
| 22.0 (1.00) | 267 (12.2) | TO | TO | TO | |
| 123 (1.00) | TO | TO | TO | TO | |
| 537 (1.00) | TO | TO | TO | TO | |
| TO | TO | TO | TO | TO |
Table 25. Matroid intersection, unweighted problems on the low-cost and two-cost families [code 4], which share their graphs (, 5 instances per size, run once in each family, mean over both runs).
| SML | Scala | Go | Sage (our oracle) [code 48] | Sage (plain) [code 48,50,51] | |
| (–) | (–) | (–) | (–) | (–) | |
| (1.00) | (86.4) | (253) | (29.6) | (954) | |
| (1.00) | (40.6) | (212) | (52.2) | (5231) | |
| (1.00) | (28.3) | (212) | (140) | (37580) | |
| (1.00) | (22.3) | (199) | (317) | TO | |
| (1.00) | (19.2) | (186) | (868) | TO | |
| (1.00) | (17.8) | (193) | (1904) | TO | |
| (1.00) | (17.4) | (206) | TO | TO | |
| (1.00) | (18.5) | TO | TO | TO | |
| (1.00) | (18.6) | TO | TO | TO | |
| (1.00) | TO | TO | TO | TO | |
| Weighted matching | |||||
| (1.00) | (21.2) | (209) | (23.8) | (1905) | |
| (1.00) | (23.2) | (255) | (63.7) | (15831) | |
| (1.00) | (19.9) | (254) | (197) | (93994) | |
| (1.00) | (19.2) | (248) | (546) | TO | |
| (1.00) | (16.2) | (229) | (1346) | TO | |
| (1.00) | (13.6) | (193) | TO | TO | |
| (1.00) | (13.2) | (185) | TO | TO | |
| (1.00) | (12.8) | TO | TO | TO | |
| (1.00) | TO | TO | TO | TO | |
| (1.00) | TO | TO | TO | TO | |
| TO | TO | TO | TO | TO |
Table 26. Matroid intersection, weighted problems on the low-cost family [code 3] (, 5 instances per size, one run each). The unweighted problems are in Table 25.
| SML | Scala | Go | Sage (our oracle) [code 48] | Sage (plain) [code 48,50,51] | |
| Weighted matching | |||||
| 32 | <0.001 (–) | 0.006 (–) | 0.013 (–) | 0.005 (–) | 0.054 (–) |
| 64 | <0.001 (–) | 0.023 (–) | 0.051 (–) | 0.027 (–) | 1.04 (–) |
| 128 | 0.001 (1.00) | 0.077 (77.0) | 0.191 (191) | 0.179 (179) | 23.1 (23107) |
| 256 | 0.005 (1.00) | 0.167 (33.4) | 0.810 (162) | 1.33 (266) | 462 (92370) |
| 512 | 0.022 (1.00) | 0.488 (21.8) | 3.42 (153) | 10.4 (463) | TO |
| 1024 | 0.097 (1.00) | 1.57 (16.2) | 15.0 (154) | 91.5 (942) | TO |
| 0.391 (1.00) | 5.86 (15.0) | 65.0 (166) | 755 (1929) | TO | |
| 1.59 (1.00) | 24.0 (15.0) | 280 (175) | TO | TO | |
| 7.17 (1.00) | 106 (14.7) | 1137 (158) | TO | TO | |
| 32.6 (1.00) | 459 (14.1) | TO | TO | TO | |
| 151 (1.00) | TO | TO | TO | TO | |
| Weighted -matching | |||||
| 32 | 0.0002 (1.00) | 0.008 (38.0) | 0.051 (257) | 0.022 (112) | 1.74 (8711) |
| 64 | 0.002 (1.00) | 0.025 (15.7) | 0.235 (147) | 0.150 (93.8) | 37.0 (23125) |
| 128 | 0.006 (1.00) | 0.116 (19.3) | 1.32 (220) | 2.11 (351) | (131998) |
| 256 | 0.030 (1.00) | 0.573 (19.2) | 7.48 (251) | 23.3 (781) | TO |
| 512 | 0.165 (1.00) | 2.88 (17.5) | 39.2 (238) | 257 (1557) | TO |
| 1024 | 1.07 (1.00) | 15.0 (14.0) | 209 (196) | TO | TO |
| 5.84 (1.00) | 76.0 (13.0) | 1050 (180) | TO | TO | |
| 30.3 (1.00) | 373 (12.3) | TO | TO | TO | |
| 164 (1.00) | TO | TO | TO | TO | |
| 856 (1.00) | TO | TO | TO | TO | |
| TO | TO | TO | TO | TO |
Table 27. Matroid intersection, weighted problems on the two-cost family [code 4] (, 5 instances per size, one run each). The unweighted problems are in Table 25.
| SML | Scala | Go | Sage (our oracle) [code 48,49] | Sage (plain) [code 48,49,50,51] | |
| Matching | |||||
| 32 | <0.001 (–) | 0.007 (–) | 0.012 (–) | 0.004 (–) | 0.038 (–) |
| 64 | 0.001 (1.00) | 0.043 (43.4) | 0.084 (84.0) | 0.023 (23.0) | 0.650 (650) |
| 128 | 0.003 (1.00) | 0.281 (82.7) | 0.666 (196) | 0.296 (87.1) | 20.0 (5892) |
| 256 | 0.029 (1.00) | 0.751 (26.3) | 5.34 (187) | 4.32 (151) | 680 (23790) |
| 512 | 0.233 (1.00) | 4.56 (19.6) | 39.7 (171) | 66.3 (285) | TO |
| 1024 | 1.72 (1.00) | 37.4 (21.7) | 306 (178) | TO | TO |
| 13.1 (1.00) | OOM | TO | TO | TO | |
| 105 (1.00) | OOM | TO | TO | TO | |
| b-matching | |||||
| 32 | 0.0002 (1.00) | 0.044 (222) | 0.076 (381) | 0.050 (252) | 0.882 (4409) |
| 64 | 0.003 (1.00) | 0.258 (99.3) | 0.877 (337) | 0.759 (292) | 25.2 (9702) |
| 128 | 0.012 (1.00) | 0.566 (48.8) | 4.27 (368) | 12.9 (1113) | (78304) |
| 256 | 0.104 (1.00) | 2.44 (23.6) | 30.9 (298) | 132 (1277) | TO |
| 512 | 0.374 (1.00) | 9.17 (24.5) | 94.9 (254) | 125 (333) | TO |
| 1024 | 8.53 (1.00) | 176 (20.6) | TO | TO | TO |
| 42.9 (1.00) | OOM | TO | TO | TO | |
| 402 (1.00) | OOM | TO | TO | TO | |
| Weighted matching | |||||
| 32 | 0.002 (1.00) | 0.135 (61.2) | 0.613 (279) | 0.009 (4.00) | 0.109 (49.5) |
| 64 | 0.057 (1.00) | 1.51 (26.6) | 17.2 (302) | 0.111 (1.94) | 5.89 (103) |
| 128 | 1.86 (1.00) | 40.4 (21.7) | 556 (298) | 1.90 (1.02) | 367 (197) |
| 256 | 56.1 (1.00) | (20.0) | TO | 40.8 (0.73) | TO |
| 512 | TO | TO | TO | 1089 (–) | TO |
| 1024 | TO | TO | TO | TO | TO |
| TO | TO | TO | TO | TO | |
| TO | TO | TO | TO | TO | |
| Weighted b-matching | |||||
| 32 | 0.004 (1.00) | 0.111 (25.3) | 1.41 (320) | 0.084 (19.0) | 9.99 (2270) |
| 64 | 0.088 (1.00) | 2.04 (23.3) | 33.2 (378) | 2.14 (24.4) | (8954) |
| 128 | 3.93 (1.00) | 81.4 (20.7) | (94.5) | 54.0 (13.7) | TO |
| 256 | 154 (1.00) | TO | TO | TO | TO |
| 512 | TO | TO | TO | TO | TO |
| 1024 | TO | TO | TO | TO | TO |
| TO | TO | TO | TO | TO | |
| TO | TO | TO | TO | TO |
Table 28. Matroid intersection, geometric family [code 5] (, 5 instances per size, one run each).
Hybrid Solver for Minimum-Cost Flows. We evaluated on 18 families [49] in total, generated by NETGEN [47], GRIDGEN, GOTO [33] and GRIDGRAPH or converted from road networks [22] and vision instances. These are goto_8 [code 12], goto_sr [code 13], grid_long [code 17], grid_square [code 18], grid_wide [code 19], gridgen_8 [code 14], gridgen_deg [code 15], gridgen_sr [code 16], netgen_8 [code 20], netgen_deg [code 21], netgen_lo_8 [code 22], netgen_lo_sr [code 23], netgen_sr [code 24], road_flow [code 25], road_paths [code 25], vision_inv [code 26], vision_prop [code 26] and vision_rnd [code 26]. For reasons of brevity, we only display 5 of them, gridgen_deg, netgen_deg, netgen_lo_sr (which performed worst), road_paths (within the range of % to % for all others) and goto_8 (with exceptionally good performance), in Table 29 to Table 33. The first two proceed by density at fixed node count, the third by node count with increasing density, and the last two by the number of nodes at fixed density. As oracles we use network simplex [code 41], cost scaling [code 37], capacity scaling and successive shortest paths [code 36], whose code was taken from LEMON. For every family, size and algorithm, five different instances were run once each, and every time is the mean of these five runs. All times are compute times in milliseconds, measured after parsing. Oracle is the C++ solver’s initialisation and main loop, Cert. the emission of the certificate and Check the verified check. Glue is what is left of the solver’s entire compute time Total. The last column is the relative cost of verification, i.e. Total divided by Oracle. For each size, the row of the algorithm whose oracle is fastest is shaded grey. Note that we here use a higher timeout of 2 hours.
Table 29. Hybrid min-cost flow solver, gridgen_deg [code 15] family generated by GRIDGEN. A density sweep induced by degree increase at the fixed node count . The first column is the average in-degree which always equals the density.
| deg | Alg. | Oracle | Cert. | Check | Glue | Total | Total/Oracle | |
| 4 | 16388 | NS | 5.70 | 0.042 | 1.59 | 0.964 | 8.30 | 1.46 |
| COS | 13.0 | 0.227 | 1.72 | 1.39 | 16.3 | 1.26 | ||
| CAS | 65.1 | 0.152 | 1.62 | 1.44 | 68.3 | 1.05 | ||
| SSP | 9.86 | 0.101 | 1.59 | 1.38 | 12.9 | 1.31 | ||
| 8 | 32776 | NS | 14.9 | 0.196 | 2.08 | 1.60 | 18.8 | 1.26 |
| COS | 27.6 | 0.439 | 2.33 | 2.51 | 32.9 | 1.19 | ||
| CAS | 228 | 0.385 | 2.08 | 2.56 | 233 | 1.02 | ||
| SSP | 544 | 0.363 | 2.10 | 2.60 | 549 | 1.01 | ||
| 16 | 65552 | NS | 23.0 | 0.321 | 3.97 | 3.05 | 30.0 | 1.32 |
| COS | 38.0 | 0.810 | 4.53 | 4.74 | 48.0 | 1.26 | ||
| CAS | 420 | 0.661 | 3.98 | 4.95 | 430 | 1.02 | ||
| SSP | 1017 | 0.694 | 3.96 | 4.34 | 1026 | 1.01 | ||
| 32 | 131104 | NS | 30.0 | 0.621 | 11.5 | 6.06 | 48.0 | 1.60 |
| COS | 60.0 | 1.46 | 12.6 | 9.38 | 83.0 | 1.39 | ||
| CAS | 812 | 1.12 | 11.3 | 9.93 | 835 | 1.03 | ||
| SSP | 1208 | 1.09 | 11.4 | 9.56 | 1230 | 1.02 | ||
| 64 | 262208 | NS | 48.0 | 1.20 | 23.2 | 11.4 | 84.0 | 1.74 |
| COS | 108 | 2.70 | 25.3 | 19.3 | 155 | 1.44 | ||
| CAS | 2182 | 1.93 | 23.2 | 19.9 | 2227 | 1.02 | ||
| SSP | 1964 | 1.94 | 23.1 | 21.0 | 2010 | 1.02 | ||
| 128 | 524416 | NS | 74.0 | 2.21 | 45.4 | 24.1 | 146 | 1.97 |
| COS | 204 | 4.47 | 49.8 | 40.4 | 299 | 1.46 | ||
| CAS | 6048 | 3.47 | 45.6 | 42.9 | 6140 | 1.01 | ||
| SSP | 2947 | 3.15 | 45.5 | 42.3 | 3038 | 1.03 | ||
| 256 | 1048832 | NS | 107 | 3.93 | 60.6 | 80.9 | 252 | 2.37 |
| COS | 459 | 8.47 | 70.3 | 127 | 665 | 1.45 | ||
| CAS | 16650 | 6.45 | 60.6 | 136 | 16853 | 1.01 | ||
| SSP | 4574 | 6.48 | 60.6 | 139 | 4780 | 1.04 | ||
| 512 | 2097664 | NS | 174 | 8.59 | 181 | 109 | 472 | 2.71 |
| COS | 1149 | 16.5 | 199 | 221 | 1585 | 1.38 | ||
| CAS | 115550 | 13.5 | 180 | 237 | 115980 | 1.00 | ||
| SSP | 6478 | 13.8 | 183 | 245 | 6920 | 1.07 | ||
| 1024 | 4195328 | NS | 316 | 16.6 | 365 | 233 | 930 | 2.95 |
| COS | 2507 | 32.6 | 401 | 481 | 3421 | 1.36 | ||
| CAS | 501030 | 27.6 | 361 | 511 | 501930 | 1.00 | ||
| SSP | 12384 | 25.3 | 361 | 511 | 13281 | 1.07 | ||
| 8390656 | NS | 546 | 29.1 | 728 | 438 | 1741 | 3.19 | |
| COS | 5715 | 56.1 | 797 | 977 | 7545 | 1.32 | ||
| CAS | 1424300 | 60.5 | 734 | 1005 | 1426100 | 1.00 | ||
| SSP | 24552 | 52.0 | 724 | 1041 | 26369 | 1.07 | ||
| 16781312 | NS | 957 | 59.2 | 1471 | 889 | 3377 | 3.53 | |
| COS | 11638 | 127 | 1614 | 1988 | 15367 | 1.32 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | 43839 | 107 | 1455 | 2138 | 47539 | 1.08 |
Table 29.
| Alg. | Oracle | Cert. | Check | Glue | Total | Total/Oracle | ||
| 256 | NS | 0.638 | 0.011 | 0.175 | 0.211 | 1.03 | 1.62 | |
| COS | 2.81 | 0.024 | 0.186 | 0.260 | 3.28 | 1.17 | ||
| CAS | 5.39 | 0.025 | 0.177 | 0.264 | 5.86 | 1.09 | ||
| SSP | 32.9 | 0.045 | 0.170 | 0.276 | 33.4 | 1.01 | ||
| NS | 23.0 | 0.060 | 1.57 | 0.842 | 26.0 | 1.11 | ||
| COS | 40.0 | 0.260 | 1.62 | 1.27 | 43.0 | 1.08 | ||
| CAS | 132 | 0.205 | 1.57 | 1.29 | 135 | 1.02 | ||
| SSP | 3672 | 0.220 | 1.54 | 1.24 | 3675 | 1.00 | ||
| NS | 108 | 0.293 | 2.26 | 2.49 | 113 | 1.05 | ||
| COS | 139 | 0.598 | 2.34 | 3.34 | 145 | 1.04 | ||
| CAS | 2054 | 0.362 | 2.25 | 3.39 | 2060 | 1.00 | ||
| SSP | 26607 | 0.380 | 2.25 | 3.37 | 26613 | 1.00 | ||
| NS | 318 | 0.505 | 4.29 | 3.13 | 326 | 1.02 | ||
| COS | 247 | 1.01 | 4.52 | 4.87 | 258 | 1.04 | ||
| CAS | 1253 | 0.619 | 4.26 | 5.12 | 1263 | 1.01 | ||
| SSP | 69189 | 0.622 | 4.27 | 5.11 | 69199 | 1.00 | ||
| NS | 1271 | 0.823 | 8.44 | 5.74 | 1286 | 1.01 | ||
| COS | 655 | 1.74 | 9.01 | 9.79 | 676 | 1.03 | ||
| CAS | 3523 | 1.12 | 8.53 | 10.3 | 3543 | 1.01 | ||
| SSP | 274510 | 1.32 | 8.48 | 10.2 | 274530 | 1.00 | ||
| NS | 31593 | 1.69 | 17.2 | 12.1 | 31624 | 1.00 | ||
| COS | 2342 | 3.04 | 18.7 | 22.2 | 2386 | 1.02 | ||
| CAS | 185270 | 2.29 | 17.2 | 20.5 | 185310 | 1.00 | ||
| SSP | 1270300 | 2.30 | 17.2 | 80.5 | 1270400 | 1.00 | ||
| NS | 35666 | 3.08 | 34.1 | 25.8 | 35729 | 1.00 | ||
| COS | 5140 | 5.88 | 36.3 | 42.9 | 5225 | 1.02 | ||
| CAS | 34066 | 4.14 | 34.1 | 44.8 | 34149 | 1.00 | ||
| SSP | 3148600 | 4.13 | 34.1 | 61.8 | 3148700 | 1.00 |
Table 33. Hybrid min-cost flow solver, goto_8 [code 12] family generated by GOTO [33]. A node sweep at the fixed density .
| Alg. | Oracle | Cert. | Check | Glue | Total | Total/Oracle | ||
| NS | 152080 | 6.73 | 68.7 | 54.5 | 152210 | 1.00 | ||
| COS | 19734 | 12.9 | 73.1 | 92.0 | 19912 | 1.01 | ||
| CAS | 105990 | 8.02 | 68.9 | 93.1 | 106160 | 1.00 | ||
| SSP | TO | TO | TO | TO | TO | TO | ||
| NS | 3203400 | 12.9 | 140 | 147 | 3203700 | 1.00 | ||
| COS | 41971 | 25.8 | 155 | 211 | 42363 | 1.01 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | TO | TO | TO | TO | TO | TO | ||
| NS | 2413900 | 24.9 | 290 | 285 | 2414500 | 1.00 | ||
| COS | 270890 | 43.7 | 308 | 388 | 271630 | 1.00 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | TO | TO | TO | TO | TO | TO | ||
| NS | TO | TO | TO | TO | TO | TO | ||
| COS | 1009100 | 85.7 | 640 | 874 | 1010700 | 1.00 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | TO | TO | TO | TO | TO | TO | ||
| NS | TO | TO | TO | TO | TO | TO | ||
| COS | 656740 | 150 | 1489 | 1931 | 660310 | 1.00 | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | TO | TO | TO | TO | TO | TO | ||
| NS | TO | TO | TO | TO | TO | TO | ||
| COS | TO | TO | TO | TO | TO | TO | ||
| CAS | TO | TO | TO | TO | TO | TO | ||
| SSP | TO | TO | TO | TO | TO | TO |
Table 34. Hybrid min-cost flow solver, goto_8 family (continued from Table 33).
Hybrid Solver for Weighted Bipartite Matching. We ran an analogous hybrid solver with CSA [code 9] as oracle on the families of Table 22 to 24, with columns as above and each time the mean over ten instances, each the median of three runs (Table 35 to 37).
| SML | Scala | Go | SciPy LSA [code 52] | SciPy MWFBM CSR [code 53] | |
| 0.014 (1.00) | 0.817 (57.6) | 16.8 (1187) | 0.025 (1.78) | 0.003 (0.22) | |
| 0.053 (1.00) | 1.47 (27.8) | 60.4 (1139) | 0.122 (2.31) | 0.007 (0.14) | |
| 0.209 (1.00) | 3.69 (17.6) | 215 (1026) | 0.813 (3.88) | 0.020 (0.10) | |
| 0.786 (1.00) | 11.7 (14.9) | 885 (1126) | 3.93 (5.01) | 0.061 (0.08) | |
| 3.25 (1.00) | 46.0 (14.2) | TO | 21.2 (6.53) | 0.175 (0.05) | |
| JGraphT KM with GC [code 32] | JGraphT MWBM CSR [code 33] | JGraphT MWBM hash [code 33] | CSA CSR [code 9] | OR-Tools [code 11] | |
| 2.60 (184) | 0.107 (7.55) | 0.238 (16.8) | 0.001 (0.09) | 0.003 (0.22) | |
| 24.7 (467) | 0.314 (5.93) | 0.655 (12.4) | 0.003 (0.05) | 0.005 (0.10) | |
| 210 (1001) | 1.02 (4.86) | 1.63 (7.78) | 0.007 (0.03) | 0.012 (0.06) | |
| TO | 3.28 (4.18) | 4.36 (5.55) | 0.016 (0.02) | 0.031 (0.04) | |
| TO | 11.1 (3.41) | 17.3 (5.32) | 0.041 (0.01) | 0.071 (0.02) |
Table 22. Table 22. Hungarian method, low-cost family [code 3] (, 10 instances per size, averaged over the medians of 3 repeats per instance).
| Oracle | Cert. | Check | Glue | Total | Total/Oracle | ||
| 22528 | 1.29 | 0.116 | 0.042 | 0.774 | 2.22 | 1.72 | |
| 49152 | 2.90 | 0.247 | 0.092 | 1.64 | 4.88 | 1.68 | |
| 106496 | 7.12 | 0.555 | 0.197 | 3.63 | 11.5 | 1.61 | |
| 229376 | 16.3 | 1.35 | 0.437 | 8.25 | 26.3 | 1.62 | |
| 491520 | 41.8 | 4.96 | 1.50 | 20.8 | 69.1 | 1.65 | |
| 1048576 | 99.4 | 14.0 | 4.08 | 45.4 | 163 | 1.64 | |
| 2228224 | 284 | 37.3 | 9.75 | 96.9 | 427 | 1.51 | |
| 4718592 | 877 | 122 | 22.9 | 212 | 1234 | 1.41 | |
| 9961472 | 2193 | 227 | 45.0 | 424 | 2890 | 1.32 | |
| 20971520 | 6237 | 545 | 98.9 | 967 | 7849 | 1.26 |
Table 35. Hybrid bipartite matching solver with CSA [code 9] as oracle, low-cost family [code 3] (10 instances per size, averaged over the medians of 3 repeats per instance). A node sweep at the density .
Code References
code 1. 13th DIMACS Implementation Challenge: Network Flows 2.0: genrmf, http://coral.ise.lehigh.edu/flow-challenge-2-0/files/2026/09/genrmfDimacs.zip, last accessed on 13/10/2026
code 2. 13th DIMACS Implementation Challenge: Network Flows 2.0: washington, https://coral.ise.lehigh.edu//wp-content/uploads/washington.c, last accessed on 13/10/2026
code 3. 1st DIMACS Implementation Challenge: Network Flows and Matching: assign.c, https://archive.dimacs.rutgers.edu/pub/netflow/generators/network/assign.c, last accessed on 13/10/2026
code 4. 1st DIMACS Implementation Challenge: Network Flows and Matching: assign.c and twocost.a, https://archive.dimacs.rutgers.edu/pub/netflow/generators/network/assign.c, with https://archive.dimacs.rutgers.edu/pub/netflow/generators/network/twocost.a. Last accessed on 13/10/2026
code 5. 1st DIMACS Implementation Challenge: Network Flows and Matching: dcube.c and geomasn.a, https://archive.dimacs.rutgers.edu/pub/netflow/generators/matching/dcube.c, with https://archive.dimacs.rutgers.edu/pub/netflow/generators/network/geomasn.a. Last accessed on 13/10/2026
code 6. 9th DIMACS Implementation Challenge: Shortest Paths: Code suite ch9-1.1 (spgrid, sprand), http://www.diag.uniroma1.it/~challenge9/code/ch9-1.1.tar.gz, last accessed on 13/10/2026
code 7. 9th DIMACS Implementation Challenge: Shortest Paths: USA-road-t, download, http://www.diag.uniroma1.it/~challenge9/download.shtml, last accessed on 13/10/2026
code 8. Cherkassky, B.V., Goldberg, A.V.: ak. PRF 1.8, Andrew Goldberg’s Network Optimization Library, http://web.archive.org/web/2018id_/http://www.avglab.com/andrew/soft/prf.tar, last accessed on 13/10/2026
code 9. Goldberg, A.V.: CSA. Andrew Goldberg’s Network Optimization Library, http://web.archive.org/web/20191209133545/http://www.avglab.com:80/andrew/soft.html, CSA 1.2, built as csa_q. Last accessed on 13/10/2026
code 10. Goldberg, A.V.: HIPR. Andrew Goldberg’s Network Optimization Library, http://web.archive.org/web/20191209133545/http://www.avglab.com:80/andrew/soft.html, hi_pr 3.5. Last accessed on 13/10/2026
code 11. Google OR-Tools: Solving an assignment problem: Linear sum assignment solver, https://developers.google.com/optimization/assignment/linear_assignment, OR-Tools 9.15.6755. Last accessed on 10/10/2026
code 12. Kovács, P.: goto_8.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/goto_8.sh, last accessed on 14/10/2026
code 13. Kovács, P.: goto_sr.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/goto_sr.sh, last accessed on 14/10/2026
code 14. Kovács, P.: gridgen_8.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/gridgen_8.sh, last accessed on 14/10/2026
code 15. Kovács, P.: gridgen_deg.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/gridgen_deg.sh, last accessed on 14/10/2026
code 16. Kovács, P.: gridgen_sr.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/gridgen_sr.sh, last accessed on 14/10/2026
code 17. Kovács, P.: grid_long.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/grid_long.sh, last accessed on 14/10/2026
code 18. Kovács, P.: grid_square.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/grid_square.sh, last accessed on 14/10/2026
code 19. Kovács, P.: grid_wide.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/grid_wide.sh, last accessed on 14/10/2026
code 20. Kovács, P.: netgen_8.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/netgen_8.sh, last accessed on 14/10/2026
code 21. Kovács, P.: netgen_deg.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/netgen_deg.sh, last accessed on 14/10/2026
code 22. Kovács, P.: netgen_lo_8.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/netgen_lo_8.sh, last accessed on 14/10/2026 code 23. Kovács, P.: netgen_lo_sr.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/netgen_lo_sr.sh, last accessed on 14/10/2026
code 24. Kovács, P.: netgen_sr.sh. Benchmark Data for the Minimum-Cost Flow Problem, https://lemon.cs.elte.hu/trac/lemon/raw-attachment/wiki/MinCostFlowData/netgen_sr.sh, last accessed on 14/10/2026
code 25. Kovács, P.: Road instances. Benchmark Data for the Minimum-Cost Flow Problem, http://lime.cs.elte.hu/~kpeter/data/mcf/road/, last accessed on 14/10/2026
code 26. Kovács, P.: Vision instances. Benchmark Data for the Minimum-Cost Flow Problem, http://lime.cs.elte.hu/~kpeter/data/mcf/vision/, last accessed on 14/10/2026
code 27. Lammich, P., Sefidgar, S.R.: Formalizing push-relabel algorithms. Arch. Formal Proofs (Jun 2017), https://isa-afp.org/entries/Prpu_Maxflow.html
code 28. The JGraphT Developers: BreadthFirstIterator, https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/traverse/BreadthFirstIterator.html, JGraphT 1.5.3. Last accessed on 12/10/2026
code 29. The JGraphT Developers: DepthFirstIterator, https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/traverse/DepthFirstIterator.html, JGraphT 1.5.3. Last accessed on 15/10/2026
code 30. The JGraphT Developers: IntVertexDijkstraShortestPath, https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/shortestpath/IntVertexDijkstraShortestPath.html, JGraphT 1.5.3. Last accessed on 11/10/2026
code 31. The JGraphT Developers: KruskalMinimumSpanningTree, https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/spanning/KruskalMinimumSpanningTree.html, JGraphT 1.5.3. Last accessed on 15/10/2026
code 32. The JGraphT Developers: KuhnMunkresMinimalWeightBipartitePerfectMatching, https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/matching/KuhnMunkresMinimalWeightBipartitePerfectMatching.html, JGraphT 1.5.3. Last accessed on 10/10/2026
code 33. The JGraphT Developers: MaximumWeightBipartiteMatching, https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/matching/MaximumWeightBipartiteMatching.html, JGraphT 1.5.3. Last accessed on 10/10/2026
code 34. The JGraphT Developers: PushRelabelMFImpl, https://jgrapht.org/javadoc/org.jgrapht.core/org/jgrapht/alg/flow/PushRelabelMFImpl.html, JGraphT 1.5.3. Last accessed on 13/10/2026
code 35. The LEMON Developers: Bfs< GR, TR > class template reference, https://lemon.cs.elte.hu/pub/doc/1.3.1/a00051.html, LEMON 1.3.1. Last accessed on 12/10/2026
code 36. The LEMON Developers: Capacityscaling< GR, V, C, TR > class template reference, https://lemon.cs.elte.hu/pub/doc/1.3.1/a00074.html, LEMON 1.3.1. Last accessed on 14/10/2026
code 37. The LEMON Developers: Costscaling< GR, V, C, TR > class template reference, https://lemon.cs.elte.hu/pub/doc/1.3.1/a00109.html, LEMON 1.3.1. Last accessed on 14/10/2026
code 38. The LEMON Developers: Dfs< GR, TR > class template reference, https://lemon.cs.elte.hu/pub/doc/1.3.1/a00119.html, LEMON 1.3.1. Last accessed on 15/10/2026
AI-Assisted Development
Style Statistics
To make the stylistic conventions of the library measurable, we use a set of statistics that are computed mechanically from the theory sources. The depth-first and breadth-first search theories (DFS.thy and BFS_2.thy) serve as the reference: their values define the target range. The other columns of Table 39 give the values for the Hopcroft–Karp development before and after the restyling. Both columns cover five theories. The restyling renamed and reorganised them: the characterisation of augmenting paths, the top loop, a new generic search for disjoint paths, the implementation of a phase, and the executable example. For the layering statistics, the reference columns cover the whole families, i.e. also DFS_Example, BFS_Subprocedures and BFS_Example.
All statistics are computed by two scripts. They do not use Isabelle; they work on the source text, as follows:
Comments are removed.
The contents of inner-syntax strings and cartouches are masked, so that keywords occurring inside terms are not counted.
Each theory is split into its top-level commands.
Each lemma (a lemma, theorem, corollary or proposition command; lemmas is not counted) is split into its statement and its proof. The proof begins at the first proof keyword (by, apply, proof, using, unfolding, including, supply, subgoal).
Unless stated otherwise, “per lemma” means a total over all proofs divided by the number of lemmas. A share of method calls is taken over all method calls in the group.
Size. Proofs and specifications are counted separately, in non-blank lines. Comments, top-level text blocks and section headings are not counted in either.
Proof lines The lines of all proofs: the proofs of lemmas, the proofs of interpretation, global_interpretation and sublocale commands, and the proofs of function definitions.
Definition and specification lines The lines of all lemma statements, all definitions (definition, abbreviation, fun, function, partial_function, primrec, record, datatype), the headers of locales and contexts (parents, fixes, assumes), and the instantiation part of interpretations.
Lemmas The number of lemma commands as defined above. It is the denominator of all per-lemma figures.
Loop-template lemmas The lemmas that the loop template of the reference theories prescribes, recognised by their names. They are:
branch conditions;
the four standard lemmas
_cases,_simps,_inductand_domintros;the elimination, introduction and preservation lemmas of the invariants;
termination;
the initial state, the return branches, the final lemmas and the executable twin.
They are short and uniform. In the reference theories they make up about four fifths of all lemmas.
Proof form. These statistics classify each proof by the commands it uses. They indicate how much of the reasoning is delegated to a single call of an automatic method.
Single-step proofs The share of lemmas whose proof contains no proof and no apply. Such a proof consists of one by call, possibly preceded by using or unfolding, and possibly with two methods (by ).
Structured The share of lemmas whose proof contains at least one proof, i.e. an Isar proof with intermediate steps.
With apply The share of lemmas whose proof is a sequence of apply steps, with no proof. A structured proof that uses apply inside it, as the loop lemmas of DFS do, is counted as structured.
Proof length. The length of a proof is its number of non-blank lines, from its first proof keyword to the end of the command.
Median, mean and 90th percentile The distribution of proof lengths over all lemmas. A median of one or two lines means that most lemmas are proved by one call.
Proof lines per statement line The total number of proof lines divided by the total number of statement lines. It relates the effort spent on proofs to the size of what is proved.
Steps per structured proof The mean number of have, show, hence, thus and obtain commands in a structured proof. It measures how finely a structured proof is subdivided.
Handling of facts. These statistics describe how intermediate and assumed facts are named and passed on. Explicit names and explicit forward application point to proofs that spell out book-keeping which the automatic methods could find themselves.
Labelled have/show/obtain The number of intermediate facts given a name (have h: ..., also with show, obtain, hence and thus), per lemma.
[OF ...] The number of explicit instantiations of a theorem with given facts, per lemma.
using The number of using commands, per lemma. Each one inserts named facts into a goal.
Facts quoted as cartouches The number of cartouches in proofs that do not open a text block or a comment, per lemma. These are mostly references to earlier facts by their statement. The count also includes cartouches used as method arguments, so it is approximate.
Named assumptions The number of assumptions given a name in the statement (assumes h: ... or and h: ...), per lemma. The reference theories refer to assumptions by position (assms(2)) or by statement instead.
Proof methods. For each by, apply and proof, the name of the first method that follows is recorded. Each row gives the share of one method among all recorded calls.
auto, force and fastforce The automatic methods that combine simplification with classical reasoning. They are the usual closing methods in the reference theories.
simp Simplification alone.
rule The application of one named rule. A high share indicates step-by-step forward reasoning.
metis and smt Calls to proof reconstruction from external provers. They are excluded by the rules of this project, although the BFS theory still contains some.
Closing calls inside structured proofs. These statistics are computed over the by calls inside structured proofs only.
by (rule ...) The share of calls that apply a single rule.
Bare by simp/auto/blast/... The share of calls to an automatic method without any arguments (simp, auto, blast, force, fastforce, linarith, presburger, simp_all, arith, fast). A high share indicates many small steps, each of which is trivial.
Method modifiers. The number of occurrences of a modifier in proofs, per lemma.
elim!: and intro!: Rules declared as safe elimination and introduction rules for a single call. In the reference theories these modifiers mostly carry the named theorem collections (call_cond_elims, invar_props_elims, invar_props_intros). Their frequency therefore shows how far proofs are driven by these collections rather than by individual facts.
Statements.
Plain form The share of lemmas stated as a single proposition, without assumes/shows. Premises are then written as .
⟦ per statement The number of premise brackets in statements, per lemma. It shows how often several premises are stated in this compact form.
Lemmas with an attribute The share of lemmas declared with an attribute, such as [simp] or [invar_holds_intros]. Attributes make a lemma available to later automatic calls, so this share measures how far the theory prepares its own automation.
Layout.
by (using) opening its own line The share of occurrences of by (using) inside proofs that begin a new line. The keyword that opens a proof is counted as beginning a line, so the figure mainly reflects the steps inside structured proofs. The reference theories place using and by on their own indented lines; they do not append them to the stated fact.
proof-/proof( versus proof -/proof ( The number of occurrences of each spelling. The reference theories write these keywords without a space.
Line length, 95th percentile The length, in characters, that 95% of the non-blank lines do not exceed.
Definitions and program state.
State records The number of record commands. In the reference theories, a record holds the complete state of an algorithm.
Loops as function (domintros) over one record The number of loops defined by the function package with domain introduction rules generated, whose single argument is a state record. The number of arguments is counted by the script; that the argument is a record was checked in the source.
Loops written as fun Recursive algorithm definitions by fun, which the reference theories do not use for loops.
Executable twins The number of partial_function (tailrec) definitions. Each is an executable copy of a loop, related to it by a lemma.
named_theorems declared The number of named theorem collections declared, such as invar_holds_intros and call_cond_elims. They are the means by which proofs refer to whole families of lemmas.
Untyped definitions The number of definitions given as an equation without a type signature, out of all definitions.
Invariants.
invar_* definitions The number of definitions whose name begins with invar_, i.e. the number of separately stated invariants of the algorithm states.
Complete families The number of these invariants that have the full family of lemmas of the reference theories:
an elimination form
invar_x_props;an introduction form
invar_x_intro;at least one preservation lemma for a branch of the loop (
invar_x_holds_i);the preservation lemma for the whole loop (
invar_x_holds).
Uses of [invar_holds_intros] The number of lemmas registered in the collection of preservation lemmas.
Naming.
Mean lemma-name length and parts The mean number of characters, and the mean number of parts separated by underscores, over all named lemmas. Short names with few parts point to names that do not say what the lemma is about.
Constants with the prefix hk_ The number of defined constants whose names begin with hk_. The library writes the name of an algorithm out in full.
Global abbreviations named with characters The number of abbreviations with names of at most three characters, such as es or CG.
Layering. These statistics concern the arrangement of algorithms, sub-procedures and implementations in locales and theories. Each theory is in one of three classes:
the example theory (
*_Example), the only theory in which the reference algorithms are instantiated with concrete data structures;the sub-procedure theory (
*_Subprocedures), which implements the sub-procedures of an algorithm;an algorithm theory, which is any other theory.
Interpretations in algorithm theories, in the sub-procedure theory and in the example theory The number of global_interpretation and interpretation commands in theories of each class, given as global/plain. In the reference families, interpretations occur only in the example theories.
sublo-cale commands The number of sublocale commands. The reference theories do not use them to relate algorithms.
Algorithm theories importing concrete data structures The number of algorithm theories that import an implementation by red-black trees, or a theory that builds an executable instance on one.
Locales with qualified data-structure parents The number of locale definitions that import a data-structure specification as a qualified parent (Graph: Pair_Graph_Specs, set_ops: Set2). Locales that only inherit such a parent are not counted.
Sub-procedure contracts in the definitions locale Whether the specifications of the sub-procedures, which are parameters of a loop, are assumptions of the locale that defines the loop (as in BFS), or of a separate locale used only for proofs. This was determined by reading the source; “–” means that there are no sub-procedures.
Limitations. The statistics are computed from the source text, not from the logical content that Isabelle constructs, so some of them are approximations:
the count of cartouches used as fact references;
the classification of a
byat the start of a proof as beginning a line;the recording of only the first method of a call with two methods.
They measure conformity of form; they do not measure the difficulty of the mathematics. A theory without loops, such as the characterisation of augmenting paths in Alt_BFS_Bipartite, naturally has longer structured proofs than a loop theory, even when it is written in the same style.
References
- [1]Leanprover-community/mathlib4. leanprover-community (2024), https://github.com/leanprover-community/mathlib4
- [2]Functional Data Structures and Algorithms: A Proof Assistant Approach. 1 edn. (2025)DOI
- [3]Abdulaziz, M., Ammer, T.: A Formal Analysis of Capacity Scaling Algorithms for Minimum Cost Flows. In: 15th Int. Conf. Interact. Theorem Proving ITP (2024). https://doi.org/10.4230/LIPIcs.ITP.2024.3
- [4]Abdulaziz, M., Ammer, T., Madlener, C.: Formal Primal-Dual Algorithm Analysis. In: 17th Int. Conf. Interact. Theorem Proving ITP. LIPIcs (2026). https://doi.org/10.4230/LIPIcs.ITP.2026.33
- [5]Abdulaziz, M., Ammer, T., Meenakshisundaram, S., Rimpapa, A.: A Formal Analysis of Algorithms for Matroids and Greedoids. In: 16th Int. Conf. Interact. Theorem Proving ITP (2025). https://doi.org/10.48550/arXiv.2505.19816
- [6]Abdulaziz, M., Madlener, C.: A Formal Analysis of RANKING. In: 14th Conf. Interact. Theorem Proving ITP (2023). https://doi.org/10.48550/arXiv.2302.13747
- [7]Abdulaziz, M., Mehlhorn, K.: A Formal Correctness Proof of Edmonds’ Blossom Shrinking Algorithm. Accept. Publ. J. Autom. Reason. (2025)arxiv.org/abs/2412.20878
- [8]Aggarwal, P., Parno, B., Welleck, S.: AlphaVerus: Bootstrapping formally verified code generation through self-improving translation and treetreatment. In: 42nd Int. Conf. Mach. Learn. ICML. Proc. Mach. Learn. Res., vol. 267, pp. 587–615 (2025)arxiv.org/abs/2412.06176
- [9]Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall (1993)
- [10]Ahuja, R., Avigad, J., Tetali, P., Welleck, S.: ImProver: Agent-based automated proof optimization. In: 13th Int. Conf. Learn. Represent. ICLR (2025)arxiv.org/abs/2410.04753
- [11]Alkassar, E., Böhmе, S., Mehlhorn, K., Rizkallah, C.: A Framework for the Verification of Certifying Computations. J. Autom. Reason. (2014). https://doi.org/10.1007/S10817-013-9289-2
- [12]Baier, C., Katoen, J.P.: Principles of Model Checking (2008)
- [13]Bairi, R., Sonwane, A., Kanade, A., C, V.D., Iyer, A., Parthasarathy, S., Rajamani, S., Ashok, B., Shet, S.: CoDePlan: Repository-level coding using LLMs and planning. Proc. ACM Softw. Eng. 1(FSE), 675–698 (2024). https://doi.org/10.1145/3643757
- [14]Ballarin, C.: Locales: A Module System for Mathematical Theories. J. Autom. Reason. (2014). https://doi.org/10.1007/s10817-013-9284-7
- [15]Bellman, R.: On a routing problem. Q. Appl. Math. (1958). https://doi.org/10.1090/qam/102435
- [16]Berge, C.: Two theorems in graph theory. Proc. Natl. Acad. Sci. (1957). https://doi.org/10.1073/pnas.43.9.842
- [17]Biró, P., van de Klundert, J., Manlove, D., Pettersson, W., Andersson, T., Burnapp, L., Chromy, P., Delgado, P., Dworczak, P., Haase, B., Hemke, A., Johnson, R., Klimentova, X., Kuypers, D., Nanni Costa, A., Smeulders, B., Spieksma, F., Valentín, M.O., Viana, A.: Modelling and optimisation in European Kidney Exchange Programmes. Eur. J. Oper. Res. (2021). https://doi.org/10.1016/j.ejor.2019.09.006
- [18]Blanchette, J.C., Haslbeck, M., Matichuk, D., Nipkow, T.: Mining the Archive of Formal Proofs. In: Intell. Comput. Math. CICM. LNCS, vol. 9150, pp. 3–17 (2015). https://doi.org/10.1007/978-3-319-2615-8_1
- [19]Bonet, B., Geffner, H.: Planning as heuristic search. Artif. Intell. (2001). https://doi.org/10.1016/S0004-3702(01)00108-4
- [20]Bulwahn, L., Krauss, A., Haftmann, F., Erkök, L., Matthews, J.: Imperative functional programming with isabelle/hol. In: Mohamed, O.A., Muñoz, C., Tahar, S. (eds.) Theorem Proving in Higher Order Logics. pp. 134–149. Springer Berlin Heidelberg, Berlin, Heidelberg (2008)DOI
- [21]Cherkassky, B.V., Goldberg, A.V.: On implementing the push-relabel method for the maximum flow problem. Algorithmica 19(4), 390–410 (1997). https://doi.org/10.1007/PL00009180, hi_pr 3.5
- [22]Demetrescu, C., Goldberg, A.V., Johnson, D.S. (eds.): The Shortest Path Problem: Ninth DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 74. American Mathematical Society (2009). https://doi.org/10.1090/dimacs/074
- [23]Developers, T.S.: The Abstract Matroid Class - Matroid Theory, https://doc.sagemath.org/html/en/reference/matroids/sage/matroids/matroid.html, last accessed on 25/03/2025
- [24]Dezső, B., Jüttner, A., Kovács, P.: LEMON – an open source C++ graph template library. Electron. Notes Theor. Comput. Sci. 264(5), 23–45 (2011). https://doi.org/10.1016/j.entcs.2011.06.003
- [25]Edmonds, C.: Undirected Graph Theory. Arch. Formal Proofs (Sep 2022), https://isa-afp.org/entries/Undirected_Graph_Theory.html
- [26]Edmonds, C.: Hypergraphs. Arch. Formal Proofs (Sep 2023), https://isa-afp.org/entries/Hypergraph_Basics.html
- [27]Edmonds, J.: Paths, Trees, and Flowers. Can. J. Math. (1965/ed). https://doi.org/10.4153/CJM-1965-045-4
- [28]First, E., Rabe, M.N., Ringer, T., Brun, Y.: Baldur: Whole-Proof Generation and Repair with Large Language Models. In: Proc. 31st ACM Jt. Eur. Softw. Eng. Conf. Symp. Found. Softw. Eng. (2023). https://doi.org/10.1145/3611643.3616243
- [29]Frank, A.: A Weighted Matroid Intersection Algorithm. J. Algorithms (1981). https://doi.org/10.1016/0196-6774(81)90032-8
- [30]Gallai, T.: Kritische Graphen II. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8, 373–395 (1963)
- [31]Gallai, T.: Maximale Systeme unabhängiger Kanten. Magyar Tud. Akad. Mat. Kutató Int. Közl. 9, 401–413 (1964)
- [32]Goldberg, A.V., Kennedy, R.: An efficient cost scaling algorithm for the assignment problem. Math. Program. 71(2), 153–177 (1995). https://doi.org/10.1007/BF01585996, CSA 1.2
- [33]Goldberg, A.V., Kharitonov, M.: On implementing scaling push-relabel algorithms for the minimum-cost flow problem. In: Johnson, D.S., McGeoch, C.C. (eds.) Network Flows and Matching: First DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 12, pp. 157–198. American Mathematical Society (1993). https://doi.org/10.1090/dimacs/012/07
- [34]Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921–940 (1988). https://doi.org/10.1145/48014.61051
- [35]Greenaway, D., Andronick, J., Klein, G.: Bridging the Gap: Automatic Verified Abstraction of C. In: Interact. Theorem Proving (2012). https://doi.org/10.1007/978-3-642-32347-8_8
- [36]Gu, A., Piotrowski, B., Gloeckle, F., Yang, K., Markosyan, A.H.: ProofOptimizer: Training language models to simplify proofs without human demonstrations. In: 14th Int. Conf. Learn. Represent. ICLR (2026)arxiv.org/abs/2510.15700
- [37]Haftmann, F., Nipkow, T.: Code Generation via Higher-Order Rewrite Systems. In: Funct. Log. Program. FLOPS. pp. 103–117 (2010). https://doi.org/10.1007/978-3-642-12251-4_9
- [38]Haslbeck, M.P.L., Lammich, P., Biendarra, J.: Kruskal’s Algorithm for Minimum Spanning Forest. Arch. Formal Proofs (Feb 2019), https://isa-afp.org/entries/Kruskal.html
- [39]Hoare, C.A.R.: Proof of correctness of data representations. Acta Informatica (1972). https://doi.org/10.1007/BF00289507
- [40]Jacobi, C.G.: De investigando Ordine Systematis Aequationum Differentialium vulgarium cuiuscumque. Journal für die reine und angewandte Mathematik 64, 297–320 (1890), https://www.lix.polytechnique.fr/~ollivier/JACOBI/Jacobi_De_Investigando.pdf
- [41]Jiang, A.Q., Welleck, S., Zhou, J.P., Li, W., Liu, J., Jamnik, M., Lacroix, T., Wu, Y., Lample, G.: Draft, sketch, and prove: Guiding formal theorem provers with informal proofs. In: 11th Int. Conf. Learn. Represent. ICLR (2023)arxiv.org/abs/2210.12283
- [42]Jiang, X., Dong, Y., Wang, L., Fang, Z., Shang, Q., Li, G., Jin, Z., Jiao, W.: Self-planning code generation with large language models. ACM Trans. Softw. Eng. Methodol. 33(7), 1–30 (2024). https://doi.org/10.1145/3672456
- [43]Johnson, D.S., McGeoch, C.C. (eds.): Network Flows and Matching: First DIMACS Implementation Challenge, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 12. American Mathematical Society (1993). https://doi.org/10.1090/dimacs/012
- [44]Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38(4), 325–340 (1987). https://doi.org/10.1007/BF02278710
- [45]Kappelmann, K., Huch, F., Stevens, L., Abdulaziz, M.: Proof-Producing Translation of Functional Programs into a Time & Space Reasonable Model (2025). https://doi.org/10.48550/arXiv.2503.02975
- [46]Klein, M.: A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. Manag. Sci. (1967). https://doi.org/10.1287/mnsc.14.3.205
- [47]Klingman, D., Napier, A., Stutz, J.: NETGEN: A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. Manag. Sci. 20(5), 814–821 (1974). https://doi.org/10.1287/mnsc.20.5.814
- [48]Korte, B., Vygen, J.: Combinatorial Optimization (2012). https://doi.org/10.1007/978-3-642-24488-9
- [49]Kovács, P.: Minimum-cost flow algorithms: An experimental evaluation. Optim. Methods Softw. 30(1), 94–127 (2015). https://doi.org/10.1080/10556788.2014.895828
- [50]Krauss, A.: Partial recursive functions in higher-order logic. In: Furbach, U., Shankar, N. (eds.) Automated Reasoning. pp. 589–603. Springer Berlin Heidelberg, Berlin, Heidelberg (2006)
- [51]Krauss, A.: Automating Recursive Definitions and Termination Proofs in Higher-Order Logic. Ph.D. thesis, Technical University Munich (2009), http://mediatum2.ub.tum.de/doc/681651/document.pdf
- [52]Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. (1956). https://doi.org/10.1090/S0002-9939-1956-0078686-7
- [53]Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. (1955). https://doi.org/10.1002/nav.3800020109
- [54]Kuhn, H.W.: Variants of the Hungarian method for assignment problems. Nav. Res. Logist. Q. 3(4), 253–258 (1956). https://doi.org/10.1002/nav.3800030404
- [55]Lammich, P.: Refinement for Monadic Programs. Arch Form. Proofs (2012), https://www.isa-afp.org/entries/Refine_Monadic.shtml
- [56]Lammich, P.: Generating Verified LLVM from Isabelle/HOL. In: 10th Int. Conf. Interact. Theorem Proving ITP 2019 (2019). https://doi.org/10.4230/LIPIcs.ITP.2019.22
- [57]Lammich, P.: Refinement to Imperative HOL. J. Autom. Reason. (2019). https://doi.org/10.1007/s10817-017-9437-1
- [58]Lammich, P.: Refinement of Parallel Algorithms down to LLVM. In: 13th Int. Conf. Interact. Theorem Proving ITP (2022). https://doi.org/10.4230/LIPIcs.ITP.2022.24
- [59]Lammich, P., Lochbihler, A.: The Isabelle Collections Framework. In: Interact. Theorem Proving (2010). https://doi.org/10.1007/978-3-642-14052-5_24
- [60]Lammich, P., Lochbihler, A.: Automatic Refinement to Efficient Data Structures: A Comparison of Two Approaches. J Autom Reasoning (2019). https://doi.org/10.1007/s10817-018-9461-9
- [61]Lammich, P., Meis, R.: A Separation Logic Framework for Imperative HOL. Arch Form. Proofs (2012), https://www.isa-afp.org/entries/Separation_Logic_Imperative_HOL.shtml
- [62]Lammich, P., Nipkow, T.: Proof Pearl: Purely Functional, Simple and Efficient Priority Search Trees and Applications to Prim and Dijkstra. In: 10th Int. Conf. Interact. Theorem Proving ITP (2019). https://doi.org/10.4230/LIPIcs.ITP.2019.23
- [63]Lammich, P., Nipkow, T.: Purely Functional, Simple, and Efficient Implementation of Prim and Dijkstra. Arch. Formal Proofs (Jun 2019). https://isa-afp.org/entries/Prim_Dijkstra_Simple.html
- [64]Lammich, P., Seifgdar, S.R.: Flow Networks and the Min-Cut-Max-Flow Theorem. Arch. Formal Proofs (Jun 2017), https://isa-afp.org/entries/Flow_Networks.html
- [65]Lammich, P., Seifgdar, S.R.: Maximal Network Flow Algorithms: A Refinement Approach in Isabelle/HOL. J. Autom. Reason. (2019). https://doi.org/10.1007/s10817-017-9442-4
- [66]Lammich, P., Tuerk, T.: Applying Data Refinement for Monadic Programs to Hopcroft’s Algorithm. In: Interact. Theorem Proving (2012). https://doi.org/10.1007/978-3-642-32347-8_12
- [67]Lawler, E.L.: Matroid Intersection Algorithms. Math. Program. (1975). https://doi.org/10.1007/BF01681329
- [68]Lee, G.: Correctness of ford-fulkerson’s maximum flow algorithm1. Formaliz. Math. (2005)
- [69]Lu, J., Wan, Y., Huang, Y., Xiong, J., Liu, Z., Guo, Z.: FormalAlign: Automated alignment evaluation for autoformalization. In: 13th Int. Conf. Learn. Represent. ICLR (2025)arxiv.org/abs/2410.10135
- [70]Mehlhorn, K., Näher, S.: LEDA: A Platform for Combinatorial and Geometric Computing (1999), http://www.mpi-sb.mpg.de/%7Emehlhorn/LEDAbook.html
- [71]Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: AdWords and generalized online matching. J. ACM (2007). https://doi.org/10.1145/1284320.1284321
- [72]Michail, D., Kinable, J., Naveh, B., Sichi, J.V.: JGraphT – a Java library for graph data structures and algorithms. ACM Trans. Math. Softw. 46(2), 1–29 (2020). https://doi.org/10.1145/3381449
- [73]Mohan, A., Leow, W.X., Hobor, A.: Functional Correctness of C Implementations of Dijkstra’s, Kruskal’s, and Prim’s Algorithms. In: Comput. Aided Verification (2021). https://doi.org/10.1007/978-3-030-81688-9_37
- [74]Nipkow, T., Paulson, L.C., Wenzel, M.: Isabelle/HOL - A Proof Assistant for Higher-Order Logic (2002). https://doi.org/10.1007/3-540-45949-9
- [75]Noshchinski, L.: A Graph Library for Isabelle. Math. Comput. Sci. (2015). https://doi.org/10.1007/S11786-014-0183-Z
- [76]Perron, L., Furnon, V.: OR-Tools, https://developers.google.com/optimization/, OR-Tools 9.15.6755. Last accessed on 13/10/2026
- [77]Schirmer, N.: A Verification Environment for Sequential Imperative Programs in Isabelle/HOL. In: Log. Program. Artif. Intell. Reason. (2005). https://doi.org/10.1007/978-3-540-32275-7_26
- [78]Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency (2003)
- [79]Siek, J.G., Lee, L.Q., Lumsdaine, A.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley (2002), https://www.boost.org/doc/libs/release/libs/graph/
- [80]Song, P., Yang, K., Anandkumar, A.: Lean Copilot: Large language models as copilots for theorem proving in Lean. In: 2nd Int. Conf. Neuro-Symb. Syst. NeuS. Proc. Mach. Learn. Res., vol. 288, pp. 144–169 (2025)arxiv.org/abs/2404.12534
- [81]Stevens, L., Ghidini, R.: Simplified and verified: A second look at a proof-producing union-find algorithm. In: Automated Deduction – CADE 30: 30th International Conference on Automated Deduction, Stuttgart, Germany, July 28–31, 2025, Proceedings. p. 261–279. Springer-Verlag, Berlin, Heidelberg (2025). https://doi.org/10.1007/978-3-031-99984-0_15, https://doi.org/10.1007/978-3-031-99984-0_15
- [82]Stübinger, T., Hupel, L.: Extending Isabelle/HOL’s Code Generator with Support for the Go Programming Language. In: Form. Methods (2025). https://doi.org/10.1007/978-3-031-71177-0_1
- [83]The NetworkX Developers: NetworkX reference, https://networkx.org/documentation/stable/reference/index.html, NetworkX 3.4.2. Last accessed on 10/10/2026
- [84]The SciPy Community: SciPy API reference, https://docs.scipy.org/doc/scipy/reference/, SciPy 1.15.3. Last accessed on 10/10/2026
- [85]Vazirani, V.V.: Approximation Algorithms
- [86]Wang, H., Xin, H., Liu, Z., Li, W., Huang, Y., Lu, J., Yang, Z., Tang, J., Yin, J., Li, Z., Liang, X.: Proving Theorems Recursively. Adv. Neural Inf. Process. Syst. (2024), https://papers.nips.cc/paper_files/paper/2024/hash/9de7a49945898da86e062e7029baa284-Abstract-Conference.htmlarxiv.org/abs/2405.14414
- [87]Watt, C., Trela, M., Lammich, P., Märkl, F.: Wasmref-isabelle: A verified monadic interpreter and industrial fuzzing oracle for webassembly. Proc. ACM Program. Lang. 7(PLDI), 100–123 (2023). https://doi.org/10.1145/3591224, https://doi.org/10.1145/3591224
- [88]Wirth, N.: Program Development by Stepwise Refinement. Commun. ACM (1971). https://doi.org/10.1145/362575.362577
- [89]Xin, H., Ren, Z.Z., Song, J., Shao, Z., Zhao, W., Wang, H., Liu, B., Zhang, L., Lu, X., Du, Q., Gao, W., Zhu, Q., Yang, D., Gou, Z., Wu, Z.F., Luo, F., Ruan, C.: DeepSeek-Prover-V1.5: Harnessing Proof Assistant Feedback for Reinforcement Learning and Monte-Carlo Tree Search (2024). https://doi.org/10.48550/arXiv.2408.08152
- [90]Zhong, Z., Raghunathan, A., Carlini, N.: ImpossibleBench: Measuring LLMs’ propensity of exploiting test cases. In: 14th Int. Conf. Learn. Represent. ICLR (2026)arxiv.org/abs/2510.20270
- [91]Zhou, J.P., Staats, C.E., Li, W., Szegedy, C., Weinberger, K.Q., Wu, Y.: Don’t Trust: Verify – Grounding LLM Quantitative Reasoning with Autoformalization. In: The Twelfth International Conference on Learning Representations (2023), https://openreview.net/forum?id=V5tdi14plearxiv.org/abs/2403.18120