<jupyter_start><jupyter_text>Graphs and NetworksLesson IV - Advanced Graph Algorithms        <NAME>        www.data4sci.com            @bgoncalves, @data4sci<jupyter_code>from collections import Counter
from pprint import pprint
import heapq

import numpy as np
import matplotlib.pyplot as plt 

import watermark

%load_ext watermark
%matplotlib inline<jupyter_output><empty_output><jupyter_text>Watermark the notebook with current versions of all loaded libraries<jupyter_code>%watermark -n -v -m -g -iv<jupyter_output>watermark 2.0.2
numpy     1.18.1
autopep8  1.5
json      2.0.9
Mon May 18 2020 

CPython 3.7.3
IPython 6.2.1

compiler   : Clang 4.0.1 (tags/RELEASE_401/final)
system     : Darwin
release    : 19.4.0
machine    : x86_64
processor  : i386
CPU cores  : 8
interpreter: 64bit
Git hash   : 18f00e3f592dbde2d2fd53da501ba1edda5ab934<jupyter_text>Load default figure style<jupyter_code>plt.style.use('./d4sci.mplstyle')<jupyter_output><empty_output><jupyter_text>We import the previous Graph Class definition<jupyter_code>from Graph import *<jupyter_output><empty_output><jupyter_text>And add a convenience method to easily add weighted edges<jupyter_code>@add_method(Graph)
def add_weighted_edges_from(self, edges):
    # Each edge can have simply a weight of a feature dictionary 
    for edge in edges:
        if isinstance(edge[2], dict):
            self.add_edge(edge[0], edge[1], **edge[2])
        else:
            self.add_edge(edge[0], edge[1], weight=edge[2])<jupyter_output><empty_output><jupyter_text>We manually define our undirected graph<jupyter_code>G = Graph(directed=False)
G.add_weighted_edges_from(
[
    [0, 1, {"weight":5}],
    [0, 2, 10],
    [0, 4, 2],
    [1, 2, 2],
    [1, 3, 4],
    [2, 3, 7],
    [2, 5, 10],
    [3, 4, 3]
])<jupyter_output><empty_output><jupyter_text>Since the graph is undirected, we have double the edges:<jupyter_code>G.edges()<jupyter_output><empty_output><jupyter_text>Priority Queue Our implementation of Dijkstra's algorithm relies on a priority queue. We can easily build one by wrapping around the functionality of the **heapq** standard library module as a priority queue is just a min-heap<jupyter_code>class PriorityQueue:
    def __init__(self):
        self.heap = []

    def push(self, node, priority):
        heapq.heappush(self.heap, [priority, node])

    def pop(self, data=True):
        if data:
            return heapq.heappop(self.heap)
        else:
            return heapq.heappop(self.heap)[1]

    def update(self, node, new_priority):
        pos = -1 

        for i, value in enumerate(self.heap):
            priority, node_i = value

            if node_i == node:
                self.heap[i][0] = new_priority
                pos = i
                break

        if pos == -1:
            self.heap.append([new_priority, node])

        heapq.heapify(self.heap)

    def empty(self):
        return len(self.heap) == 0<jupyter_output><empty_output><jupyter_text>We test our implementation<jupyter_code>queue = PriorityQueue()
queue.push("a", 10)
queue.push("b", 7)
queue.push("c", 6)
queue.push("d", 3)<jupyter_output><empty_output><jupyter_text>The contens of the heap are then<jupyter_code>queue.heap<jupyter_output><empty_output><jupyter_text>And if we update the priority of one of the elements<jupyter_code>queue.update("c", 1)<jupyter_output><empty_output><jupyter_text>It becomes<jupyter_code>queue.heap<jupyter_output><empty_output><jupyter_text>Finally, we note that we recover a sorted list of items by simply popping them all out of the queue. This is known as Heapsort https://en.wikipedia.org/wiki/Heapsort<jupyter_code>print(queue.pop(True))
print(queue.pop(True))
print(queue.pop(True))
print(queue.pop(True))<jupyter_output>[1, 'c']
[3, 'd']
[7, 'b']
[10, 'a']<jupyter_text>Dijkstra's algorithm<jupyter_code>def dijkstra(G, source):
    N = G.number_of_nodes()
    queue = PriorityQueue()

    dist = {}

    for node in G._nodes.keys():
        dist[node] = [np.inf, []]
    
    dist[source][0] = 0
    dist[source][1].append(source)

    queue.push(source, 0)

    while not queue.empty():
        node_i = queue.pop(False)

        NN = G.neighbours(node_i)

        for node_j in NN:
            weight = G._edges[node_i][node_j]["weight"]
            new_dist = dist[node_i][0] + weight

            if new_dist < dist[node_j][0]:
                dist[node_j][0] = new_dist
                dist[node_j][1] = list(dist[node_i][1])
                dist[node_j][1].append(node_j)

                queue.update(node_j, new_dist)

    return dist
G.edges()
dist = dijkstra(G, 0)
pprint(dist)<jupyter_output>{0: [0, [0]],
 1: [5, [0, 1]],
 2: [7, [0, 1, 2]],
 3: [5, [0, 4, 3]],
 4: [2, [0, 4]],
 5: [17, [0, 1, 2, 5]]}<jupyter_text>Path representation<jupyter_code>N = G.number_of_nodes()
target = -1*np.ones((N, N), dtype='int')

for node in dist:
    path = dist[node][1]
    target[node, node] = node
    
    for i in range(len(path)-1):
        target[path[i], path[-1]] = path[i+1] 
target<jupyter_output><empty_output><jupyter_text>All shortest paths<jupyter_code>for i in range(1, 6):
    dist = dijkstra(G, i)
    
    for node in dist:
        path = dist[node][1]

        for i in range(len(path)-1):
            target[path[i], path[-1]] = path[i+1]
target<jupyter_output><empty_output><jupyter_text>Floyd-Warshall Algorithm<jupyter_code>def FloydWarshall(G):
    N = G.number_of_nodes()
    dist = np.ones((N, N), dtype='float')*np.inf
    target = -np.ones((N, N), dtype='int')

    for node_i, node_j, w in G.edges():
        weight = w["weight"]
        dist[node_i, node_j] = weight
        target[node_i, node_j] = node_j

    for node_i in G.nodes():
        dist[node_i, node_i] = 0
        target[node_i, node_i] = node_i

    for node_k in range(N):
        for node_i in range(N):
            for node_j in range(N):
                if dist[node_i, node_j] > dist[node_i, node_k] + dist[node_k, node_j]:
                    dist[node_i, node_j] = dist[node_i, node_k] + dist[node_k, node_j]
                    target[node_i, node_j] = target[node_i, node_k]

    return dist, target
G2 = Graph(directed=True)
G2.add_weighted_edges_from(
[
    [1, 0, 4],
    [0, 2, -2],
    [1, 2, 3],
    [2, 3, 2],
    [3, 1, -1],
])
dist, target = FloydWarshall(G2)
pprint(dist)
pprint(target)
def path(target, node_i, node_j):
    if target[node_i, node_j] == -1:
        return []

    path = [node_i]

    while node_i != node_j:
        node_i = target[node_i, node_j]
        path.append(node_i)

    return path
print(path(target, 2, 1))
print(path(target, 2, 0))<jupyter_output>[2, 3, 1]
[2, 3, 1, 0]
{'fraction_non_alphanumeric': 0.13558300692979813, 'fraction_numerical': 0.029828261524555588, 'mean_word_length': 3.2557692307692307, 'pattern_counts': {'":': 1, '<': 67, '<?xml version=': 0, '>': 67, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '17', 'dir': 'jupyter-structured-clean-dedup', 'id': '307826', 'license': 'MIT', 'n_tokens_mistral': 2626, 'n_tokens_neox': 2459, 'n_words': 574, 'path': '4. Advanced Graph Algorithms.ipynb', 'repo_name': 'wy36/Networks', 'size': '6647'}