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

A few more algorithms and automatically add algorithms to README#67

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 3 commits intopython-graphblas:mainfromeriknw:auto_tree
Jun 2, 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
10 changes: 6 additions & 4 deletions.github/workflows/lint.yml
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,12 @@
# Rely on pre-commit.ci instead
name: Lint via pre-commit

on:
pull_request:
push:
branches-ignore:
- main
workflow_dispatch:
# pull_request:
# push:
# branches-ignore:
# - main

permissions:
contents: read
Expand Down
10 changes: 5 additions & 5 deletions.pre-commit-config.yaml
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -25,7 +25,7 @@ repos:
- id: mixed-line-ending
- id: trailing-whitespace
- repo: https://github.com/abravalheri/validate-pyproject
rev: v0.12.2
rev: v0.13
hooks:
- id: validate-pyproject
name: Validate pyproject.toml
Expand All@@ -40,7 +40,7 @@ repos:
hooks:
- id: isort
- repo: https://github.com/asottile/pyupgrade
rev: v3.3.2
rev: v3.4.0
hooks:
- id: pyupgrade
args: [--py38-plus]
Expand All@@ -55,7 +55,7 @@ repos:
- id: black
# - id: black-jupyter
- repo: https://github.com/charliermarsh/ruff-pre-commit
rev: v0.0.264
rev: v0.0.269
hooks:
- id: ruff
args: [--fix-only, --show-fixes]
Expand All@@ -66,7 +66,7 @@ repos:
additional_dependencies: &flake8_dependencies
# These versions need updated manually
- flake8==6.0.0
- flake8-bugbear==23.3.23
- flake8-bugbear==23.5.9
- flake8-simplify==0.20.0
- repo: https://github.com/asottile/yesqa
rev: v1.4.0
Expand All@@ -81,7 +81,7 @@ repos:
additional_dependencies: [tomli]
files: ^(graphblas_algorithms|docs)/
- repo: https://github.com/charliermarsh/ruff-pre-commit
rev: v0.0.264
rev: v0.0.269
hooks:
- id: ruff
# `pyroma` may help keep our package standards up to date if best practices change.
Expand Down
225 changes: 135 additions & 90 deletionsREADME.md
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -112,93 +112,138 @@ The following NetworkX algorithms have been implemented
by graphblas-algorithms and can be used following the
dispatch pattern shown above.

- Boundary
- edge_boundary
- node_boundary
- Centrality
- degree_centrality
- eigenvector_centrality
- in_degree_centrality
- katz_centrality
- out_degree_centrality
- Cluster
- average_clustering
- clustering
- generalized_degree
- square_clustering
- transitivity
- triangles
- Community
- inter_community_edges
- intra_community_edges
- Components
- is_connected
- is_weakly_connected
- node_connected_component
- Core
- k_truss
- Cuts
- boundary_expansion
- conductance
- cut_size
- edge_expansion
- mixing_expansion
- node_expansion
- normalized_cut_size
- volume
- DAG
- ancestors
- descendants
- Dominating
- is_dominating_set
- Generators
- ego_graph
- Isolate
- is_isolate
- isolates
- number_of_isolates
- Link Analysis
- google_matrix
- hits
- pagerank
- Operators
- compose
- difference
- disjoint_union
- full_join
- intersection
- symmetric_difference
- union
- Reciprocity
- overall_reciprocity
- reciprocity
- Regular
- is_k_regular
- is_regular
- Shortest Paths
- all_pairs_bellman_ford_path_length
- all_pairs_shortest_path_length
- bellman_ford_path
- floyd_warshall
- floyd_warshall_numpy
- floyd_warshall_predecessor_and_distance
- 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
- s_metric
- Structural Holes
- mutual_weight
- Tournament
- is_tournament
- score_sequence
- tournament_matrix
- Traversal
- bfs_layers
- descendants_at_distance
- Triads
- is_triad
[//]: # (Begin auto-generated code)

```
graphblas_algorithms.nxapi
├── boundary
│ ├── edge_boundary
│ └── node_boundary
├── centrality
│ ├── degree_alg
│ │ ├── degree_centrality
│ │ ├── in_degree_centrality
│ │ └── out_degree_centrality
│ ├── eigenvector
│ │ └── eigenvector_centrality
│ └── katz
│ └── katz_centrality
├── cluster
│ ├── average_clustering
│ ├── clustering
│ ├── generalized_degree
│ ├── square_clustering
│ ├── transitivity
│ └── triangles
├── community
│ └── quality
│ ├── inter_community_edges
│ └── intra_community_edges
├── components
│ ├── connected
│ │ ├── is_connected
│ │ └── node_connected_component
│ └── weakly_connected
│ └── is_weakly_connected
├── core
│ └── k_truss
├── cuts
│ ├── boundary_expansion
│ ├── conductance
│ ├── cut_size
│ ├── edge_expansion
│ ├── mixing_expansion
│ ├── node_expansion
│ ├── normalized_cut_size
│ └── volume
├── dag
│ ├── ancestors
│ └── descendants
├── dominating
│ └── is_dominating_set
├── efficiency_measures
│ └── efficiency
├── generators
│ └── ego
│ └── ego_graph
├── isolate
│ ├── is_isolate
│ ├── isolates
│ └── number_of_isolates
├── isomorphism
│ └── isomorph
│ ├── fast_could_be_isomorphic
│ └── faster_could_be_isomorphic
├── linalg
│ ├── bethehessianmatrix
│ │ └── bethe_hessian_matrix
│ ├── graphmatrix
│ │ └── adjacency_matrix
│ ├── laplacianmatrix
│ │ ├── laplacian_matrix
│ │ └── normalized_laplacian_matrix
│ └── modularitymatrix
│ ├── directed_modularity_matrix
│ └── modularity_matrix
├── link_analysis
│ ├── hits_alg
│ │ └── hits
│ └── pagerank_alg
│ ├── google_matrix
│ └── pagerank
├── lowest_common_ancestors
│ └── lowest_common_ancestor
├── operators
│ ├── binary
│ │ ├── compose
│ │ ├── difference
│ │ ├── disjoint_union
│ │ ├── full_join
│ │ ├── intersection
│ │ ├── symmetric_difference
│ │ └── union
│ └── unary
│ ├── complement
│ └── reverse
├── reciprocity
│ ├── overall_reciprocity
│ └── reciprocity
├── regular
│ ├── is_k_regular
│ └── is_regular
├── shortest_paths
│ ├── dense
│ │ ├── floyd_warshall
│ │ ├── floyd_warshall_numpy
│ │ └── floyd_warshall_predecessor_and_distance
│ ├── generic
│ │ └── has_path
│ ├── unweighted
│ │ ├── all_pairs_shortest_path_length
│ │ ├── single_source_shortest_path_length
│ │ └── single_target_shortest_path_length
│ └── weighted
│ ├── all_pairs_bellman_ford_path_length
│ ├── bellman_ford_path
│ ├── bellman_ford_path_length
│ ├── negative_edge_cycle
│ └── single_source_bellman_ford_path_length
├── simple_paths
│ └── is_simple_path
├── smetric
│ └── s_metric
├── structuralholes
│ └── mutual_weight
├── tournament
│ ├── is_tournament
│ ├── score_sequence
│ └── tournament_matrix
├── traversal
│ └── breadth_first_search
│ ├── bfs_layers
│ └── descendants_at_distance
└── triads
└── is_triad
```

[//]: # (End auto-generated code)
2 changes: 2 additions & 0 deletionsenvironment.yml
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -42,6 +42,8 @@ dependencies:
- pydot
- pygraphviz
- sympy
# For updating algorithm list in README
- rich
# For linting
- pre-commit
# For testing
Expand Down
3 changes: 2 additions & 1 deletiongraphblas_algorithms/__init__.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
import importlib.metadata

from .classes import *
from .generators import *
from .linalg import *

from .algorithms import * # isort:skip
from .generators import * # isort:skip

try:
__version__ = importlib.metadata.version("graphblas-algorithms")
Expand Down
3 changes: 3 additions & 0 deletionsgraphblas_algorithms/algorithms/__init__.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -8,8 +8,11 @@
from .cuts import *
from .dag import *
from .dominating import *
from .efficiency_measures import *
from .isolate import *
from .isomorphism import *
from .link_analysis import *
from .lowest_common_ancestors import *
from .operators import *
from .reciprocity import *
from .regular import *
Expand Down
29 changes: 23 additions & 6 deletionsgraphblas_algorithms/algorithms/_bfs.py
View file
Open in desktop
Original file line numberDiff line numberDiff line change
Expand Up@@ -11,16 +11,25 @@ def _get_cutoff(n, cutoff):
return cutoff + 1 # Inclusive


def _bfs_plain(G, source=None, target=None, *, index=None, cutoff=None):
# Push-pull optimization is possible, but annoying to implement
def _bfs_plain(
G, source=None, target=None, *, index=None, cutoff=None, transpose=False, name="bfs_plain"
):
if source is not None:
if source not in G._key_to_id:
raise KeyError(f"The node {source} is not in the graph")
index = G._key_to_id[source]
if target is not None:
if target not in G._key_to_id:
raise KeyError(f"The node {target} is not in the graph")
dst_id = G._key_to_id[target]
else:
dst_id = None
A = G.get_property("offdiag")
if transpose and G.is_directed():
A = A.T # TODO: should we use "AT" instead?
n = A.nrows
v = Vector(bool, n, name="bfs_plain")
v = Vector(bool, n, name=name)
q = Vector(bool, n, name="q")
v[index] = True
q[index] = True
Expand All@@ -30,16 +39,22 @@ def _bfs_plain(G, source=None, target=None, *, index=None, cutoff=None):
q(~v.S, replace) << any_pair_bool(q @ A)
if q.nvals == 0:
break
v(q.S) << True
if dst_id is not None and dst_id in q:
break
v(q.S) << True
return v


def _bfs_level(G, source,cutoff=None, *, transpose=False, dtype=int):
def _bfs_level(G, source,target=None, *, cutoff=None, transpose=False, dtype=int):
if dtype == bool:
dtype = int
index = G._key_to_id[source]
if target is not None:
if target not in G._key_to_id:
raise KeyError(f"The node {target} is not in the graph")
dst_id = G._key_to_id[target]
else:
dst_id = None
A = G.get_property("offdiag")
if transpose and G.is_directed():
A = A.T # TODO: should we use "AT" instead?
Expand All@@ -55,10 +70,12 @@ def _bfs_level(G, source, cutoff=None, *, transpose=False, dtype=int):
if q.nvals == 0:
break
v(q.S) << i
if dst_id is not None and dst_id in q:
break
return v


def _bfs_levels(G, nodes, cutoff=None, *, dtype=int):
def _bfs_levels(G, nodes,*,cutoff=None, dtype=int):
if dtype == bool:
dtype = int
A = G.get_property("offdiag")
Expand DownExpand Up@@ -90,7 +107,7 @@ def _bfs_levels(G, nodes, cutoff=None, *, dtype=int):
return D


def _bfs_parent(G, source,cutoff=None, *,target=None, transpose=False, dtype=int):
def _bfs_parent(G, source,target=None, *,cutoff=None, transpose=False, dtype=int):
if dtype == bool:
dtype = int
index = G._key_to_id[source]
Expand Down
Loading
[8]ページ先頭
©2009-2025 Movatter.jp