"""Matching orders for the search (OrderEngine)."""
import heapq
[docs]
class OrderEngine:
"""Matching order for the search.
Parameters
----------
pattern_graph : networkx.Graph
The pattern.
pattern_orbits : dict, optional
``{pattern node: orbit vector}``; needed by the 'orbit' method.
method : {'auto', 'orbit', 'degree', 'core'}, default 'auto'
'auto' is OrbitSI's order: 'orbit' if ``pattern_orbits`` is given, else 'degree'.
'orbit' starts at the vertex with the largest orbit strength (sum of squared orbit counts),
then repeatedly takes the vertex with the most already-ordered neighbours, ties by orbit
strength. 'degree' is the same with degree in place of orbit strength. 'core' orders the
2-core's vertices before the trees hanging off it: it starts at the vertex with the fewest
candidates per pattern neighbour, then repeatedly takes the vertex with the most
already-ordered neighbours, ties by fewest candidates.
candidate_sets : dict, optional
``{pattern node: candidates}``; needed by the 'core' method.
"""
def __init__(self, pattern_graph, pattern_orbits=None, method='auto', candidate_sets=None):
self.pattern_graph = pattern_graph
self.pattern_orbits = pattern_orbits
self.candidate_sets = candidate_sets
self.num_nodes = pattern_graph.number_of_nodes()
if method == 'auto':
self.method = 'orbit' if pattern_orbits is not None else 'degree'
elif method == 'orbit':
if pattern_orbits is None:
raise ValueError("Orbit method selected but no orbit data provided.")
self.method = 'orbit'
elif method == 'degree':
self.method = 'degree'
elif method == 'core':
if candidate_sets is None:
raise ValueError("Core method selected but no candidate sets provided.")
self.method = 'core'
else:
raise ValueError("Invalid method: choose from 'auto', 'orbit', 'degree' or 'core'")
self.use_orbit = self.method == 'orbit'
[docs]
def compute_score(self, node):
"""A pattern vertex's strength: its orbit strength with the 'orbit' method, else its degree."""
if self.use_orbit:
return sum(x * x for x in self.pattern_orbits[node])
else:
return self.pattern_graph.degree[node]
[docs]
def run(self):
"""Compute the order.
Returns
-------
order : list
The pattern nodes in matching order.
pivot : dict
``{pattern node: an earlier neighbour in the order}``, None for a node without one.
"""
if self.num_nodes == 0:
return [], {}
if self.method == 'core':
order = self._core_order()
else:
order = self._strength_order()
pivot = {}
for i, u in enumerate(order):
pivot[u] = next((v for v in order[:i] if self.pattern_graph.has_edge(u, v)), None)
return order, pivot
def _greedy(self, start, key):
"""start, then repeatedly the unordered vertex minimising key(u, backward[u]) (backward[u]: its
already-ordered neighbours), ties to the earliest in node order. A heap with stale entries
skipped: a vertex's key changes only when a neighbour is ordered."""
G = self.pattern_graph
pos = {u: i for i, u in enumerate(G.nodes)}
backward = dict.fromkeys(G.nodes, 0)
heap = [(key(u, 0), pos[u], u) for u in G.nodes if u != start]
heapq.heapify(heap)
order, visited = [start], {start}
def place(x):
for w in G.neighbors(x):
if w not in visited:
backward[w] += 1
heapq.heappush(heap, (key(w, backward[w]), pos[w], w))
place(start)
while heap:
k, _, u = heapq.heappop(heap)
if u in visited or k != key(u, backward[u]):
continue
order.append(u)
visited.add(u)
place(u)
return order
def _strength_order(self):
"""OrbitSI's order (orbit or degree strength): most already-ordered neighbours, ties by strength."""
G = self.pattern_graph
strength = {u: self.compute_score(u) for u in G.nodes}
start = max(strength, key=strength.get)
return self._greedy(start, lambda u, b: (-b, -strength[u]))
def _two_core(self):
"""The vertices of the pattern's 2-core (nx.k_core(G, 2), without self-loops): peel vertices of
degree < 2 until none is left."""
G = self.pattern_graph
deg = {u: sum(1 for w in G.neighbors(u) if w != u) for u in G.nodes}
stack = [u for u, d in deg.items() if d < 2]
gone = set(stack)
while stack:
u = stack.pop()
for w in G.neighbors(u):
if w != u and w not in gone:
deg[w] -= 1
if deg[w] < 2:
gone.add(w)
stack.append(w)
return {u for u in G.nodes if u not in gone}
def _core_order(self):
"""The 'core' order (see the class docstring); with no 2-core, every vertex counts as in it."""
G = self.pattern_graph
core = self._two_core()
if not core:
core = set(G.nodes)
ncand = {u: len(self.candidate_sets[u]) for u in G.nodes}
in_core = {u: u in core for u in G.nodes}
start = min(G.nodes, key=lambda u: (not in_core[u], ncand[u] / max(G.degree[u], 1)))
return self._greedy(start, lambda u, b: (b == 0, not in_core[u], -b, ncand[u]))