scientific-programming-exercises/exam/ex01/dijkstra.py

from collections import deque

from cfg import config
from db_util import get_page_id

def prepare_dijkstra(connection):
	cursor = connection.cursor()
	if(config["use_sqlite"]):
		cursor.execute('''INSERT OR IGNORE INTO dijkstra_helper(page) 
				SELECT rowid FROM pages
				''')
	else:
		cursor.execute('''INSERT IGNORE INTO dijkstra_helper(page) 
				SELECT page_id FROM pages
				''')

		
	if(config["use_sqlite"]):
		cursor.execute("UPDATE dijkstra_helper SET value=1e1000")
	else:
		cursor.execute("UPDATE dijkstra_helper SET value=2147483647")
	connection.commit()

def dijkstra_one(page, value, connection):
	cursor = connection.cursor()
	if(isinstance(page, tuple)):
		# Idk why this happens.
		title = title[0]
	cursor.execute('''SELECT page 
			FROM dijkstra_helper 
			LEFT JOIN links ON links.destination=dijkstra_helper.page
			WHERE links.source=%s 
				AND dijkstra_helper.value>%s''', (page, value + 1))
	# This is the list of nodes that have to be updated
	result = cursor.fetchall()

	cursor.execute('''UPDATE dijkstra_helper 
			SET value=%s
			WHERE page IN (
				SELECT destination
				FROM links 
				WHERE source=%s)
			AND dijkstra_helper.value>%s''', (value + 1, page, value + 1))
	connection.commit()
	return result

def recursive_dijkstra(titles, value, connection):
	if(not titles):
		return

	todos = deque()
	for title in titles:
		todos.extend(dijkstra_one(title, value, connection))

	recursive_dijkstra(todos, value + 1, connection)


def dijkstra(title, connection):
	page = get_page_id(title, connection)
	cursor = connection.cursor()
	cursor.execute("UPDATE dijkstra_helper SET value=0 WHERE page=%s", (page,))

	todos = dijkstra_one(page, 1, connection)
	recursive_dijkstra(todos, 2, connection)