Switch to an adjacency list storage of vertices.

Open
  • Is something wrong?
#25 3 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
30/100
Issue type
Refactor
Clarity
Needs clarification
Activity status
Stale
Tech stack
julia
Domain
data

Research direction

Start with the linked Discourse conversation and examine the current sparse-matrix representation, adjacency lists, outneighbor access, and weight lookup behavior. Benchmark single-weight access and iteration over neighbors, then compare the proposed adjacency-list designs; done means selecting and implementing the best-supported storage approach.

Written by the indexing model from the issue text.

Description

enhancement

See this conversation

This seems to be mostly equivalent to a sparse matrix (I mentioned slower access of weights, but using binary search, I think it should be same complexity than for a sparse matrix)
You can get back the sparse matrix by simply:

  • collecting the weights in the order found in the adjacency list
  • concatenating the outneighbors adjacency lists
  • computing the cumulative degrees of the vertices.

As shown in the discussion, the benefit obtained by iterating simultaneously weights and vertices can be also achieved with the sparse matrix implementation, although it seems a bit slower.

The proposed implementation is by storing tuples in the adjacency lists, but it might be better to store in some aside adjacency list to avoid the penalty cost of accessing tuple when considering only neighbors. (we can still zip through both lists at the same time).

At this point, I think the bigger drawback will be the linear cost for generating the weight matrix, all other computations should be asymptotically equivalent.
I think we need some benchmarking to find the best implementation, by considering both the access of a single weight and the access of weights when iterating neighbors.

Dominant language
Julia
Stars
41
Forks
9
Avg merge
1d 21h
Merged PRs (30d)
1

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from JuliaGraphs/SimpleWeightedGraphs.jl

All issues in JuliaGraphs/SimpleWeightedGraphs.jl

Similar issues

More Julia issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.