123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444 |
- using System;
- using System.Collections.Generic;
- using System.Linq;
- namespace SAGA.DotNetUtils.Data
- {
- #region 概述
- /*
- * 有向图,和无向图,部分方法不同;
- *
- * 内部操作使用索引;功能扩展使用Data
- */
- #endregion
- /// <summary>
- /// 边集列表
- /// </summary>
- public class EdgesArrayGraph<V,VD,E,ED> : EdgesArrayBase<V, VD, E, ED> where V : EAVertex<VD> ,new() where E : EAEdge<ED>,new()
- {
- public EdgesArrayGraph()
- {
-
- }
- #region 控制属性
- /// <summary>
- /// 表示该图信息是否是有向的
- /// </summary>
- public bool IsDirection { get; set; }
- #endregion
- #region 编号系统
- private int m_CurrentVertexIndex;
- /// <summary>
- /// 生成节点索引
- /// </summary>
- /// <returns></returns>
- private string GenerateVertexIndex()
- {
- return "V" + (++m_CurrentVertexIndex);
- }
- /// <summary>
- /// 生成节点索引
- /// </summary>
- /// <returns></returns>
- private string GenerateEdgeIndex()
- {
- return "E" + (++m_CurrentVertexIndex);
- }
- #endregion
- #region 点操作
- #region 查找点
- /// <summary>
- /// 根据顶点Id查询相应的节点
- /// </summary>
- /// <param name="vertexId"></param>
- /// <returns></returns>
- public virtual V FindVertex(string vertexId)
- {
- if (string.IsNullOrWhiteSpace(vertexId))
- {
- return null;
- }
- if (this.m_Vertexes.Contains(vertexId))
- {
- return this.m_Vertexes[vertexId];
- }
- return null;
- }
- /// <summary>
- /// 根据顶点Id查询相应的节点
- /// </summary>
- /// <param name="v">根据顶点信息去检索点</param>
- /// <returns></returns>
- public virtual V FindVertex(V v)
- {
- /*
- * 待改进:id快索引,IsMatch值匹配慢索引
- */
- var useV = FindVertex(v.Id) ?? this.Vertexes.FirstOrDefault(c => c.IsMatch(v));
- return useV;
- }
- #endregion
- #region 增加点
- /// <summary>
- /// 增加顶点
- /// </summary>
- /// <param name="vertex"></param>
- /// <returns></returns>
- public virtual V AddVertex(V vertex)
- {
- if (vertex == null)
- return null;
- V result = vertex;
- //var useVertex = FindVertex(vertex);
- /*如果是集合形式的比较,相等不传递。比如List1与List2兼容,List2与List3兼容,不能推导出List1与List3兼容
- 综合考虑,不在基类做这种数据的处理,而是直接插入点
- */
- vertex.Id = GenerateVertexIndex();
- this.m_Vertexes.Add(vertex);
- #region 重复点判断在子类去处理
- //if (useVertex == null)
- //{
- // vertex.Id = GenerateVertexIndex();
- // this.m_Vertexes.Add(vertex);
- //}
- //else
- //{
- // useVertex.Merge(vertex);
- // result = useVertex;
- //}
- #endregion
- return result;
- }
- /// <summary>
- /// 增加顶点
- /// </summary>
- /// <param name="vData"></param>
- /// <returns></returns>
- public virtual V AddVertex(VD vData)
- {
- if (vData == null)
- return null;
- var v = new V();
- v.Data = vData;
- return AddVertex(v);
- }
- #endregion
- #region 移除点相关操作
- /// <summary>
- /// 根据Id移除节点
- /// </summary>
- /// <param name="vertexId"></param>
- /// <returns></returns>
- public virtual bool RemoveVertex(string vertexId)
- {
- var realRemove = this.m_Vertexes.Remove(vertexId);
- if (realRemove)
- {
- //移除节点需要移除相应的边
- #region 移除相关联的边
- var edges = this.Edges.Where(e => e.ContainVertex(vertexId) > -1);
- foreach (var edge in edges)
- {
- this.m_Edges.Remove(edge.Id);
- }
- #endregion
- }
- return realRemove;
- }
- /// <summary>
- /// 隐藏点
- /// </summary>
- /// <param name="vertexId"></param>
- public virtual void HideVertex(string vertexId)
- {
- /*
- * 将指定点隐藏:概念上是将该点关联的边和点信息删除重构;
- * 一般适用于三点一线,隐藏掉中间点的情况;
- * 其他情况下,边关联信息可能会出现问题
- */
- }
- #endregion
- #region 合并点
- /// <summary>
- /// 合并关联的点
- /// </summary>
- /// <param name="vs"></param>
- /// <returns></returns>
- public virtual V CombineVertexes(List<V> vs)
- {
- //将关联点合并。1、将点与点之间的边信息进行处理;2、创建新的点
- return null;
- }
- #endregion
- #endregion
- #region 边操作
- #region 查找边
- /// <summary>
- /// 获取边信息
- /// </summary>
- /// <param name="edgeId"></param>
- /// <returns></returns>
- public E FindEdge(string edgeId)
- {
- if (this.m_Edges.Contains(edgeId))
- {
- return m_Edges[edgeId];
- }
- return null;
- }
- #endregion
- #region 增加边
- /// <summary>
- /// 增加边
- /// </summary>
- /// <param name="edge"></param>
- /// <returns></returns>
- public virtual E AddEdge(E edge)
- {
- var start = FindVertex(edge.StartVertex);
- if (start == null)
- throw new Exception("start元素必须在图中");
- var end = FindVertex(edge.EndVertex);
- if (end == null)
- throw new Exception("end元素必须在图中");
- edge.Id = GenerateEdgeIndex();
- this.m_Edges.Add(edge);
- return edge;
- }
- /// <summary>
- /// 增加边信息
- /// </summary>
- /// <param name="start"></param>
- /// <param name="end"></param>
- /// <param name="edge"></param>
- /// <returns></returns>
- public virtual E AddEdge(V start, V end, E edge)
- {
- var startV = AddVertex(start);
- if (startV == null)
- {
- throw new Exception("start不能为null");
- }
- var endV = AddVertex(end);
- if (endV == null)
- {
- throw new Exception("end不能为null");
- }
- edge.StartVertex = startV.Id;
- edge.EndVertex = endV.Id;
- edge.Id = GenerateEdgeIndex();
- this.m_Edges.Add(edge);
- return edge;
- }
- #endregion
- /// <summary>
- /// 移除边信息
- /// </summary>
- /// <param name="edgeId"></param>
- /// <returns></returns>
- public virtual bool RemoveEdge(string edgeId)
- {
- return this.m_Edges.Remove(edgeId); ;
- }
- #endregion
- #region 联动查询
- /*
- * 念念不忘的可优化部分;根据点去查询边的情况
- */
- /// <summary>
- /// 获取出边
- /// </summary>
- /// <param name="vertexId"></param>
- /// <returns></returns>
- public List<E> GetOutEdges(string vertexId)
- {
- List<E> result = new List<E>();
- foreach (var edge in this.Edges)
- {
- var flag = edge.ContainVertex(vertexId);
- if (flag == -1)
- continue;
- if (!IsDirection)
- {
- result.Add(edge);
- }
- else
- {
- if (flag == 0)
- {
- result.Add(edge);
- }
- }
- }
- return result;
- }
- /// <summary>
- /// 获取入边
- /// </summary>
- /// <param name="vertexId"></param>
- /// <returns></returns>
- public List<E> GetInEdges(string vertexId)
- {
- List<E> result = new List<E>();
- foreach (var edge in this.Edges)
- {
- var flag = edge.ContainVertex(vertexId);
- if (flag == -1)
- continue;
- if (!IsDirection)
- {
- result.Add(edge);
- }
- else
- {
- if (flag == 1)
- {
- result.Add(edge);
- }
- }
- }
- return result;
- }
- /// <summary>
- /// 获取两个点确定的边信息
- /// </summary>
- /// <param name="startId"></param>
- /// <param name="endId"></param>
- /// <returns></returns>
- public List<E> GetEdges(string startId, string endId)
- {
- List<E> result = new List<E>();
- var edges = GetOutEdges(startId);
- foreach (var edge in edges)
- {
- if (edge.GetAnotherVertex(startId) == endId)
- {
- result.Add(edge);
- }
- }
- return result;
- }
- /// <summary>
- /// 获取出的邻节点
- /// </summary>
- /// <param name="vertexId"></param>
- /// <returns></returns>
- public List<V> GetOutVertexes(string vertexId)
- {
- List<V> result = new List<V>();
- var edges = GetOutEdges(vertexId);
- foreach (var edge in edges)
- {
- var otherId = edge.GetAnotherVertex(vertexId);
- if (this.m_Vertexes.Contains(otherId))
- {
- result.Add(this.m_Vertexes[otherId]);
- }
- }
- return result;
- }
- /// <summary>
- /// 获取入的邻接点
- /// </summary>
- /// <param name="vertexId"></param>
- /// <returns></returns>
- public List<V> GetInVertexes(string vertexId)
- {
- List<V> result = new List<V>();
- var edges = GetInEdges(vertexId);
- foreach (var edge in edges)
- {
- var otherId = edge.GetAnotherVertex(vertexId);
- if (this.m_Vertexes.Contains(otherId))
- {
- result.Add(this.m_Vertexes[otherId]);
- }
- }
- return result;
- }
- /// <summary>
- /// 获取边的开始点
- /// </summary>
- /// <param name="edge"></param>
- /// <returns></returns>
- public V GetStartVertex(E edge)
- {
- return FindVertex(edge.StartVertex);
- }
- /// <summary>
- /// 获取边的结束点
- /// </summary>
- /// <param name="edge"></param>
- /// <returns></returns>
- public V GetEndVertex(E edge)
- {
- return FindVertex(edge.EndVertex);
- }
- /// <summary>
- /// 获取边的开始点的根节点
- /// </summary>
- /// <param name="edge"></param>
- /// <returns></returns>
- public V GetBootStartVertex(E edge)
- {
- return FindVertex(edge.StartVertex)?.GetRoot() as V;
- }
- /// <summary>
- /// 获取边的结束店的根节点
- /// </summary>
- /// <param name="edge"></param>
- /// <returns></returns>
- public V GetBootEndVertex(E edge)
- {
- return FindVertex(edge.EndVertex)?.GetRoot() as V;
- }
- #endregion
- #region 相关公开方法
- /// <summary>
- /// 获取最后一个状态的边集集合
- /// </summary>
- /// <returns></returns>
- public static List<E> GetLastStateEdges(IEnumerable<E> inputEdges)
- {
- var edges = inputEdges.Where(e => e.Parent == null).ToList();
- return edges;
- }
- /// <summary>
- /// 获取原始状态的边集合
- /// </summary>
- /// <returns></returns>
- public static List<E> GeFirstStateEdges(IEnumerable<E> inputEdges)
- {
- var edges = inputEdges.Where(e => e.Parent.Children.Count == 0).ToList();
- return edges;
- }
- /// <summary>
- /// 获取最后一个状态的边集集合
- /// </summary>
- /// <returns></returns>
- public List<E> GetLastStateEdges()
- {
- return GetLastStateEdges(this.Edges);
- }
- /// <summary>
- /// 获取原始状态的边集合
- /// </summary>
- /// <returns></returns>
- public List<E> GeFirstStateEdges()
- {
- return GeFirstStateEdges(this.Edges);
- }
- #endregion
- }
- }
|