Graphs.jl: a graph algorithms layer for the Julia ecosystem

Three layers: concrete types, an abstract interface, algorithms

The stated goal of Graphs.jl is to offer a performant platform for network and graph analysis in Julia, following the example of libraries such as NetworkX in Python. The offering is described in three parts, and the three-part structure is the design.

The first part is a set of simple, concrete graph implementations, `SimpleGraph` for undirected graphs and `SimpleDiGraph` for directed graphs. The second is an API for the development of more sophisticated graph implementations under the `AbstractGraph` type, and the third is a large collection of graph algorithms with the same requirements as this API.

That middle layer is the part that matters for anyone who is not going to use the simple types. The algorithms are written against the abstract interface, so a specialised graph implementation that satisfies `AbstractGraph` gets the whole algorithm collection for free. The cost is that the interface is a contract, and a graph type that does not implement it fully cannot participate.

The explicit design decision the README states is worth reading carefully, because it explains the shape of the library. It is an explicit design decision that any data not required for graph manipulation, attributes and other information for example, is expected to be stored outside of the graph structure itself. A `SimpleGraph` therefore holds vertices and edges and little else, and anything richer, a weight, a label, a colour, a timestamp, lives in a parallel structure that the caller manages.

The consequence is that Graphs.jl is a graph algorithms layer rather than a graph data platform, and the packages that add the missing pieces sit next to it rather than inside it.

Installing and building a first graph

Installation is the standard Julia package route, entered by hitting the closing bracket to get to Pkg mode.

pkg> add Graphs

The basic use example starts with one of the convenience functions for generating graphs. `path_graph` builds a simple undirected path graph of a given length, and the REPL shows the type and the shape of the result.

julia> g = path_graph(6)
{6, 5} undirected simple Int64 graph

The display is worth pausing on, because it is a Julia type display and it tells you the representation. The Int64 is the vertex type, the graph is undirected, and the 6 and 5 are the vertex and edge counts. A path graph on 6 vertices has 5 edges, which is what the printed form means.

The interrogation functions are named for what they return, and the example uses them immediately.

julia> nv(g)
6

julia> ne(g)
5

And the graph is mutable, so an edge can be added to close the path into a loop.

julia> add_edge!(g, 1, 6);

Note the semicolon. In Julia that suppresses the display of the returned value, and for a mutating function like `add_edge!` the return is not interesting. The exclamation mark in the name is the Julia convention for a function that mutates its first argument, and it is used consistently across the interface, so `add_edge!` mutating the graph is a signal you can rely on rather than a naming quirk in one function.

Where the algorithms stop and the sibling packages start

The Related packages section of the README draws the boundary explicitly, and it is a boundary you will hit the first time your graph needs a weight.

Additional functionality like advanced IO and file formats, weighted graphs, property graphs, and optimization-related functions can be found in the packages of the JuliaGraphs organisation. So a weighted graph, a property graph, a file format reader or a solver-based routine is not in Graphs.jl, and the organisation's site at juliagraphs.org is where you find the package that has it.

This is a design position rather than an omission. The reason is the decision about where data lives. If the graph holds only vertices and edges, then a weight is not a property of the edge in the type system, it is a parallel array or a separate structure that the algorithm must be told about. A package that provides weighted graphs can define its own type and its own algorithms, and Graphs.jl stays free of the question. The price is that a user who needs a weight and an algorithm has to work with two packages and an interface between them.

The alternative in the ecosystem is the other direction, a graph type that carries attributes on its vertices and edges natively, where weights are fields and algorithms read them directly. That is convenient and it is also a commitment: the type system of a generic attribute-carrying graph is a much larger surface, and the algorithms have to agree about how attributes are typed and accessed.

The documentation structure reflects the split too. The full documentation is at GitHub Pages with separate stable and dev builds, and documentation for methods is also available via the Julia REPL help system, which is the path most Julia developers take first. Additional tutorials live in a separate repository, JuliaGraphsTutorials, rather than in the docs tree.

Project history, and what migrating from LightGraphs involves

Graphs.jl is the successor to LightGraphs.jl, which was archived in October 2021, and the README points at the CHANGELOG for the full transition history. That single sentence tells you most of what a migrating user needs to know about the upgrade cost, because the transition was long enough to have its own detailed history in a changelog rather than a short note.

LightGraphs was the previous name of the same idea: the graph types, the abstract interface and the algorithms. The rename to Graphs.jl was not a rewrite so much as a re-homing, and the fact that the algorithms are written against `AbstractGraph` rather than against the concrete types is what made the transition possible without breaking every downstream package.

For a user upgrading, the practical question is which of the two you have in your Project.toml and which API your code uses. A project pinned to LightGraphs needs its dependency updated and then its call sites adjusted, and the CHANGELOG is the place to find out what changed and when, since the deprecation was staged across releases rather than done at once.

The repository structure supports the ongoing work. There is a src/ directory for the source, test/ for the test suite, docs/ for the documentation, an ext/ directory for package extensions, a benchmark/ directory, and at the top level a Project.toml for the package metadata, a CHANGELOG.md, a CITATION.bib, a CONTRIBUTING.md, a LICENSE.md and a .JuliaFormatter.toml.

The badge set, and what it says about the project's process

The README's badge row is longer than most Julia packages carry, and each badge points at something specific about how the project is run.

There is a build status badge pointing at the GitHub Actions CI workflow on the master branch, and a code coverage badge pointing at codecov for the same branch. The code style badge names Blue, the style guide from invenia, and the repository also carries a .JuliaFormatter.toml, so the formatting is machine enforced rather than a matter of reviewer vigilance. An Aqua QA badge points at Aqua.jl, the quality assurance package that checks a Julia package for things like method ambiguities, unbound type parameters and stale dependencies, which is a systematic check of the kind of problems that a large interface-based package can accumulate. There is also a ColPrac badge for the collaborative practices guide for community packages, the SciML document that covers how community packages handle things like versioning and deprecation.

The documentation has two badges, one for the stable build and one for dev, and both are hosted at juliagraphs.org. The dev build is the one that tracks master, and the stable build is the one a reader should follow for published API.

The contributions policy is stated in the README as welcoming contributions and bug reports, with the detail in CONTRIBUTING.md, and the project subscribes to the Julia Community Standards, which is the code of conduct and the general behaviour agreement for the wider Julia ecosystem. The citing section asks users to cite the work and points at a CITATION.bib file in the repository for the latest citation information.

Where Graphs.jl is the wrong choice

Three cases point elsewhere. The first is a project whose graph carries rich data on its vertices and edges and whose algorithms need to see that data directly. The explicit design decision about storing data outside the graph means you are building a parallel structure, mapping from vertex identifiers to your own records, and passing it to the algorithms that need it. If the majority of your work is graph queries that read attributes, that arrangement costs more than it saves, and a property graph package from the same organisation is the closer fit.

The second is a project that wants a self-contained graph library with file formats, IO and weighted graphs included. Graphs.jl deliberately leaves those to sibling packages, so an end-to-end project needs several dependencies and has to work out which combination is compatible, rather than one install.

The third is a team that wants a graph API that is stable across many years. The `AbstractGraph` interface is a contract that other packages implement and that the algorithms are written against, so it is stable in the way a public interface is, but the concrete types have changed under it through the LightGraphs transition and can change again. A team that has to support a long-lived codebase should treat the version in Project.toml as a real dependency decision rather than taking whatever the resolver picks.

The alternative worth weighing is writing the graph algorithms directly against a specialised library, whether that is a property graph implementation, a GPU-oriented structure, or an in-house type. The difference in approach is that Graphs.jl gives you a broad algorithm catalogue for free once your type implements the interface, and the cost is that your type has to satisfy a contract written for the general case. Building your own means the algorithms fit your representation exactly, and you write and maintain them. For a graph problem where a handful of traversals and centrality measures is all you need, the general library is the cheaper route. For a problem where the graph representation is the point, and the data model matters more than the algorithm catalogue, the specialised library wins.

Editorial conclusion

Graphs.jl fits a Julia developer who needs graph algorithms and wants them to work across several graph representations rather than being tied to one, and who is prepared to keep vertex and edge data outside the graph structure as the design intends. It does not fit a project that needs weighted graphs, property graphs or advanced file formats, because the README sends those to other packages in the JuliaGraphs organisation, and it does not fit a developer who wants a batteries-included graph data model. Before you build on it, read the Related packages section to see which of the sibling packages you actually need alongside it, and check the CHANGELOG if you are migrating from LightGraphs, since this package is its successor and the transition history is long.

Frequently asked questions

Official sources

1. Issues
2. JuliaGraphs/Graphs.jl on GitHub
3. Project website
4. README
5. Releases