Skip to content

Build a weight=None from_networkx from the adjacency alone - #645

Open
eriknw wants to merge 1 commit into
41-networkx-error-without-scipyfrom
42-networkx-structural-ingest
Open

eriknw wants to merge 1 commit into
41-networkx-error-without-scipyfrom
42-networkx-structural-ingest

Conversation

@eriknw

@eriknw eriknw commented Oct 19, 2026

Copy link
Copy Markdown
Member

A structural conversion of a simple graph now reads each node's neighbors
straight from the adjacency, in nodelist order: rows from np.repeat over the
counts, columns from one np.fromiter, and Matrix.from_coo(rows, cols, 1)
builds the result (iso on SuiteSparse), with no mirroring because the adjacency
already holds both directions. Multigraphs, edgeless graphs and non-built-in
dtype= stay on the general path.

gnm_random_graph(100000, 500000) plus a self-loop, best of 5: undirected 2.1x
faster, directed 2.6x. Most calls graphblas-algorithms dispatches convert
unweighted.

The test compares weight=None with an attribute no edge carries (the general
path, every entry 1) over non-integer keys, a self-loop, reciprocal edges, an
isolated node, a reversed nodelist, subsets, an edgeless graph and three
dtypes; result, dtype and iso flag match exactly. The path reads networkx's
G._adj (as networkx's own code does; the public G.adj builds an AtlasView
per node).

@eriknw
eriknw added this pull request to stack #650 October 19, 2026 07:50
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch from f814ba8 to 2e2b73b Compare October 19, 2026 07:55
@codecov

codecov Bot commented Oct 19, 2026 •

Copy link
Copy Markdown

Codecov Report

✅ All modified and coverable lines are covered by tests.
✅ Project coverage is 99.08%. Comparing base (f85e479) to head (eb4393e).

Additional details and impacted files
@@                         Coverage Diff                         @@
##           41-networkx-error-without-scipy     #645      +/-   ##
===================================================================
- Coverage                            99.30%   99.08%   -0.22%     
===================================================================
  Files                                  106      106              
  Lines                                32931    32958      +27     
  Branches                              3829     3833       +4     
===================================================================
- Hits                                 32701    32657      -44     
- Misses                                 153      194      +41     
- Partials                                77      107      +30     
🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch 3 times, most recently from b3a4ee9 to ee13b98 Compare October 21, 2026 08:38
@eriknw
eriknw removed this pull request from stack #650 October 28, 2026 04:29
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch from ee13b98 to 64f7dc9 Compare October 28, 2026 04:29
@eriknw
eriknw added this pull request to stack #653 October 28, 2026 04:30
@eriknw
eriknw removed this pull request from stack #653 October 28, 2026 04:31
@eriknw
eriknw added this pull request to stack #655 October 28, 2026 04:32
@eriknw
eriknw removed this pull request from stack #655 October 28, 2026 04:33
@eriknw
eriknw added this pull request to stack #657 October 28, 2026 04:33
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch 5 times, most recently from dbcbbaf to 7ac9d91 Compare November 3, 2026 16:44
@eriknw
eriknw removed this pull request from stack #657 November 3, 2026 16:44
@eriknw
eriknw added this pull request to stack #660 November 3, 2026 16:45
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch from 7ac9d91 to 36945ab Compare November 3, 2026 20:07
@eriknw
eriknw removed this pull request from stack #660 November 3, 2026 23:09
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch from 36945ab to 4404714 Compare November 3, 2026 23:09
@eriknw
eriknw added this pull request to stack #662 November 3, 2026 23:09
@eriknw
eriknw removed this pull request from stack #662 November 3, 2026 23:11
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch from 52c1281 to 63ca5ad Compare November 10, 2026 16:47
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch 15 times, most recently from 6e25785 to e6461a4 Compare November 11, 2026 05:42
@eriknw
eriknw removed this pull request from stack #666 November 12, 2026 06:13
@eriknw
eriknw changed the base branch from 41-networkx-error-without-scipy to main November 12, 2026 06:14
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch from e6461a4 to 603dcc5 Compare November 12, 2026 06:15
@eriknw
eriknw changed the base branch from main to 41-networkx-error-without-scipy November 12, 2026 06:16
@eriknw
eriknw added this pull request to stack #670 November 12, 2026 06:17
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch 7 times, most recently from 72e66cf to 0d235f1 Compare November 13, 2026 04:32
A structural conversion (weight=None) of a simple graph stores 1 for
every edge, yet from_networkx built it like a weighted one: a (u, v, 1)
tuple per edge through G.edges, three tuples transposed out of those,
an array of ones inferred from a Python sequence, and a uniformity test
over it before the iso build.

Read only the coordinates instead: for each node in nodelist order, its
neighbors straight from the adjacency, which for an undirected graph
already holds both directions and each self-loop once, so nothing is
mirrored. Rows come from np.repeat over the neighbor counts and columns
from one np.fromiter; Matrix.from_coo with the scalar 1 stores the
result iso on SuiteSparse and broadcasts it elsewhere. The dtype is what
the general path infers (INT64, or dtype= when given). An edgeless graph
still takes the general path, which gives it scipy's float64; so do
multigraphs, whose parallel edges sum, and a dtype= that is not bool,
int, float or complex.

gnm_random_graph(100000, 500000) plus one self-loop, best of 5 in one
warm process, 18 SuiteSparse threads, load average about 1.2:

    undirected  159.5 ms -> 75.0 ms  (2.1x; 199.4 ms before the self-loop fix)
    directed    131.8 ms -> 49.3 ms  (2.7x)

A nodelist covering half the nodes goes through a subgraph view and
gains nothing (178 against 180 ms undirected), but loses nothing either.

The new test compares weight=None against an attribute no edge carries,
which takes the general path and fills every entry with the default 1,
over non-integer keys, a self-loop, reciprocal edges, an isolated node,
nodelist reorders and subsets, an edgeless graph and three dtypes.
Over 124 conversions (every case of a parity script also with
weight=None) the result, dtype and iso flag match the parent's exactly.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant