"""OrbitSI's search: OrbitSIEngine, and the filtering, ordering and search stages it runs."""
from .filtering import FilterEngine
from .ordering import OrderEngine
from .searching import SearchEngine
[docs]
class OrbitSIEngine:
"""OrbitSI's subgraph isomorphism search over one data graph.
Filtering is LDF and NLF, then one orbit filter on the candidate-induced subgraph
(:class:`FilterEngine`); then a matching order (:class:`OrderEngine`) and a backtracking search
(:class:`SearchEngine`). :meth:`count` runs the same pipeline in C++ (:mod:`orbitsi.core`) by default.
Parameters
----------
data_graph : networkx.Graph
The data graph, with node labels in the ``'label'`` attribute.
orbit_counter_class : type
:class:`~orbitsi.orbit.EVOKEOrbitCounter` or :class:`~orbitsi.orbit.ORCAOrbitCounter`.
graphlet_size : {4, 5}, default 4
Graphlet size of the orbit filter (ORCA supports 4 only).
order_method : {'auto', 'core'}, default 'auto'
'auto' is OrbitSI's orbit-strength order; 'core' puts the pattern's 2-core first.
arc_consistency : bool, default False
Add arc consistency before and after the orbit filter (not in OrbitSI as published).
contraction : bool, default True
Repeat NLF inside the candidate subgraph before the orbit filter (not in OrbitSI as published).
backend : {'cpp', 'python'}, default 'cpp'
Implementation of :meth:`count`; 'cpp' applies only with EVOKE, otherwise the count runs in
Python. :meth:`run` always runs in Python.
edge_thinning : bool, default True
Count orbits only on the candidate subgraph's edges that some pattern edge can map onto (not
in OrbitSI as published).
tail : bool, default True
Count the last pattern vertices together instead of searching them (not in OrbitSI as published).
published : bool, default False
OrbitSI's algorithm as published: overrides ``order_method`` ('auto') and turns off
``arc_consistency``, ``contraction``, ``edge_thinning`` and ``tail``. The candidates, the
order and the count are the published algorithm's; the implementation is the current one.
Notes
-----
None of the options changes the embeddings found or their number.
"""
def __init__(self, data_graph, orbit_counter_class, graphlet_size=4, order_method='auto', arc_consistency=False,
contraction=True, backend='cpp', edge_thinning=True, tail=True, published=False):
if backend not in ('cpp', 'python'):
raise ValueError("backend must be 'cpp' or 'python'")
self.backend = backend
if published:
order_method, arc_consistency, contraction, edge_thinning, tail = 'auto', False, False, False, False
self.edge_thinning = edge_thinning
self.tail = tail
self.data_graph = data_graph
self.orbit_counter_class = orbit_counter_class
self.graphlet_size = graphlet_size
self.order_method = order_method
self.arc_consistency = arc_consistency
self.contraction = contraction
def _prepare(self, pattern_graph):
"""The search engine for pattern_graph, or None if filtering proves there is no embedding."""
filter_engine = FilterEngine(
data_graph=self.data_graph,
pattern_graph=pattern_graph,
orbit_counter_class=self.orbit_counter_class,
graphlet_size=self.graphlet_size,
arc_consistency=self.arc_consistency,
contraction=self.contraction,
edge_thinning=self.edge_thinning
)
pattern_orbits, candidate_sets, subgraph = filter_engine.run()
if not candidate_sets:
return None
order, pivot = OrderEngine(pattern_graph, pattern_orbits, method=self.order_method,
candidate_sets=candidate_sets).run()
return SearchEngine(subgraph, pattern_graph, candidate_sets, order, pivot, tail=self.tail)
[docs]
def run(self, pattern_graph):
"""List every embedding of a pattern.
Parameters
----------
pattern_graph : networkx.Graph
The pattern, with node labels in the ``'label'`` attribute.
Returns
-------
list of dict
One ``{pattern node: data node}`` dict per embedding.
"""
if pattern_graph.number_of_nodes() == 0:
return [{}]
search = self._prepare(pattern_graph)
return search.run() if search is not None else []
[docs]
def count(self, pattern_graph):
"""Count the embeddings of a pattern without materialising them.
Parameters
----------
pattern_graph : networkx.Graph
The pattern, with node labels in the ``'label'`` attribute.
Returns
-------
int
"""
if pattern_graph.number_of_nodes() == 0:
return 1
from ..orbit import EVOKEOrbitCounter
if self.backend == 'cpp' and self.orbit_counter_class is EVOKEOrbitCounter:
from .. import core
return core.count(self.data_graph, pattern_graph, graphlet_size=self.graphlet_size,
order_method=self.order_method, arc_consistency=self.arc_consistency,
contraction=self.contraction, edge_thinning=self.edge_thinning, tail=self.tail)
search = self._prepare(pattern_graph)
return search.count() if search is not None else 0