如何在多个潜在独立的无向图中找到最小顶点集，以获取最大的总cos

Question

我有一大组顶点/节点，它们代表一组图。请注意，在这个完整的集合中可能有许多独立的图。目标是找出所有这些图的最小顶点数，这些顶点对应于由这些选定顶点捕捉的所有边的最大权重总和。我有熊猫的邻接矩阵，我正在使用networkx。在

下面是一个包含三列的示例数据帧，其中Number_Of_Trips是权重。我可以提供node=10*trips的权重，以便将两个度量合并在一起。一、 e.最大化出行次数-10*NumberOfNodes

    Number_Of_Trips dropoff_gh7 pickup_gh7
0   304 9tbqhsx 9tbqj4g
1   271 9tbqj4f 9tbqhsx
2   263 9tbqt4s 9tbqhsx
3   258 9tbqdye 9tbqdsr
4   256 9tbqhgh 9tbqjfv
5   236 9tbqhsw 9tbqj4g
6   233 9tbqt4g 9tbqv03
7   229 9tbqhsx 9tbqj4c
8   218 9tbqy3f 9tbqt4s
9   213 9tbq5v4 9tbqh41
10  210 9tbqhgh 9tbqhsw
11  192 9tbqhgh 9tbqje4
12  186 9tbqy3f 9tbqt4g
13  184 9tbqhgh 9tbqj4z
14  183 9tbqe3d 9tbqe9e
15  170 9tbq3xn 9tbq39w
16  167 9tbq5bw 9tbqht6
17  163 9tbqhsx 9tbqh0x
18  162 9tbqdk1 9tbq7p2
19  160 9tbqsch 9tbqt4s

x = nx.from_pandas_dataframe(df,"dropoff_gh7","pickup_gh7","Number_Of_Trips")
graphs = list(nx.connected_component_subgraphs(x))

Answer 1

注意，对这个问题的一个警告是，在图中可能有多个独立的子图可以作为解决方案。这个解决方案的关键直觉是，子图最可能的候选对象是彼此共享许多边的顶点。事实证明，这正是在查看图中的集团时所评估的。因此，这个解决方案只需提取所有的团，然后按团中顶点所代表的权重总数（顶点数*垂直成本）对它们进行排序。这可以使用NetworkX快速原型化。在

G = nx.from_pandas_dataframe(df, "dropoff_gh7", "pickup_gh7", ['num_of_trips'])
# Find all the cliques in the graph (not only maximal but all sub cliques as well. Note that clique finding is NP complete so this may take a long time if your graph is > 100k of edges or more. For <100k edges, this took within 5 mins on a 16GB macbook pro 3GHz machine.
cliques = nx.find_cliques(G)
clique_trips = [np.array([c,G.subgraph(c).size(weight="num_of_trips")]) for c in cliques]
df_cliques = pd.DataFrame(clique_trips,columns=["vertices","num_of_trips"])
df_cliques["num_vertices"] = df_cliques.apply(lambda x:len(x[0]), axis=1)
df_cliques["weighted_trips"] = df_cliques.apply(lambda row: 
    row["num_of_trips"] - row["num_vertices"]*COST_PER_NODE, axis=1)
df_cliques = df_cliques.sort_values("weighted_trips")[::-1]
df_cliques.head()
# The top N cliques can then be aggregated into a set to identify the precise vertices that are most valuable.

Answer 2

这是逻辑的概要。在

创建一个集群结构。一个集群有成员节点、一个内部值（总的内部行程）和到其他集群的边。在

从单个集群中的每个节点开始。将所有这些集群放入“未完成”列表中。现在，您将遍历该列表，在其中合并您发现的优势的集群。选择列表中的第一个簇。在

迭代：对于该集群的每条边，检查在该边缘另一端合并集群的净值：内部trips+edge trips-10*集群总体（节点数量）。在

合并：连接两个集群的成员节点列表。添加它们的内部值和它们之间的边的值。调整节点填充（如果您还没有在其他地方进行计算）。将边列表合并到其他簇。从“未完成”列表中删除合并的群集。在

继续这个“Kleene闭包”过程，直到你没有更多的节点可以增加利润。将这个结果集群移到“完成”列表。在“not done”列表中选择下一个节点，重复iterate&merge循环，直到“done”列表为空。在

现在，将整个“done”列表移回“not done”列表，并重复该过程，直到您完成一个过程，并进一步合并no。在

---

你对这个过程的编码是否足够详细？在