EdgesArrayGraphUtil.cs 8.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. namespace SAGA.DotNetUtils.Data
  7. {
  8. public static class EdgesArrayGraphUtil
  9. {
  10. /// <summary>
  11. /// 串联处理
  12. /// </summary>
  13. /// <typeparam name="V"></typeparam>
  14. /// <typeparam name="VD"></typeparam>
  15. /// <typeparam name="E"></typeparam>
  16. /// <typeparam name="ED"></typeparam>
  17. /// <param name="edgesArray"></param>
  18. /// <returns></returns>
  19. public static EdgesArrayGraph<V, VD, E, ED> ParallelHandle<V, VD, E, ED>(EdgesArrayGraph<V, VD, E, ED> edgesArray) where V : EAVertex<VD>,new() where E : EAEdge<ED>,new ()
  20. {
  21. var edges = edgesArray.GetLastStateEdges();
  22. VisitControl map = new VisitControl();
  23. ForwardStar<V, VD,E, ED> fs = new ForwardStar<V, VD,E, ED>();
  24. var ids = edges.SelectMany(e => new List<string>() { e.StartVertex, e.EndVertex }).Distinct();
  25. ids.ToList().ForEach(id =>
  26. {
  27. var tempV = edgesArray.FindVertex(id);
  28. if (tempV != null)
  29. {
  30. fs.AddVertex(tempV);
  31. }
  32. });
  33. fs.AddEdges(edges);
  34. for (int i = 0; i < edges.Count; i++)
  35. {
  36. var edge = edges[i];
  37. if (map.GetHandled(edge))
  38. continue;
  39. var refEdges = fs.GetEdges(edge.StartVertex, edge.EndVertex,true);
  40. if (refEdges.Count > 1)
  41. {
  42. E newEdge = new E();
  43. newEdge.StartVertex = edge.StartVertex;
  44. newEdge.EndVertex = edge.EndVertex;
  45. newEdge.Children.AddRange(refEdges);
  46. newEdge.EdgeType = EAEdgeType.Parallel;
  47. edgesArray.AddEdge(newEdge);
  48. //对象为键值
  49. refEdges.ForEach(e => map.SetHandled(e, true));
  50. }
  51. }
  52. return edgesArray;
  53. }
  54. /// <summary>
  55. /// 并联处理
  56. /// </summary>
  57. /// <typeparam name="V"></typeparam>
  58. /// <typeparam name="VD"></typeparam>
  59. /// <typeparam name="E"></typeparam>
  60. /// <typeparam name="ED"></typeparam>
  61. /// <param name="edgesArray"></param>
  62. /// <returns></returns>
  63. public static EdgesArrayGraph<V, VD, E, ED> SeriesHandle<V, VD, E, ED>(EdgesArrayGraph<V, VD, E, ED> edgesArray) where V : EAVertex<VD>, new() where E : EAEdge<ED>,new ()
  64. {
  65. var edges = edgesArray.GetLastStateEdges();
  66. VisitControl map = new VisitControl();
  67. ForwardStar<V, VD, E, ED> fs = new ForwardStar<V, VD, E, ED>();
  68. var ids = edges.SelectMany(e => new List<string>() { e.StartVertex, e.EndVertex }).Distinct();
  69. ids.ToList().ForEach(id =>
  70. {
  71. var tempV = edgesArray.FindVertex(id);
  72. if (tempV != null)
  73. {
  74. fs.AddVertex(tempV);
  75. }
  76. });
  77. fs.AddEdges(edges);
  78. for (int i = 0; i < edges.Count; i++)
  79. {
  80. var edge = edges[i];
  81. if (map.GetHandled(edge))
  82. {
  83. continue;
  84. }
  85. map.SetHandled(edge, true);
  86. var refEdges = fs.GetEdges(edge.StartVertex, edge.EndVertex, true);
  87. if (refEdges.Count > 1)
  88. {
  89. continue;
  90. }
  91. List<string> ends = new List<string>();//端点信息
  92. List<E> useEdges = new List<E>() { edge };
  93. List<string> searchVertexes = new List<string>() { edge.StartVertex, edge.EndVertex };
  94. for (int k = 0; k < searchVertexes.Count; k++)
  95. {
  96. var useId = searchVertexes[k];
  97. bool isStart = k != 0;
  98. //按照有向信息计算
  99. var tempEdges = fs.GetEdges(useId, isStart);
  100. while (tempEdges.Count == 1)
  101. {
  102. var tempEdge = tempEdges[0];
  103. if (tempEdge == null || map.GetHandled(tempEdge) || useEdges.Any(d => d.Id == tempEdge.Id))
  104. break;
  105. if (k == 0)
  106. {
  107. useEdges.Insert(0, tempEdge);
  108. }
  109. else
  110. {
  111. useEdges.Add(tempEdge);
  112. }
  113. map.SetHandled(tempEdge, true);
  114. useId = tempEdge.GetAnotherVertex(useId);
  115. tempEdges = fs.GetEdges(useId, isStart);
  116. }
  117. ends.Add(useId);
  118. }
  119. if (useEdges.Count != 1)
  120. {
  121. E newEdge = new E();
  122. newEdge.StartVertex = ends[0];
  123. newEdge.EndVertex = ends[1];
  124. newEdge.Children.AddRange(useEdges);
  125. newEdge.EdgeType = EAEdgeType.Series;
  126. edgesArray.AddEdge(newEdge);
  127. }
  128. }
  129. return edgesArray;
  130. }
  131. /// <summary>
  132. /// 拓扑分析;串并联迭代处理
  133. /// </summary>
  134. /// <typeparam name="V"></typeparam>
  135. /// <typeparam name="VD"></typeparam>
  136. /// <typeparam name="E"></typeparam>
  137. /// <typeparam name="ED"></typeparam>
  138. /// <param name="edgesArray"></param>
  139. /// <returns></returns>
  140. public static EdgesArrayGraph<V, VD, E, ED> GplotAnalyse<V, VD, E, ED>(EdgesArrayGraph<V, VD, E, ED> edgesArray) where V : EAVertex<VD>, new() where E : EAEdge<ED>,new ()
  141. {
  142. var preCount = edgesArray.GetLastStateEdges().Count;
  143. do
  144. {
  145. edgesArray = SeriesHandle(edgesArray);
  146. var current = edgesArray.GetLastStateEdges().Count;
  147. if (current == 1)
  148. break;
  149. edgesArray = ParallelHandle(edgesArray);
  150. current = edgesArray.GetLastStateEdges().Count;
  151. if (current == 1)
  152. break;
  153. if (current == preCount)
  154. break;
  155. preCount = current;
  156. } while (true);
  157. return edgesArray;
  158. }
  159. public static List<PathNodes<V, E>> GetPaths<V, VD, E, ED>(this EdgesArrayGraph<V, VD, E, ED> edgesArray, V start, Predicate<V> endPredicate) where V : EAVertex<VD>, new() where E : EAEdge<ED>, new()
  160. {
  161. List<PathNodes<V, E>> list = new List<PathNodes<V, E>>();
  162. var edges = edgesArray.GetOutEdges(start.Id);
  163. foreach (var edge in edges)
  164. {
  165. var anotherId = edge.GetAnotherVertex(start.Id);
  166. var v=edgesArray.FindVertex(anotherId)?.GetRoot() as V;
  167. if (v == null)
  168. continue;
  169. if (endPredicate != null && endPredicate(v))
  170. {
  171. PathNodes<V, E> nodes = new PathNodes<V, E>();
  172. nodes.Add(new PathNode<V, E>(v, edge));
  173. list.Add(nodes);
  174. }
  175. else
  176. {
  177. var nextList = GetPaths(edgesArray, v, endPredicate);
  178. foreach (var next in nextList)
  179. {
  180. next.Insert(0, new PathNode<V, E>(v, edge));
  181. }
  182. }
  183. }
  184. return list;
  185. }
  186. }
  187. public class PathNode<V,E>
  188. {
  189. public PathNode()
  190. {
  191. }
  192. public PathNode(V end, E path)
  193. {
  194. NextNode = end;
  195. Path = path;
  196. }
  197. public V NextNode { get; set; }
  198. public E Path { get; set; }
  199. }
  200. public class PathNodes<V,E>:List<PathNode<V, E>>
  201. { }
  202. }