blob: 117fed0bfd98b17ba2985ff83994613004af071c (
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
|
from src.helper.debug_printer import debug_print
from src.helper.check_eulerian import check_directed_eulerian, check_non_directed_eulerian
import networkx as nx
import osmnx as ox
def find_eulerian(G, debug_mode, path=False, start=None, directed=False):
"""
Trouve et renvoit un chemin ou un cycle eulérien du graph G.
Il est possible de spécifier le point de départ du cycle/chemin.
Renvoie le chemin/cycle crée ou None si la demande n'est pas possible
Parameters:
G: Graph duquel on souhaite obtenir le chemin/cycle eulérien
debug_mode: Indique si le debug est actif
path: [OPTIONNEL | DEFAUT = False] True si on souhaite avoir
un chemin eulérien. Faux pour avoir un cycle
start: [OPTIONNEL | DEFAUT = None] Noeud NetworkX de départ
du chemin/cycle. Un check est effectué si on souhaite un chemin
"""
if (G == None):
debug_print("[BASIC_EULER] Cannot procede: The graph is null")
spots = None
if (directed):
spots = check_directed_eulerian(G)
else:
spots = check_non_directed_eulerian(G)
if (spots == None):
debug_print("[BASIC_EULER] This is not an Eulerian graph: Cannot create path or cycle", debug_mode)
return None
if (path):
if (start != spots[0] and start != spots[1]):
# We just want to warn the user that the start position is invalid for this graph
debug_print("[BASIC_EULER] The starting position inputted is not a suitable start for an eulerian path", debug_mode)
start = spots[0]
# We return a list and not an iterator
return [u for u, _ in nx.eulerian_path(G, source=start)]
else:
# This condition is a bit overkill but you never know
if (spots[0] != None or spots[1] != None):
debug_print("[BASIC_EULER] Cannot create cycle on this eulerian graph", debug_mode)
return None
# We return a list and not an iterator
return [u for u, _ in nx.eulerian_circuit(G, source=start)]
|
