| Title: | Optimal Routing and Cost Allocation for the Chinese Postman Game |
|---|---|
| Description: | Solves the Chinese Postman Problem (CPP) using Dijkstra's algorithm for shortest paths, Edmonds' Blossom algorithm (1965) for minimum weight perfect matching, and Fleury's algorithm for Eulerian circuit generation. Additionally, computes the cooperative gamma-rule cost allocation proposed by Hamers, Klijn, Suijs, and Tijs (1999) <doi :10.1016/S0377-2217(98)00346-6> for weakly Eulerian networks. |
| Authors: | Maria Gabriela Perez [aut, cre] |
| Maintainer: | Maria Gabriela Perez <[email protected]> |
| License: | GPL (>= 3) |
| Version: | 0.1.0 |
| Built: | 2026-10-15 20:34:01 UTC |
| Source: | https://github.com/cran/CoopPostman |
Calculates the cooperative game cost allocation vector gamma for weakly Eulerian networks.
calcular_gamma(aristas, nodos, deposito)calcular_gamma(aristas, nodos, deposito)
aristas |
A data.frame with columns |
nodos |
A data.frame with a column |
deposito |
Identifier of the depot vertex. |
A list containing gamma allocation and bridge followers.
Duplicates edges along the shortest path between two vertices to make the graph Eulerian.
duplicate_shortest_path(grafo, from, to)duplicate_shortest_path(grafo, from, to)
grafo |
An igraph object representing the network. |
from |
Starting vertex name or index. |
to |
Destination vertex name or index. |
An updated igraph object containing duplicated edges.
Computes an Eulerian circuit on an Eulerian multigraph using Fleury's algorithm.
fleury_path(grafo)fleury_path(grafo)
grafo |
An Eulerian igraph object. |
A character vector of visited vertices in order.
Computes the all-pairs shortest path distance matrix between odd-degree vertices using Dijkstra's algorithm.
get_dijkstra_matrix(grafo, nodos_impares)get_dijkstra_matrix(grafo, nodos_impares)
grafo |
An igraph object representing the network. |
nodos_impares |
A character or numeric vector of odd-degree vertices. |
A symmetric numeric distance matrix.
En R implementation of Edmonds' Blossom algorithm (1965) for minimum weight perfect matching on complete graphs. Uses primal-dual potential adjustments, LCA detection, and blossom contraction/expansion.
get_optimal_matching(matriz_dist)get_optimal_matching(matriz_dist)
matriz_dist |
A symmetric numeric matrix of shortest path distances. |
A data.frame with columns n1, n2, and coste.
Finds all vertices with an odd degree in a given undirected graph.
odd_vertices(grafo)odd_vertices(grafo)
grafo |
An igraph object representing the network. |
A character vector with the names of vertices with odd degree.
Draws the complete graph of shortest-path distances between odd vertices.
plot_matching(matriz_dist, matching_df, main = "Optimal Blossom Matching")plot_matching(matriz_dist, matching_df, main = "Optimal Blossom Matching")
matriz_dist |
A square distance matrix. |
matching_df |
A data.frame from |
main |
Optional title. |
Invisibly returns the complete igraph object.
Master pipeline that executes full CPP resolution: odd-degree detection, shortest-path distance graph creation, minimum-weight matching, edge duplication, and Fleury Eulerian tour construction.
solve_cpp(grafo)solve_cpp(grafo)
grafo |
An undirected weighted igraph object. |
A list with the optimization results, including odd vertices, repair cost, total cost, matching pairs, and Eulerian route.
g <- igraph::make_ring(4) igraph::E(g)$weight <- c(10, 20, 15, 25) g <- igraph::add_edges(g, c(1, 3), attr = list(weight = 5)) solve_cpp(g)g <- igraph::make_ring(4) igraph::E(g)$weight <- c(10, 20, 15, 25) g <- igraph::add_edges(g, c(1, 3), attr = list(weight = 5)) solve_cpp(g)