tekitou shortest paths

tekitou_shortest_paths.py

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

import time
import numpy as np
import networkx as nx
from itertools import product
from collections import defaultdict
from generator.sample_graph import grid_graph_noisy

def build_stpath_functions(G):
    distG = dict(nx.all_pairs_dijkstra_path_length(G, weight='weight'))
    pathG = dict(nx.all_pairs_dijkstra_path(G, weight='weight'))
    ddistG = {(u, v): round(distG[u][v], 4) for u in distG for v in distG[u]}
    ppathG = {(u, v): pathG[u][v] for u in pathG for v in pathG[u]}
    return ddistG, ppathG

def build_stpath_naive(G):
    distG = {}
    pathG = {}
    for (v, u) in product(G.nodes(), G.nodes()):
        if v > u:
            continue
        path = nx.shortest_path(G, v, u, weight='weight')
        lpath = nx.shortest_path_length(G, v, u, weight='weight')
        distG[(u, v)] = distG[(v, u)] = round(lpath, 4)
        pathG[(u, v)] = path[::-1]
        pathG[(v, u)] = path
    return distG, pathG


def build_stpath_memo(G):
    distG = {(u, u): 0 for u in G.nodes()}
    pathG = {(u, u): [] for u in G.nodes()}
    constructed = set({})
    for (v, u) in product(G.nodes(), G.nodes()):
        if v > u or (v, u) in constructed or (u, v) in constructed:
            continue
        path = nx.shortest_path(G, v, u, weight='weight')
        lpath = nx.shortest_path_length(G, v, u, weight='weight')
        pathG[(u, v)] = path[::-1]
        pathG[(v, u)] = path
        distG[(u, v)] = distG[(v, u)] = round(lpath, 4)
        constructed.add((v, u))
        constructed.add((u, v))

        lpath1 = lpath
        for idx in range(1, len(path)):
            pathI = path[idx:]
            vi = path[idx]
            lpath1 -= G[path[idx - 1]][path[idx]]['weight']
            if (vi, u) not in constructed or (u, vi) not in constructed:
                pathG[(vi, u)] = pathI
                pathG[(u, vi)] = pathI[::-1]
                distG[(vi, u)] = distG[(u, vi)] = round(lpath1, 4)
                constructed.add((vi, u))
                constructed.add((u, vi))

        lpath2 = lpath
        for idx in range(len(path) - 2, 1, -1):
            ui = path[idx]
            lpath2 -= G[path[idx]][path[idx + 1]]['weight']
            if (v, ui) not in constructed or (ui, v) not in constructed:
                pathI = path[:idx + 1]
                pathG[(v, ui)] = pathI
                pathG[(ui, v)] = pathI[::-1]
                distG[(v, ui)] = distG[(ui, v)] = round(lpath2, 4)
                constructed.add((v, ui))
                constructed.add((ui, v))
    return distG, pathG

if __name__ == '__main__':
    mag = 0.3
    for m in [5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]:
        n = m
        G, pos, labels = grid_graph_noisy(m=m, n=n, mag=mag)

        ts = time.time()
        dG0, pG0 = build_stpath_functions(G)
        tfunc = time.time() - ts
        
        ts = time.time()
        dG1, pG1 = build_stpath_naive(G)
        tnaive = time.time() - ts
        
        ts = time.time()
        dG2, pG2 = build_stpath_memo(G)
        tmemo = time.time() - ts
        print("{:2.4f} {:2.4f} {:2.4f}".format(tfunc, tnaive, tmemo))