Mercurial > defical

annotate defical-sharp/libbacktrack/walk.cs @ 0:ebed2bd0d300

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial import from svn. History be damned.
author Edho P. Arief <me@myconan.net>
date Fri, 02 Apr 2010 23:11:57 +0700
parents
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
1 using System.Collections.Generic;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
2
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
3 namespace libbacktrack
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
4 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
5 public partial class Backtrack
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
6 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
7 private void walk()
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
8 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
9 if (this.myGraph.MinDef() <= this.myGraph.NumVerDef)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
10 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
11 this.isProcessing = true;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
12 walk(1);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
13 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
14 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
15 private void walk(int currentLevel)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
16 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
17 if (this.isProcessing)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
18 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
19 if (currentLevel >= this.myGraph.NumVerMain)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
20 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
21 if (this.myGraph.IsSemt())
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
22 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
23 if (!this.isRecurseAll)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
24 this.isProcessing = false;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
25 this.result += this.myGraph.Print(0);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
26 this.result += "\n" + this.myGraph.Print(1)+"\n";
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
27 this.isSemt = true;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
28 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
29 removeLabel(currentLevel - 1);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
30 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
31 else
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
32 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
33 List<int> availableLabels = new List<int>();
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
34 int start = 1, end = this.myGraph.NumVerTotal;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
35 if (currentLevel == 1 && this.firstLabel != this.myGraph.NumVerTotal)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
36 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
37 if (this.myGraph.GraphType == "wheel")
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
38 start = end; //optimization for wheel
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
39 else if (this.myGraph.GraphType == "doublefan")
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
40 start = this.firstLabel + 1; //optimization for doublefan
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
41 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
42 else if (this.pathStart != 0)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
43 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
44 if (currentLevel == this.pathEnd)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
45 start = this.pathLabel + 1; //remove possibility for reversed path labeling
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
46 else if (currentLevel == this.pathStart && start < end)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
47 end = this.myGraph.NumVerTotal - 1; //no need to test last label as it'll be checked already on all previous cases
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
48 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
49 for (int i = start; i <= end; i++)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
50 if (!this.labelVerUsed[i])
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
51 availableLabels.Add(i);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
52 if (availableLabels.Count > 0)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
53 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
54 for (int x = availableLabels.Count - 1; x >= 0; x--)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
55 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
56 if (currentLevel == this.pathStart && this.pathStart != 0)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
57 this.pathLabel = availableLabels[x];
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
58 if (this.myGraph.IsValidToLabel(currentLevel, availableLabels[x]))
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
59 {
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
60 setLabel(currentLevel, availableLabels[x]);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
61 walk(currentLevel + 1);
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
62 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
63 if (!this.isProcessing)
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
64 break;
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
65 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
66 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
67 if (currentLevel != 1) { removeLabel(currentLevel - 1); }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
68 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
69 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
70 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
71 }
ebed2bd0d300 Initial import from svn. History be damned.
Edho P. Arief <me@myconan.net>
parents:
diff changeset
72 }