CODEWITHSUNDEEP
pythonnetworkx
ogura
ogura

Reputation: 75

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:

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()

Upvotes: 1

Views: 21248

Answers (3)

Jesse
Jesse

Reputation: 3393

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

Networkx 3.21 docs for johnson

Upvotes: 2

Minh Vu
Minh Vu

Reputation: 503

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.

Upvotes: 4

ogura
ogura

Reputation: 75

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)

Upvotes: 0

Related Questions