Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

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

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Add a few more BFS-based algorithms#51

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.

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

Already on GitHub?Sign in to your account

Merged
eriknw merged 7 commits intopython-graphblas:mainfromeriknw:more_bfs
Apr 15, 2023
Merged
Show file tree
Hide file tree
Changes fromall commits
Commits
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
33 changes: 25 additions & 8 deletions.pre-commit-config.yaml
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -4,6 +4,11 @@
# To run: `pre-commit run --all-files`
# To update: `pre-commit autoupdate`
# - &flake8_dependencies below needs updated manually
ci:
# See: https://pre-commit.ci/#configuration
autofix_prs: false
autoupdate_schedule: monthly
skip: [no-commit-to-branch]
fail_fast: true
default_language_version:
python: python3
Expand All@@ -20,12 +25,13 @@ repos:
- id: mixed-line-ending
- id: trailing-whitespace
- repo: https://github.com/abravalheri/validate-pyproject
rev: v0.12.1
rev: v0.12.2
hooks:
- id: validate-pyproject
name: Validate pyproject.toml
# I don't yet trust ruff to do what autoflake does
- repo: https://github.com/myint/autoflake
rev: v2.0.1
rev: v2.0.2
hooks:
- id: autoflake
args: [--in-place]
Expand All@@ -44,36 +50,47 @@ repos:
- id: auto-walrus
args: [--line-length, "100"]
- repo: https://github.com/psf/black
rev: 23.1.0
rev: 23.3.0
hooks:
- id: black
# - id: black-jupyter
- repo: https://github.com/charliermarsh/ruff-pre-commit
rev: v0.0.261
hooks:
- id: ruff
args: [--fix-only, --show-fixes]
- repo: https://github.com/PyCQA/flake8
rev: 6.0.0
hooks:
- id: flake8
additional_dependencies: &flake8_dependencies
# These versions need updated manually
- flake8==6.0.0
- flake8-comprehensions==3.10.1
- flake8-bugbear==23.2.13
- flake8-simplify==0.19.3
- flake8-bugbear==23.3.23
- flake8-simplify==0.20.0
- repo: https://github.com/asottile/yesqa
rev: v1.4.0
hooks:
- id: yesqa
additional_dependencies: *flake8_dependencies
- repo: https://github.com/codespell-project/codespell
rev: v2.2.2
rev: v2.2.4
hooks:
- id: codespell
types_or: [python, rst, markdown]
additional_dependencies: [tomli]
files: ^(graphblas_algorithms|docs)/
- repo: https://github.com/charliermarsh/ruff-pre-commit
rev: v0.0.253
rev: v0.0.261
hooks:
- id: ruff
# `pyroma` may help keep our package standards up to date if best practices change.
# This is probably a "low value" check though and safe to remove if we want faster pre-commit.
- repo: https://github.com/regebro/pyroma
rev: "4.2"
hooks:
- id: pyroma
args: [-n, "10", .]
- repo: https://github.com/pre-commit/pre-commit-hooks
rev: v4.4.0
hooks:
Expand Down
15 changes: 13 additions & 2 deletionsREADME.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -117,6 +117,10 @@ dispatch pattern shown above.
- Community
- inter_community_edges
- intra_community_edges
- Components
- is_connected
- is_weakly_connected
- node_connected_component
- Core
- k_truss
- Cuts
Expand DownExpand Up@@ -147,11 +151,15 @@ dispatch pattern shown above.
- is_k_regular
- is_regular
- Shortest Paths
- all_pairs_bellman_ford_path_length
- all_pairs_shortest_path_length
- floyd_warshall
- floyd_warshall_predecessor_and_distance
- single_source_bellman_ford_path_length
- all_pairs_bellman_ford_path_length
- has_path
- negative_edge_cycle
- single_source_bellman_ford_path_length
- single_source_shortest_path_length
- single_target_shortest_path_length
- Simple Paths
- is_simple_path
- S Metric
Expand All@@ -162,5 +170,8 @@ dispatch pattern shown above.
- is_tournament
- score_sequence
- tournament_matrix
- Traversal
- bfs_layers
- descendants_at_distance
- Triads
- is_triad
2 changes: 2 additions & 0 deletionsgraphblas_algorithms/algorithms/__init__.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -3,6 +3,7 @@
from .centrality import *
from .cluster import *
from .community import *
from .components import *
from .core import *
from .cuts import *
from .dag import *
Expand All@@ -16,4 +17,5 @@
from .smetric import *
from .structuralholes import *
from .tournament import *
from .traversal import *
from .triads import *
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -27,7 +27,7 @@ def eigenvector_centrality(G, max_iter=100, tol=1.0e-6, nstart=None, name="eigen
# Power iteration: make up to max_iter iterations
A = G._A
xprev = Vector(float, N, name="x_prev")
for_ in range(max_iter):
for_i in range(max_iter):
xprev << x
x += x @ A
normalize(x, "L2")
Expand Down
2 changes: 1 addition & 1 deletiongraphblas_algorithms/algorithms/centrality/katz.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -44,7 +44,7 @@ def katz_centrality(

# Power iteration: make up to max_iter iterations
xprev = Vector(float, N, name="x_prev")
for_ in range(max_iter):
for_i in range(max_iter):
xprev, x = x, xprev
# x << alpha * semiring(xprev @ A) + beta
x << semiring(xprev @ A)
Expand Down
2 changes: 2 additions & 0 deletionsgraphblas_algorithms/algorithms/components/__init__.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
from .connected import *
from .weakly_connected import *
31 changes: 31 additions & 0 deletionsgraphblas_algorithms/algorithms/components/connected.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
from graphblas import Vector, replace
from graphblas.semiring import any_pair

from graphblas_algorithms.algorithms.exceptions import PointlessConcept


def is_connected(G):
if len(G) == 0:
raise PointlessConcept("Connectivity is undefined for the null graph.")
return _plain_bfs(G, next(iter(G))).nvals == len(G)


def node_connected_component(G, n):
return _plain_bfs(G, n)


def _plain_bfs(G, source):
index = G._key_to_id[source]
A = G.get_property("offdiag")
n = A.nrows
v = Vector(bool, n, name="bfs_plain")
q = Vector(bool, n, name="q")
v[index] = True
q[index] = True
any_pair_bool = any_pair[bool]
for _i in range(1, n):
q(~v.S, replace) << any_pair_bool(q @ A)
if q.nvals == 0:
break
v(q.S) << True
return v
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
from graphblas import Vector, binary, replace
from graphblas.semiring import any_pair

from graphblas_algorithms.algorithms.exceptions import PointlessConcept


def is_weakly_connected(G):
if len(G) == 0:
raise PointlessConcept("Connectivity is undefined for the null graph.")
return _plain_bfs(G, next(iter(G))).nvals == len(G)


# TODO: benchmark this and the version commented out below
def _plain_bfs(G, source):
# Bi-directional BFS w/o symmetrizing the adjacency matrix
index = G._key_to_id[source]
A = G.get_property("offdiag")
# XXX: should we use `AT` if available?
n = A.nrows
v = Vector(bool, n, name="bfs_plain")
q_out = Vector(bool, n, name="q_out")
q_in = Vector(bool, n, name="q_in")
v[index] = True
q_in[index] = True
any_pair_bool = any_pair[bool]
is_out_empty = True
is_in_empty = False
for _i in range(1, n):
# Traverse out-edges from the most recent `q_in` and `q_out`
if is_out_empty:
q_out(~v.S) << any_pair_bool(q_in @ A)
else:
q_out << binary.any(q_out | q_in)
q_out(~v.S, replace) << any_pair_bool(q_out @ A)
is_out_empty = q_out.nvals == 0
if not is_out_empty:
v(q_out.S) << True
elif is_in_empty:
break
# Traverse in-edges from the most recent `q_in` and `q_out`
if is_in_empty:
q_in(~v.S) << any_pair_bool(A @ q_out)
else:
q_in << binary.any(q_out | q_in)
q_in(~v.S, replace) << any_pair_bool(A @ q_in)
is_in_empty = q_in.nvals == 0
if not is_in_empty:
v(q_in.S) << True
elif is_out_empty:
break
return v


"""
def _plain_bfs(G, source):
# Bi-directional BFS w/o symmetrizing the adjacency matrix
index = G._key_to_id[source]
A = G.get_property("offdiag")
n = A.nrows
v = Vector(bool, n, name="bfs_plain")
q = Vector(bool, n, name="q")
q2 = Vector(bool, n, name="q_2")
v[index] = True
q[index] = True
any_pair_bool = any_pair[bool]
for _i in range(1, n):
q2(~v.S, replace) << any_pair_bool(q @ A)
v(q2.S) << True
q(~v.S, replace) << any_pair_bool(A @ q)
if q.nvals == 0:
if q2.nvals == 0:
break
q, q2 = q2, q
elif q2.nvals != 0:
q << binary.any(q | q2)
return v
"""
18 changes: 11 additions & 7 deletionsgraphblas_algorithms/algorithms/dag.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
from graphblas import Vector, replace
from graphblas.semiring importlor_pair
from graphblas.semiring importany_pair

__all__ = ["descendants", "ancestors"]

Expand All@@ -10,10 +10,12 @@ def descendants(G, source):
raise KeyError(f"The node {source} is not in the graph")
index = G._key_to_id[source]
A = G.get_property("offdiag")
q = Vector.from_coo(index, True, size=A.nrows, name="q")
q = Vector(bool, size=A.nrows, name="q")
q[index] = True
rv = q.dup(name="descendants")
for _ in range(A.nrows):
q(~rv.S, replace) << lor_pair(q @ A)
any_pair_bool = any_pair[bool]
for _i in range(A.nrows):
q(~rv.S, replace) << any_pair_bool(q @ A)
if q.nvals == 0:
break
rv(q.S) << True
Expand All@@ -26,10 +28,12 @@ def ancestors(G, source):
raise KeyError(f"The node {source} is not in the graph")
index = G._key_to_id[source]
A = G.get_property("offdiag")
q = Vector.from_coo(index, True, size=A.nrows, name="q")
q = Vector(bool, size=A.nrows, name="q")
q[index] = True
rv = q.dup(name="descendants")
for _ in range(A.nrows):
q(~rv.S, replace) << lor_pair(A @ q)
any_pair_bool = any_pair[bool]
for _i in range(A.nrows):
q(~rv.S, replace) << any_pair_bool(A @ q)
if q.nvals == 0:
break
rv(q.S) << True
Expand Down
4 changes: 2 additions & 2 deletionsgraphblas_algorithms/algorithms/dominating.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,8 @@
from graphblas.semiring importlor_pair
from graphblas.semiring importany_pair

__all__ = ["is_dominating_set"]


def is_dominating_set(G, nbunch):
nbrs =lor_pair(nbunch @ G._A).new(mask=~nbunch.S) # A or A.T?
nbrs =any_pair[bool](nbunch @ G._A).new(mask=~nbunch.S) # A or A.T?
return nbrs.size - nbunch.nvals - nbrs.nvals == 0
4 changes: 4 additions & 0 deletionsgraphblas_algorithms/algorithms/exceptions.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -14,5 +14,9 @@ class PointlessConcept(GraphBlasAlgorithmException):
pass


class NoPath(GraphBlasAlgorithmException):
pass


class Unbounded(GraphBlasAlgorithmException):
pass
4 changes: 2 additions & 2 deletionsgraphblas_algorithms/algorithms/link_analysis/hits_alg.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -30,7 +30,7 @@ def hits(G, max_iter=100, tol=1.0e-8, nstart=None, normalized=True, *, with_auth
a, h = h, a
ATA = (A.T @ A).new(name="ATA") # Authority matrix
aprev = Vector(float, N, name="a_prev")
for_ in range(max_iter):
for_i in range(max_iter):
aprev, a = a, aprev
a << ATA @ aprev
normalize(a, "Linf")
Expand All@@ -41,7 +41,7 @@ def hits(G, max_iter=100, tol=1.0e-8, nstart=None, normalized=True, *, with_auth
raise ConvergenceFailure(max_iter)
else:
hprev = Vector(float, N, name="h_prev")
for_ in range(max_iter):
for_i in range(max_iter):
hprev, h = h, hprev
a << hprev @ A
h << A @ a
Expand Down
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -79,7 +79,7 @@ def pagerank(
# Power iteration: make up to max_iter iterations
xprev = Vector(float, N, name="x_prev")
w = Vector(float, N, name="w")
for_ in range(max_iter):
for_i in range(max_iter):
xprev, x = x, xprev

# x << alpha * ((xprev * S) @ A + "dangling_weights") + (1 - alpha) * p
Expand Down
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,4 @@
from .dense import *
from .generic import *
from .unweighted import *
from .weighted import *
23 changes: 13 additions & 10 deletionsgraphblas_algorithms/algorithms/shortest_paths/generic.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
from graphblas import Vector, replace
from graphblas.semiring importlor_pair
from graphblas.semiring importany_pair

__all__ = ["has_path"]

Expand All@@ -11,23 +11,26 @@ def has_path(G, source, target):
if src == dst:
return True
A = G.get_property("offdiag")
q_src = Vector.from_coo(src, True, size=A.nrows, name="q_src")
q_src = Vector(bool, size=A.nrows, name="q_src")
q_src[src] = True
seen_src = q_src.dup(name="seen_src")
q_dst = Vector.from_coo(dst, True, size=A.nrows, name="q_dst")
seen_dst = q_dst.dup(name="seen_dst")
for _ in range(A.nrows // 2):
q_src(~seen_src.S, replace) << lor_pair(q_src @ A)
q_dst = Vector(bool, size=A.nrows, name="q_dst")
q_dst[dst] = True
seen_dst = q_dst.dup(name="seen_dst", clear=True)
any_pair_bool = any_pair[bool]
for _i in range(A.nrows // 2):
q_src(~seen_src.S, replace) << any_pair_bool(q_src @ A)
if q_src.nvals == 0:
return False
iflor_pair(q_src @ q_dst):
ifany_pair_bool(q_src @ q_dst):
return True

q_dst(~seen_dst.S, replace) << lor_pair(A @ q_dst)
seen_dst(q_dst.S) << True
q_dst(~seen_dst.S, replace) << any_pair_bool(A @ q_dst)
if q_dst.nvals == 0:
return False
iflor_pair(q_src @ q_dst):
ifany_pair_bool(q_src @ q_dst):
return True

seen_src(q_src.S) << True
seen_dst(q_dst.S) << True
return False
Loading
[8]ページ先頭
©2009-2025 Movatter.jp