删除图中不必要的节点
Removing unnecessary nodes in graph
我的图表有两个不同的 classes 节点，class A 节点和 class B 节点。
Class A 节点未连接到任何其他 A 节点并且 class B 节点未连接到任何其他 B 节点，但 B 节点连接到 A 节点，反之亦然。一些 B 节点连接到许多 A 节点，大多数 A 节点连接到许多 B 节点。
我想从图中消除尽可能多的 A 节点。
我必须保留所有的B节点，并且它们必须仍然连接到至少一个A节点（最好只有一个A节点）。
当一个A节点没有只与它相连的B节点时，我可以删除它。是否有任何算法可以找到我可以删除 A 节点的最佳或至少接近最佳的解决方案？
旧的，不正确的答案，但从这里开始
首先，您需要认识到您有一个 bipartite graph。也就是说，您可以将节点着色为红色和蓝色，这样就没有边将红色节点连接到红色节点或将蓝色节点连接到蓝色节点。
接下来，认识到您正在尝试解决 vertex cover problem。来自维基百科：
In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm.
因为你有一个特殊的图表，所以有理由认为 NP-hard 可能不适用于你。这个想法将我们带到 Kőnig's theorem which relates the maximum matching problem to the minimum vertex cover problem. Once you know this, you can apply the Hopcroft–Karp algorithm 以在 O(|E|√|V|) 时间内解决问题，尽管您可能需要稍微调整一下以确保您保留所有 B 个节点。
新，正确答案
事实证明，这个 jiggering 是创建一个 "constrained bipartitate graph vertex cover problem"，它询问我们是否存在使用少于 a 个 A 节点和更少的顶点覆盖比 b B 节点。问题是 NP 完全的，所以这是不行的。跳绳比我想象的要难！
但是使用少于最小数量的节点并不是我们想要的约束。我们要确保使用最少数量的 A 节点和最多数量的 B 节点。
上面的 Kőnig 定理是最大流问题的一个特例。从流量的角度来思考这个问题，我们很快就会想到 minimum-cost flow problems。
在这些问题中，我们得到了一个图，其边具有指定的容量和运输的单位成本。目标是找到将给定数量的供应从任意一组源节点移动到任意一组汇节点所需的最低成本。
原来你的问题可以转化为最小成本流问题。为此，让我们生成一个连接到所有 A 节点的源节点和一个连接到所有 B 节点的汇节点。
现在，让我们将使用 Source->A 边的成本设为 1，并将所有其他边的成本设为零。此外，让我们让 Source->A 边的容量等于无穷大，所有其他边的容量等于 1.
如下所示：
红边的 Cost=1，Capacity=Inf。蓝色边的成本=0，容量=1。
现在，解决最小流量问题等同于使用尽可能少的红色边。任何未使用的红色边都会将 0 流分配给其对应的 A 节点，并且可以从图中删除该节点。反之，每个B节点只能将1个单位的流量传递给sink，所以必须保留所有B节点才能解决问题。
由于我们已将您的问题重铸为这种标准形式，我们可以利用现有工具来获得解决方案；即，Google's Operation Research Tools.
这样做给出了上图的以下答案：
红色边缘未使用，黑色边缘已使用。请注意，如果红色边缘从源出现，则它连接到的 A 节点不会生成黑色边缘。另请注意，每个 B 节点至少有一个传入黑边。这满足了您提出的限制条件。
我们现在可以通过查找零使用率的 Source->A 边来检测要删除的 A 节点。
源代码
生成上述图形和相关解决方案所需的源代码如下：
#!/usr/bin/env python3
#Documentation: https://developers.google.com/optimization/flow/mincostflow
#Install dependency: pip3 install ortools
from __future__ import print_function
from ortools.graph import pywrapgraph
import matplotlib.pyplot as plt
import networkx as nx
import random
import sys
def GenerateGraph(Acount,Bcount):
assert Acount>5
assert Bcount>5
G = nx.DiGraph() #Directed graph
source_node = Acount+Bcount
sink_node = source_node+1
for a in range(Acount):
for i in range(random.randint(0.2*Bcount,0.3*Bcount)): #Connect to 10-20% of the Bnodes
b = Acount+random.randint(0,Bcount-1) #In the half-open range [0,Bcount). Offset from A's indices
G.add_edge(source_node, a, capacity=99999, unit_cost=1, usage=1)
G.add_edge(a, b, capacity=1, unit_cost=0, usage=1)
G.add_edge(b, sink_node, capacity=1, unit_cost=0, usage=1)
G.node[a]['type'] = 'A'
G.node[b]['type'] = 'B'
G.node[source_node]['type'] = 'source'
G.node[sink_node]['type'] = 'sink'
G.node[source_node]['supply'] = Bcount
G.node[sink_node]['supply'] = -Bcount
return G
def VisualizeGraph(graph, color_type):
gcopy = graph.copy()
for p, d in graph.nodes(data=True):
if d['type']=='source':
source = p
if d['type']=='sink':
sink = p
Acount = len([1 for p,d in graph.nodes(data=True) if d['type']=='A'])
Bcount = len([1 for p,d in graph.nodes(data=True) if d['type']=='B'])
if color_type=='usage':
edge_color = ['black' if d['usage']>0 else 'red' for u,v,d in graph.edges(data=True)]
elif color_type=='unit_cost':
edge_color = ['red' if d['unit_cost']>0 else 'blue' for u,v,d in graph.edges(data=True)]
Ai = 0
Bi = 0
pos = dict()
for p,d in graph.nodes(data=True):
if d['type']=='source':
pos[p] = (0, Acount/2)
elif d['type']=='sink':
pos[p] = (3, Bcount/2)
elif d['type']=='A':
pos[p] = (1, Ai)
Ai += 1
elif d['type']=='B':
pos[p] = (2, Bi)
Bi += 1
nx.draw(graph, pos=pos, edge_color=edge_color, arrows=False)
plt.show()
def GenerateMinCostFlowProblemFromGraph(graph):
start_nodes = []
end_nodes = []
capacities = []
unit_costs = []
min_cost_flow = pywrapgraph.SimpleMinCostFlow()
for node,neighbor,data in graph.edges(data=True):
min_cost_flow.AddArcWithCapacityAndUnitCost(node, neighbor, data['capacity'], data['unit_cost'])
supply = len([1 for p,d in graph.nodes(data=True) if d['type']=='B'])
for p, d in graph.nodes(data=True):
if (d['type']=='source' or d['type']=='sink') and 'supply' in d:
min_cost_flow.SetNodeSupply(p, d['supply'])
return min_cost_flow
def ColorGraphEdgesByUsage(graph, min_cost_flow):
for i in range(min_cost_flow.NumArcs()):
graph[min_cost_flow.Tail(i)][min_cost_flow.Head(i)]['usage'] = min_cost_flow.Flow(i)
def main():
"""MinCostFlow simple interface example."""
# Define four parallel arrays: start_nodes, end_nodes, capacities, and unit costs
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 15 and a unit cost of 4.
Acount = 20
Bcount = 20
graph = GenerateGraph(Acount, Bcount)
VisualizeGraph(graph, 'unit_cost')
min_cost_flow = GenerateMinCostFlowProblemFromGraph(graph)
# Find the minimum cost flow between node 0 and node 4.
if min_cost_flow.Solve() != min_cost_flow.OPTIMAL:
print('Unable to find a solution! It is likely that one does not exist for this input.')
sys.exit(-1)
print('Minimum cost:', min_cost_flow.OptimalCost())
ColorGraphEdgesByUsage(graph, min_cost_flow)
VisualizeGraph(graph, 'usage')
if __name__ == '__main__':
main()
尽管这是一个老问题，但我看到它还没有得到正确回答。
与此类似的问题也已在 this post 中得到回答。
您在这里提出的问题确实是最小集覆盖问题，这是众所周知的 NP-hard 问题之一。从Wikipedia，最小集覆盖问题可以表述为：
Given a set of elements {1,2,...,n} (called the universe) and a collection S of m sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of S whose union equals the universe. For example, consider the universe U={1,2,3,4,5} and the collection of sets S={{1,2,3},{2,4},{3,4},{4,5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1,2,3},{4,5}}.
在您的公式中，B 节点代表宇宙中的元素，A 节点代表集合，A 节点和 B 节点之间的边确定哪些元素（B 节点）属于每个集合（A 节点）。那么，最小集合覆盖就相当于A节点的最小数量，使得它们连接到所有B节点。因此，在连接到每个 B 节点的同时可以从图中删除的最大数量的 A 节点是那些不属于最小集合覆盖的节点。
因为它是 NP-hard，所以没有用于计算最优值的多项式时间算法，但是一个简单的贪心算法可以有效地提供具有紧边界的最优解的近似解。来自 Wikipedia:
There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements.
我的图表有两个不同的 classes 节点，class A 节点和 class B 节点。
Class A 节点未连接到任何其他 A 节点并且 class B 节点未连接到任何其他 B 节点，但 B 节点连接到 A 节点，反之亦然。一些 B 节点连接到许多 A 节点，大多数 A 节点连接到许多 B 节点。
我想从图中消除尽可能多的 A 节点。
我必须保留所有的B节点，并且它们必须仍然连接到至少一个A节点（最好只有一个A节点）。
当一个A节点没有只与它相连的B节点时，我可以删除它。是否有任何算法可以找到我可以删除 A 节点的最佳或至少接近最佳的解决方案？
旧的，不正确的答案，但从这里开始
首先，您需要认识到您有一个 bipartite graph。也就是说，您可以将节点着色为红色和蓝色，这样就没有边将红色节点连接到红色节点或将蓝色节点连接到蓝色节点。
接下来，认识到您正在尝试解决 vertex cover problem。来自维基百科：
In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. The problem of finding a minimum vertex cover is a classical optimization problem in computer science and is a typical example of an NP-hard optimization problem that has an approximation algorithm.
因为你有一个特殊的图表，所以有理由认为 NP-hard 可能不适用于你。这个想法将我们带到 Kőnig's theorem which relates the maximum matching problem to the minimum vertex cover problem. Once you know this, you can apply the Hopcroft–Karp algorithm 以在 O(|E|√|V|) 时间内解决问题，尽管您可能需要稍微调整一下以确保您保留所有 B 个节点。
新，正确答案
事实证明，这个 jiggering 是创建一个 "constrained bipartitate graph vertex cover problem"，它询问我们是否存在使用少于 a 个 A 节点和更少的顶点覆盖比 b B 节点。问题是 NP 完全的，所以这是不行的。跳绳比我想象的要难！
但是使用少于最小数量的节点并不是我们想要的约束。我们要确保使用最少数量的 A 节点和最多数量的 B 节点。
上面的 Kőnig 定理是最大流问题的一个特例。从流量的角度来思考这个问题，我们很快就会想到 minimum-cost flow problems。
在这些问题中，我们得到了一个图，其边具有指定的容量和运输的单位成本。目标是找到将给定数量的供应从任意一组源节点移动到任意一组汇节点所需的最低成本。
原来你的问题可以转化为最小成本流问题。为此，让我们生成一个连接到所有 A 节点的源节点和一个连接到所有 B 节点的汇节点。
现在，让我们将使用 Source->A 边的成本设为 1，并将所有其他边的成本设为零。此外，让我们让 Source->A 边的容量等于无穷大，所有其他边的容量等于 1.
如下所示：
红边的 Cost=1，Capacity=Inf。蓝色边的成本=0，容量=1。
现在，解决最小流量问题等同于使用尽可能少的红色边。任何未使用的红色边都会将 0 流分配给其对应的 A 节点，并且可以从图中删除该节点。反之，每个B节点只能将1个单位的流量传递给sink，所以必须保留所有B节点才能解决问题。
由于我们已将您的问题重铸为这种标准形式，我们可以利用现有工具来获得解决方案；即，Google's Operation Research Tools.
这样做给出了上图的以下答案：
红色边缘未使用，黑色边缘已使用。请注意，如果红色边缘从源出现，则它连接到的 A 节点不会生成黑色边缘。另请注意，每个 B 节点至少有一个传入黑边。这满足了您提出的限制条件。
我们现在可以通过查找零使用率的 Source->A 边来检测要删除的 A 节点。
源代码
生成上述图形和相关解决方案所需的源代码如下：
#!/usr/bin/env python3
#Documentation: https://developers.google.com/optimization/flow/mincostflow
#Install dependency: pip3 install ortools
from __future__ import print_function
from ortools.graph import pywrapgraph
import matplotlib.pyplot as plt
import networkx as nx
import random
import sys
def GenerateGraph(Acount,Bcount):
assert Acount>5
assert Bcount>5
G = nx.DiGraph() #Directed graph
source_node = Acount+Bcount
sink_node = source_node+1
for a in range(Acount):
for i in range(random.randint(0.2*Bcount,0.3*Bcount)): #Connect to 10-20% of the Bnodes
b = Acount+random.randint(0,Bcount-1) #In the half-open range [0,Bcount). Offset from A's indices
G.add_edge(source_node, a, capacity=99999, unit_cost=1, usage=1)
G.add_edge(a, b, capacity=1, unit_cost=0, usage=1)
G.add_edge(b, sink_node, capacity=1, unit_cost=0, usage=1)
G.node[a]['type'] = 'A'
G.node[b]['type'] = 'B'
G.node[source_node]['type'] = 'source'
G.node[sink_node]['type'] = 'sink'
G.node[source_node]['supply'] = Bcount
G.node[sink_node]['supply'] = -Bcount
return G
def VisualizeGraph(graph, color_type):
gcopy = graph.copy()
for p, d in graph.nodes(data=True):
if d['type']=='source':
source = p
if d['type']=='sink':
sink = p
Acount = len([1 for p,d in graph.nodes(data=True) if d['type']=='A'])
Bcount = len([1 for p,d in graph.nodes(data=True) if d['type']=='B'])
if color_type=='usage':
edge_color = ['black' if d['usage']>0 else 'red' for u,v,d in graph.edges(data=True)]
elif color_type=='unit_cost':
edge_color = ['red' if d['unit_cost']>0 else 'blue' for u,v,d in graph.edges(data=True)]
Ai = 0
Bi = 0
pos = dict()
for p,d in graph.nodes(data=True):
if d['type']=='source':
pos[p] = (0, Acount/2)
elif d['type']=='sink':
pos[p] = (3, Bcount/2)
elif d['type']=='A':
pos[p] = (1, Ai)
Ai += 1
elif d['type']=='B':
pos[p] = (2, Bi)
Bi += 1
nx.draw(graph, pos=pos, edge_color=edge_color, arrows=False)
plt.show()
def GenerateMinCostFlowProblemFromGraph(graph):
start_nodes = []
end_nodes = []
capacities = []
unit_costs = []
min_cost_flow = pywrapgraph.SimpleMinCostFlow()
for node,neighbor,data in graph.edges(data=True):
min_cost_flow.AddArcWithCapacityAndUnitCost(node, neighbor, data['capacity'], data['unit_cost'])
supply = len([1 for p,d in graph.nodes(data=True) if d['type']=='B'])
for p, d in graph.nodes(data=True):
if (d['type']=='source' or d['type']=='sink') and 'supply' in d:
min_cost_flow.SetNodeSupply(p, d['supply'])
return min_cost_flow
def ColorGraphEdgesByUsage(graph, min_cost_flow):
for i in range(min_cost_flow.NumArcs()):
graph[min_cost_flow.Tail(i)][min_cost_flow.Head(i)]['usage'] = min_cost_flow.Flow(i)
def main():
"""MinCostFlow simple interface example."""
# Define four parallel arrays: start_nodes, end_nodes, capacities, and unit costs
# between each pair. For instance, the arc from node 0 to node 1 has a
# capacity of 15 and a unit cost of 4.
Acount = 20
Bcount = 20
graph = GenerateGraph(Acount, Bcount)
VisualizeGraph(graph, 'unit_cost')
min_cost_flow = GenerateMinCostFlowProblemFromGraph(graph)
# Find the minimum cost flow between node 0 and node 4.
if min_cost_flow.Solve() != min_cost_flow.OPTIMAL:
print('Unable to find a solution! It is likely that one does not exist for this input.')
sys.exit(-1)
print('Minimum cost:', min_cost_flow.OptimalCost())
ColorGraphEdgesByUsage(graph, min_cost_flow)
VisualizeGraph(graph, 'usage')
if __name__ == '__main__':
main()
尽管这是一个老问题，但我看到它还没有得到正确回答。
与此类似的问题也已在 this post 中得到回答。
您在这里提出的问题确实是最小集覆盖问题，这是众所周知的 NP-hard 问题之一。从Wikipedia，最小集覆盖问题可以表述为：
Given a set of elements {1,2,...,n} (called the universe) and a collection S of m sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of S whose union equals the universe. For example, consider the universe U={1,2,3,4,5} and the collection of sets S={{1,2,3},{2,4},{3,4},{4,5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1,2,3},{4,5}}.
在您的公式中，B 节点代表宇宙中的元素，A 节点代表集合，A 节点和 B 节点之间的边确定哪些元素（B 节点）属于每个集合（A 节点）。那么，最小集合覆盖就相当于A节点的最小数量，使得它们连接到所有B节点。因此，在连接到每个 B 节点的同时可以从图中删除的最大数量的 A 节点是那些不属于最小集合覆盖的节点。
因为它是 NP-hard，所以没有用于计算最优值的多项式时间算法，但是一个简单的贪心算法可以有效地提供具有紧边界的最优解的近似解。来自 Wikipedia:
There is a greedy algorithm for polynomial time approximation of set covering that chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements.