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 98.73%. Comparing base (5f883b9) to head (808be2c).

Additional details and impacted files
@@                         Coverage Diff                         @@
##           41-networkx-error-without-scipy     #645      +/-   ##
===================================================================
+ Coverage                            98.00%   98.73%   +0.72%     
===================================================================
  Files                                  105      105              
  Lines                                30355    30382      +27     
  Branches                              3536     3540       +4     
===================================================================
+ Hits                                 29750    29998     +248     
+ Misses                                 364      253     -111     
+ Partials                               241      131     -110     
🚀 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 from 64f7dc9 to a9d5503 Compare October 28, 2026 13:21
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.
@eriknw
eriknw force-pushed the 42-networkx-structural-ingest branch from a9d5503 to 808be2c Compare October 29, 2026 02:01
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