GraphToolWPF/Model/GraphContext.cs - master - anton.bessolitsyn/GraphTool

GraphToolWPF/Model/GraphContext.cs
301 строка10 KB
Anton Bessolitsyn
in progress
22 окт 2025, 10:25
22 окт 2025, 10:258675066
using GraphToolWPF.Customs;
using Multicad.DatabaseServices;
using Multicad.DataServices;
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;
using static Multicad.Geometry.Mesh;

[assembly: InternalsVisibleTo("TestProject1")]
namespace GraphToolWPF.Model
{
    internal class GraphContext : IGraphContext
    {
        private Dictionary<Guid, Vertex> _Vertices { get; } = new();
        private Dictionary<Guid, Edge> _Edges { get; } = new();

        public IList<Vertex> Vertices => _Vertices.Select(v => v.Value).ToList();

        public IList<Edge> Edges => _Edges.Select(v => v.Value).ToList();

        public Vertex? GetVertex(Guid guid, VertexEntity? vertexEntity = null)
        {
            if (!_Vertices.TryGetValue(guid, out var vertex))
            {
                vertex = vertexEntity != null ? new Vertex(vertexEntity) : null;
            }
            return vertex;
        }

        public Edge? GetEdge(Guid guid)
        {
            if (_Edges.TryGetValue(guid, out var edge))
                return edge;
            else return null;
        }

        public void Add(VertexEntity vertex)
        {
            // TO DO  и переделать проверки далее if (_Vertices.ContainsKey(vertex.ID))
            Add(new Vertex(vertex));
        }
        public void Add(EdgeEntity edge)
        {
            Add(edge, null, null);
        }
        public void Add(EdgeEntity edge, VertexEntity? vertex1, VertexEntity? vertex2)
        {
            if (edge.Vertex1 != Guid.Empty && edge.Vertex2 != Guid.Empty)
            {
                var v1 = GetVertex(edge.Vertex1, vertex1);
                var v2 = GetVertex(edge.Vertex2, vertex2);
                if (v1 != null && v2 != null)
                {
                    Add(new Edge(v1, v2, edge));
                }
            }
        }

                
        void Add(Edge edge)
        {
            if (CheckEdge(edge))
            {
                _Edges[edge.Id] = edge;
                edge.Start.AddNeighbor(edge.End);
                Add(edge.Start);
                Add(edge.End);
            }
        }

        void Add(Vertex vertex)
        {
            if (vertex == null || _Vertices.ContainsKey(vertex.Id))
                return;

            _Vertices[vertex.Id] = vertex;
        }

        public bool Remove(Vertex vertex)
        {
            foreach (var item in _Edges.Where(e => e.Value.Start.Id == vertex.Id).ToArray())
            {
                //item.Value.Entity.OnErase();
                McObjectManager.RemoveFromDocument(item.Value.Entity);
            }
            foreach (var item in _Edges.Where(e => e.Value.End.Id == vertex.Id).ToArray())
            {
                //item.Value.Entity.OnErase();
                McObjectManager.RemoveFromDocument(item.Value.Entity);
            }
            return _Vertices.Remove(vertex.Id);
        }


        public bool Remove(Edge edge)
        {
            
            if (edge == null)
                return false;

            edge.Start.RemoveNeighbor(edge.End);
            return _Edges.Remove(edge.Id);
        }

        bool CheckEdge(Edge edge)
        {

            if (edge.Start == null || edge.End == null || edge.Start == edge.End)
                return false;


            if (_Edges.Any(e => e.Value.Start == edge.Start && e.Value.End == edge.End || e.Value.Start == edge.End && e.Value.End == edge.Start))
                return false;
            return true;
        }

        Dictionary<Vertex, Double> GetNeihborsWithDist(Vertex vertex)
        {
            Dictionary<Vertex, Double> result = new();
            for (int i = 0; i < vertex.Neighbors.Count; i++)
            {
                var edge = GetEdgeByVertex(vertex, vertex.Neighbors[i]);
                result[vertex.Neighbors[i]] = edge.Length;
            }
            return result;
        }

        Edge? GetEdgeByVertex(Vertex v1, Vertex v2)
        {
            return Edges.FirstOrDefault(e => (e.Start.Id == v1.Id && e.End.Id == v2.Id) || (e.End.Id == v1.Id && e.Start.Id == v2.Id));
        }


        
        #region Алгоритм Дейкстры для поиска кратчайшего пути по весам модифицированный для ненаправленного графа 

        Dictionary<Vertex, Dictionary<Vertex, Double>> MakeGraphTable()
        {
            var table = new Dictionary<Vertex, Dictionary<Vertex, Double>>();

            foreach (var vertex in _Vertices.Values)
            {
                table[vertex] = GetNeihborsWithDist(vertex);
            }
            return table;

        }
        Dictionary<Vertex, Double> MakeDistTable(Vertex startVertex, Vertex targetVertex)
        {
            var table = new Dictionary<Vertex, Double>();

            //table[targetVertex] = double.PositiveInfinity;          

            foreach (var vertex in _Vertices.Values)
            {
                table[vertex] = double.PositiveInfinity;

            }
            foreach (var vertex in GetNeihborsWithDist(startVertex))
            {
                table[vertex.Key] = vertex.Value;

            }
            //distances[startVertex] = 0;
            return table;

        }

        Dictionary<Vertex, Vertex?> MakeParentsTable(Vertex startVertex, Vertex targetVertex)
        {
            Dictionary<Vertex, Vertex?> table = new();
            foreach (var vertex in startVertex.Neighbors)
            {
                table[vertex] = startVertex;
            }
            table[targetVertex] = null;
            return table;

        }

        public (List<Vertex>, Double) FindShortestPath(Vertex startVertex, Vertex targetVertex)
        { 
            var graphTable= MakeGraphTable();
            var distTable = MakeDistTable(startVertex, targetVertex);
            return FindShortestPath(startVertex, targetVertex, graphTable, distTable);
        }

        
        internal (List<Vertex>, Double) FindShortestPath(Vertex startVertex, Vertex targetVertex,
                                                        Dictionary<Vertex, Dictionary<Vertex, Double>> graphTable,
                                                        Dictionary<Vertex, Double> distTable)
        {

            // Если начальная и целевая вершины совпадают
            if (startVertex == targetVertex)
                return (new List<Vertex> { startVertex }, 0);

            // Если начальная и целевая вершины совпадают
            if (startVertex.Neighbors.Contains(targetVertex))
                return (new List<Vertex> { startVertex, targetVertex }, graphTable[startVertex][targetVertex]);

            Dictionary<Vertex, Vertex?> parentTable = MakeParentsTable(startVertex, targetVertex);
            HashSet<Vertex> processedVertecies = new HashSet<Vertex>();
            processedVertecies.Add(startVertex);

            Vertex? findClosestNode()
            {
                var shortestDistance = Double.PositiveInfinity;
                Vertex closestNode = null;
                foreach (var vertex in distTable.Keys)
                {
                    var dist = distTable[vertex];
                    if (dist < shortestDistance && !processedVertecies.Contains(vertex))
                    {
                        shortestDistance = dist;
                        closestNode = vertex;
                    }
                }
                return closestNode;
            }


            
            


            var v = findClosestNode();
            while (v is not null)
            {
                var dist = distTable[v];
                var neihbors = graphTable[v];
                foreach (var nei in neihbors.Keys)
                {
                    var new_distance = dist + neihbors[nei];
                    if (!processedVertecies.Contains(nei) && distTable.ContainsKey(nei) && distTable[nei] > new_distance)
                    {
                        distTable[nei] = new_distance;
                        parentTable[nei] = v;
                    }

                }
                processedVertecies.Add(v);
                v = findClosestNode();
            }

            List<Vertex> reconstructPath()
            {
                var _path = new List<Vertex>();


                // Если целевая вершина недостижима
                if (parentTable[targetVertex] == null)
                    return _path;

                Vertex? current = targetVertex;

                // Восстанавливаем путь от целевой вершины до начальной
                _path.Add(current);
                while (current != startVertex)
                {
                    current = parentTable[current];
                    _path.Add(current);
                }

                // Разворачиваем путь, чтобы он был от start до target
                _path.Reverse();



                return _path;
            }

            var res = reconstructPath();
           
            return (res, distTable[targetVertex]);

        }

        public List<BaseGraphEntity> MakePathToEntities(List<Vertex> path)
        {
            List<BaseGraphEntity> res = new List<BaseGraphEntity>() { path[0].Entity };            
            for (int i = 1; i < path.Count; i++)
            {
                res.Add(GetEdgeByVertex(path[i - 1], path[i]).Entity);
                res.Add(path[i].Entity);
            }
            return res;
        }


        #endregion



    }
}