"""OrbitSI's count pipeline in C++ (the _orbitsi_core extension): the filter of
orbitsi.search.FilterEngine, the matching orders of OrderEngine and the counting of SearchEngine.count,
with the same semantics (the tests compare them). OrbitSIEngine.count() goes through it by default.
data_graph(G) builds the extension's copy of a data graph once (cached with its GraphIndex;
read_graph_from_file builds it at load); run(G, P, ...) filters, orders and counts one pattern.
"""
import networkx as nx
import numpy as np
from _orbitsi_core import DataGraph, run as _run
from .graphindex import GraphIndex
[docs]
def data_graph(G):
"""The C++ core's copy of data graph ``G``, built on first use and cached with its GraphIndex.
Parameters
----------
G : networkx.Graph
The data graph, with node labels in the ``'label'`` attribute.
Returns
-------
_orbitsi_core.DataGraph
"""
ix = GraphIndex.of(G)
if ix.core is None:
ix.core = DataGraph(ix.offsets, ix.nbors, ix.labels.astype(np.int64), len(ix.label_code), ix.degree)
return ix.core
[docs]
def run(G, P, graphlet_size=4, order_method="auto", arc_consistency=False, contraction=True, edge_thinning=True,
tail=True, stop="count", limit=0):
"""Filter, order and count (or enumerate) the embeddings of pattern ``P`` in ``G``, in C++.
Parameters
----------
G, P : networkx.Graph
The data and pattern graphs, with node labels in the ``'label'`` attribute.
graphlet_size : {4, 5}, default 4
Graphlet size of the orbit filter (counted by EVOKE).
order_method : {'auto', 'core'}, default 'auto'
Matching order: OrbitSI's orbit-strength order, or 2-core first (see :class:`orbitsi.search.OrderEngine`).
arc_consistency : bool, default False
Run arc consistency after NLF and after the orbit filter.
contraction : bool, default True
Repeat NLF inside the candidate subgraph before the orbit filter.
edge_thinning : bool, default True
Count orbits only on the candidate subgraph's edges that some pattern edge can map onto.
tail : bool, default True
Count the last pattern vertices together instead of searching them.
stop : {'count', 'order', 'filter'}, default 'count'
Stop after filtering or ordering instead of searching.
limit : int, default 0
If positive, enumerate the embeddings one at a time (no tail or last-level counting) and stop
after ``limit`` of them.
Returns
-------
dict
``status`` ('ok', or 'refuted' if filtering leaves some pattern vertex without candidates);
``count`` (int: the number of embeddings, at most ``limit`` if one is set);
``limit_reached`` (bool); ``candidates`` ({pattern node: [data node IDs]}, empty when refuted);
``order`` (pattern nodes in matching order); ``orbit_subgraph`` (vertices and edges of the
subgraph the orbits were counted on); ``times`` (milliseconds per stage).
"""
ix = GraphIndex.of(G)
core = data_graph(G)
pix = GraphIndex.of(P)
plab = nx.get_node_attributes(P, "label")
codes = np.array([ix.label_code.get(plab.get(u), -1) for u in pix.nodes], dtype=np.int64)
res = _run(core, pix.offsets, pix.nbors, codes, pix.degree, graphlet_size=graphlet_size,
order_method=order_method, arc_consistency=arc_consistency, contraction=contraction,
edge_thinning=edge_thinning, tail=tail, stop=stop, limit=limit)
nodes = pix.nodes
if res["status"] == "ok":
res["candidates"] = {u: ix.to_ids(c) for u, c in zip(nodes, res["candidates"])}
else:
res["candidates"] = {}
res["order"] = [nodes[i] for i in res["order"]]
return res
[docs]
def count(G, P, **kwargs):
"""The number of embeddings of pattern ``P`` in data graph ``G`` (keyword arguments as :func:`run`)."""
if P.number_of_nodes() == 0:
return 1
return run(G, P, **kwargs)["count"]