algorithm - 删除图中不必要的节点

Question

我有一个图，它有两类不同的节点，A 类节点和 B 类节点。

A 类节点不连接到任何其他 A 节点，B 类节点不连接到任何其他 B 节点，但 B 节点连接到 A 节点，反之亦然。一些 B 节点连接到许多 A 节点，大多数 A 节点连接到许多 B 节点。

我想从图中消除尽可能多的 A 节点。

我必须保留所有 B 节点，并且它们必须仍然连接到至少一个 A 节点(最好只有一个 A 节点)。

当没有 B 节点连接时，我可以删除 A 节点。是否有任何算法可以找到我可以删除 A 节点的最佳或至少接近最佳的解决方案？

Answer 1

旧的、不正确的答案，但从这里开始

首先，您需要认识到您有一个 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它将最大匹配问题与最小顶点覆盖问题联系起来。一旦你知道这一点，你就可以申请 Hopcroft–Karp algorithm在 O(|E|√|V|) 时间内解决问题，尽管您可能需要稍微调整一下以确保保留所有 B 节点.

新的正确答案

事实证明，这个 jiggering 是创建一个“受约束的二分图顶点覆盖问题”，它询问我们是否存在使用少于 a 个 A 节点且少于 < em>b B 节点。问题是 NP 完全的，所以这是不行的。跳汰机比我想象的要难!

但是使用少于最小数量的节点并不是我们想要的约束。我们要确保使用最少数量的 A 节点和最多数量的 B 节点。

上面的 Kőnig 定理是最大流问题的一个特例。从流量的角度考虑这个问题，我们很快就会想到 minimum-cost flow problems .

在这些问题中，我们得到了一个图，其边具有指定的容量和运输的单位成本。目标是找到将给定数量的供应从任意一组源节点移动到任意一组汇节点所需的最低成本。

事实证明，您的问题可以转换为最小成本流问题。为此，让我们生成一个连接到所有 A 节点的源节点和一个连接到所有 B 节点的汇节点。

现在，让我们将使用 Source->A 边的成本设为 1，并将所有其他边的成本设为零。此外，我们让 Source->A 边的容量等于无穷大，所有其他边的容量都等于 1。

这看起来像下面这样:

红色边的 Cost=1，Capacity=Inf。蓝色边的 Cost=0，Capacity=1。

现在，解决最小流量问题等同于使用尽可能少的红色边。任何未使用的红色边都会将 0 流分配给其对应的 A 节点，并且可以从图中删除该节点。相反，每个 B 节点只能将 1 个单位的流量传递给汇点，因此必须保留所有 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()