Trying to create edge list (weighted) to create adjacency list

Question

I am storing the open coords as two attributes in one list:

self.x, self.y = []

My attempt at an edge list (lifted from stack overflow lol):

edge = []
        for i in self.x, self.y:
            for j in i[1]:
                edge.append([i[0], j])
                for i in edge:
                    print(i)

Whenever I try this the error:

for j in i[1]:
TypeError: 'int' object is not subscriptable

comes up.

I'm guessing this is because it's a tuple? I am trying to create an adjacency list with weighted edges of the distance between the coords, but I haven't thought about adding the weights yet.

The coords, when added to a big list, look like this:

[[[0, 0], [1, 0], [2, 0].....]]

But when I insert them into the class, I do it separately.

On another note, can I store the all coords into one attribute like this effectively? Or would the attribute overwrite each time and only do one coord??

I was expecting, or hoped, that it would create edges between nodes to then create an adjacency list (of which I have no clue how to code either). With the completed graph, I aim to create an a* algorithm..

Sorry, if this may be obvious but I haven't coded properly in a very long time. I am aware it is kinda messy.

Thank you.

Answer 1

Something like this?

import itertools
import math

class Graph:
    def __init__(self):
        self.coords = []  # ← array of coords tuples (x, y)
        self.adjacency_list = (
            {}
        )  # ^ dictionary (hash lookup structure of 'key': 'value' pairs):
        #      where each key is a tuple (x, y)
        #      and each value is a list of (neighbor, weight) tuples.

    def add_coord(self, x, y):
        self.coords.append((x, y))

    def calculate_distance(self, coord1, coord2):
        x1, y1 = coord1
        x2, y2 = coord2
        return math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

    def build_adjacency_list(self):
        for coord1 in self.coords:
            self.adjacency_list[coord1] = []
            for coord2 in self.coords:
                if coord1 != coord2:
                    distance = self.calculate_distance(coord1, coord2)
                    self.adjacency_list[coord1].append((coord2, distance))


# Demo adjacency list
g = Graph()
for (x, y) in list(itertools.product(range(3), range(3))):
    print(x, y)
    g.add_coord(x, y)
g.build_adjacency_list()

# Print out the adjacency list
for coord, neighbors in g.adjacency_list.items():
    print(f"\n{coord}: \n{neighbors}")

which prints:

(0, 0): 
[((0, 1), 1.0), ((0, 2), 2.0), ((1, 0), 1.0), ((1, 1), 1.4142135623730951), ((1, 2), 2.23606797749979), ((2, 0), 2.0), ((2, 1), 2.23606797749979), ((2, 2), 2.8284271247461903)]

(0, 1): 
[((0, 0), 1.0), ((0, 2), 1.0), ((1, 0), 1.4142135623730951), ((1, 1), 1.0), ((1, 2), 1.4142135623730951), ((2, 0), 2.23606797749979), ((2, 1), 2.0), ((2, 2), 2.23606797749979)]

(0, 2): 
[((0, 0), 2.0), ((0, 1), 1.0), ((1, 0), 2.23606797749979), ((1, 1), 1.4142135623730951), ((1, 2), 1.0), ((2, 0), 2.8284271247461903), ((2, 1), 2.23606797749979), ((2, 2), 2.0)]

(1, 0): 
[((0, 0), 1.0), ((0, 1), 1.4142135623730951), ((0, 2), 2.23606797749979), ((1, 1), 1.0), ((1, 2), 2.0), ((2, 0), 1.0), ((2, 1), 1.4142135623730951), ((2, 2), 2.23606797749979)]

(1, 1): 
[((0, 0), 1.4142135623730951), ((0, 1), 1.0), ((0, 2), 1.4142135623730951), ((1, 0), 1.0), ((1, 2), 1.0), ((2, 0), 1.4142135623730951), ((2, 1), 1.0), ((2, 2), 1.4142135623730951)]

(1, 2): 
[((0, 0), 2.23606797749979), ((0, 1), 1.4142135623730951), ((0, 2), 1.0), ((1, 0), 2.0), ((1, 1), 1.0), ((2, 0), 2.23606797749979), ((2, 1), 1.4142135623730951), ((2, 2), 1.0)]

(2, 0): 
[((0, 0), 2.0), ((0, 1), 2.23606797749979), ((0, 2), 2.8284271247461903), ((1, 0), 1.0), ((1, 1), 1.4142135623730951), ((1, 2), 2.23606797749979), ((2, 1), 1.0), ((2, 2), 2.0)]

(2, 1): 
[((0, 0), 2.23606797749979), ((0, 1), 2.0), ((0, 2), 2.23606797749979), ((1, 0), 1.4142135623730951), ((1, 1), 1.0), ((1, 2), 1.4142135623730951), ((2, 0), 1.0), ((2, 2), 1.0)]

(2, 2): 
[((0, 0), 2.8284271247461903), ((0, 1), 2.23606797749979), ((0, 2), 2.0), ((1, 0), 2.23606797749979), ((1, 1), 1.4142135623730951), ((1, 2), 1.0), ((2, 0), 2.0), ((2, 1), 1.0)]

itertools.product(range(3), range(3)) produces:

0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2

In calling the method to build the adjacency list, all coordinates-tuple combinatorial (cartesian product, specifically) pairwise (excluding self-pairs...) connections were added to the dictionary for each individual coordinates tuple. This is what is printed above as the output. Below this is visualized.

---

Visualize the adjacency list as a network graph

import networkx as nx
from pyvis.network import Network

# Create a NetworkX graph
G_nx = nx.Graph()

# Add edges to the NetworkX graph
for coord, neighbors in g.adjacency_list.items():
    for neighbor, weight in neighbors:
        G_nx.add_edge(coord, neighbor, weight=weight)

# Create a Pyvis network
net = Network(
    notebook=True,
    cdn_resources="remote",
    width="100%",
    bgcolor="white",
    font_color="red",
)
net.repulsion()

# Add nodes to the Pyvis network
for coord in g.adjacency_list.keys():
    net.add_node(str(coord), size=5) # *

# Add edges to the Pyvis network
for coord, neighbors in g.adjacency_list.items():
    for neighbor, weight in neighbors:
        net.add_edge(str(coord), str(neighbor), weight=weight)


for edge in net.edges:
    source, target = edge["from"], edge["to"]
    weight = G_nx[eval(source)][eval(target)]["weight"]
    edge["label"] = str(round(weight, 2))


net.show("example.html")

^{* Note: The size of nodes is ok to explicitly set here because all nodes have the same number of edges anyways. By default, they come out in the visualized graph a bit too big IMO.}

And also, visualizing a slightly different pyvis+networkx graph, where the calculated distances (used to represent 'weights' in the example here) have an influence (e.g., by instead setting net.barnes_hut()):