У меня очень большой граф (25 ГБ, 35 миллионов ребер) и коллекция узлов. Я хочу найти дерево, в котором есть все эти узлы; дерево, которое минимизирует количество ребер, но максимизирует количество охватываемых узлов.
Мой подход заключался в использовании Штайнера, но мне было интересно, существует ли более быстрый способ обработки или альтернативные алгоритмы, которые быстрее.
Сейчас я использую функцию NetworkX steiner_tree для анализа, но это занимает слишком много времени.
В1) Есть ли надежный PCST на Python? Я знаю, что он есть в R, но не уверен, что он быстрее, чем NetworkX.
Q2) Есть ли лучший алгоритм, который я могу использовать, — PCST, но быстрее?В настоящее время для анализа используется NetworkX steiner_tree. Граф неориентированный, без веса ребер.
def load_graph(file_path):
df = pd.read_csv(file_path, sep='\t', low_memory=False)
G = nx.Graph()
for index, row in df.iterrows():
G.add_edge(row['subject'], row['object'], predicate=row['predicate']) # Include predicate if needed
return G
# Find largest connected component containing as many c_id
def get_subgraph(graph, node_list):
subgraph_nodes = set()
for node in node_list:
for cc in nx.connected_components(graph):
if node in cc:
subgraph_nodes.update(cc)
break
return graph.subgraph(subgraph_nodes).copy()
def find_pcst_tree(graph, node_list):
# Approximate the Steiner tree
steiner_tree_approx = steiner_tree(graph, node_list)
return steiner_tree_approx
# Load the graph from TSV file
graph_file_path ='~/graph_edge.tsv' # graph file path
graph = load_graph(graph_file_path)
# List of nodes
node_list = ['ID_TYPE1:XXXXXXX', 'ID_TYPE2:XXXXXXX', 'ID_TYPE3:XXXXXXX', 'ID_TYPE4:XXXXXXX', 'ID_TYPE5:XXXXXXX',
'ID_TYPE6:XXXXXXX', 'ID_TYPE7:XXXXXXX', 'ID_TYPE8:XXXXXXX', 'ID_TYPE9:XXXXXXX', 'ID_TYPE10:XXXXXXX',
'ID_TYPE11:XXXXXXX', 'ID_TYPE12:XXXXXXX', 'ID_TYPE13:XXXXXXX', 'ID_TYPE14:XXXXXXX', 'ID_TYPE15:XXXXXXX',
'ID_TYPE16:XXXXXXX', 'ID_TYPE17:XXXXXXX', 'ID_TYPE18:XXXXXXX', 'ID_TYPE19:XXXXXXX', 'ID_TYPE20:XXXXXXX',
'ID_TYPE21:XXXXXXX'] # list of nodes that needs to be covered
subgraph = get_subgraph(graph, node_list)
# Check which terminal nodes are in the subgraph
terminals_in_subgraph = [node for node in node_list if node in subgraph]
# Find the Steiner tree using the approximation algorithm
steiner_tree = find_pcst_tree(subgraph, terminals_in_subgraph)
# Visualize the graph and the tree
plt.figure(figsize=(30, 30))
# Plot the entire graph
pos = nx.spring_layout(graph) # Compute layout
nx.draw(graph, pos, with_labels=False, node_size=10,
node_color='lightgray', edge_color='gray', alpha=0.5)
# Plot the Prize-Collecting Steiner Tree
nx.draw_networkx_edges(pcst_tree, pos, edge_color='blue', width=2)
nx.draw_networkx_nodes(pcst_tree, pos, nodelist=terminals_in_subgraph,
node_color='red', node_size=100)
plt.title("PCST")
plt.show()
Подробнее здесь: https://stackoverflow.com/questions/785 ... arge-graph
