<commit_before>#!/usr/bin/python
#
# graphs.py
#
# Nodes can be numbers, string, or any hashable objects.
# We would like also to compare nodes.
#
# {"A":{"B":1,"C":2}, 
# "B":{"C":3,"D":4}, 
# "C":{"D":5}, 
# "D":{"C":6}, 
# "E":{"C":7}, 
# "F":{}}

from edges import Edge


class Graph(dict):
    """The class defining a graph."""

    def __init__(self, n=0, directed=False):
        """Loads up a Graph instance."""
        self.n = n              # compatibility
        self.directed = directed  # bool

    def v(self):
        """Returns the number of nodes (the graph order)."""
        return len(self)

    def e(self):
        """Returns the number of edges."""
        edges = sum(len(self[node]) for node in self)
        return (edges if self.is_directed() else edges / 2)

    def is_directed(self):
        """Test if the graph is directed."""
        return self.directed

    def add_node(self, node):
        """Add a node to the graph."""
        if node not in self:
            self[node] = dict()

    def has_node(self, node):
        """Test if a node exists."""
        return node in self

    def del_node(self, node):
        """Remove a node from the graph (with edges)."""
        # dictionary changes size during iteration.
        for edge in list(self.iterinedges(node)):
            self.del_edge(edge)
        if self.is_directed():
            for edge in list(self.iteroutedges(node)):
                self.del_edge(edge)
        del self[node]

    def add_edge(self, edge):
        """Add an edge to the graph (missing nodes are created)."""
        self.add_node(edge.source)
        self.add_node(edge.target)
        if edge.target not in self[edge.source]:
            self[edge.source][edge.target] = edge.weight
        if not self.is_directed():
            if edge.source not in self[edge.target]:
                self[edge.target][edge.source] = edge.weight

    def del_edge(self, edge):
        """Remove an edge from the graph."""
        del self[edge.source][edge.target]
        if not self.is_directed():
            del self[edge.target][edge.source]

    def has_edge(self, edge):
        """Test if an edge exists."""
        return (edge.target in self[edge.source] and
        edge.weight == self[edge.source][edge.target])

    def weight(self, source, target):
        """Returns the edge weight or zero."""
        if source in self and target in self[source]:
            return self[source][target]
        else:
            return 0

    def iternodes(self):
        """Generates nodes from the graph on demand."""
        return self.iterkeys()

    def iteradjacent(self, source):
        """Generates adjacent nodes from the graph on demand."""
        return self[source].iterkeys()

    def iteroutedges(self, source):
        """Generates outedges from the graph on demand."""
        for target in self[source]:
            yield Edge(source, target, self[source][target])

    def iterinedges(self, source):
        """Generates outedges from the graph on demand."""
        if self.is_directed():   # inefficient, time O(E)
            for edge in self.iteredges():
                if edge.target == source:
                    yield edge
        else:    # iteroutedges<commit_msg>Graph: iterinedges in O(V).<commit_after>#!/usr/bin/python
#
# graphs.py
#
# Nodes can be numbers, string, or any hashable objects.
# We would like also to compare nodes.
#
# {"A":{"B":1,"C":2}, 
# "B":{"C":3,"D":4}, 
# "C":{"D":5}, 
# "D":{"C":6}, 
# "E":{"C":7}, 
# "F":{}}

from edges import Edge


class Graph(dict):
    """The class defining a graph."""

    def __init__(self, n=0, directed=False):
        """Loads up a Graph instance."""
        self.n = n              # compatibility
        self.directed = directed  # bool

    def v(self):
        """Returns the number of nodes (the graph order)."""
        return len(self)

    def e(self):
        """Returns the number of edges."""
        edges = sum(len(self[node]) for node in self)
        return (edges if self.is_directed() else edges / 2)

    def is_directed(self):
        """Test if the graph is directed."""
        return self.directed

    def add_node(self, node):
        """Add a node to the graph."""
        if node not in self:
            self[node] = dict()

    def has_node(self, node):
        """Test if a node exists."""
        return node in self

    def del_node(self, node):
        """Remove a node from the graph (with edges)."""
        # dictionary changes size during iteration.
        for edge in list(self.iterinedges(node)):
            self.del_edge(edge)
        if self.is_directed():
            for edge in list(self.iteroutedges(node)):
                self.del_edge(edge)
        del self[node]

    def add_edge(self, edge):
        """Add an edge to the graph (missing nodes are created)."""
        self.add_node(edge.source)
        self.add_node(edge.target)
        if edge.target not in self[edge.source]:
            self[edge.source][edge.target] = edge.weight
        if not self.is_directed():
            if edge.source not in self[edge.target]:
                self[edge.target][edge.source] = edge.weight

    def del_edge(self, edge):
        """Remove an edge from the graph."""
        del self[edge.source][edge.target]
        if not self.is_directed():
            del self[edge.target][edge.source]

    def has_edge(self, edge):
        """Test if an edge exists."""
        return (edge.target in self[edge.source] and
        edge.weight == self[edge.source][edge.target])

    def weight(self, source, target):
        """Returns the edge weight or zero."""
        if source in self and target in self[source]:
            return self[source][target]
        else:
            return 0

    def iternodes(self):
        """Generates nodes from the graph on demand."""
        return self.iterkeys()

    def iteradjacent(self, source):
        """Generates adjacent nodes from the graph on demand."""
        return self[source].iterkeys()

    def iteroutedges(self, source):
        """Generates outedges from the graph on demand."""
        for target in self[source]:
            yield Edge(source, target, self[source][target])

    def iterinedges(self, source):
        """Generates inedges from the graph on demand."""
        if self.is_directed():   # time O(V)
            for (target, sources_dict) in self.iteritems():
                if source in sources_dict:
                    yield Edge(target, source, sources_dict[source])
        else:    # iteroutedges
{'fraction_non_alphanumeric': 0.13338403041825095, 'fraction_numerical': 0.003041825095057034, 'mean_word_length': 2.2078048780487807, 'pattern_counts': {'":': 26, '<': 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': '599946', 'n_tokens_mistral': 1932, 'n_tokens_neox': 1857, 'n_words': 613}