0

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

下面是一个包含三列的示例数据框，其中 Number_Of_Trips 是权重。我可以提供 node = 10*trips 的权重，以便将两个指标合并在一起。即最大化旅行次数 - 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))
4

2 回答 2

1

这是逻辑的概述。

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

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

迭代：对于该集群的每个边缘，检查在该边缘的另一端合并集群的净值：内部行程 + 边缘行程 - 10*集群人口（节点数量）。

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

继续这个“Kleene Closure”过程，直到你没有更多的节点可以盈利。将此生成的集群移动到“完成”列表。选择“未完成”列表中的下一个节点并重复迭代和合并循环，直到“完成”列表为空。

现在，将整个“完成”列表移回“未完成”列表并重复该过程，直到完成一个没有进一步合并的过程。

是否足够详细，您可以编写该过程的代码？

于 2017-10-20T21:13:24.050 回答
0

请注意，对该问题的一个警告是，您可以在图中有多个独立的子图，这可能是解决方案。这个解决方案的关键直觉是子图最有可能的候选者是彼此共享大量边的顶点。事实证明，这正是在图表中查看 Cliques 时所评估的内容。因此，该解决方案简单地提取所有派系，然后通过派系中的顶点表示的权重总数对它们进行排序 - 顶点数 * 顶点的成本。这可以使用 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.
于 2017-10-31T17:28:42.123 回答