目录
- 背景
- 预备知识
- 思路
- 核心代码
- 参考文献
背景
最近在做青浦华为周边交通仿真项目，是基于MATSim仿真引擎的一套技术路线，主要有个network，plans，schedule，vehicle等仿真需要用到的文件，其中，network是刻画的是整个路网，包含了常规路网和轨道交通路网，表示车流量的供给端，由于路网最初的数据来源于OSM，其中还不乏人工校验修正，最后一步就是整成MATSim能够识别的network，这里有几个图论的知识点。
预备知识
- 有向图
任意2个顶点之间的联线具有指向性。
- 无向图
任意2个顶点之间的联线没有指向性。
- 完全图
如果无向图中的任何一对顶点之间都有一条边，这种无向图称为完全图。
- 完全子图
给定无向图G=(V,E)。如果U⊆V，且对任意u，v⊆U 有(u，v) ⊆ E，则称U 是G 的完全子图。
- 最大团（最大完全子图）
U是G的团当且仅当U不包含在G 的更大的完全子图中,U也叫G的最大团。
- 强连通分量
在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。
思路
从上面基本概念知道最大团是针对无向图的，而强连通分量是针对有向图的，如果要求一个有向图的最大团的话首先要弱化为无向图，再求无向图的最大团，即
(1) ，先把有向图的所有强连通分量找出来；
(2)，再把每个强连通分量转化为无向图；
(3)，去每个转化后的无向图找到最大团；
(4)，更新全局最大团；
(5)，查找无向图中的最大团;
(6)，对于大型图，可能需要使用更高效的算法，如Bron-Kerbosch算法。
核心代码
import random
import networkx as nx
.....
G = nx.from_pandas_edgelist(link_df, 'froms', 'tos', create_using = nx.DiGraph()) #有向图
max_clique_nodes = find_maximum_clique_in_directed_graph(G) #通过寻找最大团来清洗
max_clique_nodes = set(max_clique_nodes)......def find_maximum_clique_in_directed_graph(directed_graph):"""在有向图中查找最大团"""# 找到所有的强连通分量sccs = list(nx.strongly_connected_components(directed_graph))max_clique_across_sccs = []max_clique_size_across_sccs = 0for scc in sccs:# 构建强连通分量内部的无向图（忽略方向）scc_graph = directed_graph.subgraph(scc).to_undirected()# 在强连通分量内部查找最大团max_clique_in_scc = find_max_clique(scc_graph)# 更新全局最大团if len(max_clique_in_scc) > max_clique_size_across_sccs:max_clique_size_across_sccs = len(max_clique_in_scc)max_clique_across_sccs = max_clique_in_sccreturn max_clique_across_sccsdef dfs(graph, visited, start_node): #进行深度优先搜索给定出发节点的最大团visited.add(start_node)neighbors = list(graph.neighbors(start_node))max_clique = set() #用来存放属于start_node的最大团for n in neighbors:if n not in visited: #如果没访问过，则以她为初始节点继续搜索clique = dfs(graph, visited, n)if len(clique) > len(max_clique):max_clique = cliquereturn visited | max_cliquedef find_max_clique(graph): #遍历整个图，找出最大的团，即完全子图max_clique_size = 0max_clique_nodes = set()select_node = random.sample(list(graph.nodes), k =1) #随机选取k个node作为初始节点for start_node in tqdm(select_node): #为每个初始节点寻找最大团visited = set() #用来存放访问过的节点clique = dfs(graph, visited, start_node) #为每个指定的节点找最大团if len(clique) > max_clique_size:max_clique_size = len(clique)max_clique_nodes = cliquereturn max_clique_nodes
由于一个有向图的强连通分量也许会有很多，针对每一个强连通分量都去找最大团的话会花费很多时间，有个取巧的办法就是取最大的强连通分量，然后只针对这一个最大的强连通分量去找最大团会省很多时间，同时也有风险点，就是这个最大团可能不是全局的而是局部的。
### 改进代码def find_maximum_clique_in_directed_graph(directed_graph): #在有向图中查找最大团sccs = max(nx.strongly_connected_components(directed_graph), key=len) #最大强连通分量max_clique_across_sccs = []max_clique_size_across_sccs = 0scc_graph = directed_graph.subgraph(sccs).to_undirected() # 构建强连通分量内部的无向图（忽略方向）max_clique_in_scc = find_max_clique(scc_graph) # 在强连通分量内部查找最大团# 更新全局最大团if len(max_clique_in_scc) > max_clique_size_across_sccs:max_clique_size_across_sccs = len(max_clique_in_scc)max_clique_across_sccs = max_clique_in_sccreturn max_clique_across_sccsdef dfs(graph, visited, start_node): #进行深度优先搜索给定出发节点的最大团visited.add(start_node)neighbors = list(graph.neighbors(start_node))max_clique = set() #用来存放属于start_node的最大团for n in neighbors:if n not in visited: #如果没访问过，则以她为初始节点继续搜索clique = dfs(graph, visited, n)if len(clique) > len(max_clique):max_clique = cliquereturn visited | max_cliquedef find_max_clique(graph): #遍历整个图，找出最大的团，即完全子图max_clique_size = 0max_clique_nodes = set()select_node = random.sample(list(graph.nodes), k =1) #随机选取k个node作为初始节点for start_node in tqdm(select_node): #为每个初始节点寻找最大团visited = set() #用来存放访问过的节点clique = dfs(graph, visited, start_node) #为每个指定的节点找最大团if len(clique) > max_clique_size:max_clique_size = len(clique)max_clique_nodes = cliquereturn max_clique_nodes
参考文献
1，https://networkx.org/
2，python 实现connected components连通分量算法
3，有向图求强连通分量的几种算法
4，极大团(maximal clique)算法:Bron-Kerbosch算法
5，图论 —— 最大团问题