blob: 31a5db42687af28d87f63a176b0c3defb19772ea (
plain)
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
|
import parameters as params
import networkx as nx
import osmnx as ox
def check_directed_eulerian(G):
"""
Check si le graph ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est
renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none.
None = non eulérien
(None, None) = eulérien mais pas de sommets de degrée impair
(V1, V2) = eulérien et possède 2 sommets de degrée impaires
Parameters:
G: Graph à tester
"""
V = list(G.nodes)
odd_start = None
odd_end = None
for node in V:
# This is the implementation used when you want to play with a directed graph
# Sadly NetworkX cannor eulerize directed graph
# Eulerzing a directed graph is... NP-Hard
if (G.in_degree(node) + 1 == G.out_degree(node)):
# We have one more edge exitting than entering
# This is the potential start of an eulerian path
if (odd_start != None):
# We already found a node that could make a staring point ?
# We have too much odd degree vertices in this graph
return None
odd_start = node
elif (G.in_degree(node) == G.out_degree(node) + 1):
# We have one more edge entering than exitting
# This is the potential end of an eulerian path
if (odd_end != None):
# We already found a node that could make an ending point ?
# We have too much odd degree vertices in this graph
return None
odd_end = node
elif (G.in_degree(node) != G.out_degree(node)):
# Something's wrong, this is not at all an eulerian graph
return None
# There is no clean XOR in python...
# Sad...
if (bool(odd_start) != bool(odd_end)):
# We only have one vertice with and odd degree
return None
return (odd_start, odd_end)
def check_non_directed_eulerian(G):
"""
Check si le graph NON ORIENTÉ donné est Eulérien [en O(V)] et si ce dernier l'est
renvoie les sommets qui ont un degré impair (si il en existe). Sinon renvoie none.
None = non eulérien
(None, None) = eulérien mais pas de sommets de degrée impair
(V1, V2) = eulérien et possède 2 sommets de degrée impaires
Parameters:
G: Graph à tester
"""
V = list(G.nodes)
odd_start = None
odd_end = None
for node in V:
if (G.degree(node) % 2 == 1):
if (odd_start == None):
odd_start = node
elif (odd_end == None):
odd_end = node
else:
return None
# There is no clean XOR in python...
# Sad...
if (bool(odd_start) != bool(odd_end)):
# We only have one vertice with and odd degree
return None
return (odd_start, odd_end)
|
