CODEWITHSUNDEEP
pythongraphdijkstraweighted-graph
Ford1892
Ford1892

Reputation: 771

Find vertices along maximum cost path in directed graph

I have a weighted directed graph like this:

enter image description here

I want to find the list of vertices along the maximum cost path from start to finish.

In this example I should get: 

'enableBrowserExtension' -> 'newWindow' -> 'newTab' -> 'startPage' -> 'typed' -> 'selectTab' -> 'clickTextField' -> 'changeField-frullatore' -> 'clickButton-VAI' -> 'submit' -> 'formSubmit' -> 'mouseClick' -> 'link'

I'm trying with this code found here:

import networkx as nx

def inverse_weight(graph, weight='weight'):
    copy_graph = graph.copy()
    for n, eds in copy_graph.adjacency():
        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('enableBrowserExtension', 'enableBrowserExtension', weight=3)
    DG.add_edge('enableBrowserExtension', 'newWindow', weight=1)
    DG.add_edge('newWindow', 'newTab', weight=1)
    DG.add_edge('newTab', 'startPage', weight=1)
    DG.add_edge('startPage', 'typed', weight=1)
    DG.add_edge('typed', 'selectTab', weight=2)
    DG.add_edge('selectTab', 'newTab', weight=1)
    DG.add_edge('newTab', 'typed', weight=1)
    DG.add_edge('typed', 'typed', weight=1)
    DG.add_edge('selectTab', 'clickTextField', weight=2)
    DG.add_edge('clickTextField', 'changeField', weight=1)
    DG.add_edge('changeField', 'clickButton', weight=1)
    DG.add_edge('clickButton', 'submit', weight=1)
    DG.add_edge('submit', 'formSubmit', weight=1)
    DG.add_edge('formSubmit', 'mouseClick', weight=1)
    DG.add_edge('mouseClick', 'link', weight=2)
    DG.add_edge('link', 'formSubmit', weight=1)
    DG.add_edge('formSubmit', 'selectTab', weight=1)
    DG.add_edge('selectTab', 'mouseClick', weight=1)
    DG.add_edge('mouseClick', 'clickLink', weight=1)
    DG.add_edge('clickLink', 'link', weight=1)
    DG.add_edge('link', 'mouseClick', weight=2)
    DG.add_edge('mouseClick', 'changeField', weight=1)
    DG.add_edge('changeField', 'mouseClick', weight=1)
    DG.add_edge('mouseClick', 'selectTab', weight=1)

    path, length = longest_path_and_length(DG, 'enableBrowserExtension', 'link')

But I get the error:

ValueError: ('Contradictory paths found:', 'negative weights?')

I also tried this java code but it only returns the total maximum cost as integer, I want the name of the vertices along the path.

Is there a way to fix this?

Upvotes: 0

Views: 186

Answers (1)

Prune
Prune

Reputation: 77900

Since you have positive-value loops in the graph, the maximum-cost path is infinite. You need to remove the trivial loops and finesse the others. Perhaps you have an unimplemented requirement that no node is visited more than once?

The various ways of infinite looping are why you get the "contradictory paths".

Upvotes: 1

Related Questions