thanasismattas / shortestpaths Goto Github PK

import shortestpaths as sp

def create_pos_weighted_graph():
    '''this is the graph from Eppstein's paper Figure 1 (a)'''
    graph = nx.DiGraph()  # Directed Graph
    for i in range(3):
        for j in range(4):
            graph.add_node((i, j), index=(i, j), name=(i, j))
    edges = []

    edges.append(((0, 0), (0, 1), 2))
    edges.append(((0, 0), (1, 0), 13))

    edges.append(((0, 1), (0, 2), 20))
    edges.append(((0, 1), (1, 1), 27))

    edges.append(((0, 2), (0, 3), 14))
    edges.append(((0, 2), (1, 2), 14))

    edges.append(((0, 3), (1, 3), 15))

    edges.append(((1, 0), (1, 1), 9))
    edges.append(((1, 0), (2, 0), 15))

    edges.append(((1, 1), (1, 2), 10))
    edges.append(((1, 1), (2, 1), 20))

    edges.append(((1, 2), (1, 3), 25))
    edges.append(((1, 2), (2, 2), 12))

    edges.append(((1, 3), (2, 3), 7))
    edges.append(((2, 0), (2, 1), 18))
    edges.append(((2, 1), (2, 2), 8))
    edges.append(((2, 2), (2, 3), 11))

    # edges.append(((2,3), (0,0),50)) # this egde makes a cycle

    graph.add_weighted_edges_from(edges)
    return graph, (0, 0), (2, 3)

G, s, t = create_pos_weighted_graph()
k_paths = sp.k_shortest_paths(G, s, t, 5)
print("k_paths:")
sp.print_paths(k_paths)
sp.plot_paths(k_paths, G)

G, s, t = create_pos_weighted_graph()
k_paths = sp.k_shortest_paths(G, s, t, 20)
print("k_paths:")
sp.print_paths(k_paths)

path 1: [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 3)]   cost: 55
path 2: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3)]   cost: 58
path 3: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3)]   cost: 59
path 4: [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3)]   cost: 61
path 5: [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3)]   cost: 62
path 6: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3)]   cost: 65
path 7: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3)]   cost: 68

found path #1 of length 55: [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2), (2, 3)]
found path #2 of length 58: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3)]
found path #3 of length 59: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3)]
found path #4 of length 61: [(0, 0), (1, 0), (1, 1), (2, 1), (2, 2), (2, 3)]
found path #5 of length 62: [(0, 0), (0, 1), (1, 1), (1, 2), (2, 2), (2, 3)]
found path #6 of length 64: [(0, 0), (1, 0), (1, 1), (1, 2), (1, 3), (2, 3)]
found path #7 of length 65: [(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3)]
found path #8 of length 68: [(0, 0), (0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
found path #9 of length 68: [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3)]
found path #10 of length 71: [(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3)]