Skip to content

GSoC 2015 Application (Lucas Jones): Adjacency matrix representation

Jump to bottom Edit New page
Lucas Jones edited this page Mar 20, 2015 · 1 revision

NetworkX: Adjacency matrix representation

Student Information

University Information

  • University(*):
  • Major(*):
    • Mathematics
  • Current Year and Expected Graduation date(*):
    • Third year
    • Expected graduation: June 2017
  • Degree(*) (e.g. BSc, PhD):
    • MMath in Mathematics (5 year integrated undergraduate/masters programme)

Project Proposal Information

  • Proposal Title (*)
    • NetworkX: Adjacency matrix representation
  • Proposal Abstract (*)
    • The goal is to implement an adjacency matrix representation for graphs in NetworkX, complementing the current adjacency list format. Many algorithms are far more efficient working on these adjacency matrices. In addition, there are many ways of storing the matrices `sparsely', massively reducing their space overhead and making it feasible even for very large graphs.  Combined, this means a matrix representation in NetworkX would allow it to analyse bigger graphs even faster than it can now.
  • Link to a patch/code sample, preferably one you have submitted to your sub-org (*)
  • Links to additional information

 

Personal Background

I am a third year student studying for an MMath in Mathematics at the University of St Andrews, Scotland. In my degree course, I have focussed on pure and discrete mathematics, including honours modules on graph theory and symbolic computation. I've been programming as a hobby for many years; recently, this has primarily been in Python and C.

Since I came to my maths degree course with a computational background, rather than the other way around, I have always been interested in relating the abstract concepts I've learned into the more concrete setting of computing. This project is the perfect way to combine two areas of mathematics --- graph theory and linear algebra --- that I have studied in the past. These are presented rather disparately in lecture courses, and the project will help me really understand the links between them, through using them to solve real-world problems.

Proposal Overview

I plan to implement new classes, SparseMatrixGraph and SparseMatrixDigraph, and their DenseMatrix equivalents, which will use either sparse matrices from the SciPy's `sparse` module [4] or ordinary NumPy dense matrices [5] to store their underlying adjacency matrices. As the two modules are already optional dependencies for NetworkX, this is not expected to be too intrusive a requirement.

I aim to preserve as much of the same functionality and interface as the existing Graph class as possible, except where this would be extremely inefficient. Any functionality common either between the two matrix graph classes or the matrix and adjacency list classes, such as high-level convenience methods, will be factored out into a common subclass in an effort to reduce redundancy.

Once the groundwork of the core matrix graph representation is implemented, I then plan to reimplement as many of the existing graph algorithms as possible in terms of the new representation, concentrating especially on those for which linear algebraic methods are particularly efficient: for example, the Floyd-Warshall algorithm for finding shortest path lengths, or computing the various centrality measures. The existing code in the `scipy.sparse.csgraph` [6] module will be an extremely useful starting point for these efforts, since it already implements various search and shortest path algorithms for both graphs and digraphs in this representation.

Project Schedule

  • Weeks 1–2

    Perform an in-depth investigation into SciPy's (and perhaps others') libraries for sparse matrices. Review the literature for the latest results on adjancency matrix-based implementations of the algorithms described above.

    Complete the initial refactoring of the existing Graph class into a common `core' subclass on top of which the new SparseMatrixGraph and DenseMatrixGraph classes can be defined.

  • Weeks 3–4

    Complete implementation of the `core' functionality for sparse and dense matrix graphs: adding and removing edges and vertices, assigning weights, etc., and corresponding test cases. Implement and document functions for converting between sparse, dense and adjacency list representations.

    A pull request should be submitted at the end of this block.

  • Weeks 5–6

    Test the interface of the new graph classes against existing algorithms to ensure as many as possible are at least functional. Correct as many as possible and identify those which are particularly inefficient.

    A pull request should be submitted at the end of this block.

  • Weeks 7–8

    Implement and document wrappers and tests for the functions available in the `scipy.sparse.csgraph` module. Amend functions in existing `linalg` module in NetworkX to work seamlessly with the new classes.

    A pull request should be submitted at the end of this block.

  • Weeks 9–10

    Implement and document the Floyd-Fulkerson/Edmonds-Karp algorithm and appropriate tests, working on the adjacency matrix representation; and centrality measures.

  • Weeks 11–

    Final cleaning up of code and completion of documentation. Merging of new code into the mainline.

    A pull request should be submitted at the end of this block.

Other Schedule Information

  • Please indicate any vacations or other time off that you may be taking or expecting to take over the course of the summer. Any time that you would not be expecting to work should be noted here, along with a reason. (e.g. "June 12-15th, travel for my sister's wedding" "May 30, midterm exam") Google expects you to work 40h/week for the entire GSoC period, so consider how you will make up any lost time (you may have to start coding during community bonding, for example).
    • University exam period is 4–24 May; my last planned exam is May 23.
    • Will work 40 hr/wk as required from May 25.
  • Please indicate any other commitments you have that you think we should know about. (e.g. part time-jobs, large volunteer projects, summer courses)
    • None.
  • Have you applied with any other organizations? If so, do you have a preferred project/org? (This will help us in the event that more than one organization decides they wish to accept your proposal.)
    • None.
Add a custom footer
Add a custom sidebar

Clone this wiki locally