ForwardStar.cs 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Collections.ObjectModel;
  4. using System.Linq;
  5. using System.Text;
  6. using System.Threading.Tasks;
  7. namespace SAGA.DotNetUtils.Data
  8. {
  9. public class ForwardStar<V, VD,E, ED> : BaseEdgesArray<V, VD, E, ED> where V : EAVertex<VD> where E : EAEdge<ED>
  10. {
  11. public ForwardStar()
  12. {
  13. }
  14. #region 顶点操作
  15. /// <summary>
  16. /// 增加节点
  17. /// </summary>
  18. /// <param name="v"></param>
  19. public void AddVertex(V v)
  20. {
  21. m_Vertexes.Add(v);
  22. }
  23. #endregion
  24. #region 边操作
  25. public void AddEdge(E edge)
  26. {
  27. this.m_Edges.Add(edge);
  28. SortEdges();
  29. }
  30. public void AddEdges(List<E> edges)
  31. {
  32. edges.ForEach(e => this.m_Edges.Add(e));
  33. SortEdges();
  34. }
  35. #endregion
  36. #region 初始化排序队列
  37. private Dictionary<string,List<E>> StartRelations { get; set; }
  38. private Dictionary<string, List<E>> EndRelations { get; set; }
  39. /// <summary>
  40. /// 给指定边排序
  41. /// </summary>
  42. public void SortEdges()
  43. {
  44. #region 前项列表
  45. var groupsStart = this.m_Edges.GroupBy(e => e.StartVertex).ToList();
  46. StartRelations = new Dictionary<string, List<E>>();
  47. foreach (var group in groupsStart)
  48. {
  49. StartRelations[group.Key] = group.ToList();
  50. }
  51. #endregion
  52. #region 后项列表
  53. EndRelations = new Dictionary<string, List<E>>();
  54. var groupsEnd = this.m_Edges.GroupBy(e => e.EndVertex).ToList();
  55. foreach (var group in groupsEnd)
  56. {
  57. EndRelations[group.Key] = group.ToList();
  58. }
  59. #endregion
  60. }
  61. #endregion
  62. /// <summary>
  63. /// 获取指定边的信息
  64. /// </summary>
  65. /// <param name="vId1"></param>
  66. /// <param name="vId2"></param>
  67. /// <param name="isDirection">是否当有向图处理</param>
  68. /// <returns></returns>
  69. public List<E> GetEdges(string vId1, string vId2, bool isDirection)
  70. {
  71. List<E> edges = new List<E>();
  72. List<Tuple<string, string>> keys = new List<Tuple<string, string>>();
  73. keys.Add(new Tuple<string, string>(vId1, vId2));
  74. if (!isDirection)
  75. {
  76. keys.Add(new Tuple<string, string>(vId2, vId1));
  77. }
  78. for (int i = 0; i < keys.Count; i++)
  79. {
  80. var currentKey = keys[i].Item1;
  81. var nextKey = keys[i].Item2;
  82. bool flag = StartRelations.TryGetValue(currentKey, out List<E> tempEdges);
  83. if (flag)
  84. {
  85. edges.AddRange(tempEdges.Where(e => e.EndVertex == nextKey));
  86. }
  87. }
  88. return edges;
  89. }
  90. /// <summary>
  91. /// 获取和指定点关联的边
  92. /// </summary>
  93. /// <param name="vId">指定点</param>
  94. /// <param name="isStart">是否是开始点</param>
  95. /// <returns></returns>
  96. public List<E> GetEdges(string vId, bool isStart)
  97. {
  98. List<E> edges = new List<E>();
  99. Dictionary<string, List<E>> dataSource = isStart ? StartRelations : EndRelations;
  100. bool flag = dataSource.TryGetValue(vId, out List<E> tempEdges);
  101. if (flag)
  102. {
  103. edges.AddRange(tempEdges);
  104. }
  105. return edges;
  106. }
  107. /// <summary>
  108. /// 获取和指点点关联的边
  109. /// </summary>
  110. /// <param name="vId">指定点</param>
  111. /// <returns></returns>
  112. public List<E> GetEdges(string vId)
  113. {
  114. List<E> edges = new List<E>();
  115. edges.AddRange(GetEdges(vId,true));
  116. var attach = GetEdges(vId, false);
  117. foreach (var item in attach)
  118. {
  119. if (edges.Any(c => c.Id == item.Id))
  120. {
  121. continue;
  122. }
  123. edges.Add(item);
  124. }
  125. return edges;
  126. }
  127. }
  128. }