I made a few minor modifications to the algorithms from what we wrote together today. I'm happy to answer any questions. I tinkered around a little to make things faster.

We can probably get this to work withdask-graphblas too, which I think would be pretty interesting, because it can create a massive, distributed matrix. It may not be thebest way to compute APSP, buta way is better than no way at all :)

See the original LAGraph version of Floyd-Warshall here:
https://github.com/GraphBLAS/LAGraph/blob/ed55a49ee7138d2b5a6c5eb4329ccd0bf9e4ac17/old/experimental_algorithm/LAGraph_FW.c

I'll try to benchmark and compare this with a NumPy implementation on a beefy machine with lots of memory.

Addfloyd_warshall

f2f2cec

Copy link

Member

SultanOrazbayev commentedJan 31, 2023

A potential optimization is to loop over n, where n is rows with non-zero values.

Copy link

codecov-commenter commentedJan 31, 2023•
edited
Loading

Codecov Report

Base:72.91% // Head:72.25% // Decreases project coverage by-0.66%⚠️

Coverage data is based on head(b02851b) compared to base(140bea8).
Patch coverage: 38.29% of modified lines in pull request are covered.

📣 This organization is not using Codecov’sGitHub App Integration. We recommend you install it so Codecov can continue to function properly for your repositories.Learn more

Additional details and impacted files

@@            Coverage Diff             @@##             main      #42      +/-   ##==========================================- Coverage   72.91%   72.25%   -0.66%==========================================  Files          70       72       +2       Lines        2573     2617      +44       Branches      475      479       +4     ==========================================+ Hits         1876     1891      +15- Misses        528      557      +29  Partials      169      169

Impacted Files	Coverage Δ
...blas_algorithms/algorithms/shortest_paths/dense.py	`16.12% <16.12%> (ø)`
graphblas_algorithms/nxapi/shortest_paths/dense.py	`57.14% <57.14%> (ø)`
...s_algorithms/algorithms/shortest_paths/__init__.py	`100.00% <100.00%> (ø)`
graphblas_algorithms/interface.py	`97.46% <100.00%> (+0.13%)`	⬆️
...phblas_algorithms/nxapi/shortest_paths/__init__.py	`100.00% <100.00%> (ø)`

Help us with your feedback. Take ten seconds to tell ushow you rate us. Have a feature suggestion?Share it here.

☔ View full report at Codecov.
📢 Do you have feedback about the report comment?Let us know in this issue.

Optimization: better handle sparsity such as skip empty nodes

44d2719

Copy link

MemberAuthor

eriknw commentedJan 31, 2023•
edited
Loading

A potential optimization is to loop over n, where n is rows with non-zero values.

Good suggestion. I added an optimization where we only iterate over vertices that have nonempty rowsand nonempty columns. Ithink this behaves correctly, but would appreciate if somebody could verify it.

I also introduced another temporary matrix to hold the outer product. We then drop the diagonal values from them.

All this performs better or similar in my limited benchmarking. Our strategy of keeping things sparse isprobably reasonable, because what if there are multiple groups of connected components? The final result frequently may not be dense.

With the goal of "keeping things sparse", I wonder if there are any heuristics we could employ, such as iterating over vertices with small degrees first.

eriknw commented

Jan 31, 2023

View reviewed changes

graphblas_algorithms/algorithms/shortest_paths/dense.py

		A, row_degrees, column_degrees = G.get_properties("offdiag row_degrees- column_degrees-")
		nonempty_nodes = binary.pair(row_degrees & column_degrees).new(name="nonempty_nodes")
		else:
		A, nonempty_nodes = G.get_properties("offdiag degrees-")

Copy link

MemberAuthor

eriknwJan 31, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Note that we use some shorthand notation here."degrees-"does not include self-edges (i.e., diagonals), but"degrees+"does include self-edges.

Simplify (so this PR can be a reference)

f96a8a2

SultanOrazbayev reviewed

Feb 1, 2023

View reviewed changes

graphblas_algorithms/algorithms/shortest_paths/dense.py

		Row = Matrix(dtype, nrows=1, ncols=n, name="Row")
		Col = Matrix(dtype, nrows=n, ncols=1, name="Col")
		Outer = Matrix(dtype, nrows=n, ncols=n, name="temp")
		for i in nonempty_nodes:

Copy link

Member

SultanOrazbayevFeb 1, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others.Learn more.

Looks good!

Copy link

Member

SultanOrazbayev commentedFeb 1, 2023

With the goal of "keeping things sparse", I wonder if there are any heuristics we could employ, such as iterating over vertices with small degrees first.

Not sure about this, it could lead to gotchas if users don't expect sorting to happen. (and sorting itself could be an issue, e.g. when using distributed graphs)

Better name ("Outer", not "temp")

b02851b

eriknw merged commit6dd93bd intopython-graphblas:main

Feb 2, 2023

eriknw mentioned this pull request

Feb 7, 2023

Add floyd_warshall_predecessor_and_distance#43

Merged

Labels

None yet

Movatterモバイル変換

Navigation Menu

Search code, repositories, users, issues, pull requests...

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Add`floyd_warshall`#42

Add`floyd_warshall`#42

Uh oh!

Conversation

eriknw commentedJan 31, 2023•
edited
Loading

Uh oh!