/usr/lib/python2.7/dist-packages/networkx/algorithms/euler.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | # -*- 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)
|