Skip to content

Convert from networkx without the scipy detour - #600

Open
eriknw wants to merge 9 commits into
32-udf-typing-only-typesfrom
20-networkx-ingestion
Open

eriknw wants to merge 9 commits into
32-udf-typing-only-typesfrom
20-networkx-ingestion

Conversation

@eriknw

@eriknw eriknw commented Aug 4, 2026 •

Copy link
Copy Markdown
Member

from_networkx routed every conversion through scipy CSR, paying the
scipy.sparse import (over 100ms) plus an extra coo to csr materialization.
It now builds COO arrays straight from the networkx adjacency and calls
Matrix.from_coo.

  • Simple graphs with numeric weights: the node selection preamble
    mirrors nx.to_scipy_sparse_array, so ordering, subsetting, and error
    behavior match exactly. Non-numeric and array-valued weights keep the scipy
    fallback and its identical errors (until the PR above that removes it).
    graphblas without scipy installed can now convert simple graphs (previously
    ImportError).
  • Multigraphs: the directed branch passes dup_op=plus so parallel edges
    accumulate exactly as scipy's coo to csr summation does. Numeric multigraphs
    no longer need scipy at all; non-numeric weights still defer to it.
  • Test the int32 widening (was Test the from_networkx int32 widening and correct its coverage claim #618, folded in here): pins the from_networkx
    int32 widening and corrects its coverage claim.
  • Keep undirected self-loops iso and exact (new, folded in so this PR never
    ships without it): mirroring every entry and appending -wt per self-loop,
    as nx.to_scipy_sparse_array does, lost the iso storage of an unweighted
    undirected graph with a self-loop (a regression against main), turned an
    inf self-loop into nan and 1e308 into inf, raised OverflowError for an
    unsigned dtype= under numpy 2, made bool weights INT64, and gave 257 for an
    np.uint8 self-loop of weight 1 next to int weights. Only off-diagonal entries
    are mirrored now, so a self-loop is stored once with its own weight, and
    simple graphs need no accumulator (207.6 to 168.2 ms on a 100k-node,
    500k-edge graph, best of 5).

Parity with the retained scipy path is pinned by tests over parallel edges,
parallel self-loops, reciprocal parallel edges, weights that cancel to zero,
absent weight attributes, weight=None, bool and int weights, and nodelist
permutations and subsets; the self-loop fix adds iso and dtype checks for
Graph and DiGraph with and without self-loops.


Stack created with GitHub Stacks CLI • Give Feedback 💬

@eriknw eriknw changed the title 20 networkx ingestion Convert from networkx without the scipy detour Aug 4, 2026
@eriknw
eriknw marked this pull request as ready for review August 4, 2026 16:07
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 89c3e75 to 5f347b7 Compare August 4, 2026 16:12
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch 2 times, most recently from b339cb8 to d088e70 Compare August 5, 2026 03:18
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from d088e70 to 3e0c056 Compare August 5, 2026 17:44
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 3e0c056 to 14e68f5 Compare August 5, 2026 18:03
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 14e68f5 to a6e6e62 Compare August 5, 2026 18:05
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from a6e6e62 to 2901f07 Compare August 6, 2026 07:59
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 2901f07 to 5839782 Compare August 6, 2026 15:39
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 5839782 to 9ed5084 Compare August 6, 2026 15:41
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 9ed5084 to 4dc2ee7 Compare August 6, 2026 20:36
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 4dc2ee7 to 6ad41be Compare August 6, 2026 20:42
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 6ad41be to 7e083a0 Compare August 7, 2026 02:48
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 7e083a0 to 29c4957 Compare August 7, 2026 05:09
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 29c4957 to d686518 Compare August 26, 2026 17:30
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch 3 times, most recently from 6fe1fba to f18bde8 Compare October 1, 2026 17:11
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch 3 times, most recently from fd5a904 to 659aa7f Compare October 3, 2026 04:57
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 659aa7f to 858bbc4 Compare October 4, 2026 06:21
@eriknw
eriknw removed this pull request from stack #634 October 8, 2026 21:02
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 858bbc4 to 5ae447e Compare October 8, 2026 21:40
@eriknw
eriknw added this pull request to stack #635 October 8, 2026 21:46
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 5ae447e to 8a0490e Compare October 9, 2026 03:06
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from 8a0490e to a1fa8f3 Compare October 9, 2026 05:25
@eriknw
eriknw force-pushed the 20-networkx-ingestion branch from a1fa8f3 to e83adce Compare October 14, 2026 18:45
@codecov

codecov Bot commented Oct 19, 2026 •

Copy link
Copy Markdown

Codecov Report

❌ Patch coverage is 99.38650% with 1 line in your changes missing coverage. Please review.
⚠️ Please upload report for BASE (32-udf-typing-only-types@ac8b757). Learn more about missing BASE report.

Additional details and impacted files
@@                     Coverage Diff                     @@
##             32-udf-typing-only-types     #600   +/-   ##
===========================================================
  Coverage                            ?   98.79%           
===========================================================
  Files                               ?      105           
  Lines                               ?    30278           
  Branches                            ?     3528           
===========================================================
  Hits                                ?    29912           
  Misses                              ?      244           
  Partials                            ?      122           
🚀 New features to boost your workflow:
  • ❄️ Test Analytics: Detect flaky tests, report on failures, and find test suite problems.

from_networkx always routed nx -> scipy CSR -> Matrix, so every
conversion paid for scipy.sparse (importing it alone costs over 100ms)
plus an extra coo -> csr materialization. Simple graphs with numeric
weights now build COO arrays straight from the nx adjacency and call
Matrix.from_coo. The node selection preamble mirrors
nx.to_scipy_sparse_array so ordering, subsetting, and error behavior
match exactly; undirected graphs are symmetrized with the same diagonal
correction nx uses (self-loop entries appear as wt + wt - wt under
dup_op=plus, which is exact in IEEE arithmetic).

Kept on the scipy fallback automatically: multigraphs (scipy's
duplicate-coordinate summation matches exactly) and weights that do not
form a 1-D numeric array. That second condition covers non-numeric
attributes, including all-string weights, which infer a <U dtype rather
than object; the fallback raises the identical ValueError. It also
covers array-valued weights: sequence attributes of uniform length
infer a 2-D numeric array, which passes a dtype-kind test but which
from_coo would read as a UDT, so they keep raising ValueError as before
rather than quietly widening what from_networkx accepts.

graphblas without scipy installed can now convert simple graphs
(previously ImportError); multigraphs still need scipy.
A networkx multigraph fell back to scipy in from_networkx because the
direct path could not sum the weights of parallel edges. The directed
branch now passes dup_op=plus when the graph is a multigraph, so
parallel edges accumulate exactly as scipy's coo -> csr summation does.
Simple graphs keep dup_op=None and are unchanged, and the undirected
branch already summed because it uses plus for the self-loop diagonal
correction. Numeric multigraphs no longer need scipy at all; non-numeric
weights still defer to it.

Parity with the retained scipy path holds for MultiGraph and
MultiDiGraph with parallel edges, parallel self-loops, reciprocal
parallel edges, parallel edges whose weights cancel to zero (both sides
keep the explicit zero), absent weight attributes (nx defaults to 1),
weight=None, bool and int weights, and nodelist permutations and
subsets. New tests pin the multigraph diagonal sum and assert the
numeric path never reaches the scipy fallback.
Converting through scipy ended in ``from_scipy_sparse``, which checks whether
every value is the same and imports one value instead of nvals of them. The
direct path added here ends in ``from_coo``, which does not, so an unweighted
graph quietly started storing a full values array.

Nothing caught it because SuiteSparse was still doing its own post-build iso
check, and the result came out iso either way. 10.5.0 dropped that check, at
which point ``test_matrix_to_from_networkx`` failed and the regression became
visible. The memory it costs was there the whole time.

Ask for iso outright, under the same uniformity test ``from_scipy_sparse``
uses. Multigraphs are excluded because ``plus`` sums parallel edges and can
make uniform inputs non-uniform. Undirected graphs need no exclusion: without
self-loops their coordinates are unique so ``plus`` never fires, and with them
the diagonal correction puts both ``wt`` and ``-wt`` in the values array,
which fails the uniformity test on its own.
The widening added while stabilizing CI was marked "pragma: no cover
(win64 numpy < 2)", but the branch is reachable on every platform:
np.int32 scalar edge weights infer an int32 array from the edge sequence
anywhere, not only where python ints do. The pragma therefore hid live
code from coverage, and the comment implied the change was platform-local
when it is user-visible everywhere: int32-weighted graphs that previously
round-tripped through scipy as INT32 now come back INT64.

The widening itself is kept, deliberately. from_coo widens an int32 dtype
inferred from sequence input to int64 on every platform
(values_to_numpy_buffer), and from_networkx builds its values from a
Python sequence, so identical weights now produce the same dtype through
either constructor. Gating the widening to win64 instead would have
re-introduced a from_coo/from_networkx disagreement everywhere else.

Drop the pragma, restate the comment in terms of the real contract, and
pin the behavior: np.int32 weights widen to INT64 and agree with from_coo,
an explicit dtype= is preserved exactly, and np.int16 stays INT16 through
both constructors. Release-note item: the from_networkx result dtype for
int32-weighted graphs changes from INT32 to INT64.
The direct ingestion path symmetrized an undirected graph the way
nx.to_scipy_sparse_array does: it mirrored every entry, self-loops
included, and appended -wt for each self-loop so that plus would sum the
diagonal triple wt + wt - wt back to wt. That arithmetic had four
consequences:

- The iso test added in a1fa8f3 reads the values array, which then held
  both wt and -wt, so an unweighted (or uniformly weighted) undirected
  graph with a self-loop was stored with a full values array. Through
  scipy it was stored iso, because from_scipy_sparse tested the summed
  values. Code that branches on A.ss.is_iso (graphblas-algorithms runs
  BFS instead of Bellman-Ford for an iso graph) took the slow path.
- An infinite self-loop came back nan (inf + inf - inf), and a finite
  one near the float max came back inf.
- An unsigned dtype= raised OverflowError under numpy 2, which cannot
  write -wt in it.
- bool weights came back INT64 when the graph had a self-loop (-True is
  the int -1) and BOOL when it did not.

A self-loop is its own mirror, so mirror only the off-diagonal entries.
Every stored value is then an edge's own weight, and a simple graph has
no repeated coordinate: it builds without an accumulator, and a uniform
one takes the iso path whether or not it has self-loops. Multigraphs
still sum parallel edges and parallel self-loops with plus. The second
pass over the graph for nx.selfloop_edges goes away.

nx.to_scipy_sparse_array still sums wt + wt - wt, so from_networkx now
differs from it in exactly those four cases. Compared with the parent
over 74 graphs (empty, edgeless, isolated nodes, nodelist subsets and
reorders, non-integer keys, int, float, bool, complex, int32, missing
and nan weights, multigraphs, and the error cases), nothing else changes.
The old diagonal correction negated each self-loop's weight. For an
np.uint8 weight that wraps (-np.uint8(1) is 255), and beside a Python
int weight the values infer int64, so the self-loop of weight 1 summed
to 1 + 1 + 255 = 257, with only a RuntimeWarning. The parent commit
fixed this along with the four cases its message lists; pin it too.
from_networkx checks a nodelist as nx.to_scipy_sparse_array does, so
that the direct path raises its errors without needing scipy, but no
test gave it an empty nodelist, a node not in the graph, or a duplicate.
Check each message, and that a missing node is reported before a
duplicate.
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