ID/Assets/Code/Lab6/Graph.cs

using System;
using System.Collections.Generic;
using System.Linq;
using UnityEngine;

namespace Code.Lab6
{
    public abstract class Graph : MonoBehaviour
    {
        public GameObject vertexPrefab;
        protected List<Vertex> Vertices;
        protected List<List<Vertex>> Neighbours;
        protected List<List<float>> Costs;

        public virtual void Start()
        {
            if (Application.isPlaying)
            {
                Load();
            }
        }

        public virtual void Load() { }

        public virtual int GetSize()
        {
            if (ReferenceEquals(Vertices, null)) return 0;
            return Vertices.Count;
        }

        public virtual Vertex GetNearestVertex(Vector3 position)
        {
            return null;
        }

        public virtual Vertex GetVertexObj(int id)
        {
            if (ReferenceEquals(Vertices, null) || Vertices.Count == 0)
                return null;
            if (id < 0 || id >= Vertices.Count)
                return null;
            return Vertices[id];
        }

        public virtual Vertex[] GetNeighbours(Vertex v)
        {
            if (ReferenceEquals(Neighbours, null) || Neighbours.Count == 0 || v.id < 0 || v.id >= Neighbours.Count)
                return Array.Empty<Vertex>();
            return Neighbours[v.id].ToArray();
        }

        public virtual Edge[] GetEdges(Vertex v)
        {
            return v.neighbours == null ? Array.Empty<Edge>() : v.neighbours.ToArray();
        }

        public List<Vertex> GetPathBfs(GameObject srcObj, GameObject dstObj)
        {
            if (!srcObj || !dstObj)
                return new List<Vertex>();

            var src = GetNearestVertex(srcObj.transform.position);
            var dst = GetNearestVertex(dstObj.transform.position);

            if (!src || !dst)
            {
                Debug.LogWarning("Source or destination vertex is null");
                return new List<Vertex>();
            }

            Debug.Log($"BFS from {src.id} to {dst.id}");

            var previous = new Dictionary<int, int>();
            var visited = new HashSet<int>();
            var queue = new Queue<Vertex>();

            visited.Add(src.id);
            previous[src.id] = src.id;
            queue.Enqueue(src);

            while (queue.Count > 0)
            {
                var current = queue.Dequeue();

                if (current.id == dst.id)
                {
                    Debug.Log("BFS: Path found!");
                    return BuildPath(src.id, dst.id, previous);
                }

                var neighbours = GetNeighbours(current);

                foreach (var neighbour in neighbours)
                {
                    if (!neighbour) continue;

                    if (!visited.Add(neighbour.id)) continue;
                    
                    previous[neighbour.id] = current.id;
                    queue.Enqueue(neighbour);
                }
            }

            Debug.LogWarning("BFS: No path found");
            return new List<Vertex>();
        }

        public List<Vertex> GetPathDfs(GameObject srcObj, GameObject dstObj)
        {
            if (!srcObj || !dstObj)
                return new List<Vertex>();

            var src = GetNearestVertex(srcObj.transform.position);
            var dst = GetNearestVertex(dstObj.transform.position);

            if (!src || !dst)
            {
                Debug.LogWarning("Source or destination vertex is null");
                return new List<Vertex>();
            }

            Debug.Log($"DFS from {src.id} to {dst.id}");

            var previous = new Dictionary<int, int>();
            var visited = new HashSet<int>();
            var stack = new Stack<Vertex>();

            visited.Add(src.id);
            previous[src.id] = src.id;
            stack.Push(src);

            while (stack.Count > 0)
            {
                var current = stack.Pop();

                if (current.id == dst.id)
                {
                    Debug.Log("DFS: Path found!");
                    return BuildPath(src.id, dst.id, previous);
                }

                var neighbours = GetNeighbours(current);

                foreach (var neighbour in neighbours)
                {
                    if (!neighbour) continue;

                    if (!visited.Add(neighbour.id)) continue;
                    
                    previous[neighbour.id] = current.id;
                    stack.Push(neighbour);
                }
            }

            Debug.LogWarning("DFS: No path found");
            return new List<Vertex>();
        }

        private List<Vertex> BuildPath(int srcId, int dstId, Dictionary<int, int> previous)
        {
            var path = new List<Vertex>();

            if (!previous.ContainsKey(dstId))
            {
                Debug.LogError("Destination not in previous dictionary");
                return path;
            }

            var currentId = dstId;

            while (currentId != srcId)
            {
                var currentVertex = GetVertexById(currentId);
                if (!currentVertex)
                {
                    Debug.LogError($"Vertex with id {currentId} not found");
                    break;
                }

                path.Add(currentVertex);

                if (!previous.TryGetValue(currentId, out var previou))
                {
                    Debug.LogError($"Previous not found for id {currentId}");
                    break;
                }

                currentId = previou;
            }

            var srcVertex = GetVertexById(srcId);
            if (srcVertex is not null)
            {
                path.Add(srcVertex);
            }

            path.Reverse();

            Debug.Log($"Path built with {path.Count} vertices");
            return path;
        }

        private Vertex GetVertexById(int id)
        {
            return Vertices?.FirstOrDefault(v => v && v.id == id);
        }

        private List<Vertex> BuildPath(int srcId, int dstId, ref int[] prevList)
        {
            var path = new List<Vertex>();
            var prev = dstId;

            do
            {
                var v = GetVertexById(prev);
                if (v == null)
                {
                    Debug.LogError($"Vertex with id {prev} not found");
                    break;
                }

                path.Add(v);

                if (prev < 0 || prev >= prevList.Length)
                {
                    Debug.LogError($"Index {prev} out of range for prevList (size {prevList.Length})");
                    break;
                }

                prev = prevList[prev];
            } while (prev != srcId && prev != -1);

            if (prev != -1)
            {
                var srcV = GetVertexById(srcId);
                if (srcV != null)
                    path.Add(srcV);
            }

            path.Reverse();
            return path;
        }
        
        public List<Vertex> GetPathWeights(GameObject srcObj, GameObject dstObj)
        {
            if (!srcObj || !dstObj)
                return new List<Vertex>();

            var src = GetNearestVertex(srcObj.transform.position);
            var dst = GetNearestVertex(dstObj.transform.position);

            if (!src || !dst)
            {
                Debug.LogWarning("Source or destination vertex is null");
                return new List<Vertex>();
            }

            Debug.Log($"Dijkstra from {src.id} to {dst.id}");

            var distances = new Dictionary<int, float>();
            var previous = new Dictionary<int, int>();
            var unvisited = new HashSet<int>();

            foreach (var vertex in Vertices.Where(vertex => vertex))
            {
                distances[vertex.id] = float.MaxValue;
                unvisited.Add(vertex.id);
            }
            
            distances[src.id] = 0;
            previous[src.id] = src.id;
            
            while (unvisited.Count > 0)
            {
                var minDist = float.MaxValue;
                var currentId = -1;
                
                foreach (var id in unvisited)
                {
                    if (distances.TryGetValue(id, out var dist) && dist < minDist)
                    {
                        minDist = dist;
                        currentId = id;
                    }
                }
                
                if (currentId == -1) break;

                if (currentId == dst.id)
                {
                    Debug.Log($"Dijkstra: Path found! Total cost: {distances[dst.id]:F2}");
                    return BuildPathWeights(src.id, dst.id, previous);
                }
                
                unvisited.Remove(currentId);

                var currentVertex = GetVertexById(currentId);
                if (!currentVertex) continue;
                
                var edges = GetEdges(currentVertex);

                foreach (var edge in edges)
                {
                    if (!edge.Vertex) continue;
                    
                    var neighbourId = edge.Vertex.id;
                    if (!unvisited.Contains(neighbourId)) continue;
                    
                    var newDist = distances[currentId] + edge.cost;
                    
                    if (newDist < distances[neighbourId])
                    {
                        distances[neighbourId] = newDist;
                        previous[neighbourId] = currentId;
                    }
                }
            }
            
            Debug.LogWarning("Dijkstra: No path found");
            return new List<Vertex>();
        }

        private List<Vertex> BuildPathWeights(int srcId, int dstId, Dictionary<int, int> previous)
        {
            var path = new List<Vertex>();

            if (!previous.ContainsKey(dstId))
            {
                Debug.LogError("Destination not in previous dictionary");
                return path;
            }

            var currentId = dstId;

            while (currentId != srcId)
            {
                var currentVertex = GetVertexById(currentId);
                if (!currentVertex)
                {
                    Debug.LogError($"Vertex with id {currentId} not found");
                    break;
                }

                path.Add(currentVertex);

                if (!previous.TryGetValue(currentId, out var prevId))
                {
                    Debug.LogError($"Previous not found for id {currentId}");
                    break;
                }

                currentId = prevId;
            }

            var srcVertex = GetVertexById(srcId);
            if (srcVertex is not null)
            {
                path.Add(srcVertex);
            }

            path.Reverse();

            Debug.Log($"Path built with {path.Count} vertices");
            return path;
        }
    }
}