diff options
Diffstat (limited to 'ero1/src/drone/postier_chinois_Martial.py')
| -rw-r--r-- | ero1/src/drone/postier_chinois_Martial.py | 122 |
1 files changed, 122 insertions, 0 deletions
diff --git a/ero1/src/drone/postier_chinois_Martial.py b/ero1/src/drone/postier_chinois_Martial.py new file mode 100644 index 0000000..a0afb14 --- /dev/null +++ b/ero1/src/drone/postier_chinois_Martial.py @@ -0,0 +1,122 @@ +import parameters as params +import itertools +from src.helper.debug_printer import debug_print +import networkx as nx +import pandas as pd + +def postier_chinois(G, debug_mode=False): + """ + Parcourt le graphe en résolvant le problème du postier chinois + Source: https://brooksandrew.github.io/simpleblog/articles/intro-to-graph-optimization-solving-cpp/#solving-the-chinese-postman-problem + Parameters: + G: Le graphe des routes + debug_mode: Logs de debug + Returns: + La liste des arêtes (routes) avec entre 2.5 et 15 cm de neige + """ + gu = nx.to_undirected(G) + nodes_odd_degree = [v for v, d in gu.degree() if d % 2 == 1] + debug_print('Number of nodes of odd degree: {}'.format(len(nodes_odd_degree)), debug_mode) + debug_print('Number of total nodes: {}'.format(len(gu.nodes())), debug_mode) + + odd_node_pairs = list(itertools.combinations(nodes_odd_degree, 2)) + debug_print('Number of odd degree node pairs: {}'.format(len(odd_node_pairs)), debug_mode) + + def get_shortest_paths_distances(graph, pairs, edge_weight_name): + """ + Compute shortest distance between each pair of nodes in a graph. Return a dictionary keyed on node pairs (tuples). + """ + distances = {} + for pair in pairs: + distances[pair] = nx.dijkstra_path_length(graph, pair[0], pair[1], weight=edge_weight_name) + return distances + odd_node_pairs_shortest_paths = get_shortest_paths_distances(gu, odd_node_pairs, 'length') + + def create_complete_graph(pair_weights, flip_weights=True): + """ + Create a completely connected graph using a list of vertex pairs and the shortest path distances between them + Parameters: + pair_weights: list[tuple] from the output of get_shortest_paths_distances + flip_weights: Boolean. Should we negate the edge attribute in pair_weights? + """ + g = nx.Graph() + for k, v in pair_weights.items(): + wt_i = - v if flip_weights else v + # g.add_edge(k[0], k[1], {'distance': v, 'weight': wt_i}) # deprecated after NX 1.11 + g.add_edge(k[0], k[1], **{'distance': v, 'weight': wt_i}) + return g + g_odd_complete = create_complete_graph(odd_node_pairs_shortest_paths, flip_weights=True) + debug_print('Number of nodes in complete graph of odd nodes: {}'.format(len(g_odd_complete.nodes())), debug_mode) + debug_print('Number of edges in complete graph of odd nodes: {}'.format(len(g_odd_complete.edges())), debug_mode) + + odd_matching_dupes = nx.algorithms.max_weight_matching(g_odd_complete, True) + odd_matching = list(pd.unique([tuple(sorted([k, v])) for k, v in odd_matching_dupes])) + debug_print('Number of edges in max weight matching: {}'.format(len(odd_matching)), debug_mode) + + def add_augmenting_path_to_graph(graph, min_weight_pairs): + """ + Add the min weight matching edges to the original graph + Parameters: + graph: NetworkX graph (original graph from trailmap) + min_weight_pairs: list[tuples] of node pairs from min weight matching + Returns: + augmented NetworkX graph + """ + + # We need to make the augmented graph a MultiGraph so we can add parallel edges + graph_aug = nx.MultiGraph(graph.copy()) + for pair in min_weight_pairs: + graph_aug.add_edge(pair[0], + pair[1], + **{'length': nx.dijkstra_path_length(graph, pair[0], pair[1]), 'name': 'augmented'} + # attr_dict={'distance': nx.dijkstra_path_length(graph, pair[0], pair[1]), + # 'trail': 'augmented'} # deprecated after 1.11 + ) + return graph_aug + g_aug = add_augmenting_path_to_graph(gu, odd_matching) + + # Counts + debug_print('Number of edges in original graph: {}'.format(len(gu.edges())), debug_mode) + debug_print('Number of edges in augmented graph: {}'.format(len(g_aug.edges())), debug_mode) + + def create_eulerian_circuit(graph_augmented, graph_original): + """ + Create the eulerian path using only edges from the original graph. + """ + debug_print("Creating eulerian circuit", debug_mode) + euler_circuit = [] + naive_circuit = list(nx.eulerian_circuit(graph_augmented)) + dbg = False + + for edge in naive_circuit: + edge_data = graph_augmented.get_edge_data(edge[0], edge[1]) + + if len(edge_data) == 1 and 'name' in edge_data[0] and edge_data[0]['name'] != 'augmented': + # If `edge` exists in original graph, grab the edge attributes and add to eulerian circuit. + edge_att = graph_original[edge[0]][edge[1]] + euler_circuit.append((edge[0], edge[1], edge_att)) + else: + aug_path = nx.shortest_path(graph_original, edge[0], edge[1], weight='length') + aug_path_pairs = list(zip(aug_path[:-1], aug_path[1:])) + + debug_print('Filling in edges for augmented edge: {}'.format(edge), dbg) + debug_print('Augmenting path: {}'.format(' => '.join(str(aug_path))), dbg) + debug_print('Augmenting path pairs: {}\n'.format(aug_path_pairs), dbg) + + # If `edge` does not exist in original graph, find the shortest path between its nodes and + # add the edge attributes for each link in the shortest path. + for edge_aug in aug_path_pairs: + edge_aug_att = graph_original[edge_aug[0]][edge_aug[1]] + euler_circuit.append((edge_aug[0], edge_aug[1], edge_aug_att)) + + return euler_circuit + euler_circuit = create_eulerian_circuit(g_aug, gu) + debug_print('Length of Eulerian circuit: {}'.format(len(euler_circuit)), debug_mode) + + debug_print("Extraction des la météo des neiges depuis le parcours eulérien...", debug_mode) + + routes_enneigées = [] + for edge in euler_circuit: + if params.SNOW_THRESHOLD <= edge[2][0]['snow'] <= params.SNOW_MAX: + routes_enneigées.append(edge) + return routes_enneigées
\ No newline at end of file |