<commit_before>import collections

FORWARD = 1
REVERSE = 0

__all__ = ['edge_dfs']

def helper_funcs(G, orientation):
    """
    These are various G-specific functions that help us implement the algorithm
    for all graph types: graph, multigraph, directed or not.

    """
    ignore_orientation = G.is_directed() and orientation == 'ignore'
    if ignore_orientation:
        # When we ignore the orientation, we still need to know how the edge
        # was traversed, so we add an integer representing the direction.
        def out_edges(u, **kwds):
            for edge in G.out_edges(u, **kwds):
                yield edge + (FORWARD,)
            for edge in G.in_edges(u, **kwds):
                yield edge + (REVERSE,)
    else:
        # If "yield from" were an option, we could pass kwds automatically.
        out_edges = G.edges_iter

    # If every edge had a unique key, then it would be easier to track which
    # edges had been visited. Since that is not available, we will form a
    # unique identifier from the edge and key (if present). If the graph
    # is undirected, then the head and tail need to be stored as a frozenset.
    if ignore_orientation:
        # edge is a 4-tuple: (u, v, key, direction)
        # u and v always represent the true tail and head of the edge.
        def key(edge):
            # We want everything but the direction.
            return edge[:-1]
    else:
        if G.is_directed():
            def key(edge):
                return edge
        else:
            # edge is a 3-tuple:  (u, v, key)
            def key(edge):
                new_edge = (frozenset(edge[:2]),) + edge[2:]
                return new_edge

    def traversed_tailhead(edge):
        """
        Returns the tail and head of an edge, as it was traversed.

        So in general, this is different from the true tail and head.

        """
        if ignore_orientation and edge[-1] == REVERSE:
            tail, head = edge[1], edge[0]
        else:
            tail, head = edge[0], edge[1]
        return tail, head

    return out_edges, key, traversed_tailhead

def edge_dfs(G, source=None, orientation='respect'):
    """
    A directed, depth-first traversal of edges in G, beginning at `source`.

    Parameters
    ----------
    G : graph
        A directed/undirected graph/multigraph.

    source : node, list of nodes
        The node from which the traversal begins. If `None`, then a source
        is chosen arbitrarily and repeatedly until all edges from each node in
        the graph are searched.

    orientation : 'respect' | 'ignore'
        For directed graphs and directed multigraphs, the orientation of the
        edges can be respected or ignored.  When set to 'ignore', then each
        directed edge is treated as a single undirected edge. For undirected
        graphs and undirected multigraphs, the value of this parameter is not
        used by the algorithm.

    Yields
    ------
    edge : directed edge
        A directed edge indicating the path taken by the depth-first traversal.
        For graphs, `edge` is of the form (u, v) where `u` and `v` are the
        tail and head of the edge as determined by the traversal. For
        multigraphs, `edge` is of the form (u, v, key), where `key` is the key
        of the edge. When the graph is directed, then `u` and `v` are always in
        the order of the actual directed edge. If orientation is 'ignore', then
        `edge` takes the form (u, v, key, direction) where direction indicates
        if the edge was followed in the forward (tail to head) or reverse
        (head to tail) direction. When the direction is forward, the value of
        `direction` is 1, and when the direction in reverse, the value is 0.

    Examples
    --------
    >>> nodes = [0, 1, 2, 3]
    >>> edges = [(0, 1), (1, 0), (1, 0), (2, 1), (3, 1)]

    >>> list(nx.edges_dfs(nx.Graph(edges), nodes))
    [(0, 1), (1, 2), (1, 3)]
<commit_msg>Add import statement for doctest.<commit_after>import collections

FORWARD = 1
REVERSE = 0

__all__ = ['edge_dfs']

def helper_funcs(G, orientation):
    """
    These are various G-specific functions that help us implement the algorithm
    for all graph types: graph, multigraph, directed or not.

    """
    ignore_orientation = G.is_directed() and orientation == 'ignore'
    if ignore_orientation:
        # When we ignore the orientation, we still need to know how the edge
        # was traversed, so we add an integer representing the direction.
        def out_edges(u, **kwds):
            for edge in G.out_edges(u, **kwds):
                yield edge + (FORWARD,)
            for edge in G.in_edges(u, **kwds):
                yield edge + (REVERSE,)
    else:
        # If "yield from" were an option, we could pass kwds automatically.
        out_edges = G.edges_iter

    # If every edge had a unique key, then it would be easier to track which
    # edges had been visited. Since that is not available, we will form a
    # unique identifier from the edge and key (if present). If the graph
    # is undirected, then the head and tail need to be stored as a frozenset.
    if ignore_orientation:
        # edge is a 4-tuple: (u, v, key, direction)
        # u and v always represent the true tail and head of the edge.
        def key(edge):
            # We want everything but the direction.
            return edge[:-1]
    else:
        if G.is_directed():
            def key(edge):
                return edge
        else:
            # edge is a 3-tuple:  (u, v, key)
            def key(edge):
                new_edge = (frozenset(edge[:2]),) + edge[2:]
                return new_edge

    def traversed_tailhead(edge):
        """
        Returns the tail and head of an edge, as it was traversed.

        So in general, this is different from the true tail and head.

        """
        if ignore_orientation and edge[-1] == REVERSE:
            tail, head = edge[1], edge[0]
        else:
            tail, head = edge[0], edge[1]
        return tail, head

    return out_edges, key, traversed_tailhead

def edge_dfs(G, source=None, orientation='respect'):
    """
    A directed, depth-first traversal of edges in G, beginning at `source`.

    Parameters
    ----------
    G : graph
        A directed/undirected graph/multigraph.

    source : node, list of nodes
        The node from which the traversal begins. If `None`, then a source
        is chosen arbitrarily and repeatedly until all edges from each node in
        the graph are searched.

    orientation : 'respect' | 'ignore'
        For directed graphs and directed multigraphs, the orientation of the
        edges can be respected or ignored.  When set to 'ignore', then each
        directed edge is treated as a single undirected edge. For undirected
        graphs and undirected multigraphs, the value of this parameter is not
        used by the algorithm.

    Yields
    ------
    edge : directed edge
        A directed edge indicating the path taken by the depth-first traversal.
        For graphs, `edge` is of the form (u, v) where `u` and `v` are the
        tail and head of the edge as determined by the traversal. For
        multigraphs, `edge` is of the form (u, v, key), where `key` is the key
        of the edge. When the graph is directed, then `u` and `v` are always in
        the order of the actual directed edge. If orientation is 'ignore', then
        `edge` takes the form (u, v, key, direction) where direction indicates
        if the edge was followed in the forward (tail to head) or reverse
        (head to tail) direction. When the direction is forward, the value of
        `direction` is 1, and when the direction in reverse, the value is 0.

    Examples
    --------
    >>> import networkx as nx
    >>> nodes = [0, 1, 2, 3]
    >>> edges = [(0, 1), (1, 0), (1, 0), (2, 1), (3, 1)]

    >>> list(nx.edges_dfs(nx.Graph(edges), nodes))
    [(0, 1), (1, 2), (1, 3)]

{'fraction_non_alphanumeric': 0.08931259407927747, 'fraction_numerical': 0.008529854490717512, 'mean_word_length': 2.2084507042253523, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 24, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '238209', 'n_tokens_mistral': 2302, 'n_tokens_neox': 2180, 'n_words': 1032}