1 files changed, 77 insertions, 0 deletions
diff --git a/ero1/src/helper/check_eulerian.py b/ero1/src/helper/check_eulerian.py
new file mode 100644
index 0000000..31a5db4
--- /dev/null
+++ b/ero1/src/helper/check_eulerian.py
@@ -0,0 +1,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)
+\ No newline at end of file