betaFeedback

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).

AlgorithmProvedLines
Reachability and cycle detection
Depth-first search [2]T, C877
Breadth-first search [2]T, C1,805
Cycle detectionT, C3,305
Directed cycle detectionT, C697
Shortest paths
BFS with distancesT, C2,901
Bellman–FordC, O2,837
DijkstraT, C, O2,865
Maximum flow
DinicT, C, O1,455
Blocking flowT, C713
DFS with backtrackingT, C746
Push-relabelT, C, O4,897
Minimum-cost flow
Successive shortest paths [3]T, C, O1,158
Capacity scaling [3]T, C, O1,785
Orlin [3]T, C, O12,080
Network simplexT, C, O7,582
Acyclic flowsT, C10,691
Spanning trees and matroids
Best-in-greedy [5]T, C, A, O5,750
Kruskal [5]T, C, O1,559
Greedoid greedy [5]T, C, O2,217
Jarník–Prim [5]T, C, O1,277
Matroid intersection [5]T, C, O2,646
Weighted matroid intersectionT, C, O5,274
Matroid partitioningC, O1,215
Matching
Edmonds’ blossom [7]T, C, O10,460
Weighted blossomC, O5,801
Edmonds–Gallai decompositionT, C5,007
Hopcroft–KarpT, C, O2,381
Hungarian method [4]T, C, O4,123
Primal-dual (Egerváry) [4]T, C, O1,863
Online matching
RANKING [6]A6,973
RANKING, primal-dual [4]A4,861
AdWords [4]C, A1,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 GG is a walk in the directed graph that has both orientations of every edge of GG, 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.

Representations of graphs in the library and the connections between them

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 GG has degree at most two, then every connected component of GG is the vertex set of a path without repeated vertices, and it is proved by induction on GG. The induction step has to know how the connected components change when an edge {u1,u2}\{u_1,u_2\} is added to GG, 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 GG, the new component {u1,u2}\{u_1,u_2\}, 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 GG 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.

ADTGraph; abstractionImplementationCostsReasons and users
Pair_Graph_SpecsDirected; vertex to set of out-neighbours; digraph_absRed-black treesLooking up a neighbourhood, adding or deleting an edge: O(log⁡n+log⁡d)O(\log n + \log d); choosing a neighbour: O(1)O(1)Purely functional; vertices of any linearly ordered type; e.g. depth-first and breadth-first search, Dinic’s algorithm, Prim’s algorithm
AVL treesAs for red-black treesAs for red-black trees; no algorithm in the main branch uses it
Pair_Graph_U_SpecsUndirected; both orientations of every edge; ugraph_absRed-black treesAs for Pair_Graph_Specs, with every edge added or deleted twiceReuses the directed ADT and its lemmas; e.g. Kruskal’s algorithm
Adj_Map_Specs2Directed, over a map without deletion; digraph_absRed-black treesLooking up a neighbourhood, adding an edge: O(log⁡n+log⁡d)O(\log n + \log d)Requires no deletion from the map; the forest that Orlin’s algorithm maintains
Pair_Graph_ImperativeDirected, on the heap; vertex to list of out-neighbours; graph_assnArray maps and listsLooking up a neighbourhood: O(1)O(1); adding an edge: O(d)O(d), since a neighbourhood is a list without duplicatesIn-place updates; vertices must be numbers below a fixed bound; e.g. imperative depth-first search
Hash maps and listsLooking up a neighbourhood: expected O(1)O(1); adding an edge: O(d)O(d)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_absArrays (CSR)Accessing the edges of a vertex: O(1)O(1)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_abstractArrays (CSR), csr_graph and, with weights, weighted_csrElement and weight at a cursor, advancing or resetting a cursor: O(1)O(1); building the arrays: O(n+m)O(n + m)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_abstractArrays (CSR)As for indexed_iterable_setAs 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 nn is the number of vertices, mm the number of edges, and dd 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 EE, 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 EE 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.

AlgorithmPat.Inv.ProvedMain theoremLines
Graph search and shortest paths
Depth-first search✓5T, CFinds a path from the source to the target iff one exists877
Cycle detection✓16T, CReports a cycle iff the graph has one3,305
Directed cycle detection†✓5 (1)T, CReports a cycle iff the searched part has one697
Breadth-first search✓13T, CVisits exactly the reachable vertices, along shortest paths1,805
BFS with distances†✓15T, CAlso computes distances and shortest-path parents2,901
Bellman–Ford−8C, OWithout negative cycles, computes shortest paths2,837
Dijkstra†✓14T, C, OComputes shortest paths to the settled vertices2,865
Greedy algorithms and spanning trees
Best-in-greedy✓4T, C, A, ORank-quotient approximation; optimal for all weights iff matroid5,750
Kruskalinst.(4)T, C, OComputes a maximum-weight spanning forest1,559
Greedoid greedy−2T, C, OOptimal for all modular weights iff strong exchange2,217
Jarník–Priminst.(2)T, C, OComputes a maximum-weight spanning tree1,277
Flows
Successive shortest paths✓3T, C, OComputes a minimum-cost flow or reports none1,158
Capacity scaling✓3T, C, OAs for successive shortest paths1,785
Orlin✓30T, C, OAs for successive shortest paths12,080
Dinic✓1T, C, OComputes a maximum flow1,455
Blocking flow(✓)3T, CComputes a blocking flow713
DFS with backtracking5T, CRemoved edges lie on no source–target path746
Push-relabel†✓7T, C, OComputes a maximum flow4,897
Network simplex†✓7T, C, OMinimum-cost flow or infinite negative cycle7,582
Acyclic flows†✓9T, CMakes a flow acyclic, not raising its cost10,691
Matchings
Edmonds’ blossom(✓)15T, C, OComputes a maximum-cardinality matching10,460
Weighted blossom†(✓)11C, OMin-weight perfect matching or reports none, if it terminates5,801
Edmonds–Gallai decomposition†−0T, CComputes the decomposition from a maximum matching5,007
Hopcroft–Karp†✓7T, C, OComputes a maximum-cardinality bipartite matching2,381
Hungarian method✓8T, C, OMin-weight perfect matching or reports none4,123
Primal-dual (Egerváry)(✓)0T, C, OMax-weight matching and an optimal dual1,863
RANKING−0ACompetitive ratio tending to 1−1/e1 - 1/e6,973
RANKING, primal-dual−0ARatio 1−1/e1 - 1/e, also vertex-weighted4,861
AdWords−0C, ARatio in terms of bids and budgets1,347
Matroid intersection
Matroid intersection✓1T, C, OMax-cardinality common independent set2,646
Weighted matroid intersection†✓1T, C, OMax-weight common independent set5,274
Matroid partitioning†−0C, OOptimal partition from a max-cardinality common independent set1,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.

NetworknnSML imp.SML func.Scala imp.Scala func.Go imp.Go func.
NY2643460.039 (1.00)854 (21644)0.761 (19.3)TO4.95 (125)TO
BAY3212700.024 (1.00)1037 (42977)0.803 (33.3)TO5.33 (221)TO
COL4356660.022 (1.00)TO1.02 (45.8)TO7.68 (346)TO
FLA10703760.067 (1.00)TO2.23 (33.3)TO19.1 (285)TO
NW12079450.075 (1.00)TO2.39 (31.9)TO19.9 (266)TO
NE15244530.102 (1.00)TO3.18 (31.3)TOOOMTO
CAL18908150.138 (1.00)TO3.85 (27.9)TOOOMTO
LKS27581190.210 (1.00)TO5.79 (27.5)TOOOMTO
E35986230.358 (1.00)TO7.51 (21.0)TOOOMTO
W62621040.528 (1.00)TO13.7 (25.9)TOOOMTO
CTR140818161.36 (1.00)TO34.2 (25.1)TOOOMTO
USA239473471.85 (1.00)TO56.8 (30.7)TOOOMTO

Table 12. Table 12. Breadth-first search, USA-road-t family [code 7] (2.35n≤m≤2.78n2.35n \le m \le2.78n, 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 ⟨P⟩c⟨λx. Q x⟩\langle P\rangle c \langle\lambda x.\ Q\ x\rangle, with separation logic assertions PP and QQ. It expresses partial correctness: if PP holds for the initial heap and cc returns without errors, then Q xQ\ x holds for the result xx 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 A a cA\ a\ c relates an abstract value aa to a concrete one cc that may refer to the heap. For example, is_iam m a states that aa points to an array on the heap that implements the map mm 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 (bb-)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 O(n+m)O(n+m), we generally use it since our implementations of simpler algorithms, which themselves are O(n+m)O(n+m) or close, are intended as repeatedly executed sub-procedures of more complex algorithms, which amortises the cost. Note the convention that nn denotes the number of vertices and mm denotes the number of edges in a graph.

We present plots (running time in seconds against the number of vertices nn 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.

Performance comparison of graph algorithms across benchmark graphs and algorithm variants

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.

Six-panel performance comparison of graph matching algorithms

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 bb-matching, in which every vertex vv can be matched up to b(v)b(v) times. The abstract algorithms obtain information about the concrete problem by oracles. One iteration of our MI takes O(m2)O(m^2) 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 O(m2)O(m^2) oracle calls per iteration, and internal glue code adds a factor of O(m)O(m). An oracle built from Sage’s primitives takes O(m)O(m) time, and our own customised one takes constant time, resulting in O(m4)O(m^4) and O(m3)O(m^3) per iteration, respectively. Bipartite matching as MI takes O(B⋅l)O(B \cdot l) time, where ll is the time of one iteration and B=∑min⁡{deg⁡(v),b(v)}B = \sum\min\{\deg(v), b(v)\}.

We benchmark the resulting solvers for (un-)weighted (bb-)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 bb-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.

Matroid Intersection, matching, b-matching and weighted b-matching benchmark plots

Figure 6. Matroid Intersection, matching, bb-matching and weighted bb-matching; on matching and bb-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 O(n+m)O(n + m) 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 nn the density grows up to n2n^2, 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 nn 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.

FamilySize\\backslash jj123456789…\ldots12
netgen_degn=4096n = 4096, m=2jnm = 2^j n1.181.241.281.311.501.681.882.232.61…\ldots3.69
netgen_lo_srn=2j+7n = 2^{j+7}, m=n1.5m = n^{1.5}3.173.343.402.942.962.382.221.891.80
road_pathsn≈1.5⋅104⋅2jn \approx1.5 \cdot10^4 \cdot2^j, m≈2.4nm \approx2.4n1.911.631.401.221.291.16
LCn=2j+8n = 2^{j+8}, m=nlog⁡2nm = n \log_2 n1.721.681.611.621.651.641.51…\ldots1.26
TCn=2j+8n = 2^{j+8}, m=nlog⁡2nm = n \log_2 n1.181.161.161.161.181.181.10…\ldots1.05
GEOn=2j+7n = 2^{j+7}, m=n2/4m = n^2/42.212.352.432.362.131.971.69

Table 2. CV derived from Table 30, Table 31, Table 32, Table 35, Table 36, Table 37 in the appendix.

degmmAlg.OracleCert.CheckGlueTotalTotal/Oracle
28192NS7.790.0210.6490.6979.151.18
COS20.70.1190.6960.94622.51.08
CAS1030.0810.6740.9651051.02
SSP1230.0840.6750.9611251.01
416384NS10.90.0481.611.0013.51.24
COS19.30.2441.721.4222.71.18
CAS2860.1981.621.472901.01
SSP2120.1951.631.462151.01
832768NS16.80.1982.102.4321.61.28
COS26.80.4342.363.4533.01.23
CAS9720.3772.093.469781.01
SSP5370.3702.123.465431.01
1665536NS24.00.3304.073.0631.01.31
COS38.00.8034.624.8048.01.27
CAS38430.8024.064.1438521.00
SSP9110.7204.064.769211.01
32131072NS36.00.62811.56.0354.01.50
COS56.01.4512.79.3879.01.42
CAS88541.2611.510.288771.00
SSP12651.1211.59.3912871.02
64262144NS52.01.2122.711.788.01.68
COS94.02.6725.119.31411.50
CAS237552.4022.818.8237991.00
SSP19101.9422.819.319541.02
128524288NS84.02.2945.326.61581.88
COS1914.4649.638.42831.49
CAS752974.2145.541.3753881.00
SSP33353.4345.240.434241.03
2561048576NS1234.2089.856.92742.23
COS4098.5299.483.86011.47
CAS2817408.0391.190.92819301.00
SSP45646.0989.884.147441.04
5122097152NS1908.441811174952.61
COS105816.019718214531.37
CAS92482015.71821929252101.00
SSP785412.717918682311.05
10244194304NS33915.83582439562.82
COS230932.139640831461.36
CASTOTOTOTOTOTO
SSP1394526.2357390147181.05
2112^{11}8388608NS57529.671651218333.19
COS510056.479782867821.33
CASTOTOTOTOTOTO
SSP2600848.8709807275721.06
2122^{12}16252992NS91653.5148991933783.69
COS1032011016381501135691.31
CASTOTOTOTOTOTO
SSP5128911515221585545111.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 n=4096n = 4096. The first column is the average in-degree m/nm/n which is equal to the out-degree and the density.

nnmmAlg.OracleCert.CheckGlueTotalTotal/Oracle
2564096NS0.2660.0100.2790.2870.8423.17
COS0.9360.0220.3240.3931.681.79
CAS0.6350.0170.2790.4051.342.10
SSP0.7920.0170.2840.3981.491.88
51211585NS0.6960.0151.040.5762.333.34
COS2.600.0691.160.8934.721.82
CAS2.090.0251.040.9034.061.94
SSP3.110.0251.030.8955.061.63
102432768NS1.870.1632.841.506.373.40
COS7.130.3373.142.3513.01.82
CAS7.010.2442.862.4212.51.79
SSP10.30.2482.822.3715.71.53
2112^{11}92682NS6.210.3527.853.8418.22.94
COS20.40.9008.706.4336.41.79
CAS27.70.7027.896.7143.01.55
SSP40.00.7157.956.6855.31.38
2122^{12}262144NS17.81.0122.511.652.92.96
COS62.52.6525.018.81091.74
CAS86.51.9422.619.11301.50
SSP1451.9222.519.01881.30
2132^{13}741455NS58.73.0643.134.71402.38
COS2036.0850.257.33171.56
CAS2784.5443.159.53861.39
SSP5624.8243.260.66711.19
2142^{14}2097152NS2038.521231174502.22
COS82216.714218711681.42
CAS108111.412419414111.30
SSP210412.912219824371.16
2152^{15}5931642NS75420.835429814271.89
COS283244.340956638511.36
CAS353930.935359745201.28
SSP741733.635359483971.13
2162^{16}16777216NS282254.01102110250801.80
COS948211412671731125941.33
CAS1267910411061886157751.24
SSP2750210911061899306161.11

Table 31. Hybrid min-cost flow solver, netgen_lo_sr [code 23] family generated by NETGEN [47]. A node sweep at the density m=n1.5m = n^{1.5}.

Instancennmmm/nm/nAlg.OracleCert.CheckGlueTotalTotal/Oracle
01_DC9559297683.11NS15.20.1652.091.8519.31.27
COS31.00.4152.242.5436.21.17
CAS4.750.1642.082.669.652.03
SSP4.730.1742.082.699.672.05
02_DE491091205762.46NS1431.239.118.051621.13
COS2392.259.2710.72611.09
CAS23.20.6348.6311.844.31.91
SSP23.20.6178.8311.644.31.91
03_NH1169202654022.27NS6782.2819.217.97181.06
COS8454.1320.624.18941.06
CAS76.71.4719.327.31251.63
SSP76.91.4519.226.91241.62
04_NV2611556209242.38NS28544.5345.640.929451.03
COS33398.9149.058.034551.03
CAS2802.9846.063.63931.40
SSP2792.9245.363.53911.40
05_WI51915712668762.44NS915010.796.287.193441.02
COS885919.810312291041.03
CAS11216.2796.714413681.22
SSP11165.7496.614213601.22
06_FL104850626536242.53NSTOTOTOTOTOTO
COSTOTOTOTOTOTO
CAS184212.521130923751.29
SSP185911.421230223841.28
07_TX207387051560882.49NSTOTOTOTOTOTO
COSTOTOTOTOTOTO
CAS668821.442759077271.16
SSP666524.242560977231.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 nn.

nnmmOracleCert.CheckGlueTotalTotal/Oracle
2112^{11}225284.890.1160.0410.7455.791.18
2122^{12}4915212.20.2480.0921.6314.21.16
2132^{13}10649627.50.5830.1983.6531.91.16
2142^{14}22937665.61.730.4718.1576.01.16
2152^{15}4915201505.231.4920.31771.18
2162^{16}104857635614.93.9643.44181.18
2172^{17}2228224143837.09.4794.315791.10
2182^{18}4718592436211422.920046991.08
2192^{19}99614721080526449.7431115501.07
2202^{20}2097152031019552102956326301.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 m=nlog⁡2nm = n \log_{2} n.

nnmmOracleCert.CheckGlueTotalTotal/Oracle
2562142^{14}0.5450.0610.0230.5771.212.21
5122162^{16}2.090.4100.0902.314.902.35
10242182^{18}8.630.7490.35211.221.02.43
2112^{11}2202^{20}44.24.531.8353.91042.36
2122^{12}2222^{22}25845.06.972415512.13
2132^{13}2242^{24}134817134.6110126541.97
2142^{14}2262^{26}69906411934000118241.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, m=n2/4m = n^{2}/4.

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 nn and mm, 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.

StatisticDFSBFSBeforeAfter
Size
Proof lines323104113421055
Definition and specification lines355552472917
Lemmas81103108182
of which loop-template lemmas6583392
Proof form (share of lemmas)
Single-step proofs76.5%63.1%38.0%69.2%
Structured (proof . . . qed)21.0%27.2%61.1%27.5%
With apply2.5%9.7%0.0%3.3%
Proof length (non-blank lines)
Median1282
Mean3.79.912.05.6
90th percentile8313015
Proof lines per statement line1.503.154.432.02
Steps per structured proof2.48.48.74.1
Handling of facts (per lemma)
Labelled have/show/obtain0.010.212.290.12
[OF ...]0.260.612.100.74
using0.441.663.100.79
Facts quoted as cartouches0.071.640.020.19
Named assumptions0.000.000.510.00
Proof methods (share of all method calls)
auto61.2%50.7%10.7%40.2%
force + fastforce9.3%12.4%0.4%1.9%
simp2.2%4.3%29.0%11.6%
rule10.1%7.5%23.8%13.8%
metis + smt0.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.380.500.000.14
intro!:0.460.490.000.16
Statements
Plain form [\[A; B\]] \Longrightarrow C79.0%77.7%57.4%79.1%
[[ per statement0.690.790.000.34
Lemmas with an attribute80.2%67.0%6.5%45.6%
Layout
by opening its own line100%95.0%16.8%100%
using opening its own line100%99.4%34.9%100%
proof-/proof( (no space)4/1515/430/030/28
proof -/proof ( (space)0/00/041/520/0
Line length, 95th percentile11911799104
Definitions and program state
State records1102
Loops as function (domintros) over one record1102
Loops written as fun0010
Executable twins (partial_function)1112
named_theorems declared99014
Untyped definitions22/2223/2324/2650/50
Invariants
invar_* definitions51308
Complete families (elim., intro., per branch, loop)5708
Uses of [invar_holds_intros]2633033
Naming
Mean lemma-name length (characters)18.222.114.222.8
Mean lemma-name parts4.04.53.04.0
Constants with the prefix hk_––110
Global abbreviations named with ≤3\le3 characters0090
Layering
Interpretations in algorithm theories (global/plain)0/00/02/30/0
Interpretations in the sub-procedure theory (global/plain)–0/0–4/3a
Interpretations in the example theory (global/plain)1/02/01/11/1
sublocale commands0000
Algorithm theories importing concrete data structures0010
Locales with qualified data-structure parents1102
Sub-procedure contracts in the definitions locale–yesnoyes

Table 39. a^{a} 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.

AlgorithmAbstractFunctionalImperative
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 nn (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 k/mk/m marks a mean over only the kk of mm 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-nn 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 m−nm-n 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 nn, we set m=n2/16m = n^2/16 arcs, so the average degree grows from 64 at n=1024n = 1024 to 2048 at n=32768n = 32768. Weights are between 0 and nn.

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.

nnSML CSRSML listsSML RBTScala CSRScala listsScala RBTGo CSRGo listsGo RBT
10240.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)
20250.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)
40960.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)
81900.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)
163840.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)
327610.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)
655360.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)
1310440.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)
2621440.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)
5241760.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)
10485760.184 (1.00)1.42 (7.72)43.8 (238)4.98 (27.0)3.56 (19.3)49.1 (266)OOM20.4 (110)OOM
20967040.729 (1.00)1.11 (1.53)101 (138)10.9 (15.0)7.27 (9.98)111 (152)OOMOOMOOM
nnLEMON 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]
10240.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)
20250.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)
40960.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)
81900.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)
163840.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)
327610.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)
655360.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)
1310440.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)
2621440.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)
5241760.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)
10485760.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)
20967040.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] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnSML CSRSML listsSML RBTScala CSRScala listsScala RBTGo CSRGo listsGo RBT
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}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)
2142^{14}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)
2152^{15}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)
2162^{16}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)
2172^{17}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)
2182^{18}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)
2192^{19}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)
2202^{20}0.169 (1.00)1.39 (8.19)38.3 (226)4.81 (28.4)3.33 (19.7)47.5 (281)OOM19.7 (116)OOM
2212^{21}0.708 (1.00)1.04 (1.47)98.3 (139)10.9 (15.4)6.97 (9.85)108 (152)OOMOOMOOM

Table 6. Table 6. Depth-first search, Long-n family [code 6] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnLEMON 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]
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}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)
2142^{14}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)
2152^{15}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)
2162^{16}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)
2172^{17}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)
2182^{18}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)
2192^{19}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)
2202^{20}0.246 (1.45)0.170 (1.00)296 (1746)373 (2202)0.158 (0.93)0.079 (0.46)6.53 (38.6)
2212^{21}0.616 (0.87)0.513 (0.72)TOTO0.550 (0.78)0.356 (0.50)15.0 (21.2)

Table 6.

Long-n (sparse), Tb. 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.

nnSML CSRSML listsSML RBTScala CSRScala listsScala RBTGo CSRGo listsGo RBT
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}0.048 (1.00)90.6 (1876)39.9 (826)3.79 (78.5)119 (2462)51.6 (1068)OOM133 (2757)110 (2282)
2142^{14}0.335 (1.00)923 (2751)210 (626)17.3 (51.5)TO281 (837)OOMOOMOOM
2152^{15}1.40 (1.00)TO11343/1011343/10 (812)OOMTOTOOOMOOMOOM
nnLEMON 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]
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}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)
2142^{14}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)
2152^{15}1.28 (0.92)12.3 (8.79)647 (464)TO3.21 (2.30)0.159 (0.11)26.3 (18.8)

Table 7. Depth-first search, dense connected rand. family [code 6] (m=n2/16m = n^2/16, 10 instances per size, averaged over the medians of 3 repeats per instance). The instances are those of Table 11.

NetworknnSML CSRSML listsSML RBTScala CSRScala listsScala RBTGo CSRGo listsGo RBTLEMON 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]
NY2643460.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)
BAY3212700.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)
COL4356660.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)
FLA10703760.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)OOM0.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)
NW12079450.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)OOM0.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)
NE15244530.099 (1.00)1.12 (11.4)31.9 (324)3.98 (40.4)1.99 (20.2)30.1 (306)OOMOOMOOM0.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)
CAL18908150.145 (1.00)1.14 (7.87)41.8 (290)5.16 (35.7)2.50 (17.3)38.1 (263)OOMOOMOOM0.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)
LKS27581190.214 (1.00)1.48 (6.93)60.2 (281)7.36 (34.4)3.78 (17.6)56.7 (265)OOMOOMOOM0.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)
E35986230.346 (1.00)0.882 (2.55)83.9 (242)9.40 (27.1)5.00 (14.4)77.0 (222)OOMOOMOOM0.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)
W62621040.469 (1.00)1.50 (3.19)151 (321)17.3 (36.9)8.53 (18.2)139 (296)OOMOOMOOM0.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)
CTR140818161.42 (1.00)3.87 (2.73)425 (299)45.3 (31.9)21.7 (15.3)425 (299)OOMOOMOOM1.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)
USA239473472.24 (1.00)7.39 (3.30)643 (287)78.8 (35.2)33.2 (14.8)605 (270)OOMOOMOOM2.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.35nn ≤m≤\le m \le 2.78nn, one network per size, 10 sources each, median of 3 repeats each).

nnSML imp.SML func.Scala imp.Scala func.Go imp.Go func.
10240.0001 (1.00)0.019 (174)0.010 (90.8)0.234 (2085)0.027 (241)0.145 (1293)
20250.0001 (1.00)0.064 (605)0.019 (178)0.473 (4462)0.033 (310)0.376 (3547)
40960.0002 (1.00)0.230 (1105)0.037 (178)1.12 (5384)0.076 (366)1.47 (7045)
81900.0004 (1.00)0.808 (1980)0.067 (164)3.68 (9023)0.174 (426)5.76 (14126)
163840.0009 (1.00)3.15 (3592)0.134 (153)16.5 (18794)0.375 (428)22.7 (25969)
327610.002 (1.00)12.3 (6453)0.264 (138)78.3 (41005)0.836 (438)92.5 (48419)
655360.004 (1.00)53.2 (12532)0.421 (99.1)501 (118038)1.78 (420)577 (135887)
1310440.010 (1.00)200 (20687)0.639 (66.3)TO3.71 (384)TO
2621440.020 (1.00)TO1.06 (52.6)TO7.58 (377)TO
5241760.049 (1.00)TO2.03 (41.8)TO15.1 (310)TO
10485760.125 (1.00)TO3.91 (31.3)TOOOMTO
20967040.452 (1.00)TO8.46 (18.7)TOOOMTO

Table 9. Breadth-first search, Square-n family [code 6] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnLEMON 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]
10240.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)
20250.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)
40960.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)
81900.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)
163840.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)
327610.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)
655360.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)
1310440.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)
2621440.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)
5241760.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)
10485760.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)
20967040.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] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnSML imp.SML func.Scala imp.Scala func.Go imp.Go func.
10240.0001 (1.00)0.019 (371)0.010 (195)0.239 (4588)0.039 (743)0.104 (2000)
2112^{11}0.0001 (1.00)0.063 (599)0.020 (185)0.438 (4136)0.033 (316)0.382 (3603)
2122^{12}0.0002 (1.00)0.226 (1126)0.037 (186)1.14 (5691)0.076 (380)1.44 (7140)
2132^{13}0.0004 (1.00)0.793 (1992)0.072 (181)3.47 (8726)0.169 (426)5.66 (14217)
2142^{14}0.0009 (1.00)3.07 (3564)0.138 (161)19.8 (22951)0.375 (435)22.1 (25582)
2152^{15}0.002 (1.00)11.9 (6241)0.264 (139)66.5 (34831)0.817 (428)91.1 (47750)
2162^{16}0.004 (1.00)51.4 (12221)0.437 (104)561 (133494)1.75 (416)549 (130735)
2172^{17}0.010 (1.00)191 (19408)0.648 (65.7)TO3.66 (371)TO
2182^{18}0.020 (1.00)TO1.11 (55.6)TO7.42 (371)TO
2192^{19}0.045 (1.00)TO2.05 (45.9)TO14.9 (334)TO
2202^{20}0.123 (1.00)TO3.93 (31.9)TOOOMTO
2212^{21}0.459 (1.00)TO8.45 (18.4)TOOOMTO

Table 10. Breadth-first search, Long-n family [code 6] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnLEMON 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]
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}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)
2142^{14}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)
2152^{15}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)
2162^{16}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)
2172^{17}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)
2182^{18}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)
2192^{19}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)
2202^{20}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)
2212^{21}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] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

Long-n (sparse), Tb. 10

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.

nnSML imp.SML func.Scala imp.Scala func.Go imp.Go func.
10240.0006 (1.00)0.315 (573)0.109 (198)1.20 (2179)0.366 (666)1.81 (3297)
2112^{11}0.002 (1.00)2.27 (1040)0.386 (177)11.3 (5182)1.68 (769)19.1 (8760)
2122^{12}0.009 (1.00)37.9 (4232)0.884 (98.7)115 (12876)6.85 (765)248 (27722)
2132^{13}0.043 (1.00)180 (4205)3.04 (70.9)772 (18027)OOMTO
2142^{14}0.310 (1.00)TO13.7 (44.3)TOOOMTO
2152^{15}1.38 (1.00)TOOOMTOOOMTO
nnLEMON 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]
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}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)
2142^{14}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)
2152^{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] (m=n2/16m = n^2/16, 10 instances per size, averaged over the medians of 3 repeats per instance).

NetworknnLEMON 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]
NY2643460.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)
BAY3212700.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)
COL4356660.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)
FLA10703760.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)
NW12079450.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)
NE15244530.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)
CAL18908150.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)
LKS27581190.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)
E35986230.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)
W62621040.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)
CTR140818161.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)
USA239473472.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.

nnSMLScalaGoLEMON CSR [code 39]LEMON linked [code 39]nnJGraphT CSR [code 30]JGraphT hash [code 30]SciPy CSR [code 56]SciPy prebuilt [code 56]NetworkX [code 47]
10240.0004 (1.00)0.016 (38.1)0.036 (87.5)0.0002 (0.54)0.0001 (0.13)10240.0008 (2.01)0.0007 (1.79)0.0006 (1.56)0.0003 (0.71)0.001 (2.75)
20250.0007 (1.00)0.023 (31.3)0.057 (78.1)0.0002 (0.23)0.0001 (0.07)20250.001 (1.81)0.0009 (1.27)0.0009 (1.19)0.0005 (0.68)0.003 (3.66)
40960.002 (1.00)0.060 (34.9)0.178 (104)0.0004 (0.24)0.0002 (0.10)40960.003 (1.69)0.003 (1.75)0.001 (0.83)0.0009 (0.54)0.005 (3.03)
81900.004 (1.00)0.132 (33.8)0.459 (118)0.0009 (0.23)0.0004 (0.11)81900.006 (1.49)0.008 (2.01)0.003 (0.67)0.002 (0.50)0.014 (3.52)
163840.007 (1.00)0.220 (30.6)0.953 (133)0.002 (0.24)0.0008 (0.10)163840.012 (1.61)0.013 (1.76)0.006 (0.78)0.004 (0.59)0.032 (4.50)
327610.008 (1.00)0.370 (47.6)1.97 (253)0.003 (0.43)0.002 (0.22)327610.024 (3.02)0.024 (3.03)0.012 (1.49)0.009 (1.18)0.068 (8.79)
655360.052 (1.00)0.530 (10.2)3.85 (73.8)0.007 (0.13)0.003 (0.06)655360.059 (1.14)0.038 (0.73)0.025 (0.48)0.020 (0.38)0.150 (2.88)
1310440.063 (1.00)0.978 (15.4)11.0 (174)0.022 (0.34)0.013 (0.20)1310440.249 (3.94)0.145 (2.29)0.056 (0.88)0.046 (0.72)1.06 (16.7)
2621440.100 (1.00)1.58 (15.9)18.8 (188)0.052 (0.52)0.026 (0.26)2621440.505 (5.07)0.290 (2.91)0.127 (1.27)0.109 (1.09)1.89 (18.9)
5241760.216 (1.00)2.80 (12.9)32.2 (149)0.118 (0.55)0.048 (0.22)5241761.18 (5.44)0.468 (2.17)0.343 (1.59)0.304 (1.40)3.71 (17.2)
10485760.707 (1.00)5.02 (7.10)OOM0.252 (0.36)0.101 (0.14)10485762.45 (3.47)0.753 (1.06)0.778 (1.10)0.736 (1.04)6.08 (8.60)
20967041.70 (1.00)13.6 (8.00)OOM0.691 (0.41)0.425 (0.25)20967046.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] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnSMLScalaGoLEMON 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]
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}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)
2142^{14}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)
2152^{15}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)
2162^{16}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)
2172^{17}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)
2182^{18}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)
2192^{19}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)
2202^{20}0.750 (1.00)5.58 (7.45)OOM0.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)
2212^{21}1.51 (1.00)11.9 (7.92)OOM0.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-nn family [code 6] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

NetworknnSMLScalaGoLEMON CSR [code 39]LEMON linked [code 39]
NY2643460.131 (1.00)1.15 (8.76)14.1 (107)0.061 (0.46)0.020 (0.15)
BAY3212700.114 (1.00)1.45 (12.7)19.2 (168)0.039 (0.34)0.029 (0.25)
COL4356660.115 (1.00)1.69 (14.7)21.8 (190)0.048 (0.42)0.032 (0.28)
FLA10703760.300 (1.00)3.93 (13.1)51.1 (170)0.134 (0.45)0.094 (0.31)
NW12079450.363 (1.00)4.93 (13.6)61.4 (169)0.168 (0.46)0.123 (0.34)
NE15244530.724 (1.00)6.63 (9.16)80.1 (111)0.233 (0.32)0.172 (0.24)
CAL18908150.788 (1.00)7.71 (9.78)OOM0.289 (0.37)0.208 (0.26)
LKS27581191.14 (1.00)11.2 (9.83)OOM0.415 (0.36)0.300 (0.26)
E35986231.54 (1.00)15.2 (9.91)OOM0.528 (0.34)0.394 (0.26)
W62621042.35 (1.00)25.4 (10.8)OOM0.870 (0.37)0.598 (0.25)
CTR140818167.13 (1.00)71.1 (9.97)OOM2.67 (0.37)2.02 (0.28)
USA2394734712.5 (1.00)1106/10 (8.83)OOM4.13 (0.33)3.90 (0.31)
NetworknnJGraphT CSR [code 30]JGraphT hash [code 30]SciPy CSR [code 56]SciPy prebuilt [code 56]NetworkX [code 47]
NY2643460.175 (1.33)0.180 (1.38)0.082 (0.62)0.080 (0.61)1.08 (8.24)
BAY3212700.219 (1.92)0.263 (2.30)0.094 (0.82)0.088 (0.77)2.66 (23.3)
COL4356660.267 (2.33)0.324 (2.83)0.140 (1.22)0.128 (1.11)2.96 (25.8)
FLA10703760.995 (3.31)0.695 (2.31)0.384 (1.28)0.347 (1.16)8.14 (27.1)
NW12079451.22 (3.36)1.01 (2.78)0.452 (1.25)0.440 (1.21)16.2 (44.6)
NE15244531.89 (2.61)1.22 (1.68)0.586 (0.81)0.573 (0.79)19.3 (26.6)
CAL18908152.28 (2.90)1.28 (1.63)0.819 (1.04)0.784 (0.99)29.3 (37.2)
LKS27581194.22 (3.70)2.05 (1.80)1.21 (1.06)1.14 (1.00)42.9 (37.7)
E35986235.70 (3.71)3.02 (1.96)1.65 (1.07)1.60 (1.04)47.59/10 (30.9)
W626210410.4 (4.43)4.15 (1.77)2.97 (1.26)2.92 (1.24)OOM
CTR1408181629.0 (4.07)13.2 (1.85)8.30 (1.16)8.17 (1.15)OOM
USA2394734745.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] (2.35n≤m≤2.78n2.35n \le m \le2.78n, one network per size, 10 source-target pairs each, median of 3 repeats each).

nnSMLScalaGoLEMON [code 40]JGraphT [code 31]SciPy [code 58]NetworkX [code 45]
10240.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)
20250.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)
40960.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)
81900.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)
163840.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)
327610.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)
655360.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)
1310440.064 (1.00)303 (4708)85.1 (1321)0.024 (0.37)0.285 (4.42)0.035 (0.55)1.40 (21.7)
2621440.146 (1.00)TO7288/10 (4981)0.056 (0.38)0.743 (5.08)0.078 (0.54)3.26 (22.3)
5241760.354 (1.00)TOTO0.129 (0.37)1.76 (4.98)0.160 (0.45)7.56 (21.4)
10485760.765 (1.00)TOTO0.301 (0.39)4.06 (5.30)0.365 (0.48)15.9 (20.8)
20967041.67 (1.00)TOTO0.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] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnSMLScalaGoLEMON [code 40]JGraphT [code 31]SciPy [code 58]NetworkX [code 45]
10240.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)
2112^{11}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)
2122^{12}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)
2132^{13}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)
2142^{14}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)
2152^{15}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)
2162^{16}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)
2172^{17}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)
2182^{18}0.136 (1.00)11473/1011473/10 (8427)672 (4935)0.055 (0.40)0.703 (5.17)0.073 (0.54)3.29 (24.2)
2192^{19}0.368 (1.00)TOTO0.126 (0.34)1.73 (4.69)0.158 (0.43)6.79 (18.4)
2202^{20}0.739 (1.00)TOTO0.292 (0.39)3.99 (5.40)0.348 (0.47)15.5 (21.0)
2212^{21}1.67 (1.00)TOTO0.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] (m≈4nm \approx4n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnSMLScalaGoLEMON [code 40]JGraphT [code 31]SciPy [code 58]NetworkX [code 45]
10240.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)
2112^{11}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)
2122^{12}0.291 (1.00)TOTO0.087 (0.30)0.698 (2.39)0.091 (0.31)2.92 (10.0)
2132^{13}1.26 (1.00)TOTO0.456 (0.36)2.88 (2.28)0.448 (0.35)14.0 (11.1)
2142^{14}7.23 (1.00)TOTO2.02 (0.28)12.9 (1.78)2.24 (0.31)67.9 (9.39)
2152^{15}34.1 (1.00)TOTO8.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] (m=n2/16m = n^2/16, 10 instances per size, averaged over the medians of 3 repeats per instance). The instances are those of Table 11.

nnSML HLSML FIFOSML 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]
40960.047 (1.00)0.056 (1.17)n/a0.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)
90000.151 (1.00)0.201 (1.33)n/a0.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)
154880.377 (1.00)0.714 (1.89)n/a0.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)
305890.914 (1.00)2.01 (2.20)n/a0.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)
655362.12 (1.00)5.63 (2.65)n/a0.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)
1303215.57 (1.00)14.4 (2.58)n/a1.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)
27031929.4 (1.00)100 (3.41)n/a4.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)
527067147 (1.00)467 (3.17)n/a22.7 (0.15)300 (2.04)31.9 (0.22)147 (1.00)150 (1.02)358 (2.43)1.47 (0.01)
1046528509 (1.00)TOn/a51.5 (0.10)TO80.4 (0.16)743 (1.46)792 (1.56)923 (1.82)4.53 (0.01)
2090912TOTOn/a267 (–)TO200 (–)TOTOTO6.56 (–)
4147200TOTOn/a827 (–)TO469 (–)TOTOTO19.4 (–)
8444736TOTOn/aTOTOTOTOTOTO90.2 (–)
16777216TOTOn/aTOTOTOTOTOTO242 (–)
33460368TOTOn/aTOTOTOTOTOTO598 (–)
67109224TOTOn/aTOTOTOTOTOTOTO

Table 19. Push-relabel, RMF-long family [code 1] (m≈5nm \approx5n, 3 instances per size). Plots were cut off at n=223n = 2^{23}. The family does not meet the structural prerequisites for SML AFP [code 27].

nnSML HLSML FIFOSML 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]
40980.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)
81940.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)
163860.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)
327700.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)
655382.54 (1.00)3.67 (1.44)OVF1.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)
1310746.89 (1.00)8.76 (1.27)OVF3.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)
26214636.6 (1.00)35.8 (0.98)OVF3.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)
524290273 (1.00)299 (1.09)OVF90.2 (0.33)92.9 (0.34)29.4 (0.11)130 (0.48)129 (0.47)154 (0.56)0.748 (0.00)
1048578TOTOOVF139 (–)138 (–)72.4 (–)498 (–)512 (–)304 (–)1.01 (–)
2097154TOTOOVF137 (–)134 (–)180 (–)TOTO568 (–)2.04 (–)
4194306TOTOOVF350 (–)353 (–)459 (–)TOTOTO4.69 (–)
8388610TOTOOVFTOTOTOTOTOTO9.33 (–)
16777218TOTOOVFTOTOTOTOTOTO17.3 (–)
33554434TOTOOVFTOTOTOTOTOTO38.8 (–)
67108866TOTOOVFTOTOTOTOTOTO81.4 (–)

Table 20. Push-relabel, WASH-RLG-long family [code 2] (m≈3nm \approx3n, 3 instances per size). Plots were cut off at n=223n = 2^{23}.

nnSML HLSML FIFOSML 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]
41020.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)
81980.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)
163901.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)
327744.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)
6554215.0 (1.00)9.14 (0.61)OVF0.198 (0.01)0.242 (0.02)32.5 (2.17)34.9 (2.33)35.5 (2.37)TO2.19 (0.15)
13107855.3 (1.00)33.0 (0.60)OVF0.730 (0.01)0.793 (0.01)392 (7.09)138 (2.51)138 (2.51)TO6.96 (0.13)
262150222 (1.00)129 (0.58)OVF3.41 (0.02)3.68 (0.02)TO553 (2.49)553 (2.49)TO28.3 (0.13)
524294883 (1.00)510 (0.58)OVF11.9 (0.01)11.9 (0.01)TOTOTOTO111 (0.13)
1048582TOTOOVF43.8 (–)43.0 (–)TOTOTOTO441 (–)

Table 21. Push-relabel, AK family [code 8] (m≈3n/2m \approx3n/2, 1 instance per size, median of 3 repeats).

nnSMLScalaGoSciPy LSA [code 52]SciPy MWFBM CSR [code 53]
2112^{11}0.005 (1.00)0.537 (102)4.81 (916)0.012 (2.32)0.002 (0.46)
2122^{12}0.016 (1.00)0.763 (47.9)13.6 (853)0.058 (3.62)0.006 (0.40)
2132^{13}0.054 (1.00)1.22 (22.5)40.4 (748)0.351 (6.50)0.020 (0.36)
2142^{14}0.163 (1.00)2.61 (16.0)137 (838)2.32 (14.2)0.069 (0.42)
2152^{15}0.588 (1.00)6.28 (10.7)320 (544)20.9 (35.5)0.251 (0.43)
nnJGraphT KM with GC [code 32]JGraphT MWBM CSR [code 33]JGraphT MWBM hash [code 33]CSA CSR [code 9]OR-Tools [code 11]
2112^{11}2.43 (463)0.108 (20.5)0.192 (36.5)0.005 (0.93)0.009 (1.69)
2122^{12}23.3 (1460)0.288 (18.1)0.489 (30.7)0.012 (0.76)0.018 (1.13)
2132^{13}201 (3715)0.758 (14.0)1.18 (21.9)0.027 (0.50)0.042 (0.78)
2142^{14}TO2.33 (14.3)3.11 (19.1)0.064 (0.39)0.095 (0.58)
2152^{15}TO6.68 (11.4)9.89 (16.8)0.152 (0.26)0.218 (0.37)

Table 23. Hungarian method, two-cost family [code 4] (m=nlog⁡2nm = n \log_{2} n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnSMLScalaGoSciPy LSA [code 52]SciPy MWFBM CSR [code 53]
2560.005 (1.00)0.494 (106)8.20 (1766)0.0006 (0.13)0.005 (0.99)
5120.024 (1.00)1.04 (43.5)42.8 (1784)0.003 (0.11)0.013 (0.56)
10240.143 (1.00)3.48 (24.4)279 (1953)0.012 (0.09)0.045 (0.32)
2112^{11}0.945 (1.00)19.9 (21.0)11862^{2}/10 (1256)0.069 (0.07)0.198 (0.21)
2122^{12}6.03 (1.00)133 (22.0)TO0.333 (0.06)0.817 (0.14)
nnJGraphT KM with GC [code 32]JGraphT MWBM CSR [code 33]JGraphT MWBM hash [code 33]CSA CSR [code 9]OR-Tools [code 11]
2560.036 (7.83)0.093 (19.9)0.105 (22.7)0.0006 (0.12)0.004 (0.88)
5120.321 (13.4)0.313 (13.0)0.425 (17.7)0.002 (0.09)0.009 (0.38)
10242.38 (16.7)1.28 (8.97)1.49 (10.4)0.009 (0.06)0.052 (0.37)
2112^{11}34.6 (36.6)9.13 (9.66)15.7 (16.7)0.046 (0.05)0.386 (0.41)
2122^{12}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] (m=n2/4m = n^2 / 4, 10 instances per size, averaged over the medians of 3 repeats per instance).

b-Matching. For bb-matching, we set the capacities b(x)=min⁡{β,deg⁡(x)}b(x) = \min\{\beta, \deg(x)\}, where β\beta is selected uniformly at random between 1 and 20 and deg⁡(x)\deg(x) is the vertex degree.

Matroid intersection, unweighted problems on the low-cost and two-cost families [code 4], which share their graphs (m=nlog⁡2nm = n \log_2 n, 5 instances per size, run once in each family, mean over both runs).

nnSMLScalaGoSage (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 (–)
1280.0006 (1.00)0.123 (206)0.094 (157)0.053 (88.8)1.49 (2480)
2560.002 (1.00)0.229 (99.3)0.337 (146)0.337 (147)14.8 (6421)
5120.009 (1.00)0.488 (53.6)1.52 (167)4.42 (485)176 (19357)
10240.032 (1.00)0.830 (26.0)5.70 (179)46.3 (1452)TO
2112^{11}0.146 (1.00)2.27 (15.5)28.1 (193)TOTO
2122^{12}0.394 (1.00)7.29 (18.5)116 (294)TOTO
2132^{13}1.67 (1.00)29.1 (17.4)476 (284)TOTO
2142^{14}7.93 (1.00)123 (15.5)TOTOTO
2152^{15}37.0 (1.00)530 (14.3)TOTOTO
bb-matching
32<0.001 (–)0.013 (–)0.019 (–)0.011 (–)0.233 (–)
64<0.001 (–)0.039 (–)0.067 (–)0.076 (–)2.56 (–)
1280.002 (1.00)0.234 (117)0.623 (312)1.63 (815)40.2 (20079)
2560.018 (1.00)0.614 (34.9)4.79 (272)31.2 (1775)591 (33606)
5120.121 (1.00)2.24 (18.5)30.1 (249)539 (4460)TO
10240.885 (1.00)11.8 (13.3)201 (227)TOTO
2112^{11}4.83 (1.00)59.6 (12.4)1069 (221)TOTO
2122^{12}22.0 (1.00)267 (12.2)TOTOTO
2132^{13}123 (1.00)TOTOTOTO
2142^{14}537 (1.00)TOTOTOTO
2152^{15}TOTOTOTOTO

Table 25. Matroid intersection, unweighted problems on the low-cost and two-cost families [code 4], which share their graphs (m=nlog⁡2nm = n \log_2 n, 5 instances per size, run once in each family, mean over both runs).

nnSMLScalaGoSage (our oracle) [code 48]Sage (plain) [code 48,50,51]
3232<0.001<0.001 (–)0.0280.028 (–)0.0670.067 (–)0.0050.005 (–)0.0470.047 (–)
64640.0010.001 (1.00)0.0860.086 (86.4)0.2530.253 (253)0.0300.030 (29.6)0.9540.954 (954)
1281280.0040.004 (1.00)0.1540.154 (40.6)0.8070.807 (212)0.1980.198 (52.2)19.919.9 (5231)
2562560.0110.011 (1.00)0.3000.300 (28.3)2.242.24 (212)1.491.49 (140)398398 (37580)
5125120.0370.037 (1.00)0.8260.826 (22.3)7.387.38 (199)11.711.7 (317)TO
102410240.1190.119 (1.00)2.292.29 (19.2)22.122.1 (186)103103 (868)TO
2112^{11}0.4560.456 (1.00)8.128.12 (17.8)88.188.1 (193)868868 (1904)TO
2122^{12}1.691.69 (1.00)29.329.3 (17.4)349349 (206)TOTO
2132^{13}6.816.81 (1.00)126126 (18.5)TOTOTO
2142^{14}31.031.0 (1.00)577577 (18.6)TOTOTO
2152^{15}157157 (1.00)TOTOTOTO
Weighted matching
32320.0010.001 (1.00)0.0210.021 (21.2)0.2090.209 (209)0.0240.024 (23.8)1.901.90 (1905)
64640.0030.003 (1.00)0.0600.060 (23.2)0.6620.662 (255)0.1660.166 (63.7)41.241.2 (15831)
1281280.0110.011 (1.00)0.2150.215 (19.9)2.742.74 (254)2.122.12 (197)10151/51015^{1/5} (93994)
2562560.0440.044 (1.00)0.8400.840 (19.2)10.810.8 (248)23.923.9 (546)TO
5125120.1930.193 (1.00)3.133.13 (16.2)44.144.1 (229)259259 (1346)TO
102410240.9970.997 (1.00)13.513.5 (13.6)192192 (193)TOTO
2112^{11}4.694.69 (1.00)61.861.8 (13.2)866866 (185)TOTO
2122^{12}22.722.7 (1.00)290290 (12.8)TOTOTO
2132^{13}114114 (1.00)TOTOTOTO
2142^{14}591591 (1.00)TOTOTOTO
2152^{15}TOTOTOTOTO

Table 26. Matroid intersection, weighted problems on the low-cost family [code 3] (m=nlog⁡2nm = n \log_{2} n, 5 instances per size, one run each). The unweighted problems are in Table 25.

nnSMLScalaGoSage (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 (–)
1280.001 (1.00)0.077 (77.0)0.191 (191)0.179 (179)23.1 (23107)
2560.005 (1.00)0.167 (33.4)0.810 (162)1.33 (266)462 (92370)
5120.022 (1.00)0.488 (21.8)3.42 (153)10.4 (463)TO
10240.097 (1.00)1.57 (16.2)15.0 (154)91.5 (942)TO
2112^{11}0.391 (1.00)5.86 (15.0)65.0 (166)755 (1929)TO
2122^{12}1.59 (1.00)24.0 (15.0)280 (175)TOTO
2132^{13}7.17 (1.00)106 (14.7)1137 (158)TOTO
2142^{14}32.6 (1.00)459 (14.1)TOTOTO
2152^{15}151 (1.00)TOTOTOTO
Weighted bb-matching
320.0002 (1.00)0.008 (38.0)0.051 (257)0.022 (112)1.74 (8711)
640.002 (1.00)0.025 (15.7)0.235 (147)0.150 (93.8)37.0 (23125)
1280.006 (1.00)0.116 (19.3)1.32 (220)2.11 (351)7921/5792^{1/5} (131998)
2560.030 (1.00)0.573 (19.2)7.48 (251)23.3 (781)TO
5120.165 (1.00)2.88 (17.5)39.2 (238)257 (1557)TO
10241.07 (1.00)15.0 (14.0)209 (196)TOTO
2112^{11}5.84 (1.00)76.0 (13.0)1050 (180)TOTO
2122^{12}30.3 (1.00)373 (12.3)TOTOTO
2132^{13}164 (1.00)TOTOTOTO
2142^{14}856 (1.00)TOTOTOTO
2152^{15}TOTOTOTOTO

Table 27. Matroid intersection, weighted problems on the two-cost family [code 4] (m=nlog⁡2nm = n \log_2 n, 5 instances per size, one run each). The unweighted problems are in Table 25.

nnSMLScalaGoSage (our oracle) [code 48,49]Sage (plain) [code 48,49,50,51]
Matching
32<0.001 (–)0.007 (–)0.012 (–)0.004 (–)0.038 (–)
640.001 (1.00)0.043 (43.4)0.084 (84.0)0.023 (23.0)0.650 (650)
1280.003 (1.00)0.281 (82.7)0.666 (196)0.296 (87.1)20.0 (5892)
2560.029 (1.00)0.751 (26.3)5.34 (187)4.32 (151)680 (23790)
5120.233 (1.00)4.56 (19.6)39.7 (171)66.3 (285)TO
10241.72 (1.00)37.4 (21.7)306 (178)TOTO
2112^{11}13.1 (1.00)OOMTOTOTO
2122^{12}105 (1.00)OOMTOTOTO
b-matching
320.0002 (1.00)0.044 (222)0.076 (381)0.050 (252)0.882 (4409)
640.003 (1.00)0.258 (99.3)0.877 (337)0.759 (292)25.2 (9702)
1280.012 (1.00)0.566 (48.8)4.27 (368)12.9 (1113)90822/59082^{2/5} (78304)
2560.104 (1.00)2.44 (23.6)30.9 (298)132 (1277)TO
5120.374 (1.00)9.17 (24.5)94.9 (254)125 (333)TO
10248.53 (1.00)176 (20.6)TOTOTO
2112^{11}42.9 (1.00)OOMTOTOTO
2122^{12}402 (1.00)OOMTOTOTO
Weighted matching
320.002 (1.00)0.135 (61.2)0.613 (279)0.009 (4.00)0.109 (49.5)
640.057 (1.00)1.51 (26.6)17.2 (302)0.111 (1.94)5.89 (103)
1281.86 (1.00)40.4 (21.7)556 (298)1.90 (1.02)367 (197)
25656.1 (1.00)11204/51120^{4/5} (20.0)TO40.8 (0.73)TO
512TOTOTO1089 (–)TO
1024TOTOTOTOTO
2112^{11}TOTOTOTOTO
2122^{12}TOTOTOTOTO
Weighted b-matching
320.004 (1.00)0.111 (25.3)1.41 (320)0.084 (19.0)9.99 (2270)
640.088 (1.00)2.04 (23.3)33.2 (378)2.14 (24.4)78622/57862^{2/5} (8954)
1283.93 (1.00)81.4 (20.7)37212/53721^{2/5} (94.5)54.0 (13.7)TO
256154 (1.00)TOTOTOTO
512TOTOTOTOTO
1024TOTOTOTOTO
2112^{11}TOTOTOTOTO
2122^{12}TOTOTOTOTO

Table 28. Matroid intersection, geometric family [code 5] (m=n2/4m = n^2/4, 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 ≤10\le10 % to ≤30\le30 % 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 n=4097n = 4097. The first column is the average in-degree m/nm/n which always equals the density.

degmmAlg.OracleCert.CheckGlueTotalTotal/Oracle
416388NS5.700.0421.590.9648.301.46
COS13.00.2271.721.3916.31.26
CAS65.10.1521.621.4468.31.05
SSP9.860.1011.591.3812.91.31
832776NS14.90.1962.081.6018.81.26
COS27.60.4392.332.5132.91.19
CAS2280.3852.082.562331.02
SSP5440.3632.102.605491.01
1665552NS23.00.3213.973.0530.01.32
COS38.00.8104.534.7448.01.26
CAS4200.6613.984.954301.02
SSP10170.6943.964.3410261.01
32131104NS30.00.62111.56.0648.01.60
COS60.01.4612.69.3883.01.39
CAS8121.1211.39.938351.03
SSP12081.0911.49.5612301.02
64262208NS48.01.2023.211.484.01.74
COS1082.7025.319.31551.44
CAS21821.9323.219.922271.02
SSP19641.9423.121.020101.02
128524416NS74.02.2145.424.11461.97
COS2044.4749.840.42991.46
CAS60483.4745.642.961401.01
SSP29473.1545.542.330381.03
2561048832NS1073.9360.680.92522.37
COS4598.4770.31276651.45
CAS166506.4560.6136168531.01
SSP45746.4860.613947801.04
5122097664NS1748.591811094722.71
COS114916.519922115851.38
CAS11555013.51802371159801.00
SSP647813.818324569201.07
10244195328NS31616.63652339302.95
COS250732.640148134211.36
CAS50103027.63615115019301.00
SSP1238425.3361511132811.07
2112^{11}8390656NS54629.172843817413.19
COS571556.179797775451.32
CAS142430060.5734100514261001.00
SSP2455252.07241041263691.07
2122^{12}16781312NS95759.2147188933773.53
COS1163812716141988153671.32
CASTOTOTOTOTOTO
SSP4383910714552138475391.08

Table 29.

nnmmAlg.OracleCert.CheckGlueTotalTotal/Oracle
2562112^{11}NS0.6380.0110.1750.2111.031.62
COS2.810.0240.1860.2603.281.17
CAS5.390.0250.1770.2645.861.09
SSP32.90.0450.1700.27633.41.01
2112^{11}2142^{14}NS23.00.0601.570.84226.01.11
COS40.00.2601.621.2743.01.08
CAS1320.2051.571.291351.02
SSP36720.2201.541.2436751.00
2122^{12}2152^{15}NS1080.2932.262.491131.05
COS1390.5982.343.341451.04
CAS20540.3622.253.3920601.00
SSP266070.3802.253.37266131.00
2132^{13}2162^{16}NS3180.5054.293.133261.02
COS2471.014.524.872581.04
CAS12530.6194.265.1212631.01
SSP691890.6224.275.11691991.00
2142^{14}2172^{17}NS12710.8238.445.7412861.01
COS6551.749.019.796761.03
CAS35231.128.5310.335431.01
SSP2745101.328.4810.22745301.00
2152^{15}2182^{18}NS315931.6917.212.1316241.00
COS23423.0418.722.223861.02
CAS1852702.2917.220.51853101.00
SSP12703002.3017.280.512704001.00
2162^{16}2192^{19}NS356663.0834.125.8357291.00
COS51405.8836.342.952251.02
CAS340664.1434.144.8341491.00
SSP31486004.1334.161.831487001.00

Table 33. Hybrid min-cost flow solver, goto_8 [code 12] family generated by GOTO [33]. A node sweep at the fixed density m=8nm = 8n.

nnmmAlg.OracleCert.CheckGlueTotalTotal/Oracle
2172^{17}2202^{20}NS1520806.7368.754.51522101.00
COS1973412.973.192.0199121.01
CAS1059908.0268.993.11061601.00
SSPTOTOTOTOTOTO
2182^{18}2212^{21}NS320340012.914014732037001.00
COS4197125.8155211423631.01
CASTOTOTOTOTOTO
SSPTOTOTOTOTOTO
2192^{19}2222^{22}NS241390024.929028524145001.00
COS27089043.73083882716301.00
CASTOTOTOTOTOTO
SSPTOTOTOTOTOTO
2202^{20}2232^{23}NSTOTOTOTOTOTO
COS100910085.764087410107001.00
CASTOTOTOTOTOTO
SSPTOTOTOTOTOTO
2212^{21}2242^{24}NSTOTOTOTOTOTO
COS656740150148919316603101.00
CASTOTOTOTOTOTO
SSPTOTOTOTOTOTO
2222^{22}2252^{25}NSTOTOTOTOTOTO
COSTOTOTOTOTOTO
CASTOTOTOTOTOTO
SSPTOTOTOTOTOTO

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).

nnSMLScalaGoSciPy LSA [code 52]SciPy MWFBM CSR [code 53]
2112^{11}0.014 (1.00)0.817 (57.6)16.8 (1187)0.025 (1.78)0.003 (0.22)
2122^{12}0.053 (1.00)1.47 (27.8)60.4 (1139)0.122 (2.31)0.007 (0.14)
2132^{13}0.209 (1.00)3.69 (17.6)215 (1026)0.813 (3.88)0.020 (0.10)
2142^{14}0.786 (1.00)11.7 (14.9)885 (1126)3.93 (5.01)0.061 (0.08)
2152^{15}3.25 (1.00)46.0 (14.2)TO21.2 (6.53)0.175 (0.05)
nnJGraphT KM with GC [code 32]JGraphT MWBM CSR [code 33]JGraphT MWBM hash [code 33]CSA CSR [code 9]OR-Tools [code 11]
2112^{11}2.60 (184)0.107 (7.55)0.238 (16.8)0.001 (0.09)0.003 (0.22)
2122^{12}24.7 (467)0.314 (5.93)0.655 (12.4)0.003 (0.05)0.005 (0.10)
2132^{13}210 (1001)1.02 (4.86)1.63 (7.78)0.007 (0.03)0.012 (0.06)
2142^{14}TO3.28 (4.18)4.36 (5.55)0.016 (0.02)0.031 (0.04)
2152^{15}TO11.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] (m=nlog⁡2nm = n \log_{2} n, 10 instances per size, averaged over the medians of 3 repeats per instance).

nnmmOracleCert.CheckGlueTotalTotal/Oracle
2112^{11}225281.290.1160.0420.7742.221.72
2122^{12}491522.900.2470.0921.644.881.68
2132^{13}1064967.120.5550.1973.6311.51.61
2142^{14}22937616.31.350.4378.2526.31.62
2152^{15}49152041.84.961.5020.869.11.65
2162^{16}104857699.414.04.0845.41631.64
2172^{17}222822428437.39.7596.94271.51
2182^{18}471859287712222.921212341.41
2192^{19}9961472219322745.042428901.32
2202^{20}20971520623754598.996778491.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 m=nlog⁡2nm = n \log_2 n.

Code References

  1. 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

  1. 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

  1. 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

  1. 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

  1. 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:

  1. Comments are removed.

  2. The contents of inner-syntax strings and cartouches are masked, so that keywords occurring inside terms are not counted.

  3. Each theory is split into its top-level commands.

  4. 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, _induct and _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 m1m_1 m2m_2).

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 [[A;B]]⟹C[[A; B]] \Longrightarrow C.

⟦ 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 ≤3\leq3 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 by at 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. [1]Leanprover-community/mathlib4. leanprover-community (2024), https://github.com/leanprover-community/mathlib4
  2. [2]Functional Data Structures and Algorithms: A Proof Assistant Approach. 1 edn. (2025)DOI
  3. [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. [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. [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. [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. [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. [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. [9]Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice Hall (1993)
  10. [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. [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. [12]Baier, C., Katoen, J.P.: Principles of Model Checking (2008)
  13. [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. [14]Ballarin, C.: Locales: A Module System for Mathematical Theories. J. Autom. Reason. (2014). https://doi.org/10.1007/s10817-013-9284-7
  15. [15]Bellman, R.: On a routing problem. Q. Appl. Math. (1958). https://doi.org/10.1090/qam/102435
  16. [16]Berge, C.: Two theorems in graph theory. Proc. Natl. Acad. Sci. (1957). https://doi.org/10.1073/pnas.43.9.842
  17. [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. [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. [19]Bonet, B., Geffner, H.: Planning as heuristic search. Artif. Intell. (2001). https://doi.org/10.1016/S0004-3702(01)00108-4
  20. [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. [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. [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. [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. [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. [25]Edmonds, C.: Undirected Graph Theory. Arch. Formal Proofs (Sep 2022), https://isa-afp.org/entries/Undirected_Graph_Theory.html
  26. [26]Edmonds, C.: Hypergraphs. Arch. Formal Proofs (Sep 2023), https://isa-afp.org/entries/Hypergraph_Basics.html
  27. [27]Edmonds, J.: Paths, Trees, and Flowers. Can. J. Math. (1965/ed). https://doi.org/10.4153/CJM-1965-045-4
  28. [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. [29]Frank, A.: A Weighted Matroid Intersection Algorithm. J. Algorithms (1981). https://doi.org/10.1016/0196-6774(81)90032-8
  30. [30]Gallai, T.: Kritische Graphen II. Magyar Tud. Akad. Mat. Kutató Int. Közl. 8, 373–395 (1963)
  31. [31]Gallai, T.: Maximale Systeme unabhängiger Kanten. Magyar Tud. Akad. Mat. Kutató Int. Közl. 9, 401–413 (1964)
  32. [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. [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. [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. [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. [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. [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. [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. [39]Hoare, C.A.R.: Proof of correctness of data representations. Acta Informatica (1972). https://doi.org/10.1007/BF00289507
  40. [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. [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. [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. [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. [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. [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. [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. [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. [48]Korte, B., Vygen, J.: Combinatorial Optimization (2012). https://doi.org/10.1007/978-3-642-24488-9
  49. [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. [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. [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. [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. [53]Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. (1955). https://doi.org/10.1002/nav.3800020109
  54. [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. [55]Lammich, P.: Refinement for Monadic Programs. Arch Form. Proofs (2012), https://www.isa-afp.org/entries/Refine_Monadic.shtml
  56. [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. [57]Lammich, P.: Refinement to Imperative HOL. J. Autom. Reason. (2019). https://doi.org/10.1007/s10817-017-9437-1
  58. [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. [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. [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. [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. [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. [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. [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. [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. [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. [67]Lawler, E.L.: Matroid Intersection Algorithms. Math. Program. (1975). https://doi.org/10.1007/BF01681329
  68. [68]Lee, G.: Correctness of ford-fulkerson’s maximum flow algorithm1. Formaliz. Math. (2005)
  69. [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. [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. [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. [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. [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. [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. [75]Noshchinski, L.: A Graph Library for Isabelle. Math. Comput. Sci. (2015). https://doi.org/10.1007/S11786-014-0183-Z
  76. [76]Perron, L., Furnon, V.: OR-Tools, https://developers.google.com/optimization/, OR-Tools 9.15.6755. Last accessed on 13/10/2026
  77. [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. [78]Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency (2003)
  79. [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. [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. [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. [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. [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. [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. [85]Vazirani, V.V.: Approximation Algorithms
  86. [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. [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. [88]Wirth, N.: Program Development by Stepwise Refinement. Commun. ACM (1971). https://doi.org/10.1145/362575.362577
  89. [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. [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. [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

Paper details

vlnc:W_jeq7beu2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

large language models (LLMs)

View statement
Looking for related papers…
Contents