in GraphLayout/MSAGL/Layout/LargeGraphLayout/LgInteractor.cs [250:388]
private static void ComputePathSimplification(Tiling g, Stopwatch stopwatch, List<Tiling> graphs)
{
Dictionary<int,int> cycle = new Dictionary<int, int>();
stopwatch.Start();
foreach (Tiling graph in graphs)
{
//find all degree two vertices.
List<int> Deg2Vertices = new List<int>();
for (int j = graph.N; j < graph.NumOfnodes; j++)
{
if (graph.DegList[j] == 2) Deg2Vertices.Add(j);
graph.VList[j].Visited = false;
}
foreach (int w in Deg2Vertices)
{
if (graph.VList[w].Visited) continue;
//find the one end of the path
int currentVertexId = w;
int oldVertexId = -1;
cycle[w] = 1;
while (graph.DegList[currentVertexId] == 2 && currentVertexId >= g.N)
{
int neighbor1 = graph.EList[currentVertexId, 0].NodeId;
;
int neighbor2 = graph.EList[currentVertexId, 1].NodeId;
;
if (oldVertexId != neighbor1)
{
oldVertexId = currentVertexId;
currentVertexId = neighbor1;
}
else if (oldVertexId != neighbor2)
{
oldVertexId = currentVertexId;
currentVertexId = neighbor2;
}
if (cycle.ContainsKey(currentVertexId))
{
cycle.Clear();
break;
}
cycle.Add(currentVertexId, 1);
}
if (cycle.Count == 0) continue;
//find the path from this end
var tempId = oldVertexId;
oldVertexId = currentVertexId;
currentVertexId = tempId;
List<int> path = new List<int>();
path.Add(oldVertexId);
path.Add(currentVertexId);
graph.VList[oldVertexId].Visited = true;
graph.VList[currentVertexId].Visited = true;
//find the path and add it into a list
while (graph.DegList[currentVertexId] == 2 && currentVertexId >= g.N)
{
int neighbor1 = graph.EList[currentVertexId, 0].NodeId;
;
int neighbor2 = graph.EList[currentVertexId, 1].NodeId;
;
if (oldVertexId != neighbor1)
{
oldVertexId = currentVertexId;
currentVertexId = neighbor1;
}
else if (oldVertexId != neighbor2)
{
oldVertexId = currentVertexId;
currentVertexId = neighbor2;
}
path.Add(currentVertexId);
graph.VList[currentVertexId].Visited = true;
}
int[] pathVertices = path.ToArray();
Point[] PointList = new Point[path.Count];
int q = 0;
foreach (int vertex in path)
{
PointList[q++] = new Point(graph.VList[vertex].XLoc, graph.VList[vertex].YLoc);
}
LocalModifications.PolygonalChainSimplification(PointList, 0, PointList.Length - 1, 1000);
//Modify graph according to the simplified path
for (int currentPoint = 0; currentPoint < PointList.Length - 1;)
{
int nextPoint = currentPoint + 1;
for (; nextPoint < PointList.Length; nextPoint++)
{
if (PointList[nextPoint].X == -1)
{
//jyoti: RemoveEdge was added to make things fast
graph.RemoveEdge(pathVertices[nextPoint], pathVertices[nextPoint - 1]);
continue;
}
//jyoti: RemoveEdge was added to make things fast
graph.RemoveEdge(pathVertices[nextPoint], pathVertices[nextPoint - 1]);
break;
}
if (nextPoint < PointList.Length)
{
//////graph.AddEdge(pathVertices[nextPoint], pathVertices[currentPoint]);
int left = currentPoint;
int right = nextPoint;
while (graph.noCrossings(pathVertices, pathVertices[left], pathVertices[right]) == false &&
left < right)
{
left++;
right--;
}
if (left < right)
{
//connect each path vertrex in between to this path
for (int index = left + 1; index < right; index++)
{
Vertex intermediateVertex = graph.VList[pathVertices[index]];
Vertex leftVertex = graph.VList[pathVertices[left]];
Vertex rightVertex = graph.VList[pathVertices[right]];
Point p = PointToSegmentDistance.getClosestPoint
(leftVertex, rightVertex, intermediateVertex);
intermediateVertex.PreciseX = p.X;
intermediateVertex.PreciseY = p.Y;
intermediateVertex.LeftX = leftVertex.XLoc;
intermediateVertex.LeftY = leftVertex.YLoc;
intermediateVertex.RightX = rightVertex.XLoc;
intermediateVertex.RightY = rightVertex.YLoc;
}
}
currentPoint = nextPoint;
}
}
}
}
}