# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3.10.0 64-bit
#     language: python
#     name: python3
# ---

import math
import random
import urllib as ul
import heapq as hq
import csv


# # Algoritmo de dijkstra a todos los puntos

def dijkstra(G, s):
  n = len(G)
  visited = [False]*n
  path = [None]*n
  cost = [math.inf]*n
  cost[s] = 0
  queue = [(0, s)]
  while queue:
    g_u, u = hq.heappop(queue)
    if not visited[u]:
      visited[u] = True
      for v, w in G[u]:
        f = g_u + w
        if f < cost[v]:
          cost[v] = f
          path[v] = u
          hq.heappush(queue, (f, v))

  return path, cost


# Generamos aleatoriamente los pesos a las aristas, debido a que es necesario para que se realice el algoritmo Dijkstra

# +
def getGraphWeighted(G):
  adjlListWeighted = [[] for i in range(len(G))]
  for i in range(len(G)):
    for j in range(len(G[i])):
      adjlListWeighted[i].append(   ( G[i][j], random.randint(0,10)  )    )
  return adjlListWeighted

def readAdjl(filename):
  with ul.request.urlopen(filename) as f:
    L = []
    for line in f:
        L.append(list(map(int, (line.decode("utf-8").strip().split(",")))))
  return L


# +
G = readAdjl("https://raw.githubusercontent.com/RodriCalle/cc41_tf_201915889_201910127_201917028_201718169_20141a449/master/TrabajoFinal/GeneratorAdjancencyList/adjancencyList.txt")

GW = getGraphWeighted(G)

path, cost = dijkstra(GW, 0)

pathFile = open('dijkstraForAll.txt', 'w', newline='')
with pathFile:
  writer = csv.writer(pathFile)
  writer.writerows(str(path))

#Solo imprimirmos los 1000 primeros nodos con su respectivo padre
for i in range(1000):
  print(f"{i}: {path[i]}")


# -

# # Algoritmo de Dijkstra de cada almacen a cada punto de entrega

# +
def getIndexFromCoords(size, arr):
  alm = []
  for a in arr:
    x, y = a[0], a[1]
    pos = x*size + y
    alm.append(pos)
  return alm

def getCoordFromIndex(index, size):
  x = index // size
  y = index % size
  return (x, y)

def dijkstraEntregas(almacenes, entregas, G):
  sol = [] 
  for i in almacenes:
    path, cost = dijkstra(G,i)
    for j in entregas:
      node = j
      p = [j]
      c = cost[j]
      while node != i:
        node = path[node]
        p.append(node)
      p.reverse()
      sol.append((i,j,c,p))
  return sol


# +
def getCoords(filename, arrx, arry):
  arrx.clear()
  arry.clear()

  with ul.request.urlopen(filename) as f:
    for line in f:
      xy = list(map(int, (line.decode("utf-8").strip().split(","))))
      arrx.append(xy[0])
      arry.append(xy[1])

urlAlmacen = "https://raw.githubusercontent.com/RodriCalle/cc41_tf_201915889_201910127_201917028_201718169_20141a449/master/Datasets/puntos_almacenes.csv"
urlEntrega = "https://raw.githubusercontent.com/RodriCalle/cc41_tf_201915889_201910127_201917028_201718169_20141a449/master/Datasets/puntos_entregas.csv"

almacenx, almaceny = [], []
getCoords(urlAlmacen, almacenx, almaceny)

entregax, entregay = [], []
getCoords(urlEntrega, entregax, entregay)

almacenes, entregas = [], []
for i in range(len(almacenx)):
  almacenes.append([almacenx[i], almaceny[i]])
for i in range(len(entregax)):
  entregas.append([entregax[i], entregay[i]])

# +
arregloAlm = getIndexFromCoords(1000,almacenes)
arregloEnt = getIndexFromCoords(1000,entregas)

djpd = dijkstraEntregas(arregloAlm, arregloEnt, GW)

djpdFile = open('dijkstraforeach.txt', 'w')
with djpdFile:
  writer = csv.writer(djpdFile)
  writer.writerows(str(djpd))

StarcoderdataJupyterScriptsDedupFiltered