Repository navigation
Expand file tree
/
Copy pathutils.py
More file actions
86 lines (65 loc) · 2.71 KB
/
Copy pathutils.py
File metadata and controls
86 lines (65 loc) · 2.71 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
"""Utility functions for the tree decomposition assignment.
Provides:
- Fractional edge cover computation via linear programming.
- Fractional hypertree width computation.
"""
import numpy as np
from scipy.optimize import linprog
from query import ConjunctiveQuery, Relation
def fractional_edge_cover(variables, query):
"""Compute the optimal fractional edge cover for a set of variables.
A fractional edge cover assigns a non-negative weight to each relation
such that every variable is covered (the sum of weights of relations
containing that variable is >= 1), and the total weight is minimized.
Args:
variables: A set/list of variables to cover.
query: A ConjunctiveQuery object.
Returns:
A dict mapping relation name -> optimal weight (float).
Only relations with non-zero weight are included.
Example:
>>> R = Relation("R", ["x", "y"])
>>> S = Relation("S", ["y", "z"])
>>> T = Relation("T", ["x", "z"])
>>> cover = fractional_edge_cover({"x", "y", "z"}, query=ConjunctiveQuery([], [R, S, T]))
>>> # For the triangle, optimal cover assigns 0.5 to each relation
"""
variables = list(variables)
n_vars = len(variables)
n_rels = len(query.relations)
if n_vars == 0:
return {}
# Objective: minimize sum of weights
c = np.ones(n_rels)
# Constraints: for each variable, sum of weights of relations containing it >= 1
# linprog uses A_ub @ x <= b_ub, so we negate for >= constraints
A_ub = np.zeros((n_vars, n_rels))
for i, var in enumerate(variables):
for j, rel in enumerate(query.relations):
if var in rel.variables:
A_ub[i, j] = -1.0
b_ub = -np.ones(n_vars)
# Bounds: weights >= 0
bounds = [(0, None) for _ in range(n_rels)]
result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')
if not result.success:
raise ValueError(f"LP solver failed: {result.message}")
# Build result dict (only include relations with non-negligible weight)
cover = {}
for j, rel in enumerate(query.relations):
if result.x[j] > 1e-9:
cover[rel.name] = float(result.x[j])
return cover
def fractional_edge_cover_value(variables, query):
"""Compute the optimal fractional edge cover number (rho*).
This is the minimum total weight of a fractional edge cover.
Equivalently, this is the maximum weight of a fractional vertex
packing.
Args:
variables: A set/list of variables to cover.
query: A ConjunctiveQuery object.
Returns:
The fractional edge cover number (float).
"""
cover = fractional_edge_cover(variables, query)
return sum(cover.values())