I have a Node
class as below
class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] def __eq__(self, other) -> bool: if isinstance(other, self.__class__): return all([other.val == self.val, self.neighbors == other.neighbors]) return False def __repr__(self): return f"Node(val: {self.val}, neighbors: {self.neighbors})" def __str__(self): return self.__repr__()
I am trying to construct a Graph using an adjacency list as below:
[ [2,4], [1,3], [2,4], [1,3] ]
In the above adjacency list that is indexed from 1
, the index is the Node
value i.e. Node.val
and the list at that index are the neighbors i.e. Node.neighbors
For e.g., for index 1:
Node.val = 1 Node.neighbors = [Node(2), Node(4)]
For index 2:
Node.val = 2 Node.neighbors = [Node(1), Node(3)]
and so on …
How can I construct the Graph using python, where I want to consider the Node
represented by index=1 in the adjacency list to be it’s entry point i.e. the root.
Basically a function that returns the root of the Graph:
def make_graph(adj_list: List) -> Node: ...
I have tried iterative approach, resulting in infinite loops or wrong output.
One of my attempts that resulted in wrong output:
def make_graph(adj_list: List) -> Node: if not adj_list: return [] root = Node(1) node_dict = {} for i in adj_list[0]: neighbor = Node(i) root.neighbors.append(neighbor) node_dict[i] = neighbor node_dict[1] = root for i in range(1, len(adj_list)): node = Node(i) if i not in node_dict else node_dict[i] for neighbor in adj_list[i]: if neighbor not in node_dict: neighbor_node = Node(neighbor) node_dict[neighbor] = neighbor_node else: neighbor_node = node_dict[neighbor] node.neighbors.append(neighbor_node) if i not in node_dict: node_dict[i] = node return root
Which gives the output:
Node( val: 1, neighbors: [ Node( val: 2, neighbors: [ Node( val: 2, neighbors: [...] ), Node( val: 4, neighbors: [] ) ] ), Node( val: 4, neighbors: [] ), Node( val: 1, neighbors: [...] ), Node( val: 3, neighbors: [ Node( val: 1, neighbors: [...] ), Node(val: 3, neighbors: [...] ) ] ) ] )
Any kind of help or pointing in the right direction is immensely appreciated.
Advertisement
Answer
It will be easier if you first create all the node instances, and then populate the neighbors, by mapping those neighbor numbers to the nodes you will then have at your disposal.
Here is a function you could use:
def make_graph(adj_list: List) -> Node: nodes = [Node(i + 1) for i in range(len(adj_list))] for i, neighbors in enumerate(adj_list): nodes[i].neighbors = [nodes[j-1] for j in neighbors] return nodes[0]
Code to test this with the example input:
from typing import List class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] def __repr__(self): return f"Node(val: {self.val}, neighbors: {self.neighbors})" def make_graph(adj_list: List) -> Node: nodes = [Node(i + 1) for i in range(len(adj_list))] for i, neighbors in enumerate(adj_list): nodes[i].neighbors = [nodes[j-1] for j in neighbors] return nodes[0] adj_list = [[2,4],[1,3],[2,4],[1,3]] node = make_graph(adj_list) print(node)