Working with graphs in Julia
Latest commit 9cb3624 Oct 6, 2016 @dehann dehann committed on GitHub Merge pull request #225 from dehann/master
Implement dicts and fix shortest_path bug
Failed to load latest commit information.
doc Update to 0.4 Jun 26, 2015
src fix Sep 30, 2016
test Fix dep warns Aug 16, 2016
.gitignore add sphinx document Apr 21, 2013
.travis.yml Drop 0.3 support, add 0.5 Aug 16, 2016 Usable graphs package Dec 24, 2012 Add maintenance status note to README (#229) Aug 27, 2016
REQUIRE Change min version in REQUIRE to v0.4 Aug 16, 2016


Build Status Coverage Status

Graphs Graphs

Graphs.jl is a Julia package that provides graph types and algorithms. The design of this package is inspired by the Boost Graph Library (e.g. using standardized generic interfaces), while taking advantage of Julia's language features (e.g. multiple dispatch).

Note: as of 2016, this package's original author is no longer actively maintaining it. See the discussion here.

Main Features

An important aspect of Graphs.jl is the generic abstraction of graph concepts expressed via standardized interfaces, which allows access to a graph's structure while hiding the implementation details. This encourages reuse of data structures and algorithms. In particular, one can write generic graph algorithms that can be applied to different graph types as long as they implement the required interface.

In addition to the generic abstraction, there are other important features:

  • A variety of graph types tailored to different purposes

    • generic adjacency list
    • generic incidence list
    • a simple graph type with compact and efficient representation
    • an extended graph type that supports labels and attributes
  • A collection of graph algorithms:

    • graph traversal with visitor support: BFS, DFS
    • cycle detection
    • connected components
    • topological sorting
    • shortest paths: Dijkstra, Floyd-Warshall, A*
    • minimum spanning trees: Prim, Kruskal
    • maximal cliques
    • random graph generation: Erdős–Rényi, Watts-Strogatz (see the RandomGraphs.jl package for more random graph models)
    • more algorithms are being implemented
  • Matrix-based characterization: adjacency matrix, weight matrix, Laplacian matrix

  • All data structures and algorithms are implemented in pure Julia, and thus they are portable.

  • We paid special attention to the runtime performance. Many of the algorithms are very efficient. For example, a benchmark shows that it takes about 15 milliseconds to run the Dijkstra's algorithm over a graph with 10 thousand vertices and 1 million edges on a macbook pro.


Please refer to Graphs.jl Documentation for latest documentation.