NetworkX：在 DAG 中查找最长路径，返回最大值的所有关系
NetworkX: Find longest path in DAG returning all ties for max
我无法弄清楚如何将 networkx dag_find_longest_path() 算法更新为 return "N" 而非 return 第一个最大边找到，或者 returning 一个包含最大权重的所有边的列表。
我首先从 pandas 数据帧创建了一个 DAG，其中包含如下子集的边缘列表：
edge1 edge2 weight
115252161:T 115252162:A 1.0
115252162:A 115252163:G 1.0
115252163:G 115252164:C 3.0
115252164:C 115252165:A 5.5
115252165:A 115252166:C 5.5
115252162:T 115252163:G 1.0
115252166:C 115252167:A 7.5
115252167:A 115252168:A 7.5
115252168:A 115252169:A 6.5
115252165:A 115252166:G 0.5
然后我用下面的代码对图进行拓扑排序，然后根据边的权重找到最长的路径：
G = nx.from_pandas_edgelist(edge_df, source="edge1",
target="edge2",
edge_attr=['weight'],
create_using=nx.OrderedDiGraph())
longest_path = pd.DataFrame(nx.dag_longest_path(G))
这很好用，除非最大加权边有关系，它 return 是找到的第一个最大边，相反我希望它只是 return 和 "N"代表"Null"。
所以目前，输出是：
115252161 T
115252162 A
115252163 G
115252164 C
115252165 A
115252166 C
但我真正需要的是：
115252161 T
115252162 N (or [A,T] )
115252163 G
115252164 C
115252165 A
115252166 C
寻找最长路径的算法是：
def dag_longest_path(G):
dist = {} # stores [node, distance] pair
for node in nx.topological_sort(G):
# pairs of dist,node for all incoming edges
pairs = [(dist[v][0] + 1, v) for v in G.pred[node]]
if pairs:
dist[node] = max(pairs)
else:
dist[node] = (0, node)
node, (length, _) = max(dist.items(), key=lambda x: x[1])
path = []
while length > 0:
path.append(node)
length, node = dist[node]
return list(reversed(path))
G.
的可复制粘贴定义
import pandas as pd
import networkx as nx
import numpy as np
edge_df = pd.read_csv(
pd.compat.StringIO(
"""edge1 edge2 weight
115252161:T 115252162:A 1.0
115252162:A 115252163:G 1.0
115252163:G 115252164:C 3.0
115252164:C 115252165:A 5.5
115252165:A 115252166:C 5.5
115252162:T 115252163:G 1.0
115252166:C 115252167:A 7.5
115252167:A 115252168:A 7.5
115252168:A 115252169:A 6.5
115252165:A 115252166:G 0.5"""
),
sep=r" +",
)
G = nx.from_pandas_edgelist(
edge_df,
source="edge1",
target="edge2",
edge_attr=["weight"],
create_using=nx.OrderedDiGraph(),
)
longest_path = pd.DataFrame(nx.dag_longest_path(G))
函数内的这一行似乎丢弃了你想要的路径；因为 max 只有 returns 个结果：
node, (length, _) = max(dist.items(), key=lambda x: x[1])
我会保留最大值，然后根据它搜索所有项目。然后重用代码来找到所需的路径。一个例子是这样的：
def dag_longest_path(G):
dist = {} # stores [node, distance] pair
for node in nx.topological_sort(G):
# pairs of dist,node for all incoming edges
pairs = [(dist[v][0] + 1, v) for v in G.pred[node]]
if pairs:
dist[node] = max(pairs)
else:
dist[node] = (0, node)
# store max value inside val variable
node, (length, val) = max(dist.items(), key=lambda x: x[1])
# find all dictionary items that have the maximum value
nodes = [(item[0], item[1][0]) for item in dist.items() if item[1][1] == val]
paths = []
# iterate over the different nodes and append the paths to a list
for node, length in nodes:
path = []
while length > 0:
path.append(node)
length, node = dist[node]
paths.append(list(reversed(path)))
return paths
PS。我还没有测试这段代码以了解它是否正确运行。
根据您的示例判断，每个节点都由位置 ID（: 之前的数字）确定，并且连接不同碱基的两个节点在计算路径长度时是相同的。如果这是正确的，则无需修改算法，您可以通过操作顶点标签来获得结果。
基本上，删除 edge_df 中分号后的所有内容，计算最长路径并附加原始数据中的基本标签。
edge_df_pos = pd.DataFrame(
{
"edge1": edge_df.edge1.str.partition(":")[0],
"edge2": edge_df.edge2.str.partition(":")[0],
"weight": edge_df.weight,
}
)
vert_labels = dict()
for col in ("edge1", "edge2"):
verts, lbls = edge_df[col].str.partition(":")[[0, 2]].values.T
for vert, lbl in zip(verts, lbls):
vert_labels.setdefault(vert, set()).add(lbl)
G_pos = nx.from_pandas_edgelist(
edge_df_pos,
source="edge1",
target="edge2",
edge_attr=["weight"],
create_using=nx.OrderedDiGraph(),
)
longest_path_pos = nx.dag_longest_path(G_pos)
longest_path_df = pd.DataFrame([[node, vert_labels[node]] for node in longest_path_pos])
结果
# 0 1
# 0 115252161 {T}
# 1 115252162 {A, T}
# 2 115252163 {G}
# 3 115252164 {C}
# 4 115252165 {A}
# 5 115252166 {G, C}
# 6 115252167 {A}
# 7 115252168 {A}
# 8 115252169 {A}
如果我的解释不正确，我怀疑是否有基于拓扑排序的算法的简单扩展。问题是一个图可以接受多种拓扑排序。如果您打印示例中 dag_longest_path 中定义的 dist，您将得到如下内容：
{'115252161:T': (0, '115252161:T'),
'115252162:A': (1, '115252161:T'),
'115252162:T': (0, '115252162:T'),
'115252163:G': (2, '115252162:A'),
'115252164:C': (3, '115252163:G'),
'115252165:A': (4, '115252164:C'),
'115252166:C': (5, '115252165:A'),
'115252166:G': (5, '115252165:A'),
'115252167:A': (6, '115252166:C'),
'115252168:A': (7, '115252167:A'),
'115252169:A': (8, '115252168:A')}
请注意 '115252162:T' 出现在第三行而不是其他地方。因此，dist 无法区分您的示例和另一个 '115252162:T' 作为不相交组件出现的示例。因此，仅使用 dist.
中的数据，应该不可能通过 '115252162:T' 恢复任何路径
我最终只是在 defaultdict 计数器对象中对行为进行建模。
from collections import defaultdict, Counter
我将边缘列表修改为（位置、核苷酸、权重）的元组：
test = [(112,"A",23.0), (113, "T", 27), (112, "T", 12.0), (113, "A", 27), (112,"A", 1.0)]
然后使用 defaultdict(counter) 快速求和每个核苷酸在每个位置的出现次数：
nucs = defaultdict(Counter)
for key, nuc, weight in test:
nucs[key][nuc] += weight
然后遍历字典，找出所有等于最大值的核苷酸：
for key, nuc in nucs.items():
seq_list = []
max_nuc = []
max_val = max(nuc.values())
for x, y in nuc.items():
if y == max_val:
max_nuc.append(x)
if len(max_nuc) != 1:
max_nuc = "N"
else:
max_nuc = ''.join(max_nuc)
seq_list.append(max_nuc)
sequence = ''.join(seq_list)
这个 returns 找到最大值的核苷酸的最终序列，returns N 在平局的位置：
TNGCACAAATGCTGAAAGCTGTACCATANCTGTCTGGTCTTGGCTGAGGTTTCAATGAATGGAATCCCGTAACTCTTGGCCAGTTCGTGGGCTTGTTTTGTATCAACTGTCCTTGTTGGCAAATCACACTTGTTTCCCACTAGCACCAT
但是，这个问题困扰着我，所以我最终使用 networkx 中的节点属性来标记每个节点是否为平局。现在，当在最长路径中返回一个节点时，我可以检查 "tie" 属性并用 "N" 替换节点名称（如果它已被标记）：
def get_path(self, edge_df):
G = nx.from_pandas_edgelist(
edge_df,
source="edge1",
target="edge2",
edge_attr=["weight"],
create_using=nx.OrderedDiGraph()
)
# flag all nodes as not having a tie
nx.set_node_attributes(G, "tie", False)
# check nodes for ties
for node in G.nodes:
# create list of all edges for each node
edges = G.in_edges(node, data=True)
# if there are multiple edges
if len(edges) > 1:
# find max weight
max_weight = max([edge[2]['weight'] for edge in edges])
tie_check = []
for edge in edges:
# pull out all edges that match max weight
if edge[2]["weight"] == max_weight:
tie_check.append(edge)
# check if there are ties
if len(tie_check) > 1:
for x in tie_check:
# flag node as being a tie
G.node[x[0]]["tie"] = True
# return longest path
longest_path = nx.dag_longest_path(G)
return longest_path
我无法弄清楚如何将 networkx dag_find_longest_path() 算法更新为 return "N" 而非 return 第一个最大边找到，或者 returning 一个包含最大权重的所有边的列表。
我首先从 pandas 数据帧创建了一个 DAG，其中包含如下子集的边缘列表：
edge1 edge2 weight
115252161:T 115252162:A 1.0
115252162:A 115252163:G 1.0
115252163:G 115252164:C 3.0
115252164:C 115252165:A 5.5
115252165:A 115252166:C 5.5
115252162:T 115252163:G 1.0
115252166:C 115252167:A 7.5
115252167:A 115252168:A 7.5
115252168:A 115252169:A 6.5
115252165:A 115252166:G 0.5
然后我用下面的代码对图进行拓扑排序，然后根据边的权重找到最长的路径：
G = nx.from_pandas_edgelist(edge_df, source="edge1",
target="edge2",
edge_attr=['weight'],
create_using=nx.OrderedDiGraph())
longest_path = pd.DataFrame(nx.dag_longest_path(G))
这很好用，除非最大加权边有关系，它 return 是找到的第一个最大边，相反我希望它只是 return 和 "N"代表"Null"。 所以目前，输出是：
115252161 T
115252162 A
115252163 G
115252164 C
115252165 A
115252166 C
但我真正需要的是：
115252161 T
115252162 N (or [A,T] )
115252163 G
115252164 C
115252165 A
115252166 C
寻找最长路径的算法是：
def dag_longest_path(G):
dist = {} # stores [node, distance] pair
for node in nx.topological_sort(G):
# pairs of dist,node for all incoming edges
pairs = [(dist[v][0] + 1, v) for v in G.pred[node]]
if pairs:
dist[node] = max(pairs)
else:
dist[node] = (0, node)
node, (length, _) = max(dist.items(), key=lambda x: x[1])
path = []
while length > 0:
path.append(node)
length, node = dist[node]
return list(reversed(path))
G.
import pandas as pd
import networkx as nx
import numpy as np
edge_df = pd.read_csv(
pd.compat.StringIO(
"""edge1 edge2 weight
115252161:T 115252162:A 1.0
115252162:A 115252163:G 1.0
115252163:G 115252164:C 3.0
115252164:C 115252165:A 5.5
115252165:A 115252166:C 5.5
115252162:T 115252163:G 1.0
115252166:C 115252167:A 7.5
115252167:A 115252168:A 7.5
115252168:A 115252169:A 6.5
115252165:A 115252166:G 0.5"""
),
sep=r" +",
)
G = nx.from_pandas_edgelist(
edge_df,
source="edge1",
target="edge2",
edge_attr=["weight"],
create_using=nx.OrderedDiGraph(),
)
longest_path = pd.DataFrame(nx.dag_longest_path(G))
函数内的这一行似乎丢弃了你想要的路径；因为 max 只有 returns 个结果：
node, (length, _) = max(dist.items(), key=lambda x: x[1])
我会保留最大值，然后根据它搜索所有项目。然后重用代码来找到所需的路径。一个例子是这样的：
def dag_longest_path(G):
dist = {} # stores [node, distance] pair
for node in nx.topological_sort(G):
# pairs of dist,node for all incoming edges
pairs = [(dist[v][0] + 1, v) for v in G.pred[node]]
if pairs:
dist[node] = max(pairs)
else:
dist[node] = (0, node)
# store max value inside val variable
node, (length, val) = max(dist.items(), key=lambda x: x[1])
# find all dictionary items that have the maximum value
nodes = [(item[0], item[1][0]) for item in dist.items() if item[1][1] == val]
paths = []
# iterate over the different nodes and append the paths to a list
for node, length in nodes:
path = []
while length > 0:
path.append(node)
length, node = dist[node]
paths.append(list(reversed(path)))
return paths
PS。我还没有测试这段代码以了解它是否正确运行。
根据您的示例判断，每个节点都由位置 ID（: 之前的数字）确定，并且连接不同碱基的两个节点在计算路径长度时是相同的。如果这是正确的，则无需修改算法，您可以通过操作顶点标签来获得结果。
基本上，删除 edge_df 中分号后的所有内容，计算最长路径并附加原始数据中的基本标签。
edge_df_pos = pd.DataFrame(
{
"edge1": edge_df.edge1.str.partition(":")[0],
"edge2": edge_df.edge2.str.partition(":")[0],
"weight": edge_df.weight,
}
)
vert_labels = dict()
for col in ("edge1", "edge2"):
verts, lbls = edge_df[col].str.partition(":")[[0, 2]].values.T
for vert, lbl in zip(verts, lbls):
vert_labels.setdefault(vert, set()).add(lbl)
G_pos = nx.from_pandas_edgelist(
edge_df_pos,
source="edge1",
target="edge2",
edge_attr=["weight"],
create_using=nx.OrderedDiGraph(),
)
longest_path_pos = nx.dag_longest_path(G_pos)
longest_path_df = pd.DataFrame([[node, vert_labels[node]] for node in longest_path_pos])
结果
# 0 1
# 0 115252161 {T}
# 1 115252162 {A, T}
# 2 115252163 {G}
# 3 115252164 {C}
# 4 115252165 {A}
# 5 115252166 {G, C}
# 6 115252167 {A}
# 7 115252168 {A}
# 8 115252169 {A}
如果我的解释不正确，我怀疑是否有基于拓扑排序的算法的简单扩展。问题是一个图可以接受多种拓扑排序。如果您打印示例中 dag_longest_path 中定义的 dist，您将得到如下内容：
{'115252161:T': (0, '115252161:T'),
'115252162:A': (1, '115252161:T'),
'115252162:T': (0, '115252162:T'),
'115252163:G': (2, '115252162:A'),
'115252164:C': (3, '115252163:G'),
'115252165:A': (4, '115252164:C'),
'115252166:C': (5, '115252165:A'),
'115252166:G': (5, '115252165:A'),
'115252167:A': (6, '115252166:C'),
'115252168:A': (7, '115252167:A'),
'115252169:A': (8, '115252168:A')}
请注意 '115252162:T' 出现在第三行而不是其他地方。因此，dist 无法区分您的示例和另一个 '115252162:T' 作为不相交组件出现的示例。因此，仅使用 dist.
'115252162:T' 恢复任何路径
我最终只是在 defaultdict 计数器对象中对行为进行建模。
from collections import defaultdict, Counter
我将边缘列表修改为（位置、核苷酸、权重）的元组：
test = [(112,"A",23.0), (113, "T", 27), (112, "T", 12.0), (113, "A", 27), (112,"A", 1.0)]
然后使用 defaultdict(counter) 快速求和每个核苷酸在每个位置的出现次数：
nucs = defaultdict(Counter)
for key, nuc, weight in test:
nucs[key][nuc] += weight
然后遍历字典，找出所有等于最大值的核苷酸：
for key, nuc in nucs.items():
seq_list = []
max_nuc = []
max_val = max(nuc.values())
for x, y in nuc.items():
if y == max_val:
max_nuc.append(x)
if len(max_nuc) != 1:
max_nuc = "N"
else:
max_nuc = ''.join(max_nuc)
seq_list.append(max_nuc)
sequence = ''.join(seq_list)
这个 returns 找到最大值的核苷酸的最终序列，returns N 在平局的位置：
TNGCACAAATGCTGAAAGCTGTACCATANCTGTCTGGTCTTGGCTGAGGTTTCAATGAATGGAATCCCGTAACTCTTGGCCAGTTCGTGGGCTTGTTTTGTATCAACTGTCCTTGTTGGCAAATCACACTTGTTTCCCACTAGCACCAT
但是，这个问题困扰着我，所以我最终使用 networkx 中的节点属性来标记每个节点是否为平局。现在，当在最长路径中返回一个节点时，我可以检查 "tie" 属性并用 "N" 替换节点名称（如果它已被标记）：
def get_path(self, edge_df):
G = nx.from_pandas_edgelist(
edge_df,
source="edge1",
target="edge2",
edge_attr=["weight"],
create_using=nx.OrderedDiGraph()
)
# flag all nodes as not having a tie
nx.set_node_attributes(G, "tie", False)
# check nodes for ties
for node in G.nodes:
# create list of all edges for each node
edges = G.in_edges(node, data=True)
# if there are multiple edges
if len(edges) > 1:
# find max weight
max_weight = max([edge[2]['weight'] for edge in edges])
tie_check = []
for edge in edges:
# pull out all edges that match max weight
if edge[2]["weight"] == max_weight:
tie_check.append(edge)
# check if there are ties
if len(tie_check) > 1:
for x in tie_check:
# flag node as being a tie
G.node[x[0]]["tie"] = True
# return longest path
longest_path = nx.dag_longest_path(G)
return longest_path