#!/usr/bin/env python3

"""
One of the many ways to represent a graph in Python.
"""

import collections

Vertex = collections.namedtuple("Vertex", ("id", "data"))
Edge = collections.namedtuple("Edge", ("first", "second"))


class Graph(object):
    """
    This graph class uses two sets to store the vertices and edges.

    However, it would also be possible to use an adjacency matrix or adjacency
    list. Depending on the purpose of the graph and the algorithms using the
    graph, these alternative implementations might highly benefit the runtime.
    """
    def __init__(self, vertici, edges):
        self.__vertici = set(vertici)
        self.__edges = set(edges)

    def add_vertex(self, v):
        self.__vertici.add(v)

    def add_edge(self, e):
        self.__vertici.add(e.first)
        self.__vertici.add(e.second)
        self.__edges.add(e)

    def remove_vertex(self, v):
        try:
            self.__vertici.remove(v)
        except KeyError:
            pass
        to_remove = {e for e in self.__edges if v == e.first or v == e.second}
        self.__edges -= to_remove

    def is_adjacent(self, v1, v2):
        # this would be much faster with an adjacency matrix
        for e in self.__edges:
            if e.first == v1 and e.second == v2:
                return True
            if e.first == v2 and e.second == v1:
                return True
        return False

    # many more useful methods...

v1 = Vertex('1', '')
v2 = Vertex('2', '')
v3 = Vertex('3', '')
v4 = Vertex('4', '')
v5 = Vertex('5', '')
g = Graph(tuple(), (Edge(v1, v2), Edge(v1, v3), Edge(v2, v3), Edge(v3, v3),
                    Edge(v3, v4), Edge(v4, v5), Edge(v5, v1)))
print("1->2", g.is_adjacent(v1, v2))
print("1->5", g.is_adjacent(v1, v5))
print("1->4", g.is_adjacent(v1, v4))