Click here to Skip to main content
15,867,686 members
Articles / Database Development / Data Visualization

Millenium Problem Solved ?!

Rate me:
Please Sign up or sign in to vote.
4.86/5 (50 votes)
7 Jan 2023CPOL6 min read 97.4K   585   38   83
Implementation of a polynomial time algorithm searching Hamilton cycles in an undirected graph

Update Info

The code was updated.

  • Now the application allows testing the validity of a path for being a Hamiltonian cycle of the current graph. The current graph is the graph which was opened from file or created by hand. See the class CycleTester and its usage.
  • The path may be read from a *.path-file or *.txt-file (see the button 'Open Ham Path'). This file must contain a succession of comma separated (or space separated) numbers of graph nodes. Nodes numbering starts with zero.
  • One more view mode was added (click 'Switch View' button several times).

Introduction

Most of you heard about Seven Millennium Prize Problems established by (The Clay Mathematics Institute of Cambridge) with $1 million allocated to the solution of each problem. It seems that one of these problems was solved by professor (Lizhi Du), Wuhan University of Science, China.

Background

I read his article a year ago, but could not decipher the logic of the algorithm (and for sure, I doubted the real success). Later, I tried to implement the algorithm but after some efforts gave up. Unfortunately, the author does not open his C++ code.

There is a great advantage of being a teacher - you can give a task to a student, and if he happens to have an exceptional mind (moreover, a great patience, belief in his own abilities, belief that a teacher does not doubt a success), then you can win. And this happened to me and my student Ivan Fedorov. He worked very hard for a month (or more), putting aside all other obligations and finally succeeded. He managed to get the logic of written words (description of the algorithm that you can find using the link above) and convert it to a working code. But first, you should be sure that the solution is possible.

Main Idea

The main idea of Prof. Lizhi Du's approach is to present a graph (any undirected graph) as a ring of nodes (see Fig.1) and try to mend the breaks in successive chain of nodes. A break (or breakpoint by the author's terminology) is the absence of an edge between two neighboring nodes (along the ring chain).

Breaks

If you managed to mend all the breaks, then Hamiltonian cycle is found. It is just the succession of nodes along the ring. Long ago, I developed an app that allows to redraw any graph in a RingView fashion and drag its nodes all over. If you try (using the application which accompanies this article) to intuitively drag the nodes of some graph trying to mend all the breaks, quite often, you can succeed.

See Fig.2 where one break was mended by dragging down the node #8 (compare Fig.1 and Fig.2).

Image 2

Fig.3. shows the final result of mending all the breaks by dragging several nodes. Compare Fig.3 and Fig.1. Pay attention to nodes' numbers. Consider the fact that while dragging, you don't change the graph structure (or adjacency matrix). As you see, all the breaks were mended and now we have a Hamiltonian cycle (it is the succession of nodes along the ellipsoidal ring).

Image 3

This kind of exercise made me believe that Prof. Lizhi Du's approach is quite reasonable. Showing this trick to Ivan Fedorov, I made him believe that the solution is near. All you have to do is to convert intuitive dragging manipulations to some strict programming logic. Oh, don't forget to use the description of the Lizhi Du's algorithm on several pages of PDF document.

Inspired by this logic, Ivan started working. The resulting code turned out to be very impressive in a sense that it worked! But it was not so good in a sense that it was compressed into two big functions with many repetitions and very-hard-to-follow logic. After two days pondering of over the problem and wrestling with the code, I hope the code became more readable and manageable. Now it is encapsulated in a class that has eight methods (each of them implements a separate step of the algorithm). The code works a little faster than the original (two functions approach).

Points of Interest

Even now, I am not sure that can clearly explain all the magic (especially the logic of methods named TrySecond, TryThird and CutAndInsert). I think I perceived and can explain the rotational technique used to change the graph structure, but nevertheless I am not 100% sure that I could explain all the actions. Ivan says that he shares my opinion in spite of the fact that it was he who resurrected the code from honest but rather verbose Lizhi Du's document (see the link to his article above).

Code Usage

Data files have an extension '*.gv' (GraphView Files). It is the simplest format (the list of adjacent nodes for each of the graph nodes). If you change the filter in OpenFileDialog to '*.hcp', you can open many of the existing in the net graph files. The format of such files is very simple -- a list of edges (pairs of connected nodes). I placed only two such files in Data folder of the project. The file named 'TestGraph_11_4.hcp' does not contain Hamiltonian cycle, but prof. Lizhi Du has found a Hamiltonian path in this graph. Note, our implementation does not search for Hamiltonian paths (only cycles are at stake).

While playing with the application, first open a file (Ctrl+O) with the small digit prefixes and try to use older known algorithms (Posa, Roberts and Flores, Recursive Backtracking). They were implemented by me several years ago. By the way, Posa's algorithm does not always finds the solution, for it selects nodes randomly (description of algorithm is here). Try it several times on simple graphs and it sometimes will find a solution (may be different each time). More capable, but not so fast, is the algorithm created by Roberts and Flores (you may find its description in the net). It surely will find a Hamiltonian cycle or will give a message that one does not exist.

You can circularly toggle the currently selected algorithm by pressing right arrow key. Press space to start the search. You also can see the inner cooking (details) of searching algorithm by setting a delay of animation (use toolstrip button with the tooltip: Change Animation Delay). Don't forget to set the delay time to zero when you open some bigger graphs (the files, after 09 Knight.gv). This graph corresponds to the famous Knight's tour problem which is mentioned in Wikipedia. In order to see the essence of Lizhi Du's algorithm (and the purpose of this article), do the following steps:

  • Open the file 09 Knight.gv,
  • Select the algorithm RobertsFlores
  • Clear the delay (use button Change Animation Delay).
  • Press space and go drink some coffee. Computer will be looking for the solution for several hours because it requires billions of backtracking steps.
  • Stop the algorithm (use toolstrip button Stop the search) if you don't want to wait.
  • Select the algorithm LizhiDu and press spacebar.

The solution will be found instantly (if you did not forget to clear the delay). The algorithm requires only 234 steps. That's fantastic!

Conclusion

If the Math community will adopt professor Lizhi Du's proof of the solution, the famous P vs NP Problem, then as (the authorities warn us), all Public Key RSA cryptosystems will go down. Should it be troubling news for us? I don't know, I always neglected security problems. The mathematicians would have to invent something new.

History

  • 21st May, 2017: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Instructor / Trainer Peter the Great St.Petersburg Polytechnic Universi
Russian Federation Russian Federation
Peter the Great St. Petersburg Polytechnic University professor,
Microsoft Authorized Educational Center trainer,
Microsoft Certified Professional (C# Desktop Apps and MFC)
Lectures on OOP, C# and C++, Windows programming with C# and C++.
Have long practice and experience in finding the right way to formulate and numerically solve differential equations.

Comments and Discussions

 
QuestionThanks for the new input Pin
Member 1462903820-Oct-19 8:24
Member 1462903820-Oct-19 8:24 
BugRegarding wrong output from exe file Pin
Member 1069906312-Jul-18 3:51
Member 1069906312-Jul-18 3:51 
GeneralRe: Regarding wrong output from exe file Pin
Jan Heckman23-Jan-23 9:39
professionalJan Heckman23-Jan-23 9:39 
QuestionA famous German man has a paper on arxiv said: P!=NP, my oppinion Pin
Lizhi Du17-Aug-17 16:49
Lizhi Du17-Aug-17 16:49 
SuggestionHi, every friends: PinPopular
Lizhi Du2-Jul-17 23:20
Lizhi Du2-Jul-17 23:20 
Hi, every friends:
Thank you for your attention.
Firstly, I am very sorry that I do not open my code now. The main reason is: I really do not have a formal code. My code only serves for my thinking of the algorithm and proof. Also I am not a good programmer. So my code is terribly unreadable. It is only for me.
I do not know C#. So I do not understand this code here, cannot compile it and run it. But I just read one part of the code (LizhDu.cs).
I think:
1, this code is too easy and too short. Mine is much longer and much harder.
2, this code only remember breaks (of two vertices), not main segment (of four vertices).
3,this code only has one hc ( mine has a search tree, i.e., I remember a lot of hc).
4,this code does not remember the repeating paths, main segments on the repeating path can be repeated one time later, i.e., this code does not handle the two problems I stated in my paper.
So I suppose that for some really hard graphs, this code may not get a correct result, probably.
I will be very sorry if my understanding of this code is wrong.
I think Mr. Wang, xiaolong had a code. It may be like this. Also I had a code a lot of years ago, which is like this.
Thanks to everybody, thanks to Prof. and his that student. I will be very happy if anyone can give your doubt about this algorithm and proof and the code to me, and discuss with me. For me, I think I wrote completely in the paper (the last version), so I wish your attention on it and discuss it with you.
Sincerely,
Lizhi Du
QuestionLet's test it on other NP complete problems Pin
Claude Chaunier22-Jun-17 5:56
Claude Chaunier22-Jun-17 5:56 
AnswerRe: Let's test it on other NP complete problems Pin
Lizhi Du22-Jun-17 22:26
Lizhi Du22-Jun-17 22:26 
GeneralRe: Let's test it on other NP complete problems Pin
Yang Kok Wah23-Jun-17 1:24
Yang Kok Wah23-Jun-17 1:24 
GeneralRe: Let's test it on other NP complete problems Pin
Lizhi Du23-Jun-17 2:27
Lizhi Du23-Jun-17 2:27 
GeneralRe: Let's test it on other NP complete problems Pin
Claude Chaunier23-Jun-17 6:01
Claude Chaunier23-Jun-17 6:01 
GeneralRe: Let's test it on other NP complete problems Pin
Lizhi Du23-Jun-17 11:39
Lizhi Du23-Jun-17 11:39 
GeneralRe: Let's test it on other NP complete problems Pin
Claude Chaunier24-Jun-17 3:10
Claude Chaunier24-Jun-17 3:10 
GeneralRe: Let's test it on other NP complete problems Pin
Lizhi Du23-Jun-17 2:18
Lizhi Du23-Jun-17 2:18 
GeneralRe: Let's test it on other NP complete problems Pin
Lizhi Du23-Jun-17 2:23
Lizhi Du23-Jun-17 2:23 
GeneralRe: Let's test it on other NP complete problems Pin
Claude Chaunier24-Jun-17 4:02
Claude Chaunier24-Jun-17 4:02 
GeneralRe: Let's test it on other NP complete problems Pin
Claude Chaunier24-Jun-17 4:42
Claude Chaunier24-Jun-17 4:42 
GeneralRe: Let's test it on other NP complete problems Pin
Lizhi Du24-Jun-17 12:31
Lizhi Du24-Jun-17 12:31 
SuggestionThank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Lizhi Du21-Jun-17 2:36
Lizhi Du21-Jun-17 2:36 
GeneralRe: Thank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Yang Kok Wah21-Jun-17 3:41
Yang Kok Wah21-Jun-17 3:41 
GeneralRe: Thank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Lizhi Du21-Jun-17 4:02
Lizhi Du21-Jun-17 4:02 
GeneralRe: Thank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Member 1139809425-Jun-17 0:27
Member 1139809425-Jun-17 0:27 
GeneralRe: Thank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Lizhi Du25-Jun-17 1:12
Lizhi Du25-Jun-17 1:12 
GeneralRe: Thank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Lizhi Du2-Jul-17 23:23
Lizhi Du2-Jul-17 23:23 
GeneralRe: Thank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Member 113980945-Jul-17 13:47
Member 113980945-Jul-17 13:47 
GeneralRe: Thank you, Professor Alexander Chernosvitov. I am Lizhi Du: https://www.researchgate.net/post/Algorithm_and_program_Is_the_problem_NP_vs_P_solved Pin
Lizhi Du5-Jul-17 17:15
Lizhi Du5-Jul-17 17:15 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.