GraphTraversal_CTU.cs
4.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TheMachine
{
public class GraphTraversal_CTU
{
public List<Point_CTU> PointCodes = new List<Point_CTU>();
// 用于存储单向联通的边
public List<(Point_CTU, Point_CTU)> oneWayEdges = new List<(Point_CTU, Point_CTU)>();
// 用于存储双向联通的边
public List<(Point_CTU, Point_CTU)> twoWayEdges = new List<(Point_CTU, Point_CTU)>();
public void Traverse(Point_CTU start)
{
Stack<Point_CTU> stack = new Stack<Point_CTU>();
stack.Push(start);
while (stack.Count > 0)
{
Point_CTU current = stack.Pop();
if (current.Visited)
continue;
current.Visited = true;
var up = ComputeCTUPoint(current, current.Up, "Up"); // 上
var down = ComputeCTUPoint(current, current.Down, "Down"); // 上
var left = ComputeCTUPoint(current, current.Left, "Left"); // 上
var right = ComputeCTUPoint(current, current.Right, "Right"); // 上
if (up != null)
{
current.Up.X = up.X;
current.Up.Y = up.Y;
}
if (down != null)
{
current.Down.X = down.X;
current.Down.Y = down.Y;
}
if (left != null)
{
current.Left.X = left.X;
current.Left.Y = left.Y;
}
if (right != null)
{
current.Right.X = right.X;
current.Right.Y = right.Y;
}
// 将未访问的邻近点压入栈中
if (current.Up != null && !current.Up.Visited)
stack.Push(current.Up);
if (current.Down != null && !current.Down.Visited)
stack.Push(current.Down);
if (current.Left != null && !current.Left.Visited)
stack.Push(current.Left);
if (current.Right != null && !current.Right.Visited)
stack.Push(current.Right);
}
}
private Point_CTU ComputeCTUPoint(Point_CTU from, Point_CTU to, string angle)
{
if (to == null)
return null;
//if (to.Id == 1709)
//{
// int tt = 1;
//}
Point_CTU point_CTU = new Point_CTU(from.X, from.Y, to.Id);
if (angle == "Up")
{
point_CTU.Y = point_CTU.Y + from.UpDistance;
PointCodes.Add(point_CTU);
to = point_CTU;
}
else if (angle == "Down")
{
point_CTU.Y = point_CTU.Y - from.DownDistance;
PointCodes.Add(point_CTU);
to = point_CTU;
}
else if (angle == "Left")
{
point_CTU.X = point_CTU.X - from.LeftDistance;
PointCodes.Add(point_CTU);
to = point_CTU;
}
else if (angle == "Right")
{
point_CTU.X = point_CTU.X + from.RightDistance;
PointCodes.Add(point_CTU);
to = point_CTU;
}
//if (point_CTU.Id == 1707)
//{
// int yy = 1;
//}
return to;
}
// 添加边到对应的列表中
private void AddEdges(Point_CTU from, Point_CTU to)
{
if (to == null)
return;
// 单向联通
if (from.Up == to || from.Down == to || from.Left == to || from.Right == to)
oneWayEdges.Add((from, to));
// 双向联通（如果两个点都互相指向对方）
if ((to.Up == from || to.Down == from || to.Left == from || to.Right == from) &&
!twoWayEdges.Contains((to, from))) // 避免重复添加
{
twoWayEdges.Add((from, to));
}
}
}
}