Internals

These are used by the public API and may change between versions.

Graph index

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.

class orbitsi.graphindex.GraphIndex(G, arrays=None)

Bases: object

Integer arrays of a graph, used by the filter and the C++ core.

Get one with 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).

property nodes

Node IDs, in vertex-index order (a list, built on first use).

property index

vertex index}, built on first use; None when the nodes are 0..n-1 in order.

Type:

{node ID

classmethod of(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.

nlf_table()

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.

nlf_count(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).

to_ids(rows)

Node IDs of vertex indices.

to_index(node)

The vertex index of a node ID.

property graph

The indexed graph (None if it no longer exists).

class orbitsi.graphindex.CandidateSubgraph(index, rows)

Bases: object

The subgraph of an indexed graph induced by the vertex indices rows (sorted, unique).

property nodes

Node IDs of the subgraph’s vertices, in vertex-index order.

number_of_nodes()

The number of vertices in the subgraph.

neighbors(v)

An iterator over v’s neighbours inside the subgraph (node IDs).

has_edge(u, v)

Whether u and v are both in the subgraph and adjacent.

csr()

The subgraph in CSR form over local vertex indices 0..k-1 (in the order of rows).

to_networkx()

A NetworkX copy of the subgraph (with the original graph’s attributes).

orbitsi.graphindex.gather(offsets, nbors, rows)

For the vertices rows: (position of each in rows, repeated per neighbour; the neighbours), concatenated over rows in order.

orbitsi.graphindex.index_of(G)

The GraphIndex of G (GraphIndex.of(G)).

C++ extension modules

_orbitsi_core

The C++ pipeline behind orbitsi.core and the graph reader behind orbitsi.utils.read_graph_from_file().

class _orbitsi_core.DataGraph

Bases: pybind11_object

A data graph for run(): CSR offsets and neighbours over vertices 0..n-1, label codes 0..num_labels-1 and NetworkX degrees (a self-loop counting twice).

_orbitsi_core.run(graph: _orbitsi_core.DataGraph, offsets: Annotated[numpy.typing.ArrayLike, numpy.int64], nbors: Annotated[numpy.typing.ArrayLike, numpy.int64], labels: Annotated[numpy.typing.ArrayLike, numpy.int64], degree: Annotated[numpy.typing.ArrayLike, numpy.int64], graphlet_size: SupportsInt | SupportsIndex = 4, order_method: str = 'auto', arc_consistency: bool = False, contraction: bool = True, edge_thinning: bool = True, tail: bool = True, stop: str = 'count', limit: SupportsInt | SupportsIndex = 0) → dict

Filter, order and count the embeddings of one pattern (CSR over its vertices 0..k-1, each one’s data label code or -1, NetworkX degrees). Returns a dict: status (‘ok’ or ‘refuted’), count (int), candidates (per pattern vertex, data vertex indices), order (pattern vertex indices), orbit_subgraph (vertices, edges), times (ms per stage). edge_thinning and tail switch off the orbit stage’s edge thinning and the search’s tail counting; stop=’filter’ or ‘order’ ends early. limit > 0 enumerates the embeddings one at a time (no tail or last-level counting) and stops after limit of them (limit_reached in the result).

_orbitsi_core.read_graph(data: bytes) → tuple

Parse a graph file’s contents (t/v/e lines) into (node IDs, labels, has_label, CSR offsets, CSR neighbours) in the node and neighbour order NetworkX builds from the same file: every ‘v’ node first, then nodes seen only in edges, neighbours in order of first occurrence, duplicates collapsed.

_evoke_cpp

EVOKE’s orbit counting, behind orbitsi.orbit.EVOKEOrbitCounter.

_evoke_cpp.evoke_count(adj: collections.abc.Sequence[collections.abc.Sequence[SupportsInt | SupportsIndex]], size: SupportsInt | SupportsIndex, parallel: bool = False) → list[list[int]]

Non-induced vertex orbit counts for graphlets of size 4 or 5, using EVOKE.

Parameters:

• adj (list of list of int) – Adjacency lists, vertices numbered 0..n-1.

• size (int) – Graphlet size (4 or 5).

• parallel (bool) – Run the 5-vertex routines concurrently.

Returns:

list of list of int – n rows of 64-bit counts (15 orbits for size 4, 73 for size 5).

_evoke_cpp.evoke_count_csr(offsets: Annotated[numpy.typing.ArrayLike, numpy.int64], nbors: Annotated[numpy.typing.ArrayLike, numpy.int64], size: SupportsInt | SupportsIndex, parallel: bool = False, skip: SupportsInt | SupportsIndex = 0) → numpy.typing.NDArray[numpy.int64]

Non-induced vertex orbit counts (EVOKE) of a CSR graph, as an n x num_orbits int64 array. skip (size 4): bit 1 leaves orbit 8 at 0, bit 2 orbit 14, bit 4 orbits 9, 10, 12 and 13.

_orca_cpp

ORCA’s orbit counting, behind orbitsi.orbit.ORCAOrbitCounter.

_orca_cpp.orca_count(adj: collections.abc.Sequence[collections.abc.Sequence[SupportsInt | SupportsIndex]], size: SupportsInt | SupportsIndex) → list[list[int]]

ORCA node orbit counts for graphlet size 4 (non-induced input, induced counts)