kh_si0567 - 4 months ago 47

Python Question

Using NetworkX

I want to get lowest common ancestor from node1 and node11 in DiGraph.

The following is the code.

`import networkx as nx`

G = nx.DiGraph() #Directed graph

G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])

G.add_edges_from([(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)])

ancestors1 = nx.ancestors(G, 1)

ancestors2 = nx.ancestors(G, 11)

src_set = set(ancestors1)

tag_set = set(ancestors2)

matched_list = list(src_set & tag_set)

dic = {}

for elem in matched_list:

print elem

length1 = nx.dijkstra_path_length(G, elem, 1)

path1 = nx.dijkstra_path(G, elem, 1)

dist1 = len(path1)

length2 = nx.dijkstra_path_length(G, elem, 11)

path2 = nx.dijkstra_path(G, elem, 11)

dist2 = len(path2)

dist_sum = dist1 + dist2

dic[elem] = dist_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

I have a problem with a execution speed, so I want faster execution speed.

If you have any good idea or algorithm, please tell me the idea.

Sorry for the poor English.

Answer

Rerunning Dijkstra in a loop indeed seems like an overkill.

Say we build the digraph obtained by *reversing* the edges:

```
import networkx as nx
G = nx.DiGraph() #Directed graph
G.add_nodes_from([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15])
edges = [(2,1),(3,1),(4,1),(5,2),(6,2),(7,3),(8,3),(9,3),(10,4),(10,12),(14,9),(15,8),(12,11),(13,11),(14,12),(15,13)]
G.add_edges_from(edges)
```

Now we run BFS from each of the two nodes:

```
preds_1 = nx.bfs_predecessors(G, 1)
preds_2 = nx.bfs_predecessors(G, 11)
```

Finding the common vertices reachable from both nodes in the reversed graph is easy:

```
common_preds = set([n for n in preds_1]).intersection(set([n for n in preds_2]))
```

Now you can query the above easily. For example, to find the common vertex reachable from both, closest to 1, is:

```
>>> min(common_preds, key=lambda n: preds_1[n])
10
```