"""Backtracking search over the filtered candidates (SearchEngine)."""
import sys
[docs]
class SearchEngine:
"""Backtracking search for the embeddings of a pattern over filtered candidate sets.
Local candidates come from a candidate-space index, filled in as the search reaches it: for every
pattern edge (u', u) with u' earlier in the order, and every candidate v' of u', the candidates of u
adjacent to v'. The candidates of u at a search node are the intersection of those sets over u's
already-matched (backward) neighbours, so every candidate tried is adjacent to all of them; only
injectivity remains to be checked. A pattern vertex with no backward neighbour (the first vertex of
each connected component) takes its whole candidate set.
Parameters
----------
data_graph : graph
The graph searched: the candidate subgraph returned by :meth:`FilterEngine.run` (any graph
with NetworkX's ``adj`` works).
pattern_graph : networkx.Graph
The pattern.
candidate_sets : dict
``{pattern node: candidate data nodes}``.
order : list
The pattern nodes in matching order.
pivot : dict, optional
Accepted for compatibility; not needed.
tail : bool, default True
Let :meth:`count` count the last vertices of the order together instead of searching them, if
they are mutually non-adjacent and their candidate sets pairwise disjoint (the longest such run
at the end, up to ``TAIL_MAX``; the order is not changed). Once the others are mapped, every
neighbour of a tail vertex is mapped, and since no two tail vertices can take the same data
vertex, their images number the product, over tail vertices, of each one's unused local
candidates. Not in OrbitSI as published.
"""
TAIL_MAX = 5
def __init__(self, data_graph, pattern_graph, candidate_sets, order, pivot=None, tail=True):
self.use_tail = tail
self.data_graph = data_graph
self.pattern_graph = pattern_graph
self.candidate_sets = candidate_sets
self.order = list(order)
self.matches = []
self._prepared = False
self._tail = 1
def _prepare(self):
"""Per depth of the order: the candidate sets, and each backward neighbour's depth with an empty index for it."""
order = self.order
pos = {u: i for i, u in enumerate(order)}
self._cand = [frozenset(self.candidate_sets[u]) for u in order]
self._cand_list = [list(self.candidate_sets[u]) for u in order]
self._adj = self.data_graph.adj
self._backward = []
for d, u in enumerate(order):
self._backward.append([(pos[w], {}) for w in self.pattern_graph.neighbors(u) if pos[w] < d])
self._empty = frozenset()
self._prepared = True
def _adjacent(self, d, b, index, v_prev):
"""The candidates of order[d] adjacent to v_prev (the image of order[b]), from the index."""
s = index.get(v_prev)
if s is None:
cand_d, nbrs = self._cand[d], self._adj[v_prev]
if len(cand_d) <= len(nbrs):
s = frozenset(v for v in cand_d if v in nbrs)
else:
s = cand_d.intersection(nbrs)
index[v_prev] = s
return s
def _choose_tail(self):
"""For count(): the tail (see the class docstring) -- the longest run at the end of the order of
vertices with neighbours, mutually non-adjacent and with pairwise disjoint candidate sets, at most
TAIL_MAX, leaving one vertex before it. Sets self._tail."""
P, order = self.pattern_graph, self.order
tail, seen = [], set()
for u in reversed(order):
if len(tail) == self.TAIL_MAX or len(tail) == len(order) - 1:
break
nbrs = set(P.neighbors(u))
cands = set(self.candidate_sets[u])
if not nbrs or u in nbrs or any(t in nbrs for t in tail) or not seen.isdisjoint(cands):
break
tail.append(u)
seen |= cands
if len(tail) >= 2:
self._tail = len(tail)
def _search(self, count_only, on_match=None):
"""Depth-first search. The local candidates of each depth are computed inline, specialised by
the number of backward neighbours (the hot path: one is a cached lookup, two one intersection).
Counting adds up the last level directly; with count_only, the last two levels are fused, so no
call is made per vertex of the second-to-last level. on_match(mapping, v) gets each embedding
otherwise (the last vertex's image is v)."""
if not self._prepared:
self._prepare()
n = len(self.order)
if n == 0:
if on_match is not None:
on_match([], None)
return 1
backward, cand_list, adjacent, empty = self._backward, self._cand_list, self._adjacent, self._empty
kinds = [len(e) for e in backward]
mapping = [None] * n
used = set()
last = n - 1
total = 0
def local(d):
k = kinds[d]
if k == 1:
b, index = backward[d][0]
v = mapping[b]
s = index.get(v)
return s if s is not None else adjacent(d, b, index, v)
if k == 0:
return cand_list[d]
if k == 2:
(b1, i1), (b2, i2) = backward[d]
v1, v2 = mapping[b1], mapping[b2]
s1 = i1.get(v1)
if s1 is None:
s1 = adjacent(d, b1, i1, v1)
if not s1:
return empty
s2 = i2.get(v2)
if s2 is None:
s2 = adjacent(d, b2, i2, v2)
return s1 & s2
sets = []
for b, index in backward[d]:
v = mapping[b]
s = index.get(v)
if s is None:
s = adjacent(d, b, index, v)
if not s:
return empty
sets.append(s)
sets.sort(key=len)
return sets[0].intersection(*sets[1:])
def count_last(cands):
if isinstance(cands, frozenset):
return len(cands) - len(used.intersection(cands))
return sum(1 for v in cands if v not in used)
tail = self._tail if count_only else 1
first_tail = n - tail
def count_tail():
"""The injective images of the tail vertices: their candidate sets are pairwise disjoint, so
the product of each one's unused local candidates."""
prod = 1
for d in range(first_tail, n):
s = local(d)
c = len(s) - len(used.intersection(s)) if s else 0
if c <= 0:
return 0
prod *= c
return prod
def extend(d):
nonlocal total
if d == first_tail and tail > 1:
total += count_tail()
return
cands = local(d)
if not cands:
return
if d == last:
if count_only:
total += count_last(cands)
else:
for v in cands:
if v not in used:
total += 1
on_match(mapping, v)
return
if count_only and tail == 1 and d == last - 1:
for v in cands:
if v in used:
continue
mapping[d] = v
lc = local(last)
if lc:
total += count_last(lc) - (v in lc)
mapping[d] = None
return
for v in cands:
if v in used:
continue
mapping[d] = v
used.add(v)
extend(d + 1)
used.discard(v)
mapping[d] = None
old_limit = sys.getrecursionlimit()
sys.setrecursionlimit(max(old_limit, n + 1000))
try:
extend(0)
finally:
sys.setrecursionlimit(old_limit)
return total
[docs]
def run(self, return_all=True):
"""List the embeddings.
Parameters
----------
return_all : bool, default True
If False, stop at the first embedding.
Returns
-------
list of dict
One ``{pattern node: data node}`` dict per embedding.
"""
order = self.order
matches = []
if not order:
self._search(False, lambda mapping, v: matches.append({}))
else:
last_u = order[-1]
def on_match(mapping, v):
match = dict(zip(order, mapping))
match[last_u] = v
matches.append(match)
self._search(False, on_match)
self.matches = matches
return matches if return_all else matches[:1]
[docs]
def count(self):
"""Count the embeddings without materialising them.
Returns
-------
int
"""
if not self._prepared and self.use_tail:
self._choose_tail()
return self._search(True)