子图匹配 / 模式匹配：VF2 与 Ullmann 的工程化剪枝 ACERS 解析

模式 Q：A -knows-> B -works_at-> C
数据 G：含多个 A/B/C 标签节点与有向边
结果：存在至少 1 个满足标签与方向的映射

模式 Q：节点 X 度数>=4 且 label=Merchant
数据 G：所有 Merchant 节点最大度数=2
结果：候选为空，直接失败（无需回溯）

from typing import Dict, List, Set, Tuple


class Graph:
    def __init__(self, n: int):
        self.n = n
        self.adj = [set() for _ in range(n)]
        self.label = [""] * n

    def add_edge(self, u: int, v: int) -> None:
        self.adj[u].add(v)


def build_candidates(G: Graph, Q: Graph) -> List[Set[int]]:
    cands: List[Set[int]] = []
    for u in range(Q.n):
        s = set()
        for v in range(G.n):
            # 语义 + 度数下界剪枝
            if Q.label[u] == G.label[v] and len(Q.adj[u]) <= len(G.adj[v]):
                s.add(v)
        cands.append(s)
    return cands


def refine_candidates(G: Graph, Q: Graph, cands: List[Set[int]]) -> None:
    # Ullmann 风格邻域一致性收缩
    changed = True
    while changed:
        changed = False
        for u in range(Q.n):
            remove = []
            for v in cands[u]:
                ok = True
                for nu in Q.adj[u]:
                    # 至少存在一个候选邻居可承接边 u->nu
                    if not any((nv in G.adj[v]) for nv in cands[nu]):
                        ok = False
                        break
                if not ok:
                    remove.append(v)
            if remove:
                changed = True
                for x in remove:
                    cands[u].remove(x)


def has_match_vf2_style(G: Graph, Q: Graph) -> bool:
    cands = build_candidates(G, Q)
    refine_candidates(G, Q, cands)
    if any(len(s) == 0 for s in cands):
        return False

    order = sorted(range(Q.n), key=lambda u: len(cands[u]))
    used_g: Set[int] = set()
    mapping: Dict[int, int] = {}

    def feasible(u: int, v: int) -> bool:
        # 与已匹配节点的边一致性检查
        for qu, gv in mapping.items():
            if u in Q.adj[qu] and v not in G.adj[gv]:
                return False
            if qu in Q.adj[u] and gv not in G.adj[v]:
                return False
        return True

    def dfs(i: int) -> bool:
        if i == len(order):
            return True
        u = order[i]
        for v in cands[u]:
            if v in used_g:
                continue
            if not feasible(u, v):
                continue
            mapping[u] = v
            used_g.add(v)
            if dfs(i + 1):
                return True  # early stop: existence
            used_g.remove(v)
            del mapping[u]
        return False

    return dfs(0)


if __name__ == "__main__":
    # 数据图
    G = Graph(6)
    G.label = ["A", "B", "C", "A", "B", "C"]
    G.add_edge(0, 1)
    G.add_edge(1, 2)
    G.add_edge(3, 4)
    G.add_edge(4, 5)

    # 模式图 A->B->C
    Q = Graph(3)
    Q.label = ["A", "B", "C"]
    Q.add_edge(0, 1)
    Q.add_edge(1, 2)

    print(has_match_vf2_style(G, Q))  # True

python3 subgraph_match_demo.py

def is_suspicious(match_count: int, threshold: int = 1) -> bool:
    return match_count >= threshold

print(is_suspicious(2, 1))

package main

import "fmt"

func estimateSearchSpace(cands []int) int {
	space := 1
	for _, x := range cands {
		space *= x
	}
	return space
}

func main() {
	fmt.Println(estimateSearchSpace([]int{3, 5, 2})) // 30
}

function shardHint(candidateNodes, shardCount) {
  const hit = new Set(candidateNodes.map((x) => x % shardCount));
  return [...hit];
}

console.log(shardHint([12, 18, 25, 31], 4));

# existence-only subgraph match skeleton

def has_match(candidates, feasible):
    order = sorted(range(len(candidates)), key=lambda i: len(candidates[i]))
    used = set()
    map_q2g = {}

    def dfs(i):
        if i == len(order):
            return True
        u = order[i]
        for v in candidates[u]:
            if v in used:
                continue
            if not feasible(u, v, map_q2g):
                continue
            used.add(v)
            map_q2g[u] = v
            if dfs(i + 1):
                return True
            used.remove(v)
            del map_q2g[u]
        return False

    return dfs(0)

#include <stdio.h>

int main(void) {
    // C 版给出核心工程信号：先剪枝再回溯
    int candidate_size_q0 = 3;
    int candidate_size_q1 = 5;
    int search_space_upper = candidate_size_q0 * candidate_size_q1;
    printf("upper search space = %d\n", search_space_upper);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> cand = {3, 4, 2};
    long long upper = 1;
    for (int x : cand) upper *= x;
    cout << "upper=" << upper << "\n";
}

package main

import "fmt"

func upperBound(cands []int) int {
	ans := 1
	for _, x := range cands {
		ans *= x
	}
	return ans
}

func main() {
	fmt.Println(upperBound([]int{3, 4, 2}))
}

fn upper_bound(cands: &[usize]) -> usize {
    cands.iter().product()
}

fn main() {
    let cands = vec![3, 4, 2];
    println!("{}", upper_bound(&cands));
}

function upperBound(cands) {
  return cands.reduce((acc, x) => acc * x, 1);
}

console.log(upperBound([3, 4, 2]));