Stack Overflow
Stack Overflow

Questions tagged [chinese-postman]

Use this tag with finding the minimum cycle through every edge of a graph. This is also know as Eulerian Cycle.

References:

Eulerian Cycle/Chinese Postman - Stony Brook Algorithm Repository

15 questions
21
votes
7 answers

What's the difference between traveling salesman and chinese traveling?

What's the difference between travelling salesman problem (TSP) and Chinese postman problem (CPP)? For me, both wants go to a destination, and then back.
alansiqueira27
  • 8,129
  • 15
  • 67
  • 111
16
votes
1 answer

How should I generate the partitions / pairs for the Chinese Postman problem?

I'm working on a program for class that involves solving the Chinese Postman problem. Our assignment only requires us to write a program to solve it for a hard-coded graph but I'm attempting to solve it for the general case on my own. The part that…
anon
6
votes
5 answers

Minimal path - all edges at least once

I have directed graph with lot of cycles, probably strongly connected, and I need to get a minimal cycle from it. I mean I need to get cycle, which is the shortest cycle in graph, and every edge is covered at least once. I have been searching for…
joseph
  • 63
  • 1
  • 3
3
votes
1 answer

How to plan the most efficient route for patio lights Part 2

This is a continuation of some questions I posed earlier, How to plan the most efficient route for patio lights and Christmas Light Route Efficiency (CS), about my attempt to cover a screened-in structure with patio lights as efficiently as…
Travis Heeter
  • 13,002
  • 13
  • 87
  • 129
2
votes
0 answers

Shortest path to cover all edges, in non-weighted, directed graph

Well, I'm facing a problem with a small work I have in hands right now... The main goal is, having a given graph (without weights, and directed), I have to discover the group of paths(if possible, only one path, but they can be more) with minimum…
norim_13
  • 303
  • 2
  • 11
2
votes
0 answers

Algorithm for Chinese Postman where some edges are optional

I have a graph that contains edges that must be visited, as well as edges that are optional. The edges have varying weights and can be traveled in either direction and as many times as required. I am trying to determine the route that minimises the…
AdamDynamic
  • 761
  • 6
  • 15
  • 29
1
vote
1 answer

Solving Chinese Postman algorithm with eulerization

I'm would like to solve Chinese Postman problem in a graph where an eulerian cycle does not exist. So basically I'm looking for a path in a graph which visits every edge exactly once, and starts and ends at the same node. A graph will have an euler…
Tripy
  • 79
  • 1
  • 10
1
vote
1 answer

Hierholzer's algorithm for finding Eulerian Cycle Python

I am a beginner at Graph theory. I've been trying to implement Hierholzer's algorithm into code using Python since 5 days. My experience with graph theory is also 5 days so far. My codes are below: def cycle(D1): import random key =…
user4637416
1
vote
1 answer

Generating a connected graph and checking if it has eulerian cycle

So, I wanted to have some fun with graphs and now it's driving me crazy. First, I generate a connected graph with a given number of edges. This is the easy part, which became my curse. Basically, it works as intended, but the results I'm getting…
Maciej Zwierzchlewski
  • 19
  • 1
  • 1
  • 7
0
votes
0 answers

How to use SimSun-ExtB to bold chinese text

I need to make simsun(Chinese) words in bold font for my project(Themelyaf). For that , I have added simsunb.ttf in fonts file. Also, I have added in renderer as below: renderer.getFontResolver().addfont(FONTDIR+"simsunb.ttf", …
Jay
  • 1
  • 1
0
votes
1 answer

How to create an algorithm to find all possible pairings (referring to the chinese postman problem)?

When trying to solve the chinese postman problem you will have to find minimum cost of all possible pairings of all odd vertexes in the graph and add found edges (pairings), which my question is almost about. How to implement an algorithm, which…
corken
  • 19
  • 6
0
votes
1 answer

which one is more time complexity between TSP or CPP?

What's the difference between traveling-salesman problem and Chinese postman problem From a Time complexity perspective? I mean which one is more time complexity between TSP and CPP ?
Mohammad Reza
  • 1
  • 2
0
votes
2 answers

Can a non-oriented graph have more than one Eulerian cycle?

I know that my question is more about graphs than programming but, I like the community here which is very active and you guys may have work with graphs. So here Im wondering if the set of the Eulerian cycle of a non-oriented graph can contain more…
Indray
  • 19
  • 2
0
votes
1 answer

problems with eulerian cycle in a directed graph

so below is my code for finding if a graph has a eulerian cycle in a directed graph. The code works for several case(the commented lines in my main method works). But it does work for the g1 graph(the uncommented code in my main method) . it says…
user3137376
  • 1,527
  • 2
  • 19
  • 29
0
votes
2 answers

algorithm for Chinese postman circuit in a bidirected graph

Im looking for an algorithm that finds a Chinese postman circuit in a bidirected graph. Bidirected graph here is not the symmetric directed graph, but the graph introduced by Edmonds & Johnson in 1970. I found few papers that solved similar problem…
user2037661
  • 51
  • 3