multidag_longest_path.py

multidag_longest_path.py

# -*- coding: utf-8 -*-

import networkx as nx
import networkx.algorithms as nxa

def longest_path_for_multidigraph(G, weight='weight', default_weight=1):
    dist = {}
    for v in nx.topological_sort(G):
        us = []
        for u, data in G.pred[v].items():
            if 'pos' in data:
                us.append((dist[u][0] + data["pos"].get(weight, default_weight), u))
            elif 'neg' in data:
                us.append((dist[u][0] + data["neg"].get(weight, default_weight), u))
            else:
                raise AssertionError("Unexpected edge grouping key; should be pos/neg")
        # us = [(dist[u][0] + data.get(weight, default_weight), u)
        #       for u, data in G.pred[v].items()]
        # Use the best predecessor if there is one and its distance is
        # non-negative, otherwise terminate.
        # print(v, us)
        maxu = max(us, key=lambda x: x[0]) if us else (0, v)
        dist[v] = maxu if maxu[0] >= 0 else (0, v)
    u = None
    v = max(dist, key=lambda x: dist[x][0])
    path = []
    while u != v:
        path.append(v)
        u = v
        v = dist[v][1]
    path.reverse()
    return path

def get_example():
    G = nx.MultiDiGraph()
    V = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
    E = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5),
         (3, 6), (3, 7), (4, 8), (5, 7), (5, 8),
         (6, 9), (6, 10), (7, 10), (8, 10), (8, 10),
         (9, 11), (9, 11), (10, 11)]
    Ew = [0, 20, 0, 40, 0, 0, 50, 0, 50, 0,
          0, 10, 0, 0, 10, 0, 30, 0]
    G.add_nodes_from(V)
    for i in range(len(E)):
        u, v = E[i]
        key = "pos" if Ew[i] > 0 else "neg"
        wuv = Ew[i]
        G.add_edge(u, v, key=key, weight=wuv)

    # v = 7
    # for u, data in G.pred[v].items():
    #     print(u, data, data.get('weight', 0))

    return G

def main():
    G = get_example()
    # gp = nxa.dag.dag_longest_path(G, weight='weight')
    gp = longest_path_for_multidigraph(G, weight='weight')
    print(gp)

if __name__ == '__main__':
    main()