EdgesArray.cs 6.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223
  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 EdgesArray<V,VD,E,ED> : BaseEdgesArray<V, VD, E, ED> where V : EAVertex<VD> where E : EAEdge<ED>
  17. {
  18. public EdgesArray()
  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. /// <summary>
  48. /// 增加顶点
  49. /// </summary>
  50. /// <param name="vertex"></param>
  51. /// <returns></returns>
  52. public virtual V AddVertex(V vertex)
  53. {
  54. if (vertex == null)
  55. return null;
  56. V result = vertex;
  57. var useVertex = FindVertex(vertex);
  58. if (useVertex == null)
  59. {
  60. vertex.Id = GenerateVertexIndex();
  61. this.m_Vertexes.Add(vertex);
  62. }
  63. else
  64. {
  65. useVertex.Merge(vertex);
  66. result = useVertex;
  67. }
  68. return result;
  69. }
  70. /// <summary>
  71. /// 根据顶点Id查询相应的节点
  72. /// </summary>
  73. /// <param name="vertexId"></param>
  74. /// <returns></returns>
  75. public virtual V FindVertex(string vertexId)
  76. {
  77. if (string.IsNullOrWhiteSpace(vertexId))
  78. {
  79. return null;
  80. }
  81. if (this.m_Vertexes.Contains(vertexId))
  82. {
  83. return this.m_Vertexes[vertexId];
  84. }
  85. return null ;
  86. }
  87. /// <summary>
  88. /// 根据顶点Id查询相应的节点
  89. /// </summary>
  90. /// <param name="v">根据顶点信息去检索点</param>
  91. /// <returns></returns>
  92. public virtual V FindVertex(V v)
  93. {
  94. /*
  95. * 待改进:id快索引,IsMatch值匹配慢索引
  96. */
  97. var useV = FindVertex(v.Id);
  98. if(useV==null)
  99. {
  100. useV= this.Vertexes.FirstOrDefault(c =>c.IsMatch(v));
  101. }
  102. return useV;
  103. }
  104. /// <summary>
  105. /// 根据Id移除节点
  106. /// </summary>
  107. /// <param name="vertexId"></param>
  108. /// <returns></returns>
  109. public virtual bool RemoveVertex(string vertexId)
  110. {
  111. var realRemove = this.m_Vertexes.Remove(vertexId);
  112. if (realRemove)
  113. {
  114. //移除节点需要移除相应的边
  115. }
  116. return realRemove;
  117. }
  118. /// <summary>
  119. /// 隐藏点
  120. /// </summary>
  121. /// <param name="vertexId"></param>
  122. public virtual void HideVertex(string vertexId)
  123. {
  124. }
  125. /// <summary>
  126. /// 合并关联的点
  127. /// </summary>
  128. /// <param name="vs"></param>
  129. /// <returns></returns>
  130. public virtual V CombineVertexes(List<V> vs)
  131. {
  132. return null;
  133. }
  134. #endregion
  135. #region 边操作
  136. public E GetEdge(string edgeId)
  137. {
  138. if (this.m_Edges.Contains(edgeId))
  139. {
  140. return m_Edges[edgeId];
  141. }
  142. return null;
  143. }
  144. /// <summary>
  145. /// 增加边
  146. /// </summary>
  147. /// <param name="edge"></param>
  148. /// <returns></returns>
  149. public virtual E AddEdge(E edge)
  150. {
  151. var start = FindVertex(edge.StartVertex);
  152. if (start == null)
  153. throw new Exception("start元素必须在图中");
  154. var end = FindVertex(edge.EndVertex);
  155. if (end == null)
  156. throw new Exception("end元素必须在图中");
  157. edge.Id = GenerateEdgeIndex();
  158. this.m_Edges.Add(edge);
  159. return edge;
  160. }
  161. /// <summary>
  162. /// 增加边信息
  163. /// </summary>
  164. /// <param name="start"></param>
  165. /// <param name="end"></param>
  166. /// <param name="edge"></param>
  167. /// <returns></returns>
  168. public virtual E AddEdge(V start, V end, E edge)
  169. {
  170. var startV = AddVertex(start);
  171. if (startV == null)
  172. {
  173. throw new Exception("start不能为null");
  174. }
  175. var endV = AddVertex(end);
  176. if (endV == null)
  177. {
  178. throw new Exception("end不能为null");
  179. }
  180. edge.StartVertex =startV.Id;
  181. edge.EndVertex = endV.Id;
  182. edge.Id = GenerateEdgeIndex();
  183. this.m_Edges.Add(edge);
  184. return edge;
  185. }
  186. /// <summary>
  187. /// 移除边信息
  188. /// </summary>
  189. /// <param name="edgeId"></param>
  190. /// <returns></returns>
  191. public virtual bool RemoveEdge(string edgeId)
  192. {
  193. return this.m_Edges.Remove(edgeId); ;
  194. }
  195. #endregion
  196. #region 相关公开方法
  197. /// <summary>
  198. /// 获取最后一个状态的边集集合
  199. /// </summary>
  200. /// <returns></returns>
  201. public List<E> GetLastStateEdges()
  202. {
  203. var edges=this.Edges.Where(e => e.Parent == null).ToList();
  204. return edges;
  205. }
  206. /// <summary>
  207. /// 获取原始状态的边集合
  208. /// </summary>
  209. /// <returns></returns>
  210. public List<E> GeFirstStateEdges()
  211. {
  212. var edges = this.Edges.Where(e => e.Parent.Children.Count==0).ToList();
  213. return edges;
  214. }
  215. #endregion
  216. }
  217. }