"""Integer (CSR) views of NetworkX graphs, for the vectorised filter and the search.
GraphIndex.of(G) builds -- once per graph object, cached weakly and rebuilt if the graph's node count
changes; after changing only edges, call GraphIndex.of(G, refresh=True) (NetworkX counts edges in O(n),
too slow to check on every lookup) -- vertex indices 0..n-1 in G's node order, integer label codes, degrees (a self-loop
counting twice, as in NetworkX) and the adjacency in compressed sparse row form: the neighbours of
vertex i are nbors[offsets[i]:offsets[i + 1]], in G's adjacency order. Nodes may be any hashable
labels; graphs on the nodes 0..n-1, in that order, take a faster path.
CandidateSubgraph is the subgraph induced by a set of vertices, built lazily: adj[v] (the neighbours
of v inside the set, as a frozenset of node IDs) is computed the first time it is asked for.
"""
import itertools
import weakref
import numpy as np
_CACHE = weakref.WeakKeyDictionary()
[docs]
def gather(offsets, nbors, rows):
"""For the vertices `rows`: (position of each in `rows`, repeated per neighbour; the neighbours),
concatenated over rows in order."""
starts = offsets[rows]
lens = offsets[rows + 1] - starts
total = int(lens.sum())
owner = np.repeat(np.arange(len(rows), dtype=np.int64), lens)
pos = np.arange(total, dtype=np.int64) + np.repeat(starts - (np.cumsum(lens) - lens), lens)
return owner, nbors[pos]
[docs]
class GraphIndex:
"""Integer arrays of a graph, used by the filter and the C++ core.
Get one with :meth:`of`, which caches it per graph. Vertex indices are 0..n-1 in the graph's node
order. Attributes: ``offsets`` and ``nbors`` (the adjacency in CSR form, the neighbours of vertex
``i`` being ``nbors[offsets[i]:offsets[i + 1]]``, in the graph's adjacency order), ``degree``
(NetworkX degrees, a self-loop counting twice), ``labels`` (integer label codes, numbered in order
of first appearance; ``label_code`` maps labels to codes), ``by_label`` and ``by_label_deg``
(each code's vertices, the latter by decreasing degree), ``nodes`` (node IDs) and ``contiguous``
(whether the nodes are 0..n-1 in order).
"""
def __init__(self, G, arrays=None):
self._graph = weakref.ref(G)
self.signature = G.number_of_nodes()
self._nlf = None
self.core = None
if arrays is None:
self._from_networkx(G)
else:
self._from_arrays(*arrays)
lens = np.diff(self.offsets)
n = self.n
owner = np.repeat(np.arange(n, dtype=np.int64), lens)
loops = np.bincount(owner[self.nbors == owner], minlength=n)
self.degree = lens + loops
codes = self.labels
order = np.argsort(codes, kind="stable")
bounds = np.searchsorted(codes[order], np.arange(len(self.label_code) + 1))
self.by_label = [order[bounds[c]:bounds[c + 1]] for c in range(len(self.label_code))]
order = np.lexsort((-self.degree, codes))
self.by_label_deg = [order[bounds[c]:bounds[c + 1]] for c in range(len(self.label_code))]
self.neg_deg = [-self.degree[r] for r in self.by_label_deg]
def _from_networkx(self, G):
"""Fill the arrays from a NetworkX graph's dictionaries."""
adj = G._adj
nodes = list(adj)
n = len(nodes)
self.n = n
self._node_ids = None
self._nodes = nodes
self.contiguous = all(type(x) is int for x in nodes) and nodes == list(range(n))
self._index = None if self.contiguous else {v: i for i, v in enumerate(nodes)}
lens = np.fromiter(map(len, adj.values()), dtype=np.int64, count=n)
self.offsets = np.zeros(n + 1, dtype=np.int64)
np.cumsum(lens, out=self.offsets[1:])
flat = itertools.chain.from_iterable(adj.values())
total = int(self.offsets[-1])
if self.contiguous:
self.nbors = np.fromiter(flat, dtype=np.int64, count=total)
else:
idx = self._index
self.nbors = np.fromiter((idx[x] for x in flat), dtype=np.int64, count=total)
self.label_code = {}
codes = np.empty(n, dtype=np.int32)
for i, attrs in enumerate(G._node.values()):
lab = attrs.get("label")
codes[i] = self.label_code.setdefault(lab, len(self.label_code))
self.labels = codes
def _from_arrays(self, node_ids, labels, has_label, offsets, nbors):
"""Fill the arrays from the reader's (orbitsi.arraygraph.ArrayGraph)."""
n = len(node_ids)
self.n = n
self._node_ids = node_ids
self._nodes = None
self._index = None
self.contiguous = bool(np.array_equal(node_ids, np.arange(n, dtype=node_ids.dtype)))
self.offsets = offsets
self.nbors = nbors
if has_label.all():
uniq, first, inv = np.unique(labels, return_index=True, return_inverse=True)
by_first = np.argsort(first, kind="stable")
rank = np.empty(len(uniq), dtype=np.int32)
rank[by_first] = np.arange(len(uniq), dtype=np.int32)
self.labels = rank[inv.reshape(-1)]
self.label_code = dict(zip(uniq[by_first].tolist(), range(len(uniq))))
else:
self.label_code = {}
codes = np.empty(n, dtype=np.int32)
for i, (lab, has) in enumerate(zip(labels.tolist(), has_label.tolist())):
codes[i] = self.label_code.setdefault(lab if has else None, len(self.label_code))
self.labels = codes
@property
def nodes(self):
"""Node IDs, in vertex-index order (a list, built on first use)."""
if self._nodes is None:
self._nodes = self._node_ids.tolist()
return self._nodes
@property
def index(self):
"""{node ID: vertex index}, built on first use; None when the nodes are 0..n-1 in order."""
if self._index is None and not self.contiguous:
self._index = {v: i for i, v in enumerate(self.nodes)}
return self._index
[docs]
@classmethod
def of(cls, G, refresh=False):
"""The index of ``G``, built once and cached (weakly) with it.
Rebuilt if ``G``'s node count changes; after changing only edges, pass ``refresh=True``.
"""
idx = _CACHE.get(G)
if refresh or idx is None or idx.signature != G.number_of_nodes():
idx = cls(G, G.__dict__.get("arrays"))
_CACHE[G] = idx
return idx
NLF_DENSE_MAX = 1 << 27
NLF_CAP = np.iinfo(np.uint16).max
[docs]
def nlf_table(self):
"""Neighbour-label frequencies, built on first use (read_graph_from_file builds them at load).
Vertex i has nlf_count([i], [c])[0] neighbours with label code c; a self-loop counts the vertex
as its own neighbour, as NetworkX's neighbors() does. Stored densely (i * L + c -> count,
capped at NLF_CAP) if n * L <= NLF_DENSE_MAX, else as sorted keys i * L + c with their counts."""
if self._nlf is None:
L = max(len(self.label_code), 1)
owner = np.repeat(np.arange(self.n, dtype=np.int64), np.diff(self.offsets))
key = owner * L + self.labels[self.nbors].astype(np.int64)
del owner
if self.n * L <= self.NLF_DENSE_MAX:
dense = np.bincount(key, minlength=self.n * L)
self._nlf = ("dense", L, np.minimum(dense, self.NLF_CAP).astype(np.uint16), None)
else:
keys, counts = np.unique(key, return_counts=True)
self._nlf = ("sparse", L, keys, counts)
return self._nlf
[docs]
def nlf_count(self, rows, codes):
"""For each i: the number of neighbours of vertex rows[i] with label code codes[i] (capped at
NLF_CAP; compare it only with numbers up to NLF_CAP)."""
kind, L, a, b = self.nlf_table()
k = rows * L + codes
if kind == "dense":
return a[k]
if len(a) == 0:
return np.zeros(len(k), dtype=np.int64)
j = np.minimum(np.searchsorted(a, k), len(a) - 1)
return np.where(a[j] == k, b[j], 0)
[docs]
def to_ids(self, rows):
"""Node IDs of vertex indices."""
if self.contiguous:
return rows.tolist()
if self._node_ids is not None:
return self._node_ids[rows].tolist()
nodes = self.nodes
return [nodes[i] for i in rows.tolist()]
[docs]
def to_index(self, node):
"""The vertex index of a node ID."""
return node if self.contiguous else self.index[node]
@property
def graph(self):
"""The indexed graph (None if it no longer exists)."""
return self._graph()
class _LazyAdjacency:
"""adj[v] for a CandidateSubgraph: v's neighbours inside the vertex set, as a frozenset of node IDs."""
def __init__(self, sub):
self._sub = sub
self._cache = {}
def __getitem__(self, v):
s = self._cache.get(v)
if s is None:
sub = self._sub
ix = sub.index
i = ix.to_index(v)
nb = ix.nbors[ix.offsets[i]:ix.offsets[i + 1]]
nb = nb[sub.member[nb]]
s = self._cache[v] = frozenset(ix.to_ids(nb))
return s
def __contains__(self, v):
try:
i = self._sub.index.to_index(v)
except KeyError:
return False
return bool(self._sub.member[i])
def __iter__(self):
return iter(self._sub.nodes)
def __len__(self):
return len(self._sub.rows)
[docs]
class CandidateSubgraph:
"""The subgraph of an indexed graph induced by the vertex indices `rows` (sorted, unique)."""
def __init__(self, index, rows):
self.index = index
self.rows = rows
self.member = np.zeros(index.n, dtype=bool)
self.member[rows] = True
self.adj = _LazyAdjacency(self)
@property
def nodes(self):
"""Node IDs of the subgraph's vertices, in vertex-index order."""
return self.index.to_ids(self.rows)
[docs]
def number_of_nodes(self):
"""The number of vertices in the subgraph."""
return len(self.rows)
[docs]
def neighbors(self, v):
"""An iterator over v's neighbours inside the subgraph (node IDs)."""
return iter(self.adj[v])
[docs]
def has_edge(self, u, v):
"""Whether u and v are both in the subgraph and adjacent."""
return u in self.adj and v in self.adj[u]
[docs]
def csr(self):
"""The subgraph in CSR form over local vertex indices 0..k-1 (in the order of `rows`)."""
ix = self.index
local = np.full(ix.n, -1, dtype=np.int64)
local[self.rows] = np.arange(len(self.rows), dtype=np.int64)
owner, nb = gather(ix.offsets, ix.nbors, self.rows)
keep = self.member[nb]
owner, nb = owner[keep], local[nb[keep]]
offsets = np.zeros(len(self.rows) + 1, dtype=np.int64)
np.cumsum(np.bincount(owner, minlength=len(self.rows)), out=offsets[1:])
return offsets, nb, local
[docs]
def to_networkx(self):
"""A NetworkX copy of the subgraph (with the original graph's attributes)."""
return self.index.graph.subgraph(self.nodes).copy()
[docs]
def index_of(G):
"""The GraphIndex of G (GraphIndex.of(G))."""
return GraphIndex.of(G)
__all__ = ["GraphIndex", "CandidateSubgraph", "gather", "index_of"]