Skip to main content
`Ctrl`+`K`

# Source code for networkx.algorithms.euler

    """
    Eulerian circuits and graphs.
    """

    from itertools import combinations

    import networkx as nx

    from ..utils import arbitrary_element, not_implemented_for

    __all__ = [
        "is_eulerian",
        "eulerian_circuit",
        "eulerize",
        "is_semieulerian",
        "has_eulerian_path",
        "eulerian_path",
    ]

    @nx._dispatchable
    def is_eulerian(G):
        """Returns True if and only if `G` is Eulerian.

        A graph is *Eulerian* if it has an Eulerian circuit. An *Eulerian
        circuit* is a closed walk that includes each edge of a graph exactly
        once.

        Graphs with isolated vertices (i.e. vertices with zero degree) are not
        considered to have Eulerian circuits. Therefore, if the graph is not
        connected (or not strongly connected, for directed graphs), this function
        returns False.

        Parameters
        ----------
        G : NetworkX graph
           A graph, either directed or undirected.

        Examples
        --------
        >>> nx.is_eulerian(nx.DiGraph({0: [3], 1: [2], 2: [3], 3: [0, 1]}))
        True
        >>> nx.is_eulerian(nx.complete_graph(5))
        True
        >>> nx.is_eulerian(nx.petersen_graph())
        False

        If you prefer to allow graphs with isolated vertices to have Eulerian circuits,
        you can first remove such vertices and then call `is_eulerian` as below example shows.

        >>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])
        >>> G.add_node(3)
        >>> nx.is_eulerian(G)
        False

        >>> G.remove_nodes_from(list(nx.isolates(G)))
        >>> nx.is_eulerian(G)
        True

        """
        if G.is_directed():
            # Every node must have equal in degree and out degree and the
            # graph must be strongly connected
            return all(
                G.in_degree(n) == G.out_degree(n) for n in G
            ) and nx.is_strongly_connected(G)
        # An undirected Eulerian graph has no vertices of odd degree and
        # must be connected.
        return all(d % 2 == 0 for v, d in G.degree()) and nx.is_connected(G)

    @nx._dispatchable
    def is_semieulerian(G):
        """Return True iff `G` is semi-Eulerian.

        G is semi-Eulerian if it has an Eulerian path but no Eulerian circuit.

        See Also
        --------
        has_eulerian_path
        is_eulerian
        """
        return has_eulerian_path(G) and not is_eulerian(G)

    def _find_path_start(G):
        """Return a suitable starting vertex for an Eulerian path.

        If no path exists, return None.
        """
        if not has_eulerian_path(G):
            return None

        if is_eulerian(G):
            return arbitrary_element(G)

        if G.is_directed():
            v1, v2 = (v for v in G if G.in_degree(v) != G.out_degree(v))
            # Determines which is the 'start' node (as opposed to the 'end')
            if G.out_degree(v1) > G.in_degree(v1):
                return v1
            else:
                return v2

        else:
            # In an undirected graph randomly choose one of the possibilities
            start = [v for v in G if G.degree(v) % 2 != 0][0]
            return start

    def _simplegraph_eulerian_circuit(G, source):
        if G.is_directed():
            degree = G.out_degree
            edges = G.out_edges
        else:
            degree = G.degree
            edges = G.edges
        vertex_stack = [source]
        last_vertex = None
        while vertex_stack:
            current_vertex = vertex_stack[-1]
            if degree(current_vertex) == 0:
                if last_vertex is not None:
                    yield (last_vertex, current_vertex)
                last_vertex = current_vertex
                vertex_stack.pop()
            else:
                _, next_vertex = arbitrary_element(edges(current_vertex))
                vertex_stack.append(next_vertex)
                G.remove_edge(current_vertex, next_vertex)

    def _multigraph_eulerian_circuit(G, source):
        if G.is_directed():
            degree = G.out_degree
            edges = G.out_edges
        else:
            degree = G.degree
            edges = G.edges
        vertex_stack = [(source, None)]
        last_vertex = None
        last_key = None
        while vertex_stack:
            current_vertex, current_key = vertex_stack[-1]
            if degree(current_vertex) == 0:
                if last_vertex is not None:
                    yield (last_vertex, current_vertex, last_key)
                last_vertex, last_key = current_vertex, current_key
                vertex_stack.pop()
            else:
                triple = arbitrary_element(edges(current_vertex, keys=True))
                _, next_vertex, next_key = triple
                vertex_stack.append((next_vertex, next_key))
                G.remove_edge(current_vertex, next_vertex, next_key)

    @nx._dispatchable
    def eulerian_circuit(G, source=None, keys=False):
        """Returns an iterator over the edges of an Eulerian circuit in `G`.

        An *Eulerian circuit* is a closed walk that includes each edge of a
        graph exactly once.

        Parameters
        ----------
        G : NetworkX graph
           A graph, either directed or undirected.

        source : node, optional
           Starting node for circuit.

        keys : bool
           If False, edges generated by this function will be of the form
           ``(u, v)``. Otherwise, edges will be of the form ``(u, v, k)``.
           This option is ignored unless `G` is a multigraph.

        Returns
        -------
        edges : iterator
           An iterator over edges in the Eulerian circuit.

        Raises
        ------
        NetworkXError
           If the graph is not Eulerian.

        See Also
        --------
        is_eulerian

        Notes
        -----
        This is a linear time implementation of an algorithm adapted from [1]_.

        For general information about Euler tours, see [2]_.

        References
        ----------
        .. [1] J. Edmonds, E. L. Johnson.
           Matching, Euler tours and the Chinese postman.
           Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
        .. [2] https://en.wikipedia.org/wiki/Eulerian_path

        Examples
        --------
        To get an Eulerian circuit in an undirected graph::

            >>> G = nx.complete_graph(3)
            >>> list(nx.eulerian_circuit(G))
            [(0, 2), (2, 1), (1, 0)]
            >>> list(nx.eulerian_circuit(G, source=1))
            [(1, 2), (2, 0), (0, 1)]

        To get the sequence of vertices in an Eulerian circuit::

            >>> [u for u, v in nx.eulerian_circuit(G)]
            [0, 2, 1]

        """
        if not is_eulerian(G):
            raise nx.NetworkXError("G is not Eulerian.")
        if G.is_directed():
            G = G.reverse()
        else:
            G = G.copy()
        if source is None:
            source = arbitrary_element(G)
        if G.is_multigraph():
            for u, v, k in _multigraph_eulerian_circuit(G, source):
                if keys:
                    yield u, v, k
                else:
                    yield u, v
        else:
            yield from _simplegraph_eulerian_circuit(G, source)

    @nx._dispatchable
    def has_eulerian_path(G, source=None):
        """Return True iff `G` has an Eulerian path.

        An Eulerian path is a path in a graph which uses each edge of a graph
        exactly once. If `source` is specified, then this function checks
        whether an Eulerian path that starts at node `source` exists.

        A directed graph has an Eulerian path iff:
            - at most one vertex has out_degree - in_degree = 1,
            - at most one vertex has in_degree - out_degree = 1,
            - every other vertex has equal in_degree and out_degree,
            - and all of its vertices belong to a single connected
              component of the underlying undirected graph.

        If `source` is not None, an Eulerian path starting at `source` exists if no
        other node has out_degree - in_degree = 1. This is equivalent to either
        there exists an Eulerian circuit or `source` has out_degree - in_degree = 1
        and the conditions above hold.

        An undirected graph has an Eulerian path iff:
            - exactly zero or two vertices have odd degree,
            - and all of its vertices belong to a single connected component.

        If `source` is not None, an Eulerian path starting at `source` exists if
        either there exists an Eulerian circuit or `source` has an odd degree and the
        conditions above hold.

        Graphs with isolated vertices (i.e. vertices with zero degree) are not considered
        to have an Eulerian path. Therefore, if the graph is not connected (or not strongly
        connected, for directed graphs), this function returns False.

        Parameters
        ----------
        G : NetworkX Graph
            The graph to find an euler path in.

        source : node, optional
            Starting node for path.

        Returns
        -------
        Bool : True if G has an Eulerian path.

        Examples
        --------
        If you prefer to allow graphs with isolated vertices to have Eulerian path,
        you can first remove such vertices and then call `has_eulerian_path` as below example shows.

        >>> G = nx.Graph([(0, 1), (1, 2), (0, 2)])
        >>> G.add_node(3)
        >>> nx.has_eulerian_path(G)
        False

        >>> G.remove_nodes_from(list(nx.isolates(G)))
        >>> nx.has_eulerian_path(G)
        True

        See Also
        --------
        is_eulerian
        eulerian_path
        """
        if nx.is_eulerian(G):
            return True

        if G.is_directed():
            ins = G.in_degree
            outs = G.out_degree
            # Since we know it is not eulerian, outs - ins must be 1 for source
            if source is not None and outs[source] - ins[source] != 1:
                return False

            unbalanced_ins = 0
            unbalanced_outs = 0
            for v in G:
                if ins[v] - outs[v] == 1:
                    unbalanced_ins += 1
                elif outs[v] - ins[v] == 1:
                    unbalanced_outs += 1
                elif ins[v] != outs[v]:
                    return False

            return (
                unbalanced_ins <= 1 and unbalanced_outs <= 1 and nx.is_weakly_connected(G)
            )
        else:
            # We know it is not eulerian, so degree of source must be odd.
            if source is not None and G.degree[source] % 2 != 1:
                return False

            # Sum is 2 since we know it is not eulerian (which implies sum is 0)
            return sum(d % 2 == 1 for v, d in G.degree()) == 2 and nx.is_connected(G)

    @nx._dispatchable
    def eulerian_path(G, source=None, keys=False):
        """Return an iterator over the edges of an Eulerian path in `G`.

        Parameters
        ----------
        G : NetworkX Graph
            The graph in which to look for an eulerian path.
        source : node or None (default: None)
            The node at which to start the search. None means search over all
            starting nodes.
        keys : Bool (default: False)
            Indicates whether to yield edge 3-tuples (u, v, edge_key).
            The default yields edge 2-tuples

        Yields
        ------
        Edge tuples along the eulerian path.

        Warning: If `source` provided is not the start node of an Euler path
        will raise error even if an Euler Path exists.
        """
        if not has_eulerian_path(G, source):
            raise nx.NetworkXError("Graph has no Eulerian paths.")
        if G.is_directed():
            G = G.reverse()
            if source is None or nx.is_eulerian(G) is False:
                source = _find_path_start(G)
            if G.is_multigraph():
                for u, v, k in _multigraph_eulerian_circuit(G, source):
                    if keys:
                        yield u, v, k
                    else:
                        yield u, v
            else:
                yield from _simplegraph_eulerian_circuit(G, source)
        else:
            G = G.copy()
            if source is None:
                source = _find_path_start(G)
            if G.is_multigraph():
                if keys:
                    yield from reversed(
                        [(v, u, k) for u, v, k in _multigraph_eulerian_circuit(G, source)]
                    )
                else:
                    yield from reversed(
                        [(v, u) for u, v, k in _multigraph_eulerian_circuit(G, source)]
                    )
            else:
                yield from reversed(
                    [(v, u) for u, v in _simplegraph_eulerian_circuit(G, source)]
                )

    @not_implemented_for("directed")
    @nx._dispatchable(returns_graph=True)
    def eulerize(G):
        """Transforms a graph into an Eulerian graph.

        If `G` is Eulerian the result is `G` as a MultiGraph, otherwise the result is a smallest
        (in terms of the number of edges) multigraph whose underlying simple graph is `G`.

        Parameters
        ----------
        G : NetworkX graph
           An undirected graph

        Returns
        -------
        G : NetworkX multigraph

        Raises
        ------
        NetworkXError
           If the graph is not connected.

        See Also
        --------
        is_eulerian
        eulerian_circuit

        References
        ----------
        .. [1] J. Edmonds, E. L. Johnson.
           Matching, Euler tours and the Chinese postman.
           Mathematical programming, Volume 5, Issue 1 (1973), 111-114.
        .. [2] https://en.wikipedia.org/wiki/Eulerian_path
        .. [3] http://web.math.princeton.edu/math_alive/5/Notes1.pdf

        Examples
        --------
            >>> G = nx.complete_graph(10)
            >>> H = nx.eulerize(G)
            >>> nx.is_eulerian(H)
            True

        """
        if G.order() == 0:
            raise nx.NetworkXPointlessConcept("Cannot Eulerize null graph")
        if not nx.is_connected(G):
            raise nx.NetworkXError("G is not connected")
        odd_degree_nodes = [n for n, d in G.degree() if d % 2 == 1]
        G = nx.MultiGraph(G)
        if len(odd_degree_nodes) == 0:
            return G

        # get all shortest paths between vertices of odd degree
        odd_deg_pairs_paths = [
            (m, {n: nx.shortest_path(G, source=m, target=n)})
            for m, n in combinations(odd_degree_nodes, 2)
        ]

        # use the number of vertices in a graph + 1 as an upper bound on
        # the maximum length of a path in G
        upper_bound_on_max_path_length = len(G) + 1

        # use "len(G) + 1 - len(P)",
        # where P is a shortest path between vertices n and m,
        # as edge-weights in a new graph
        # store the paths in the graph for easy indexing later
        Gp = nx.Graph()
        for n, Ps in odd_deg_pairs_paths:
            for m, P in Ps.items():
                if n != m:
                    Gp.add_edge(
                        m, n, weight=upper_bound_on_max_path_length - len(P), path=P
                    )

        # find the minimum weight matching of edges in the weighted graph
        best_matching = nx.Graph(list(nx.max_weight_matching(Gp)))

        # duplicate each edge along each path in the set of paths in Gp
        for m, n in best_matching.edges():
            path = Gp[m][n]["path"]
            G.add_edges_from(nx.utils.pairwise(path))
        return G