File: euler.py

package info (click to toggle)
python-networkx 1.7~rc1-3
  • links: PTS, VCS
  • area: main
  • in suites: wheezy
  • size: 4,128 kB
  • sloc: python: 44,557; makefile: 135
file content (135 lines) | stat: -rw-r--r-- 3,543 bytes parent folder | download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
# -*- coding: utf-8 -*-
"""
Eulerian circuits and graphs.
"""
import networkx as nx

__author__ = """\n""".join(['Nima Mohammadi (nima.irt[AT]gmail.com)',
                            'Aric Hagberg <hagberg@lanl.gov>'])
#    Copyright (C) 2010 by 
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.

__all__ = ['is_eulerian', 'eulerian_circuit']

def is_eulerian(G):
    """Return True if G is an Eulerian graph, False otherwise.

    An Eulerian graph is a graph with an Eulerian circuit.

    Parameters
    ----------
    G : graph
       A NetworkX Graph

    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

    Notes
    -----
    This implementation requires the graph to be connected
    (or strongly connected for directed graphs).
    """
    if G.is_directed():
        # Every node must have equal in degree and out degree
        for n in G.nodes_iter():
            if G.in_degree(n) != G.out_degree(n):
               return False
        # Must be strongly connected
        if not nx.is_strongly_connected(G):
            return False
    else:
        # An undirected Eulerian graph has no vertices of odd degrees
        for v,d in G.degree_iter():
            if d % 2 != 0:
                return False
        # Must be connected
        if not nx.is_connected(G):
            return False
    return True
	  

def eulerian_circuit(G, source=None):
    """Return the edges of an Eulerian circuit in G.

    An Eulerian circuit is a path that crosses every edge in G exactly once
    and finishes at the starting node.

    Parameters
    ----------
    G : graph
       A NetworkX Graph
    source : node, optional
       Starting node for circuit.

    Returns
    -------
    edges : generator
       A generator that produces edges in the Eulerian circuit.

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

    See Also
    --------
    is_eulerian

    Notes
    -----
    Uses Fleury's algorithm [1]_,[2]_  

    References
    ----------
    .. [1] Fleury, "Deux problemes de geometrie de situation", 
       Journal de mathematiques elementaires (1883), 257-261.
    .. [2] http://en.wikipedia.org/wiki/Eulerian_path

    Examples
    --------
    >>> G=nx.complete_graph(3)
    >>> list(nx.eulerian_circuit(G))
    [(0, 1), (1, 2), (2, 0)]
    >>> list(nx.eulerian_circuit(G,source=1)) 
    [(1, 0), (0, 2), (2, 1)]
    >>> [u for u,v in nx.eulerian_circuit(G)]  # nodes in circuit
    [0, 1, 2]
    """
    if not is_eulerian(G):
        raise nx.NetworkXError("G is not Eulerian.")

    g = G.__class__(G) # copy graph structure (not attributes)

    # set starting node
    if source is None:
        v = next(g.nodes_iter())
    else:
        v = source

    while g.size() > 0:
        n = v   
        # sort nbrs here to provide stable ordering of alternate cycles
        nbrs = sorted([v for u,v in g.edges(n)])
        for v in nbrs:
            g.remove_edge(n,v)
            bridge = not nx.is_connected(g.to_undirected())
            if bridge:
                g.add_edge(n,v)  # add this edge back and try another
            else:
                break  # this edge is good, break the for loop 
        if bridge:
            g.remove_edge(n,v)            
            g.remove_node(n)
        yield (n,v)