Python usage

Reading graphs

orbitsi.utils.read_graph_from_file() reads a graph file (see Graph file format) into a networkx.Graph, with each vertex’s label in its 'label' attribute:

from orbitsi.utils import read_graph_from_file

G = read_graph_from_file("data.graph")      # data graph
P = read_graph_from_file("pattern.graph")   # pattern

The file is parsed in C++ straight into arrays, which the filter and the C++ core use directly. The graph returned is an orbitsi.arraygraph.ArrayGraph, which builds its NetworkX node and adjacency dictionaries only when they are first used (for example by the Python backend, G.copy(), G.subgraph() or a NetworkX algorithm); it then becomes a plain networkx.Graph. Counting with the C++ core never builds them, so loading a large data graph costs little more than reading the file.

By default the reader also builds the indexes the search needs, so their cost is paid at load and not by the first pattern; pass build_index=False to skip that.

Any networkx.Graph with a 'label' attribute on every node works as well.

Counting and listing embeddings

orbitsi.search.OrbitSIEngine holds one data graph and searches it for any number of patterns:

from orbitsi.orbit import EVOKEOrbitCounter
from orbitsi.search import OrbitSIEngine

engine = OrbitSIEngine(G, EVOKEOrbitCounter, graphlet_size=4)
n = engine.count(P)          # number of embeddings (C++ core)
embeddings = engine.run(P)   # [{pattern node: data node}, ...] (Python)

An embedding maps the pattern’s vertices injectively to data vertices with the same labels, such that every pattern edge maps to a data edge (non-induced subgraph isomorphism). Counting is much faster and lighter than listing when there are many embeddings.

The engine’s options (see OrbitSIEngine and How OrbitSI works) choose the graphlet size, the matching order and which filtering and search refinements run. None of them changes the embeddings found. published=True runs OrbitSI’s algorithm as published.

Enumerating up to a limit

orbitsi.core.run() exposes the C++ pipeline directly. With limit=N it enumerates the embeddings one at a time and stops after N of them; its result also has the candidates, the matching order and the time of each stage:

from orbitsi import core

res = core.run(G, P, limit=100_000)
res["count"], res["limit_reached"], res["times"]

Orbit counting

The orbit counters work on any networkx.Graph:

from orbitsi.orbit import EVOKEOrbitCounter, ORCAOrbitCounter

counts = EVOKEOrbitCounter(G, size=5).get_orbits()               # non-induced, n x 73
induced = ORCAOrbitCounter(G, size=4).get_orbits(induced=True)   # induced, n x 15

Rows are in sorted node order. EVOKE counts graphlets of 4 or 5 vertices, ORCA of 4. EVOKE’s own counts are non-induced and ORCA’s induced; OrbitMatrixConverter converts between the two exactly.