<commit_before>class Node(object):

    def __init__(self, data):
        self._data = data


class Graph(object):

    def __init__(self, *data):
        self._edges = {}
        self._nodes = []
        for node in data:
            self._nodes.append(Node(node))

    def add_node(self, data):
        a = Node(data)
        self._nodes.append(a)
        return a

    def has_edge(self, n1, n2):
        return ((n1, n2) in self._edges) or ((n2, n1) in self._edges)

    def add_edge(self, n1, n2, w=1):
        if not self.has_edge(n1, n2):
            if n1 not in self._nodes:
                self._nodes.append(n1)
            if n2 not in self._nodes:
                self._nodes.append(n2)
            self._edges[(n1, n2)] = w

    def delete_edge(self, n1, n2):
        try:
            self._edges.pop((n1, n2))
        except(KeyError):
            try:
                self._edges.pop((n2, n1))
            except(KeyError):
                raise KeyError

    def delete_node(self, n):
        if n not in self._nodes:
            raise IndexError
        for key1, key2 in self._edges.copy():
            if (key1 == n) or (key2 == n):
                self.delete_edge(key1, key2)
        self._nodes.remove(n)

    def has_node(self, n):
        return n in self._nodes

    def has_neighbors(self, n):
        neighbors = []
        if n not in self._nodes:
            raise IndexError
        for i in self._nodes:
            if self.has_edge(n, i):
                neighbors.append(i)
        return neighbors

    def adjacent(self, n1, n2):
        if not self.has_node(n1) or not self.has_node(n2):
            raise IndexError
        return self.has_edge(n1, n2)


if __name__ == '__main__':
    g = Graph()
    a = g.add_node("a")
    b = g.add_node("b")
    g.add_edge(a, b)
    for node in g._nodes:
        print node._data
    g.delete_node(b)<commit_msg>reduce delete_node from O(n square) to O(n)<commit_after>class Node(object):

    def __init__(self, data):
        self._data = data


class Graph(object):

    def __init__(self, *data):
        self._edges = {}
        self._nodes = []
        for node in data:
            self._nodes.append(Node(node))

    def add_node(self, data):
        a = Node(data)
        self._nodes.append(a)
        return a

    def has_edge(self, n1, n2):
        return ((n1, n2) in self._edges) or ((n2, n1) in self._edges)

    def add_edge(self, n1, n2, w=1):
        if not self.has_edge(n1, n2):
            if n1 not in self._nodes:
                self._nodes.append(n1)
            if n2 not in self._nodes:
                self._nodes.append(n2)
            self._edges[(n1, n2)] = w

    def delete_edge(self, n1, n2):
        try:
            self._edges.pop((n1, n2))
        except(KeyError):
            try:
                self._edges.pop((n2, n1))
            except(KeyError):
                raise KeyError

    def delete_node(self, n):
        if n not in self._nodes:
            raise IndexError
        for i in self._nodes:
            if self.has_edge(n, i):
                self.delete_edge(n, i)
        self._nodes.remove(n)

    def has_node(self, n):
        return n in self._nodes

    def has_neighbors(self, n):
        neighbors = []
        if n not in self._nodes:
            raise IndexError
        for i in self._nodes:
            if self.has_edge(n, i):
                neighbors.append(i)
        return neighbors

    def adjacent(self, n1, n2):
        if not self.has_node(n1) or not self.has_node(n2):
            raise IndexError
        return self.has_edge(n1, n2)


if __name__ == '__main__':
    g = Graph()
    a = g.add_node("a")
    b = g.add_node("b")
    g.add_edge(a, b)
    for node in g._nodes:
        print node._data
    g.delete_node(b)
{'fraction_non_alphanumeric': 0.11543553084458565, 'fraction_numerical': 0.016944665078104316, 'mean_word_length': 1.647512263489839, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2302912', 'n_tokens_mistral': 1288, 'n_tokens_neox': 1255, 'n_words': 329}