Skip to content

Allow cancelation of Graph Searches #21765

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
wants to merge 27 commits into
base: devel
Choose a base branch
from
Open

Allow cancelation of Graph Searches #21765

wants to merge 27 commits into from
+1,040 −80

Conversation

hkernbach
Copy link
Member

@hkernbach hkernbach commented May 14, 2025 •
edited
Loading

Scope & Purpose

This PR optimizes the cancelation of all graph related searches, including:

  • Traversals (BFS, DSF and weighted order)
  • KPaths
  • ShortestPath
  • KShortestPaths
  • 💩 Bugfix
  • 🍕 New feature
  • 🔥 Performance improvement
  • 🔨 Refactoring/simplification

Checklist

  • Tests
    • Regression tests
    • C++ Unit tests
    • integration tests
    • resilience tests
  • 📖 CHANGELOG entry made
  • 📚 documentation written (release notes, API changes, ...)
  • Backports
    • Backport for 3.12.0: (Please link PR)
    • Backport for 3.11: (Please link PR)
    • Backport for 3.10: (Please link PR)

Related Information

@cla-bot cla-bot bot added the cla-signed label May 14, 2025
@hkernbach hkernbach mentioned this pull request May 14, 2025
Open
@markuspf markuspf self-assigned this Sep 3, 2025
hkernbach and others added 25 commits September 4, 2025 14:42
@hkernbach @markuspf
first draft, added cancel of traversal in one sided enumerator, and t…
5f45c6e 
…o all providers including mock provider - also added unit/gtest for providers
@hkernbach @markuspf
added bidirectionalCircle as new graph in graph test suite
9f751e8
@hkernbach @markuspf
added hugeCompleteGraph
51be506
@hkernbach @markuspf
added query cancel observer to twosided enumerator as well, so kpaths…
8f6659a 
… shortest paths and kshortestpath, also added tests
@hkernbach @markuspf
only print debug creation info if set manually in constructor
e3f7ab8
@hkernbach @markuspf
added additional check for cancelation of query in the twosidedenumer…
6fec0fc 
…ator
@hkernbach @markuspf
eslint
0268917
@hkernbach @markuspf
eslint
5242085
@hkernbach @markuspf
clang format
89f440e
@hkernbach @markuspf
clang format
298877b
@hkernbach @markuspf
batchwise verted and edge insertion during fillGraph (integration tests)
b6c8690
@hkernbach @markuspf
try to help garbage collection v8
105dbae
@hkernbach @markuspf
slightly increased timeout to 10s in clsuter, 5s in single server
9ebfb80
@hkernbach @markuspf
added early exit to weighted two sided enumerator, yens still missing
324aa21
@hkernbach @markuspf
debug flag on
dad761a
@hkernbach @markuspf
no need to call clear manually. will be called in destructor automat…
b158f12 
…ically
@hkernbach @markuspf
format
053e706
@hkernbach @markuspf
improved wait & kill mechanism - should now be way more stable
fbc3be7
@hkernbach @markuspf
adaptive kill query
7db1e7b
@hkernbach @markuspf
increase debug logging. Some are optional, some are mandatory. If our…
d3b10ba 
… CI does not see any log output for 20 minutes - It will abort the job
@hkernbach @markuspf
eslint
670eb98
@hkernbach @markuspf
more test output
80271fb
@jbajic @markuspf
Change test suite params
9ab0e8c
@hkernbach @markuspf
refactored generic graph tests based on Jures suggestion
a42d44f
@hkernbach @markuspf
incr. completegraph to consist out of 1k nodes to make computation mo…
7717203 
…re expensive
@markuspf markuspf force-pushed the feature/abort-traversals branch from 4ec116f to 7717203 Compare September 4, 2025 14:10
@markuspf markuspf marked this pull request as ready for review September 4, 2025 14:11
@markuspf markuspf changed the title Feature/abort traversals Allow cancelation of Graph Searches Sep 4, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees

@markuspf markuspf

Labels
cla-signed
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@hkernbach @markuspf @jbajic