EdgesArrayGraphUtil.cs 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296
  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. /// <summary>
  160. /// 查找相关联的路径信息,该方法如果传入的图不是有向无环图,则不能获取到正确结果【不建议使用】
  161. /// </summary>
  162. /// <typeparam name="V"></typeparam>
  163. /// <typeparam name="VD"></typeparam>
  164. /// <typeparam name="E"></typeparam>
  165. /// <typeparam name="ED"></typeparam>
  166. /// <param name="edgesArray"></param>
  167. /// <param name="start"></param>
  168. /// <param name="endPredicate"></param>
  169. /// <returns></returns>
  170. 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()
  171. {
  172. List<PathNodes<V, E>> list = new List<PathNodes<V, E>>();
  173. var edges = edgesArray.GetOutEdges(start.Id);
  174. foreach (var edge in edges)
  175. {
  176. var anotherId = edge.GetAnotherVertex(start.Id);
  177. var v=edgesArray.FindVertex(anotherId)?.GetRoot() as V;
  178. if (v == null)
  179. continue;
  180. if (endPredicate != null && endPredicate(v))
  181. {
  182. PathNodes<V, E> nodes = new PathNodes<V, E>();
  183. nodes.Add(new PathNode<V, E>(v, edge));
  184. list.Add(nodes);
  185. }
  186. else
  187. {
  188. var nextList = GetPaths(edgesArray, v, endPredicate);
  189. foreach (var next in nextList)
  190. {
  191. next.Insert(0, new PathNode<V, E>(v, edge));
  192. }
  193. list.AddRange(nextList);
  194. }
  195. }
  196. return list;
  197. }
  198. /// <summary>
  199. /// 获取指定起点,到指定条件的节点路径信息;(建议使用)
  200. /// </summary>
  201. /// <typeparam name="V"></typeparam>
  202. /// <typeparam name="VD"></typeparam>
  203. /// <typeparam name="E"></typeparam>
  204. /// <typeparam name="ED"></typeparam>
  205. /// <param name="edgesArray"></param>
  206. /// <param name="start"></param>
  207. /// <param name="endPredicate"></param>
  208. /// <returns></returns>
  209. public static List<PathNodes<V, E>> GetPaths2<V, VD, E, ED>(
  210. this EdgesArrayGraph<V, VD, E, ED> edgesArray, V start,Predicate<V> endPredicate)
  211. where V : EAVertex<VD>, new() where E : EAEdge<ED>, new()
  212. {
  213. PathNodes<V, E> prePath = new PathNodes<V, E>();
  214. prePath.Add(new PathNode<V, E>(start, null));
  215. var paths = InternalGetPaths(edgesArray, start, prePath, endPredicate);
  216. paths.ForEach(p => p.RemoveAt(0));
  217. return paths;
  218. }
  219. internal static List<PathNodes<V, E>> InternalGetPaths<V, VD, E, ED>(this EdgesArrayGraph<V, VD, E, ED> edgesArray, V start, PathNodes<V, E> prePath,Predicate<V> endPredicate) where V : EAVertex<VD>, new() where E : EAEdge<ED>, new()
  220. {
  221. List<PathNodes<V, E>> list = new List<PathNodes<V, E>>();
  222. var edges = edgesArray.GetOutEdges(start.Id);
  223. foreach (var edge in edges)
  224. {
  225. var anotherId = edge.GetAnotherVertex(start.Id);
  226. var v = edgesArray.FindVertex(anotherId)?.GetRoot() as V;
  227. if (v == null)
  228. continue;
  229. if (prePath.Count > 1 && prePath[prePath.Count - 1].NextNode.Id == anotherId)
  230. {
  231. //或者不进行数量判断,但要对NextNode进行非空判断
  232. continue;
  233. }
  234. if ((prePath.Any(n => n.NextNode.Id == anotherId)) ||(endPredicate != null && endPredicate(v)))
  235. {
  236. PathNodes<V, E> nodes = new PathNodes<V, E>(prePath);
  237. nodes.Add(new PathNode<V, E>(v, edge));
  238. list.Add(nodes);
  239. }
  240. else
  241. {
  242. var newPath = new PathNodes<V, E>(prePath);
  243. newPath.Add(new PathNode<V, E>(v, edge));
  244. var nextList = InternalGetPaths(edgesArray, v, newPath, endPredicate);
  245. list.AddRange(nextList);
  246. }
  247. }
  248. return list;
  249. }
  250. }
  251. public class PathNode<V,E>
  252. {
  253. public PathNode()
  254. {
  255. }
  256. public PathNode(V end, E path)
  257. {
  258. NextNode = end;
  259. Path = path;
  260. }
  261. public V NextNode { get; set; }
  262. public E Path { get; set; }
  263. /// <summary>
  264. /// 虚拟的开始节点,当路径为null时,认为是开始节点
  265. /// </summary>
  266. /// <returns></returns>
  267. public bool IsStart()
  268. {
  269. return Path == null;
  270. }
  271. }
  272. public class PathNodes<V, E> : List<PathNode<V, E>>
  273. {
  274. public PathNodes()
  275. {
  276. }
  277. public PathNodes(IEnumerable<PathNode<V, E>> nodes)
  278. {
  279. this.AddRange(nodes);
  280. }
  281. }
  282. }