NetworkXを持つすべての最低共通祖先

Question

ノード "a"とノード "o"からすべてのLCAノードを取得したいと考えています。

このDiGraphでは、ノード "l"とノード "m"はLCAノードです。

以下はコードです。

import networkx as nx 

def calc_length(Graph, node1, node2, elem): 
    length1 = nx.shortest_path_length(Graph, node1, elem) 
    length2 = nx.shortest_path_length(Graph, node1, elem) 
    length_sum = length1 + length2 
    return length_sum 

G = nx.DiGraph() #Directed graph 
G.add_nodes_from(["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"]) 
edges = [("a","b"),("b","c"),("b","d"),("a","e"),("a","h"),("e","f"),("e","g"),("e","i"),("h","l"),("h","m"),("g","j"),("o","p"),("o","n"),("n","m"),("n","l"),("n","k"),("p","j"),] 
G.add_edges_from([(e[0], e[1]) for e in edges]) 

preds_1 = nx.bfs_predecessors(G, "a") 
preds_2 = nx.bfs_predecessors(G, "o") 
common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2])) 
common_preds = list(common_preds) 
dic ={} 
for elem in common_preds: 
    length_sum = calc_length(G, "a", "o", elem) 
    dic[elem] = length_sum 

min_num = min(dic.values()) 
for k, v in sorted(dic.items(), key=lambda x:x[1]): 
    if v != min_num: 
     break 
    else: 
     print k, v 

実行速度が向上したい。

前述の問題よりも問題を解決する方法がある場合は、教えてください。

私はあなたの助けに感謝します。

Answer 1

ここにいくつかの問題がありますが、そのうちのいくつかはコメントで指摘しています。問題の一部は、命名法が混乱しているということです。最も一般的な祖先（as defined on wikipediaとおそらくはコンピュータサイエンス全体）は、networkxが使用している命名法に従うためには、知ってる）。したがって、あなたの幅優先探索は、前任者ではなく子孫に本当に従うべきです。次のようなLCA検索が実装されています：

import numpy as np 
import matplotlib.pyplot as plt; plt.ion() 
import networkx as nx 

def find_lowest_common_ancestor(graph, a, b): 
    """ 
    Find the lowest common ancestor in the directed, acyclic graph of node a and b. 
    The LCA is defined as on 

    @reference: 
    https://en.wikipedia.org/wiki/Lowest_common_ancestor 

    Notes: 
    ------ 
    This definition is the opposite of the term as it is used e.g. in biology! 

    Arguments: 
    ---------- 
     graph: networkx.DiGraph instance 
      directed, acyclic, graph 

     a, b: 
      node IDs 

    Returns: 
    -------- 
     lca: [node 1, ..., node n] 
      list of lowest common ancestor nodes (can be more than one) 
    """ 

    assert nx.is_directed_acyclic_graph(graph), "Graph has to be acyclic and directed." 

    # get ancestors of both (intersection) 
    common_ancestors = list(nx.descendants(graph, a) & nx.descendants(graph, b)) 

    # get sum of path lengths 
    sum_of_path_lengths = np.zeros((len(common_ancestors))) 
    for ii, c in enumerate(common_ancestors): 
     sum_of_path_lengths[ii] = nx.shortest_path_length(graph, a, c) \ 
            + nx.shortest_path_length(graph, b, c) 

    # print common_ancestors 
    # print sum_of_path_lengths 

    # return minima 
    minima, = np.where(sum_of_path_lengths == np.min(sum_of_path_lengths)) 

    return [common_ancestors[ii] for ii in minima] 

def test(): 

    nodes = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p"] 
    edges = [("a","b"), 
      ("b","c"), 
      ("b","d"), 
      ("a","e"), 
      ("a","h"), 
      ("e","f"), 
      ("e","g"), 
      ("e","i"), 
      ("h","l"), 
      ("h","m"), 
      ("g","j"), 
      ("o","p"), 
      ("o","n"), 
      ("n","m"), 
      ("n","l"), 
      ("n","k"), 
      ("p","j"),] 

    G = nx.DiGraph() 
    G.add_nodes_from(nodes) 
    G.add_edges_from(edges) 

    # plot 
    pos = nx.spring_layout(G) 
    nx.draw(G, pos) 
    nx.draw_networkx_labels(G, pos, labels=dict([(c, c) for c in 'abcdefghijklmnop'])) 
    plt.show() 

    a,b = 'a','o' 
    lca = find_lowest_common_ancestor(G, a, b) 
    print "Lowest common ancestor(s) for {} and {}: {}".format(a, b, lca) 

    return 

if __name__ == "__main__": 
    test()