123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133 |
- using System;
- using System.Collections.Generic;
- using System.Collections.ObjectModel;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace SAGA.DotNetUtils.Data
- {
- public class ForwardStar<V, VD,E, ED> : BaseEdgesArray<V, VD, E, ED> where V : EAVertex<VD> where E : EAEdge<ED>
- {
- public ForwardStar()
- {
-
- }
- #region 顶点操作
- /// <summary>
- /// 增加节点
- /// </summary>
- /// <param name="v"></param>
- public void AddVertex(V v)
- {
- m_Vertexes.Add(v);
- }
- #endregion
- #region 边操作
- public void AddEdge(E edge)
- {
- this.m_Edges.Add(edge);
- SortEdges();
- }
- public void AddEdges(List<E> edges)
- {
- edges.ForEach(e => this.m_Edges.Add(e));
- SortEdges();
- }
- #endregion
- #region 初始化排序队列
- private Dictionary<string,List<E>> StartRelations { get; set; }
- private Dictionary<string, List<E>> EndRelations { get; set; }
- /// <summary>
- /// 给指定边排序
- /// </summary>
- public void SortEdges()
- {
- #region 前项列表
- var groupsStart = this.m_Edges.GroupBy(e => e.StartVertex).ToList();
- StartRelations = new Dictionary<string, List<E>>();
- foreach (var group in groupsStart)
- {
- StartRelations[group.Key] = group.ToList();
- }
- #endregion
- #region 后项列表
- EndRelations = new Dictionary<string, List<E>>();
- var groupsEnd = this.m_Edges.GroupBy(e => e.EndVertex).ToList();
- foreach (var group in groupsEnd)
- {
- EndRelations[group.Key] = group.ToList();
- }
- #endregion
- }
- #endregion
- /// <summary>
- /// 获取指定边的信息
- /// </summary>
- /// <param name="vId1"></param>
- /// <param name="vId2"></param>
- /// <param name="isDirection">是否当有向图处理</param>
- /// <returns></returns>
- public List<E> GetEdges(string vId1, string vId2, bool isDirection)
- {
- List<E> edges = new List<E>();
- List<Tuple<string, string>> keys = new List<Tuple<string, string>>();
- keys.Add(new Tuple<string, string>(vId1, vId2));
- if (!isDirection)
- {
- keys.Add(new Tuple<string, string>(vId2, vId1));
- }
- for (int i = 0; i < keys.Count; i++)
- {
- var currentKey = keys[i].Item1;
- var nextKey = keys[i].Item2;
- bool flag = StartRelations.TryGetValue(currentKey, out List<E> tempEdges);
- if (flag)
- {
- edges.AddRange(tempEdges.Where(e => e.EndVertex == nextKey));
- }
- }
- return edges;
- }
- /// <summary>
- /// 获取和指定点关联的边
- /// </summary>
- /// <param name="vId">指定点</param>
- /// <param name="isStart">是否是开始点</param>
- /// <returns></returns>
- public List<E> GetEdges(string vId, bool isStart)
- {
- List<E> edges = new List<E>();
- Dictionary<string, List<E>> dataSource = isStart ? StartRelations : EndRelations;
- bool flag = dataSource.TryGetValue(vId, out List<E> tempEdges);
- if (flag)
- {
- edges.AddRange(tempEdges);
- }
- return edges;
- }
- /// <summary>
- /// 获取和指点点关联的边
- /// </summary>
- /// <param name="vId">指定点</param>
- /// <returns></returns>
- public List<E> GetEdges(string vId)
- {
- List<E> edges = new List<E>();
- edges.AddRange(GetEdges(vId,true));
- var attach = GetEdges(vId, false);
- foreach (var item in attach)
- {
- if (edges.Any(c => c.Id == item.Id))
- {
- continue;
- }
- edges.Add(item);
- }
- return edges;
- }
- }
- }
|