Chinese postman problem python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

A Python implementation for Chinese Postman Problem with a limitation on the length of a single route based on heuristic algorithm

TruthZZ/Single-cost-limited-Chinese-Postman-Problem

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

A Python implementation for Chinese Postman Problem with a limitation on the length of a single route based on heuristic algorithm

The two csv files are the input data of the nodes and roads: nodes.csv records the longtitude, latitude and the serialnumber of the nodes; distance is represents the approximate length of the roads betwween nodes and is recorded in the form of matrix. The distance should be zero where there is no roads between nodes.

About

A Python implementation for Chinese Postman Problem with a limitation on the length of a single route based on heuristic algorithm

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

My Python solution to the Chinese-Postman problem.

License

supermitch/Chinese-Postman

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

I wrote this program to solve the Chinese Postman problem.

The Chinese Postman Problem, or «route inspection problem» is to find a shortest closed circuit that visits every edge of a (connected) undirected graph.

I was inspired to learn about and solve this problem when I thought it would be cool to follow every trail in Pacific Spirit Park in one run.

Given that the park contains over 73 km of trail, I need to find the optimum Eularian Path. Otherwise it’s going to be a really, really long run!

The solution is roughly a three-step process:

1. Determine if the graph has an Eularian Path (Very easy)
2. Make the non-Eularian graph Eularian, at the minimum expense (Not so easy)
3. Find the fudged Eularian path (Pretty easy)

In order to convert a non- or semi-Eularian graph to an Eularian one, you must eliminate odd nodes (nodes having an odd number of edges.)

To eliminate an odd node, you need to add another edge to it (essentially retracing your steps.) However, this comes as a cost! The goal then is to find out which edges to repeat, that eliminate all the odd nodes, with the minimum cost.

1. Find all possible combinations of pairs of odd nodes
2. Using Dijkstra’s Algorithm, find the cost of the minimum path between those pairs
3. Find which set of paths (depending on how many odd nodes you have) that results in the least total cost
4. Modify your graph with these new parallel edges

Now you have an Eularian graph with only even nodes, for which an Eularian Circuit can be found.

Solving the Eularian Circuit

Solving the Eularian Circuit (now that we have one) is relatively easy. At first, I simply walked the edges randomly until I happened to find a route that either dead-ended, or resulted in a circuit. Then I implemented Fleury’s Algorithm which says always choose a non-bridge over a bridge (for obvious reasons). Now it takes very few attempts to solve most circuits.

Later I will implement an alternative circuit finding method (Hierholzer’s?)

This program will probably run in Python 2.7 and definitely in Python 3.4-3.10 (Tested recently w/ Python 3.10.6.)

• Usage: python main.py -h
• Specify which graph to load by adding the graph name python main.py north
• Optionally specify the starting node, .e.g python main.py square 4 would produce [4, 3, 2, 1, 4] .

You can find all the graph names in the data/data.py file.

There are unit tests included, in the tests directory. You can run these via

from the root project folder.

• A graph is defined as a list containing tuples
• Each tuple in the list represents an edge
• Edges are defined as (start node, end node, length)

For example, an equilateral triangle like:

Could be represented as: triangle = [(1, 2, 1), (2, 3, 1), (3, 1 ,1)]

If an edge is directed you can add an optional fourth argument, True , e.g. (1, 2, 5, True) for a one-way edge from Node 1 to Node 2 of length 5.

See network.py for the actual implementation.

About

My Python solution to the Chinese-Postman problem.

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Python application to solve the Chinese postman problem

License

rkistner/chinese-postman

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

Readme.md

This is a Python program to solve the Chinese postman problem.

Python 3.x and QGIS 3.x is required for the plugin to run.

Download the «Chinese Postman Solver», using the QGIS plugin manager.

Manual Installation — Linux / OSX

Alternatively, run ./bundle.sh , and install the generated zip file as a plugin.

1. Select the layer for which you want to solve the CPP.
2. Select the features that you want to use. The «Select Features by Polygon» tool works great if you only want to use a small part of a large network.
3. Run Plugins -> Chinese Postman -> Chinese Postman.

It should create a new layer with the results.

• Python2.7 or Python 3.x
• NetworkX
• Optionally, if you want to export PNG images from the command line (not needed for using the QGIS-plugin):
  • Graphviz, and
  • One of:
    • For all NetworkX versions except 1.10: PyGraphviz (preferred), or
    • For NetworkX =2.0: pydot, or
    • For NetworkX 1.10 and 1.11: PyDotPlus

    Input data file must be in CSV format, with each row containing the following columns:

    • Start node ID
    • End node ID
    • Segment length in meters
    • Segment name or ID
    • Start longitude, for example 18.4167
    • Start latitude, for example -33.9167
    • End longitude
    • End latitude

    Start Node,End Node,Segment Length,Segment ID,Start Longitude,Start Latitude,End Longitude,End Latitude 1,13,57,Segment 1,18.4167,-33.9167,18.6532,-33.8561 13,22,80,Segment 2,18.6532,-33.8561,18.7650,-33.7930 

    Then run (assuming the file is saved as input.csv):

    python postman.py --csv path.csv --gpx path.gpx input.csv 

    The segment ID and GPS coordinates in the input file are not used for any calculations, but are used for the CSV and GPX output.

    Use option —png to create a graph visualization of the route in PNG image format:

    python postman.py --csv path.csv --gpx path.gpx --png path.png input.csv 

    All code is licensed under The MIT License (MIT).

    Источник

    Saved searches

    Use saved searches to filter your results more quickly

    You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

    Simple Chinese Postman/Route Inspection Problem algorithm written in Python 3.x

    License

    jgspires/chinese-postman-problem

    This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

    Name already in use

    A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

    Sign In Required

    Please sign in to use Codespaces.

    Launching GitHub Desktop

    If nothing happens, download GitHub Desktop and try again.

    Launching GitHub Desktop

    If nothing happens, download GitHub Desktop and try again.

    Launching Xcode

    If nothing happens, download Xcode and try again.

    Launching Visual Studio Code

    Your codespace will open once ready.

    There was a problem preparing your codespace, please try again.

    Latest commit

    Git stats

    Files

    Failed to load latest commit information.

    README.md

    Simple Chinese Postman/Route Inspection Problem algorithm written in Python 3.x.

    Contains all of the source code pertaining to the application.

    Contains images of the original graphs whose route inspection problems are solved and outputed by this application. Should be useful if comparison is needed between graph objects contained in the application and their respective image-based representations.

    The application can be executed as is from the ‘app.py’ file located in the src folder. Any number of new graphs can be created, changed or removed by editing the ‘app.py’ for any required customization. If the ‘app.py’ file is not edited, three default graphs will be outputted as exemples (their images are found in the Graph Exemples folder).

    This project is licensed under the MIT License — see the LICENSE.md file for details.

    About

    Simple Chinese Postman/Route Inspection Problem algorithm written in Python 3.x

    Источник