Page MenuHomeSoftware Heritage
Differential D2249

swh-graph: add random walk endpoint
ClosedPublic
Actions

Authored by zack on Nov 11 2019, 7:05 PM.

Details

Reviewers
seirl
Maniphest Tasks
T2077: add random walk endpoint with limited retries
Summary

probably still a lot to be improved in terms of code cleanness, but the main
functionality seems to work and is both pretty robust and fast

Closes T2077

Diff Detail

Repository
rDGRPH Compressed graph representation
Branch
feature/random-walk
Lint
No Linters Available
Unit
No Unit Test Coverage
Build Status
Buildable 8934
Build 13048: tox-on-jenkinsJenkins
Build 13047: arc lint + arc unit

Event Timeline

zack created this revision.Nov 11 2019, 7:05 PM
swh-public-ci added a comment.Nov 11 2019, 7:07 PM

Build is green
See https://jenkins.softwareheritage.org/job/DGRPH/job/tox/82/ for more details.

Harbormaster completed remote builds in B8934: Diff 7755.Nov 11 2019, 7:07 PM
seirl requested changes to this revision.Nov 12 2019, 1:12 AM
seirl added inline comments.
docs/api.rst
199

Not the correct format but this should be fixed in all the methods, so I think it's fine to have the wrong one until the rest of the doc is fixed.

java/src/main/java/org/softwareheritage/graph/algo/Traversal.java
309

I'm not quite sure this is the semantic we want here, as we do access the edges even when we don't pick them. (Feel free to disagree with my idea of what nbEdgesAccessed should represent.)

349

Asserts are disabled in release mode, maybe we want to throw an actual error here?

swh/graph/server/app.py
92

Maybe simpler:

if random:
    it = backend.random_walk(...)
else:
    it = backend.walk(...)

for res_node in it:
    ...
This revision now requires changes to proceed.Nov 12 2019, 1:12 AM
zack marked 4 inline comments as done.Nov 12 2019, 8:47 AM
zack added inline comments.
java/src/main/java/org/softwareheritage/graph/algo/Traversal.java
309

ah, good point, I'm updating to also count the skipped edges

(not that it matters much, as we are no longer returning the stats and we should probably remove that accounting anyway; but while it's in it should indeed be correct)

349

ah, that's why I didn't hit this while debugging :-)
fixed

zack updated this revision to Diff 7764.Nov 12 2019, 8:48 AM
zack marked 2 inline comments as done.
  • skeleton for random walk endpoint
  • REST client: add binding for /randomwalk
  • test_api_client: add test case for /randomwalk
  • REST doc: update /randomwalk doc to match what is returned
  • access edge stats: also count skipped edges for /randomwalk
  • /randomwalk: use proper runtime errors instead of assertions
  • app.py: add TODO about making RANDOM_RETRIES configurable
  • app.py: refactor random v. non-random walk iteration logic
swh-public-ci added a comment.Nov 12 2019, 8:50 AM

Build is green
See https://jenkins.softwareheritage.org/job/DGRPH/job/tox/87/ for more details.

Harbormaster completed remote builds in B8943: Diff 7764.Nov 12 2019, 8:50 AM
zack updated this revision to Diff 7766.Nov 12 2019, 10:58 AM
  • randomwalk: do not bother randomizing singleton sets
swh-public-ci added a comment.Nov 12 2019, 11:48 AM

Build was aborted

Link to build: https://jenkins.softwareheritage.org/job/DGRPH/job/tox/89/
See console output for more information: https://jenkins.softwareheritage.org/job/DGRPH/job/tox/89/console

Harbormaster failed remote builds in B8945: Diff 7766!Nov 12 2019, 11:48 AM
zack updated this revision to Diff 7770.Nov 12 2019, 1:31 PM

swh-graph: add random walk endpoint

swh-public-ci added a comment.Nov 12 2019, 1:33 PM

Build is green
See https://jenkins.softwareheritage.org/job/DGRPH/job/tox/93/ for more details.

Harbormaster completed remote builds in B8950: Diff 7770.Nov 12 2019, 1:33 PM
zack updated this revision to Diff 7786.Nov 12 2019, 5:38 PM
  • random walk: include starting node into returned path
  • random walk: use reservoir sampling to pick random successor
swh-public-ci added a comment.Nov 12 2019, 5:40 PM

Build is green
See https://jenkins.softwareheritage.org/job/DGRPH/job/tox/94/ for more details.

Harbormaster completed remote builds in B8963: Diff 7786.Nov 12 2019, 5:40 PM
seirl accepted this revision.Nov 13 2019, 5:44 PM
This revision is now accepted and ready to land.Nov 13 2019, 5:44 PM
zack updated this revision to Diff 7823.Nov 13 2019, 6:01 PM
  • add random walk endpoint
  • random walk: include starting node into returned path
  • random walk: use reservoir sampling to pick random successor
swh-public-ci added a comment.Nov 13 2019, 6:03 PM

Build is green
See https://jenkins.softwareheritage.org/job/DGRPH/job/tox/96/ for more details.

Harbormaster completed remote builds in B9011: Diff 7823.Nov 13 2019, 6:03 PM
zack closed this revision.Nov 13 2019, 6:04 PM

merged in 97e79c289aff6625ebdd9068a006c10aca28fc12

Revision Contents
Changeset List

PathSize
docs/
37 lines
java/
src/
main/
java/
org/
softwareheritage/
graph/
21 lines
algo/
115 lines
swh/
graph/
10 lines
8 lines
server/
53 lines
tests/
13 lines

Diff 7755

View Options

docs/api.rst

Loading...
View Options

java/src/main/java/org/softwareheritage/graph/Entry.java

Loading...
View Options

java/src/main/java/org/softwareheritage/graph/algo/Traversal.java

Loading...
View Options

swh/graph/backend.py

Loading...
View Options

swh/graph/client.py

Loading...
View Options

swh/graph/server/app.py

Loading...
View Options

swh/graph/tests/test_api_client.py

Loading...
About · Developer information · Legal