EdgesArrayGraph.cs 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. namespace SAGA.DotNetUtils.Data
  5. {
  6. #region 概述
  7. /*
  8. * 有向图,和无向图,部分方法不同;
  9. *
  10. * 内部操作使用索引;功能扩展使用Data
  11. */
  12. #endregion
  13. /// <summary>
  14. /// 边集列表
  15. /// </summary>
  16. public class EdgesArrayGraph<V,VD,E,ED> : EdgesArrayBase<V, VD, E, ED> where V : EAVertex<VD> ,new() where E : EAEdge<ED>,new()
  17. {
  18. public EdgesArrayGraph()
  19. {
  20. }
  21. #region 控制属性
  22. /// <summary>
  23. /// 表示该图信息是否是有向的
  24. /// </summary>
  25. public bool IsDirection { get; set; }
  26. #endregion
  27. #region 编号系统
  28. private int m_CurrentVertexIndex;
  29. /// <summary>
  30. /// 生成节点索引
  31. /// </summary>
  32. /// <returns></returns>
  33. private string GenerateVertexIndex()
  34. {
  35. return "V" + (++m_CurrentVertexIndex);
  36. }
  37. /// <summary>
  38. /// 生成节点索引
  39. /// </summary>
  40. /// <returns></returns>
  41. private string GenerateEdgeIndex()
  42. {
  43. return "E" + (++m_CurrentVertexIndex);
  44. }
  45. #endregion
  46. #region 点操作
  47. #region 查找点
  48. /// <summary>
  49. /// 根据顶点Id查询相应的节点
  50. /// </summary>
  51. /// <param name="vertexId"></param>
  52. /// <returns></returns>
  53. public virtual V FindVertex(string vertexId)
  54. {
  55. if (string.IsNullOrWhiteSpace(vertexId))
  56. {
  57. return null;
  58. }
  59. if (this.m_Vertexes.Contains(vertexId))
  60. {
  61. return this.m_Vertexes[vertexId];
  62. }
  63. return null;
  64. }
  65. /// <summary>
  66. /// 根据顶点Id查询相应的节点
  67. /// </summary>
  68. /// <param name="v">根据顶点信息去检索点</param>
  69. /// <returns></returns>
  70. public virtual V FindVertex(V v)
  71. {
  72. /*
  73. * 待改进:id快索引,IsMatch值匹配慢索引
  74. */
  75. var useV = FindVertex(v.Id) ?? this.Vertexes.FirstOrDefault(c => c.IsMatch(v));
  76. return useV;
  77. }
  78. #endregion
  79. #region 增加点
  80. /// <summary>
  81. /// 增加顶点
  82. /// </summary>
  83. /// <param name="vertex"></param>
  84. /// <returns></returns>
  85. public virtual V AddVertex(V vertex)
  86. {
  87. if (vertex == null)
  88. return null;
  89. V result = vertex;
  90. //var useVertex = FindVertex(vertex);
  91. /*如果是集合形式的比较,相等不传递。比如List1与List2兼容,List2与List3兼容,不能推导出List1与List3兼容
  92. 综合考虑,不在基类做这种数据的处理,而是直接插入点
  93. */
  94. vertex.Id = GenerateVertexIndex();
  95. this.m_Vertexes.Add(vertex);
  96. #region 重复点判断在子类去处理
  97. //if (useVertex == null)
  98. //{
  99. // vertex.Id = GenerateVertexIndex();
  100. // this.m_Vertexes.Add(vertex);
  101. //}
  102. //else
  103. //{
  104. // useVertex.Merge(vertex);
  105. // result = useVertex;
  106. //}
  107. #endregion
  108. return result;
  109. }
  110. /// <summary>
  111. /// 增加顶点
  112. /// </summary>
  113. /// <param name="vData"></param>
  114. /// <returns></returns>
  115. public virtual V AddVertex(VD vData)
  116. {
  117. if (vData == null)
  118. return null;
  119. var v = new V();
  120. v.Data = vData;
  121. return AddVertex(v);
  122. }
  123. #endregion
  124. #region 移除点相关操作
  125. /// <summary>
  126. /// 根据Id移除节点
  127. /// </summary>
  128. /// <param name="vertexId"></param>
  129. /// <returns></returns>
  130. public virtual bool RemoveVertex(string vertexId)
  131. {
  132. var realRemove = this.m_Vertexes.Remove(vertexId);
  133. if (realRemove)
  134. {
  135. //移除节点需要移除相应的边
  136. #region 移除相关联的边
  137. var edges = this.Edges.Where(e => e.ContainVertex(vertexId) > -1);
  138. foreach (var edge in edges)
  139. {
  140. this.m_Edges.Remove(edge.Id);
  141. }
  142. #endregion
  143. }
  144. return realRemove;
  145. }
  146. /// <summary>
  147. /// 隐藏点
  148. /// </summary>
  149. /// <param name="vertexId"></param>
  150. public virtual void HideVertex(string vertexId)
  151. {
  152. /*
  153. * 将指定点隐藏:概念上是将该点关联的边和点信息删除重构;
  154. * 一般适用于三点一线,隐藏掉中间点的情况;
  155. * 其他情况下,边关联信息可能会出现问题
  156. */
  157. }
  158. #endregion
  159. #region 合并点
  160. /// <summary>
  161. /// 合并关联的点
  162. /// </summary>
  163. /// <param name="vs"></param>
  164. /// <returns></returns>
  165. public virtual V CombineVertexes(List<V> vs)
  166. {
  167. //将关联点合并。1、将点与点之间的边信息进行处理;2、创建新的点
  168. return null;
  169. }
  170. #endregion
  171. #endregion
  172. #region 边操作
  173. #region 查找边
  174. /// <summary>
  175. /// 获取边信息
  176. /// </summary>
  177. /// <param name="edgeId"></param>
  178. /// <returns></returns>
  179. public E FindEdge(string edgeId)
  180. {
  181. if (this.m_Edges.Contains(edgeId))
  182. {
  183. return m_Edges[edgeId];
  184. }
  185. return null;
  186. }
  187. #endregion
  188. #region 增加边
  189. /// <summary>
  190. /// 增加边
  191. /// </summary>
  192. /// <param name="edge"></param>
  193. /// <returns></returns>
  194. public virtual E AddEdge(E edge)
  195. {
  196. var start = FindVertex(edge.StartVertex);
  197. if (start == null)
  198. throw new Exception("start元素必须在图中");
  199. var end = FindVertex(edge.EndVertex);
  200. if (end == null)
  201. throw new Exception("end元素必须在图中");
  202. edge.Id = GenerateEdgeIndex();
  203. this.m_Edges.Add(edge);
  204. return edge;
  205. }
  206. /// <summary>
  207. /// 增加边信息
  208. /// </summary>
  209. /// <param name="start"></param>
  210. /// <param name="end"></param>
  211. /// <param name="edge"></param>
  212. /// <returns></returns>
  213. public virtual E AddEdge(V start, V end, E edge)
  214. {
  215. var startV = AddVertex(start);
  216. if (startV == null)
  217. {
  218. throw new Exception("start不能为null");
  219. }
  220. var endV = AddVertex(end);
  221. if (endV == null)
  222. {
  223. throw new Exception("end不能为null");
  224. }
  225. edge.StartVertex = startV.Id;
  226. edge.EndVertex = endV.Id;
  227. edge.Id = GenerateEdgeIndex();
  228. this.m_Edges.Add(edge);
  229. return edge;
  230. }
  231. #endregion
  232. /// <summary>
  233. /// 移除边信息
  234. /// </summary>
  235. /// <param name="edgeId"></param>
  236. /// <returns></returns>
  237. public virtual bool RemoveEdge(string edgeId)
  238. {
  239. return this.m_Edges.Remove(edgeId); ;
  240. }
  241. #endregion
  242. #region 联动查询
  243. /*
  244. * 念念不忘的可优化部分;根据点去查询边的情况
  245. */
  246. /// <summary>
  247. /// 获取出边
  248. /// </summary>
  249. /// <param name="vertexId"></param>
  250. /// <returns></returns>
  251. public List<E> GetOutEdges(string vertexId)
  252. {
  253. List<E> result = new List<E>();
  254. foreach (var edge in this.Edges)
  255. {
  256. var flag = edge.ContainVertex(vertexId);
  257. if (flag == -1)
  258. continue;
  259. if (!IsDirection)
  260. {
  261. result.Add(edge);
  262. }
  263. else
  264. {
  265. if (flag == 0)
  266. {
  267. result.Add(edge);
  268. }
  269. }
  270. }
  271. return result;
  272. }
  273. /// <summary>
  274. /// 获取入边
  275. /// </summary>
  276. /// <param name="vertexId"></param>
  277. /// <returns></returns>
  278. public List<E> GetInEdges(string vertexId)
  279. {
  280. List<E> result = new List<E>();
  281. foreach (var edge in this.Edges)
  282. {
  283. var flag = edge.ContainVertex(vertexId);
  284. if (flag == -1)
  285. continue;
  286. if (!IsDirection)
  287. {
  288. result.Add(edge);
  289. }
  290. else
  291. {
  292. if (flag == 1)
  293. {
  294. result.Add(edge);
  295. }
  296. }
  297. }
  298. return result;
  299. }
  300. /// <summary>
  301. /// 获取两个点确定的边信息
  302. /// </summary>
  303. /// <param name="startId"></param>
  304. /// <param name="endId"></param>
  305. /// <returns></returns>
  306. public List<E> GetEdges(string startId, string endId)
  307. {
  308. List<E> result = new List<E>();
  309. var edges = GetOutEdges(startId);
  310. foreach (var edge in edges)
  311. {
  312. if (edge.GetAnotherVertex(startId) == endId)
  313. {
  314. result.Add(edge);
  315. }
  316. }
  317. return result;
  318. }
  319. /// <summary>
  320. /// 获取出的邻节点
  321. /// </summary>
  322. /// <param name="vertexId"></param>
  323. /// <returns></returns>
  324. public List<V> GetOutVertexes(string vertexId)
  325. {
  326. List<V> result = new List<V>();
  327. var edges = GetOutEdges(vertexId);
  328. foreach (var edge in edges)
  329. {
  330. var otherId = edge.GetAnotherVertex(vertexId);
  331. if (this.m_Vertexes.Contains(otherId))
  332. {
  333. result.Add(this.m_Vertexes[otherId]);
  334. }
  335. }
  336. return result;
  337. }
  338. /// <summary>
  339. /// 获取入的邻接点
  340. /// </summary>
  341. /// <param name="vertexId"></param>
  342. /// <returns></returns>
  343. public List<V> GetInVertexes(string vertexId)
  344. {
  345. List<V> result = new List<V>();
  346. var edges = GetInEdges(vertexId);
  347. foreach (var edge in edges)
  348. {
  349. var otherId = edge.GetAnotherVertex(vertexId);
  350. if (this.m_Vertexes.Contains(otherId))
  351. {
  352. result.Add(this.m_Vertexes[otherId]);
  353. }
  354. }
  355. return result;
  356. }
  357. /// <summary>
  358. /// 获取边的开始点
  359. /// </summary>
  360. /// <param name="edge"></param>
  361. /// <returns></returns>
  362. public V GetStartVertex(E edge)
  363. {
  364. return FindVertex(edge.StartVertex);
  365. }
  366. /// <summary>
  367. /// 获取边的结束点
  368. /// </summary>
  369. /// <param name="edge"></param>
  370. /// <returns></returns>
  371. public V GetEndVertex(E edge)
  372. {
  373. return FindVertex(edge.EndVertex);
  374. }
  375. /// <summary>
  376. /// 获取边的开始点的根节点
  377. /// </summary>
  378. /// <param name="edge"></param>
  379. /// <returns></returns>
  380. public V GetBootStartVertex(E edge)
  381. {
  382. return FindVertex(edge.StartVertex)?.GetRoot() as V;
  383. }
  384. /// <summary>
  385. /// 获取边的结束店的根节点
  386. /// </summary>
  387. /// <param name="edge"></param>
  388. /// <returns></returns>
  389. public V GetBootEndVertex(E edge)
  390. {
  391. return FindVertex(edge.EndVertex)?.GetRoot() as V;
  392. }
  393. #endregion
  394. #region 相关公开方法
  395. /// <summary>
  396. /// 获取最后一个状态的边集集合
  397. /// </summary>
  398. /// <returns></returns>
  399. public static List<E> GetLastStateEdges(IEnumerable<E> inputEdges)
  400. {
  401. var edges = inputEdges.Where(e => e.Parent == null).ToList();
  402. return edges;
  403. }
  404. /// <summary>
  405. /// 获取原始状态的边集合
  406. /// </summary>
  407. /// <returns></returns>
  408. public static List<E> GeFirstStateEdges(IEnumerable<E> inputEdges)
  409. {
  410. var edges = inputEdges.Where(e => e.Parent.Children.Count == 0).ToList();
  411. return edges;
  412. }
  413. /// <summary>
  414. /// 获取最后一个状态的边集集合
  415. /// </summary>
  416. /// <returns></returns>
  417. public List<E> GetLastStateEdges()
  418. {
  419. return GetLastStateEdges(this.Edges);
  420. }
  421. /// <summary>
  422. /// 获取原始状态的边集合
  423. /// </summary>
  424. /// <returns></returns>
  425. public List<E> GeFirstStateEdges()
  426. {
  427. return GeFirstStateEdges(this.Edges);
  428. }
  429. #endregion
  430. }
  431. }