123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296 |
- using System;
- using System.Collections.Generic;
- using System.Linq;
- using System.Text;
- using System.Threading.Tasks;
- namespace SAGA.DotNetUtils.Data
- {
- public static class EdgesArrayGraphUtil
- {
- /// <summary>
- /// 串联处理
- /// </summary>
- /// <typeparam name="V"></typeparam>
- /// <typeparam name="VD"></typeparam>
- /// <typeparam name="E"></typeparam>
- /// <typeparam name="ED"></typeparam>
- /// <param name="edgesArray"></param>
- /// <returns></returns>
- public static EdgesArrayGraph<V, VD, E, ED> ParallelHandle<V, VD, E, ED>(EdgesArrayGraph<V, VD, E, ED> edgesArray) where V : EAVertex<VD>,new() where E : EAEdge<ED>,new ()
- {
- var edges = edgesArray.GetLastStateEdges();
- VisitControl map = new VisitControl();
- ForwardStar<V, VD,E, ED> fs = new ForwardStar<V, VD,E, ED>();
- var ids = edges.SelectMany(e => new List<string>() { e.StartVertex, e.EndVertex }).Distinct();
- ids.ToList().ForEach(id =>
- {
- var tempV = edgesArray.FindVertex(id);
- if (tempV != null)
- {
- fs.AddVertex(tempV);
- }
- });
- fs.AddEdges(edges);
- for (int i = 0; i < edges.Count; i++)
- {
- var edge = edges[i];
- if (map.GetHandled(edge))
- continue;
- var refEdges = fs.GetEdges(edge.StartVertex, edge.EndVertex,true);
- if (refEdges.Count > 1)
- {
- E newEdge = new E();
- newEdge.StartVertex = edge.StartVertex;
- newEdge.EndVertex = edge.EndVertex;
- newEdge.Children.AddRange(refEdges);
- newEdge.EdgeType = EAEdgeType.Parallel;
- edgesArray.AddEdge(newEdge);
- //对象为键值
- refEdges.ForEach(e => map.SetHandled(e, true));
- }
- }
- return edgesArray;
- }
- /// <summary>
- /// 并联处理
- /// </summary>
- /// <typeparam name="V"></typeparam>
- /// <typeparam name="VD"></typeparam>
- /// <typeparam name="E"></typeparam>
- /// <typeparam name="ED"></typeparam>
- /// <param name="edgesArray"></param>
- /// <returns></returns>
- public static EdgesArrayGraph<V, VD, E, ED> SeriesHandle<V, VD, E, ED>(EdgesArrayGraph<V, VD, E, ED> edgesArray) where V : EAVertex<VD>, new() where E : EAEdge<ED>,new ()
- {
- var edges = edgesArray.GetLastStateEdges();
- VisitControl map = new VisitControl();
- ForwardStar<V, VD, E, ED> fs = new ForwardStar<V, VD, E, ED>();
- var ids = edges.SelectMany(e => new List<string>() { e.StartVertex, e.EndVertex }).Distinct();
- ids.ToList().ForEach(id =>
- {
- var tempV = edgesArray.FindVertex(id);
- if (tempV != null)
- {
- fs.AddVertex(tempV);
- }
- });
- fs.AddEdges(edges);
- for (int i = 0; i < edges.Count; i++)
- {
- var edge = edges[i];
- if (map.GetHandled(edge))
- {
- continue;
- }
- map.SetHandled(edge, true);
- var refEdges = fs.GetEdges(edge.StartVertex, edge.EndVertex, true);
- if (refEdges.Count > 1)
- {
- continue;
- }
- List<string> ends = new List<string>();//端点信息
- List<E> useEdges = new List<E>() { edge };
- List<string> searchVertexes = new List<string>() { edge.StartVertex, edge.EndVertex };
- for (int k = 0; k < searchVertexes.Count; k++)
- {
- var useId = searchVertexes[k];
- bool isStart = k != 0;
- //按照有向信息计算
- var tempEdges = fs.GetEdges(useId, isStart);
- while (tempEdges.Count == 1)
- {
- var tempEdge = tempEdges[0];
- if (tempEdge == null || map.GetHandled(tempEdge) || useEdges.Any(d => d.Id == tempEdge.Id))
- break;
- if (k == 0)
- {
- useEdges.Insert(0, tempEdge);
- }
- else
- {
- useEdges.Add(tempEdge);
- }
- map.SetHandled(tempEdge, true);
- useId = tempEdge.GetAnotherVertex(useId);
- tempEdges = fs.GetEdges(useId, isStart);
- }
- ends.Add(useId);
- }
- if (useEdges.Count != 1)
- {
- E newEdge = new E();
- newEdge.StartVertex = ends[0];
- newEdge.EndVertex = ends[1];
- newEdge.Children.AddRange(useEdges);
- newEdge.EdgeType = EAEdgeType.Series;
- edgesArray.AddEdge(newEdge);
- }
- }
- return edgesArray;
- }
- /// <summary>
- /// 拓扑分析;串并联迭代处理
- /// </summary>
- /// <typeparam name="V"></typeparam>
- /// <typeparam name="VD"></typeparam>
- /// <typeparam name="E"></typeparam>
- /// <typeparam name="ED"></typeparam>
- /// <param name="edgesArray"></param>
- /// <returns></returns>
- public static EdgesArrayGraph<V, VD, E, ED> GplotAnalyse<V, VD, E, ED>(EdgesArrayGraph<V, VD, E, ED> edgesArray) where V : EAVertex<VD>, new() where E : EAEdge<ED>,new ()
- {
- var preCount = edgesArray.GetLastStateEdges().Count;
- do
- {
- edgesArray = SeriesHandle(edgesArray);
- var current = edgesArray.GetLastStateEdges().Count;
- if (current == 1)
- break;
- edgesArray = ParallelHandle(edgesArray);
- current = edgesArray.GetLastStateEdges().Count;
- if (current == 1)
- break;
- if (current == preCount)
- break;
- preCount = current;
- } while (true);
- return edgesArray;
- }
- /// <summary>
- /// 查找相关联的路径信息,该方法如果传入的图不是有向无环图,则不能获取到正确结果【不建议使用】
- /// </summary>
- /// <typeparam name="V"></typeparam>
- /// <typeparam name="VD"></typeparam>
- /// <typeparam name="E"></typeparam>
- /// <typeparam name="ED"></typeparam>
- /// <param name="edgesArray"></param>
- /// <param name="start"></param>
- /// <param name="endPredicate"></param>
- /// <returns></returns>
- public static List<PathNodes<V, E>> GetPaths<V, VD, E, ED>(this EdgesArrayGraph<V, VD, E, ED> edgesArray, V start, Predicate<V> endPredicate) where V : EAVertex<VD>, new() where E : EAEdge<ED>, new()
- {
- List<PathNodes<V, E>> list = new List<PathNodes<V, E>>();
- var edges = edgesArray.GetOutEdges(start.Id);
- foreach (var edge in edges)
- {
- var anotherId = edge.GetAnotherVertex(start.Id);
- var v=edgesArray.FindVertex(anotherId)?.GetRoot() as V;
- if (v == null)
- continue;
- if (endPredicate != null && endPredicate(v))
- {
- PathNodes<V, E> nodes = new PathNodes<V, E>();
- nodes.Add(new PathNode<V, E>(v, edge));
- list.Add(nodes);
- }
- else
- {
- var nextList = GetPaths(edgesArray, v, endPredicate);
- foreach (var next in nextList)
- {
- next.Insert(0, new PathNode<V, E>(v, edge));
- }
- list.AddRange(nextList);
- }
- }
- return list;
- }
- /// <summary>
- /// 获取指定起点,到指定条件的节点路径信息;(建议使用)
- /// </summary>
- /// <typeparam name="V"></typeparam>
- /// <typeparam name="VD"></typeparam>
- /// <typeparam name="E"></typeparam>
- /// <typeparam name="ED"></typeparam>
- /// <param name="edgesArray"></param>
- /// <param name="start"></param>
- /// <param name="endPredicate"></param>
- /// <returns></returns>
- public static List<PathNodes<V, E>> GetPaths2<V, VD, E, ED>(
- this EdgesArrayGraph<V, VD, E, ED> edgesArray, V start,Predicate<V> endPredicate)
- where V : EAVertex<VD>, new() where E : EAEdge<ED>, new()
- {
- PathNodes<V, E> prePath = new PathNodes<V, E>();
- prePath.Add(new PathNode<V, E>(start, null));
- var paths = InternalGetPaths(edgesArray, start, prePath, endPredicate);
- paths.ForEach(p => p.RemoveAt(0));
- return paths;
- }
- internal static List<PathNodes<V, E>> InternalGetPaths<V, VD, E, ED>(this EdgesArrayGraph<V, VD, E, ED> edgesArray, V start, PathNodes<V, E> prePath,Predicate<V> endPredicate) where V : EAVertex<VD>, new() where E : EAEdge<ED>, new()
- {
- List<PathNodes<V, E>> list = new List<PathNodes<V, E>>();
- var edges = edgesArray.GetOutEdges(start.Id);
- foreach (var edge in edges)
- {
- var anotherId = edge.GetAnotherVertex(start.Id);
- var v = edgesArray.FindVertex(anotherId)?.GetRoot() as V;
- if (v == null)
- continue;
- if (prePath.Count > 1 && prePath[prePath.Count - 1].NextNode.Id == anotherId)
- {
- //或者不进行数量判断,但要对NextNode进行非空判断
- continue;
- }
- if ((prePath.Any(n => n.NextNode.Id == anotherId)) ||(endPredicate != null && endPredicate(v)))
- {
- PathNodes<V, E> nodes = new PathNodes<V, E>(prePath);
- nodes.Add(new PathNode<V, E>(v, edge));
- list.Add(nodes);
- }
- else
- {
- var newPath = new PathNodes<V, E>(prePath);
- newPath.Add(new PathNode<V, E>(v, edge));
- var nextList = InternalGetPaths(edgesArray, v, newPath, endPredicate);
- list.AddRange(nextList);
- }
- }
- return list;
- }
- }
- public class PathNode<V,E>
- {
- public PathNode()
- {
- }
- public PathNode(V end, E path)
- {
- NextNode = end;
- Path = path;
- }
- public V NextNode { get; set; }
- public E Path { get; set; }
- /// <summary>
- /// 虚拟的开始节点,当路径为null时,认为是开始节点
- /// </summary>
- /// <returns></returns>
- public bool IsStart()
- {
- return Path == null;
- }
- }
- public class PathNodes<V, E> : List<PathNode<V, E>>
- {
- public PathNodes()
- {
- }
- public PathNodes(IEnumerable<PathNode<V, E>> nodes)
- {
- this.AddRange(nodes);
- }
- }
- }
|