The JuliaGraphs ecosystem offers a set of abstractions and algorithms for various aspects of graph modeling and analysis. LightGraphs.jl is the central package defining the types and essential algorithms.
Mentorship Inquiries: Drop by #graphs on Slack or file a new issue on Github.
The LightGraphs.jl package provides a fast, robust set of graph analysis tools. This project would implement additions to LightGraphs to support parallel computation for a subset of graph algorithms. Examples of algorithms that would benefit from adaptation to parallelism would include centrality measures and traversals.
Expected Results: creation of LightGraphs-based data structures and algorithms that take advantage of large-scale parallel computing environments.
At the moment, LightGraphs.jl lacks algorithms that deal with graph planarity and familiar concepts. A candidate should study the literature and implement some algorithms that deal with planarity. Potential things that could be done:
GraphBLAS is a standard similar to BLAS for dealing with graphs. There also exists a reference implementation called SuiteSparse:GraphBLAS. It would be interesting to have a bridge from LightGraphs.jl to GraphBLAS, so we can compare the performance. A candidate should do the following:
The GraphPlots.jl package could use some improvements:
LightGraphsMatching.jl currently depends on the external software BlossomV. In the past we had some problems calling that software from Julia and in addition it has a problematic license. Therefore it would be useful if we had a native Julia implementation of this algorithm. This is a rather advanced project. In addition to standard graph theory, a candidate should probably have some minor knowledge of linear programming and duality of linear programs.
LightGraphs.jl could use a set of benchmarks for measuring the performance of our algorithms and for spotting performance regressions in further updates. A candidate should do the following