How to find the longest path with Python NetworkX?

问题:

I have a directed graph from S to T.

And I would like to find the route (S, A, C, E, T) and the sum of its capacities (1 + 2 + 3 + 1 = 7) so the sum is the largest.

I tried networkx.algorithms.flow.ford_fulkerson, but I don't know how to get the one-way direction from S to T.

My environment:

• Ubuntu 12.04
• Python 2.7.8
• NetworkX 1.9
• Matplotlib 1.4.0

example.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import matplotlib.pylab as p
import networkx as nx

if __name__ == '__main__':
    DG = nx.DiGraph()
    DG.add_edge('S', 'a', capacity=1)
    DG.add_edge('a', 'b', capacity=1)
    DG.add_edge('a', 'c', capacity=2)
    DG.add_edge('b', 'd', capacity=1)
    DG.add_edge('b', 'e', capacity=2)
    DG.add_edge('c', 'e', capacity=3)
    DG.add_edge('c', 'f', capacity=2)
    DG.add_edge('d', 'T', capacity=1)
    DG.add_edge('e', 'T', capacity=1)
    DG.add_edge('f', 'T', capacity=1)

    result = nx.algorithms.flow.ford_fulkerson(DG, 'S', 'T')
    print(result.size(weight='capacity')) # 15.0, but I want 7.

    pos = nx.spectral_layout(DG)
    nx.draw(DG, pos)
    nx.draw_networkx_labels(DG, pos)
    nx.draw_networkx_edge_labels(DG, pos)
    p.show()

    # This shows a partly bidirectional graph, which is not what I want.
    pos = nx.spectral_layout(result)
    nx.draw(result, pos)
    nx.draw_networkx_labels(result, pos)
    nx.draw_networkx_edge_labels(result, pos)
    p.show()

回答1:

Using negative weight often doesn't work for Dijkstra algorithm. This error ValueError: ('Contradictory paths found:', 'negative weights?') will show up.

It should distinguish the problem of "Longest Path" and the "Maximum Sum Path".

The answer here: How to find path with highest sum in a weighted networkx graph?, that uses all_simple_paths.

Note that in the function all_simple_paths(G, source, target, cutoff=None), using cutoff param (integer number) can help to limit the depth of search from source to target. It also controls the length of the path that we want to find.

回答2:

The negative weights works for johnson. In your case, modified as:

DG = nx.DiGraph()
DG.add_edge('S', 'a', weight=-1)
DG.add_edge('a', 'b', weight=-1)
DG.add_edge('a', 'c', weight=-2)
DG.add_edge('b', 'd', weight=-1)
DG.add_edge('b', 'e', weight=-2)
DG.add_edge('c', 'e', weight=-3)
DG.add_edge('c', 'f', weight=-2)
DG.add_edge('d', 'T', weight=-1)
DG.add_edge('e', 'T', weight=-1)
DG.add_edge('f', 'T', weight=-1)

To find longest path, get the one-way direction from S to T with

p2 = nx.johnson (DG, weight='weight')
print('johnson: {0}'.format(p2['S']['T']))

result as: johnson: ['S', 'a', 'c', 'e', 'T']

My environment:

• Software Version
• Python 3.4.5 64bit [MSC v.1600 64 bit (AMD64)]
• IPython 5.1.0 OS Windows 10 10.0.14393
• networkx 1.11

Networkx 1.11 docs for johnson

回答3:

I think I found a solution.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import networkx as nx

def inverse_weight(graph, weight='weight'):
    copy_graph = graph.copy()
    for n, eds in copy_graph.adjacency_iter():
        for ed, eattr in eds.items():
            copy_graph[n][ed][weight] = eattr[weight] * -1
    return copy_graph

def longest_path_and_length(graph, s, t, weight='weight'):
    i_w_graph = inverse_weight(graph, weight)
    path = nx.dijkstra_path(i_w_graph, s, t)
    length = nx.dijkstra_path_length(i_w_graph, s, t) * -1
    return path, length

if __name__ == '__main__':
    DG = nx.DiGraph()
    DG.add_edge('S', 'a', weight=1)
    DG.add_edge('a', 'b', weight=1)
    DG.add_edge('a', 'c', weight=2)
    DG.add_edge('b', 'd', weight=1)
    DG.add_edge('b', 'e', weight=2)
    DG.add_edge('c', 'e', weight=3)
    DG.add_edge('c', 'f', weight=2)
    DG.add_edge('d', 'T', weight=1)
    DG.add_edge('e', 'T', weight=1)
    DG.add_edge('f', 'T', weight=1)

    print(longest_path_and_length(DG, 'S', 'T')) # (['S', 'a', 'c', 'e', 'T'], 7)