challenge.city_tour
¶module ensae_projects.challenge.city_tour
Function to solve the problem of the Route Inspection Problem.
class  truncated documentation 

SolutionException 
wrong solution 
function  truncated documentation 

_delete_edge 
Removes an edge from the graph. 
_euler_path 
Computes an Eulerian path. 
_explore_path 
Explores an Eulerian path, remove used edges from edges_from. 
bellman_distances 
Computes shortest distances between all vertices. It assumes edges are symmetric. 
best_euler_path 
Computes the final solution for the Eulerian path. 
compute_degrees 
Compute the degree of vertices. 
dijkstra_path 
Returns the best path between two vertices. Uses Dikjstra … 
distance_solution 
Checks if a solution is really a solution and returns the distance of it, None if it is not a solution. The function … 
distance_vertices 
Computes the length of edges if distances is None. 
euler_path 
Computes an Eulerian path. 
haversine_distance 
Computes Haversine formula. 
matching_vertices 
Finds the best match between vertices. 
Function to solve the problem of the Route Inspection Problem.
ensae_projects.challenge.city_tour.
SolutionException
[source]¶Bases: Exception
wrong solution
ensae_projects.challenge.city_tour.
_delete_edge
(edges_from, n, to)[source]¶Removes an edge from the graph.
Parameters: 


Returns:  the edge 
ensae_projects.challenge.city_tour.
_euler_path
(edges)[source]¶Computes an Eulerian path.
Parameters:  edges – edges 

Returns:  path, list of (vertex,edge) 
The function assumes every vertex in the graph defined by edges has an even degree.
ensae_projects.challenge.city_tour.
_explore_path
(edges_from, begin)[source]¶Explores an Eulerian path, remove used edges from edges_from.
Parameters: 


Returns:  path 
ensae_projects.challenge.city_tour.
bellman_distances
(edges, distances, fLOG=None)[source]¶Computes shortest distances between all vertices. It assumes edges are symmetric.
Parameters: 


Returns:  dictionary of distances 
This function could be implemented based on shortest_path.
ensae_projects.challenge.city_tour.
best_euler_path
(edges, vertices, distances, edges_index=None, algo='blossom', fLOG=None)[source]¶Computes the final solution for the Eulerian path.
Parameters: 


Returns:  list of edges as tuple, list of edges as indices, distance 
ensae_projects.challenge.city_tour.
compute_degrees
(edges)[source]¶Compute the degree of vertices.
Parameters:  edges – list of tuple 

Returns:  dictionary {key: degree} 
ensae_projects.challenge.city_tour.
dijkstra_path
(edges, distances, va, vb)[source]¶Returns the best path between two vertices. Uses Dikjstra algorithm.
Parameters: 


Returns:  list of edges 
This function could be implemented based on shortest_path.
ensae_projects.challenge.city_tour.
distance_solution
(edges_index, edges, distances, solution, exc=True)[source]¶Checks if a solution is really a solution and returns the distance of it, None if it is not a solution. The function does not case about the order.
Parameters: 


ensae_projects.challenge.city_tour.
distance_vertices
(edges, vertices, distances)[source]¶Computes the length of edges if distances is None.
Parameters: 


Returns:  distances (list of float) 
ensae_projects.challenge.city_tour.
euler_path
(edges_index, edges, solution)[source]¶Computes an Eulerian path.
Parameters: 


Returns:  path, list of edges indices 
The function assumes every vertex in the graph defined by edges has an even degree.
ensae_projects.challenge.city_tour.
haversine_distance
(lat1, lng1, lat2, lng2)[source]¶Computes Haversine formula.
Parameters: 


Returns:  distance 
ensae_projects.challenge.city_tour.
matching_vertices
(distances, algo='blossom')[source]¶Finds the best match between vertices.
Parameters: 


Returns:  sequences of best matches. 
If algo=='hungarian'
,
the function relies on linear_sum_assignment
from scipy which uses the
Hungarian Algorithm.
Vertex index do not have to start from zero and be continuous.
The function will handle that particular case. However, the method
works for a bipartite matching and is not suitable here unless
the algorithm is modified. Not done (yet?).
If algo=='blossom'
, it uses the
Blossom algorithm
which is known to be in and finds the optimal matching.
If algo=='basic'
, the function sorts the distances
by increasing order and builds new edges as they come in this list.
It does not return an optimal solution but is much faster
when the graph is big.