bloomr 0.1.2

Hybrid Blossom-Greedy approach for constructing Eulerian tours on real road graphs.

Bloomr

Solve the Mixed Chinese Postman Problem on real road networks. Find the shortest route that traverses every street at least once, handling both one-way and two-way streets.

Installation

pip install bloomr

Quick Start

from bloomr import solve_cpp

# Download road network and solve CPP
result = solve_cpp("Monaco")

# View solution
print(result.summary())  # Distance efficiency, route metrics
print(f"GPX route: {result.gpx_path}")

How It Works

Bloomr downloads road networks from OpenStreetMap, identifies degree imbalances caused by one-way streets, and computes near-optimal routes using a hybrid Blossom-Greedy matching approach:

1. Blossom algorithm finds optimal pairings for ~98% of imbalanced nodes
2. Greedy fallback handles remaining nodes when graph disconnectivity prevents full matching
3. Eulerian circuit generates the final route traversing all streets

This hybrid strategy preserves optimality where possible while gracefully handling real-world road network constraints.

API

solve_cpp()

solve_cpp(
    place: str = None,
    *,
    graphml_path: Path = None,
    output_dir: Path = None,
    network_type: str = "drive_service",
    simplify: bool = False,
    method: str = "blossom",
    verbose: bool = False,
    visualize: bool = True
)

Arguments:

• place: Location name (e.g., "Jersey, Channel Islands")
• graphml_path: Path to existing GraphML file (alternative to place)
• output_dir: Directory for output files (default: solutions/{region})
• network_type: OSMnx network type - "drive", "drive_service", "walk", "bike", or "all"
• simplify: Simplify graph topology (default: False)
• method: "blossom" (optimal, default) or "greedy" (fast approximation)
• verbose: Enable detailed logging from Rust solver
• visualize: Generate route visualization map (requires matplotlib, contextily)

Returns: CPPResult with gpx_path, metrics, and solution files

download_graph()

download_graph(
    place: str,
    *,
    output_dir: Path = None,
    network_type: str = "drive_service",
    simplify: bool = False,
    force: bool = False
) -> Path

Arguments:

• place: Location name for OSMnx (e.g., "San Francisco, California")
• output_dir: Directory for GraphML file (default: graphml_data)
• network_type: OSMnx network type - "drive", "drive_service", "walk", "bike", or "all"
• simplify: Simplify graph topology (default: False)
• force: Force re-download even if cached (default: False)

Returns: Path to saved GraphML file

Example:

from bloomr import download_graph

graph_path = download_graph("San Francisco, California")
result = solve_cpp(graphml_path=graph_path)

Output

Solutions are saved to solutions/{region}/:

• {region}_cpp_route.gpx - GPS-ready route file
• {region}_metrics.json - Efficiency metrics and statistics

Metrics:

• distance_efficiency - Proportion of route that's useful coverage (not duplicated)
• duplication_ratio - Average times each street is traversed
• deadhead_percentage - Percentage of route spent repeating streets

Architecture

• Python: OSMnx integration, API, visualization
• Rust: Graph algorithms (Blossom, shortest paths, Eulerian circuits)