如何在多个潜在独立的无向图中找到捕获最大总成本的最小顶点集
How to find the min set of vertices in multiple potentially independent UNdirected Graphs that captures the largest total cost
我有一大组 vertices/nodes 代表一组图表。请注意，在这个完整的集合中可能有许多独立的图。目标是找到所有这些图中的最小顶点数，这些顶点数对应于这些选定顶点捕获的所有边上的最大权重总和。我在 pandas 中有邻接矩阵，我正在使用 networkx.
下面是一个包含三列的示例数据框，其中 Number_Of_Trips 是权重。我可以提供 node = 10*trips 的权重，以便将两个指标合并在一起。 IE。最大化行程数 - 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))
这是逻辑的概要。
创建一个集群结构。 集群有成员节点、内部值（内部总行程）和到其他集群的边。
从单个集群中的每个节点开始。将所有这些集群放入 "not done" 列表中。您现在要遍历该列表，合并您认为这样做有优势的集群。选择列表中的第一个集群。
Iterate：对于那个cluster的每条边，检查在那个边的另一端合并cluster的净值：internal trips + edge trips - 10*cluster population （节点数量）。
Merge：拼接两个簇的成员节点列表。添加它们的内部值和它们之间的边缘值。调整节点数量（如果您还没有在其他地方进行核算）。将边列表合并到其他集群。从 "not done" 列表中删除合并的集群。
继续这个 "Kleene Closure" 过程，直到您没有更多的节点可以盈利。将此生成的集群移动到 "done" 列表。选择 "not done" 列表中的下一个节点并重复迭代和合并循环，直到 "done" 列表为空。
现在，将整个 "done" 列表移回 "not done" 列表并重复该过程，直到完成 没有 进一步合并的传递。
是否足够详细，您可以编写流程代码？
请注意，对这个问题的一个警告是，您可以在图中有多个独立的子图，这些子图可能是解决方案。这个解决方案的关键直觉是子图最有可能的候选者是彼此共享很多边的顶点。事实证明，这正是在图表中查看 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.
我有一大组 vertices/nodes 代表一组图表。请注意，在这个完整的集合中可能有许多独立的图。目标是找到所有这些图中的最小顶点数，这些顶点数对应于这些选定顶点捕获的所有边上的最大权重总和。我在 pandas 中有邻接矩阵，我正在使用 networkx.
下面是一个包含三列的示例数据框，其中 Number_Of_Trips 是权重。我可以提供 node = 10*trips 的权重，以便将两个指标合并在一起。 IE。最大化行程数 - 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))
这是逻辑的概要。
创建一个集群结构。 集群有成员节点、内部值（内部总行程）和到其他集群的边。
从单个集群中的每个节点开始。将所有这些集群放入 "not done" 列表中。您现在要遍历该列表，合并您认为这样做有优势的集群。选择列表中的第一个集群。
Iterate：对于那个cluster的每条边，检查在那个边的另一端合并cluster的净值：internal trips + edge trips - 10*cluster population （节点数量）。
Merge：拼接两个簇的成员节点列表。添加它们的内部值和它们之间的边缘值。调整节点数量（如果您还没有在其他地方进行核算）。将边列表合并到其他集群。从 "not done" 列表中删除合并的集群。
继续这个 "Kleene Closure" 过程，直到您没有更多的节点可以盈利。将此生成的集群移动到 "done" 列表。选择 "not done" 列表中的下一个节点并重复迭代和合并循环，直到 "done" 列表为空。
现在，将整个 "done" 列表移回 "not done" 列表并重复该过程，直到完成 没有 进一步合并的传递。
是否足够详细，您可以编写流程代码？
请注意，对这个问题的一个警告是，您可以在图中有多个独立的子图，这些子图可能是解决方案。这个解决方案的关键直觉是子图最有可能的候选者是彼此共享很多边的顶点。事实证明，这正是在图表中查看 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.