"""A naive pure python implementation of a Graph class

    Based on ADJACENCY LIST

    This implementation represents a graph where nodes are stored as keys in a
    dictionary (`adjacency_list`), and the values are lists containing the neighbors
    of each node. This approach is efficient for sparse graphs and provides quick
    access to neighbors, which is a common operation in graph algorithms.

    Note that this is a basic implementation. Depending on your needs, you might
    want to add error handling (e.g., when adding edges between non-existent nodes)
    or additional features like methods for removing nodes or edges, checking if a
    path exists between two nodes, etc.

    This implementation is for an UNDIRECTED GRAPH; it can be modified
    for directed graphs by adjusting how edges are added.


    E. Viennet @ USTH, March 2024
    """


    class Graph_AdjList:
        def __init__(self):
            self.adjacency_lists = {}  # { node : list of neghbors }

        def add_node(self, node):
            if node not in self.adjacency_lists:
                self.adjacency_lists[node] = []

        def add_edge(self, node1, node2):
            if node1 in self.adjacency_lists and node2 in self.adjacency_lists:
                if node2 not in self.adjacency_lists[node1]:  # avoid duplicate links
                    self.adjacency_lists[node1].append(node2)
                    # undirected graph, add reciprocal edge:
                    self.adjacency_lists[node2].append(node1)
            else:
                raise ValueError("add_edge: unknown node")

        def get_nodes(self):
            return list(self.adjacency_lists.keys())

        def get_edges(self):
            edges = []
            for node, neighbors in self.adjacency_lists.items():
                for neighbor in neighbors:
                    if (
                        neighbor,
                        node,
                    ) not in edges:  # Needed to avoid duplicates in undirected graph
                        edges.append((node, neighbor))
            return edges

        def get_neighbors(self, node):
            return self.adjacency_lists[node] if node in self.adjacency_lists else None

        def __str__(self):
            return str(self.adjacency_lists)