MaxFlowControl.cs

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace WinFormsApp1
{
    public class MaxFlowControl : BaseGraphControl
    {
        private Button btnGenerate;
        private Button btnRun;
        private Button btnReset;
        private Button btnSave;
        private Button btnLoad;
        private Button btnAddNode;
        private Button btnAddEdge;
        private Button btnMoveNode;
        private Button btnSetSource;
        private Button btnSetSink;
        private Button btnCancelMode;
        private NumericUpDown numNodes;
        private Label lblResult;
        private Label lblMode;

        private WeightedGraph.Node sourceNode = null;
        private WeightedGraph.Node sinkNode = null;
        private EditMode currentMode = EditMode.None;

        private enum EditMode { None, AddNode, AddEdge, MoveNode, SetSource, SetSink }

        public MaxFlowControl() : base()
        {
            graph = new WeightedGraph(true);
            InitializeControls();
        }

        private void InitializeControls()
        {
            var flowPanel = new FlowLayoutPanel
            {
                Dock = DockStyle.Fill,
                FlowDirection = FlowDirection.TopDown,
                WrapContents = false,
                AutoScroll = true,
                Padding = new Padding(5)
            };

            var titleLabel = CreateLabel("Алгоритм Эдмондса-Карпа", true, 11);
            titleLabel.ForeColor = Color.DarkBlue;
            flowPanel.Controls.Add(titleLabel);

            flowPanel.Controls.Add(new Label { Height = 5 });

            var genPanel = new FlowLayoutPanel { FlowDirection = FlowDirection.LeftToRight, AutoSize = true };
            genPanel.Controls.Add(CreateLabel("Узлы:"));
            numNodes = new NumericUpDown { Width = 55, Minimum = 4, Maximum = 12, Value = 6 };
            genPanel.Controls.Add(numNodes);
            btnGenerate = CreateButton("🎲 Генерировать", Color.LightBlue, (s, e) => GenerateGraph());
            genPanel.Controls.Add(btnGenerate);
            flowPanel.Controls.Add(genPanel);

            flowPanel.Controls.Add(new Label { Height = 10 });

            flowPanel.Controls.Add(CreateLabel("Редактирование:", true, 10));

            var editPanel1 = new FlowLayoutPanel { FlowDirection = FlowDirection.LeftToRight, AutoSize = true };
            btnAddNode = CreateButton("+ Узел", Color.LightGreen, (s, e) => SetMode(EditMode.AddNode));
            btnAddNode.Width = 80;
            btnAddEdge = CreateButton("+ Ребро", Color.LightYellow, (s, e) => SetMode(EditMode.AddEdge));
            btnAddEdge.Width = 80;
            btnMoveNode = CreateButton("✋ Двигать", Color.LightSkyBlue, (s, e) => SetMode(EditMode.MoveNode));
            btnMoveNode.Width = 80;
            editPanel1.Controls.AddRange(new Control[] { btnAddNode, btnAddEdge, btnMoveNode });
            flowPanel.Controls.Add(editPanel1);

            var editPanel2 = new FlowLayoutPanel { FlowDirection = FlowDirection.LeftToRight, AutoSize = true };
            btnSetSource = CreateButton("Исток (S)", Color.Lime, (s, e) => SetMode(EditMode.SetSource));
            btnSetSource.Width = 95;
            btnSetSink = CreateButton("Сток (T)", Color.Coral, (s, e) => SetMode(EditMode.SetSink));
            btnSetSink.Width = 95;
            editPanel2.Controls.AddRange(new Control[] { btnSetSource, btnSetSink });
            flowPanel.Controls.Add(editPanel2);

            lblMode = new Label
            {
                Text = "Режим: просмотр",
                AutoSize = true,
                ForeColor = Color.DarkBlue,
                Font = new Font("Segoe UI", 9, FontStyle.Italic),
                MaximumSize = new Size(250, 0)
            };
            flowPanel.Controls.Add(lblMode);

            btnCancelMode = CreateButton("↩ Отмена режима", Color.Gainsboro, (s, e) => SetMode(EditMode.None));
            flowPanel.Controls.Add(btnCancelMode);

            flowPanel.Controls.Add(new Label { Height = 10 });

            var lblSpeed = CreateLabel("Скорость анимации: 500мс");
            flowPanel.Controls.Add(lblSpeed);
            flowPanel.Controls.Add(CreateSpeedTrackBar(lblSpeed));

            flowPanel.Controls.Add(new Label { Height = 10 });

            btnRun = CreateButton("▶ Найти макс. поток", Color.RoyalBlue, async (s, e) => await RunMaxFlow());
            btnRun.ForeColor = Color.White;
            btnRun.Width = 180;
            btnRun.Height = 38;
            btnRun.Font = new Font("Segoe UI", 10, FontStyle.Bold);
            flowPanel.Controls.Add(btnRun);

            lblResult = new Label
            {
                Text = "Максимальный поток: —",
                AutoSize = true,
                Font = new Font("Segoe UI", 10, FontStyle.Bold),
                ForeColor = Color.DarkGreen
            };
            flowPanel.Controls.Add(lblResult);

            flowPanel.Controls.Add(new Label { Height = 10 });

            btnReset = CreateButton("🔄 Сбросить", Color.Silver, (s, e) => ResetGraph());
            flowPanel.Controls.Add(btnReset);

            flowPanel.Controls.Add(new Label { Height = 15 });

            flowPanel.Controls.Add(CreateLabel("Файлы:", true, 10));
            var filePanel = new FlowLayoutPanel { FlowDirection = FlowDirection.LeftToRight, AutoSize = true };
            btnSave = CreateButton("💾 Сохранить", Color.LightSteelBlue, (s, e) => SaveGraph());
            btnSave.Width = 115;
            btnLoad = CreateButton("📂 Загрузить", Color.LightSteelBlue, (s, e) => LoadGraph());
            btnLoad.Width = 115;
            filePanel.Controls.AddRange(new Control[] { btnSave, btnLoad });
            flowPanel.Controls.Add(filePanel);

            controlPanel.Controls.Add(flowPanel);
        }

        private void SetMode(EditMode mode)
        {
            currentMode = mode;
            selectedNode = null;
            isDragging = false;
            draggingNode = null;

            lblMode.Text = mode switch
            {
                EditMode.AddNode => "Режим: добавление узла",
                EditMode.AddEdge => "Режим: добавление ребра",
                EditMode.MoveNode => "Режим: перемещение узлов",
                EditMode.SetSource => "Режим: установка истока",
                EditMode.SetSink => "Режим: установка стока",
                _ => "Режим: просмотр"
            };
            lblMode.ForeColor = mode == EditMode.None ? Color.DarkBlue : Color.DarkRed;
            drawPanel.Cursor = mode == EditMode.MoveNode ? Cursors.SizeAll : Cursors.Default;
            RefreshGraph();
        }

        private void GenerateGraph()
        {
            graph = new WeightedGraph(true);
            int n = (int)numNodes.Value;
            graph.GenerateRandom(n, n * 2, drawPanel.Width, drawPanel.Height, 5, 20);

            if (graph.Nodes.Count >= 2)
            {
                sourceNode = graph.Nodes[0];
                sinkNode = graph.Nodes[graph.Nodes.Count - 1];
            }

            Log($"Сгенерирована сеть: {graph.Nodes.Count} узлов, {graph.Edges.Count} рёбер");
            UpdateMatrix();
            RefreshGraph();
        }

        private void ResetGraph()
        {
            graph.ResetFlow();
            graph.ResetState();
            lblResult.Text = "Максимальный поток: —";
            SetMode(EditMode.None);
            RefreshGraph();
        }

        protected override void OnGraphLoaded()
        {
            if (graph.Nodes.Count >= 2)
            {
                sourceNode = graph.Nodes[0];
                sinkNode = graph.Nodes[graph.Nodes.Count - 1];
            }
        }

        protected override void DrawPanel_Paint(object sender, PaintEventArgs e)
        {
            e.Graphics.Clear(Color.White);
            GraphRenderer.DrawGraph(e.Graphics, graph, selectedNode, sourceNode, sinkNode,
                showWeights: true, showFlow: true);

            var legend = new Dictionary<Color, string>
            {
                { Color.Lime, "Исток (S)" },
                { Color.Coral, "Сток (T)" },
                { Color.Yellow, "В пути BFS" },
                { Color.Green, "Использовано" }
            };
            GraphRenderer.DrawLegend(e.Graphics, legend);
        }

        protected override void OnMouseDownHandler(MouseEventArgs e)
        {
            var clickedNode = FindNodeAtPosition(e.Location);

            switch (currentMode)
            {
                case EditMode.AddNode:
                    if (clickedNode == null)
                    {
                        graph.AddNode(e.Location);
                        Log($"Добавлен узел {graph.Nodes.Count - 1}");
                        UpdateMatrix();
                        RefreshGraph();
                    }
                    break;

                case EditMode.AddEdge:
                    if (clickedNode != null)
                    {
                        if (selectedNode == null)
                        {
                            selectedNode = clickedNode;
                            lblMode.Text = $"Выбран узел {clickedNode.Id}\nКликните на второй";
                        }
                        else if (clickedNode != selectedNode)
                        {
                            string input = ShowInputDialog("Пропускная способность:", "Capacity", "10");
                            if (!string.IsNullOrEmpty(input) && int.TryParse(input, out int cap) && cap > 0)
                            {
                                graph.AddEdge(selectedNode, clickedNode, cap);
                                Log($"Добавлено ребро {selectedNode.Id} → {clickedNode.Id} (capacity: {cap})");
                                UpdateMatrix();
                            }
                            selectedNode = null;
                            lblMode.Text = "Режим: добавление ребра";
                            RefreshGraph();
                        }
                    }
                    break;

                case EditMode.MoveNode:
                    if (clickedNode != null)
                    {
                        StartDragging(clickedNode, e.Location);
                    }
                    break;

                case EditMode.SetSource:
                    if (clickedNode != null && clickedNode != sinkNode)
                    {
                        sourceNode = clickedNode;
                        Log($"Исток: узел {clickedNode.Id}");
                        SetMode(EditMode.None);
                        RefreshGraph();
                    }
                    break;

                case EditMode.SetSink:
                    if (clickedNode != null && clickedNode != sourceNode)
                    {
                        sinkNode = clickedNode;
                        Log($"Сток: узел {clickedNode.Id}");
                        SetMode(EditMode.None);
                        RefreshGraph();
                    }
                    break;

                default:
                    selectedNode = clickedNode;
                    RefreshGraph();
                    break;
            }
        }

        protected override void DrawPanel_MouseMove(object sender, MouseEventArgs e)
        {
            if (isRunning) return;

            if (currentMode == EditMode.MoveNode && isDragging && draggingNode != null)
            {
                int newX = e.X - dragOffset.X;
                int newY = e.Y - dragOffset.Y;
                
                int margin = 30;
                newX = Math.Max(margin, Math.Min(drawPanel.Width - margin, newX));
                newY = Math.Max(margin, Math.Min(drawPanel.Height - margin, newY));
                
                draggingNode.Position = new Point(newX, newY);
                RefreshGraph();
            }
            else if (currentMode == EditMode.MoveNode)
            {
                var node = FindNodeAtPosition(e.Location);
                drawPanel.Cursor = node != null ? Cursors.SizeAll : Cursors.Hand;
            }
        }

        protected override void DrawPanel_MouseUp(object sender, MouseEventArgs e)
        {
            if (currentMode == EditMode.MoveNode && isDragging && draggingNode != null)
            {
                Log($"Узел {draggingNode.Id} перемещён");
                isDragging = false;
                draggingNode = null;
                RefreshGraph();
            }
        }

        private async Task RunMaxFlow()
        {
            if (graph.Nodes.Count < 2 || sourceNode == null || sinkNode == null)
            {
                MessageBox.Show("Установите исток и сток!", "Ошибка", MessageBoxButtons.OK, MessageBoxIcon.Warning);
                return;
            }

            isRunning = true;
            SetButtonsEnabled(false);
            graph.ResetFlow();
            graph.ResetState();

            Log("\n=== Алгоритм Эдмондса-Карпа ===");
            int maxFlow = await EdmondsKarp();
            lblResult.Text = $"Максимальный поток: {maxFlow}";
            Log($"=== Максимальный поток = {maxFlow} ===\n");

            isRunning = false;
            SetButtonsEnabled(true);
        }

        private async Task<int> EdmondsKarp()
        {
            int n = graph.Nodes.Count;
            int[,] residual = new int[n, n];

            foreach (var edge in graph.Edges)
                residual[edge.From.Id, edge.To.Id] = edge.Capacity;

            int[] parent = new int[n];
            int maxFlow = 0;
            int step = 1;

            while (BFS(residual, sourceNode.Id, sinkNode.Id, parent))
            {
                List<int> path = new List<int>();
                for (int v = sinkNode.Id; v != sourceNode.Id; v = parent[v])
                    path.Add(v);
                path.Add(sourceNode.Id);
                path.Reverse();

                Log($"Шаг {step}: Путь: {string.Join(" → ", path)}");

                foreach (var edge in graph.Edges)
                    edge.IsHighlighted = false;

                for (int i = 0; i < path.Count - 1; i++)
                {
                    var edge = graph.Edges.Find(ed => ed.From.Id == path[i] && ed.To.Id == path[i + 1]);
                    if (edge != null) edge.IsHighlighted = true;
                    graph.Nodes[path[i]].Color = Color.Yellow;
                }
                graph.Nodes[path[path.Count - 1]].Color = Color.Yellow;
                RefreshGraph();
                await Task.Delay(animationDelay);

                int pathFlow = int.MaxValue;
                for (int v = sinkNode.Id; v != sourceNode.Id; v = parent[v])
                    pathFlow = Math.Min(pathFlow, residual[parent[v], v]);

                Log($"Поток: {pathFlow}");

                for (int v = sinkNode.Id; v != sourceNode.Id; v = parent[v])
                {
                    int u = parent[v];
                    residual[u, v] -= pathFlow;
                    residual[v, u] += pathFlow;

                    var edge = graph.Edges.Find(ed => ed.From.Id == u && ed.To.Id == v);
                    if (edge != null)
                    {
                        edge.Flow += pathFlow;
                        edge.IsInResult = true;
                    }
                }

                maxFlow += pathFlow;
                Log($"Общий поток: {maxFlow}");

                foreach (var node in graph.Nodes)
                    node.Color = Color.LightBlue;
                foreach (var edge in graph.Edges)
                    edge.IsHighlighted = false;

                RefreshGraph();
                await Task.Delay(animationDelay / 2);
                step++;
            }

            Log("Путей больше нет.");
            return maxFlow;
        }

        private bool BFS(int[,] residual, int s, int t, int[] parent)
        {
            int n = graph.Nodes.Count;
            bool[] visited = new bool[n];
            Queue<int> queue = new Queue<int>();

            queue.Enqueue(s);
            visited[s] = true;
            parent[s] = -1;

            while (queue.Count > 0)
            {
                int u = queue.Dequeue();
                for (int v = 0; v < n; v++)
                {
                    if (!visited[v] && residual[u, v] > 0)
                    {
                        queue.Enqueue(v);
                        parent[v] = u;
                        visited[v] = true;
                        if (v == t) return true;
                    }
                }
            }
            return false;
        }

        private void SetButtonsEnabled(bool enabled)
        {
            btnRun.Enabled = enabled;
            btnGenerate.Enabled = enabled;
            btnAddNode.Enabled = enabled;
            btnAddEdge.Enabled = enabled;
            btnMoveNode.Enabled = enabled;
            btnSetSource.Enabled = enabled;
            btnSetSink.Enabled = enabled;
            btnSave.Enabled = enabled;
            btnLoad.Enabled = enabled;
        }
    }
}