Разработка приложения для поиска максимально удалённых вершин в графе

3.1 Алгоритм поиска пути

Для поиска кратчайшего пути между двумя вершинами в графе  был использован следующий алгоритм поиска пути:

Поиск пути начинается с  первой вершины. Данная вершина заносится  в список, а затем, производится цикличный  перебор вершин из списка. В этом цикле соседние с вершинами из списка вершины нумеруются в соответствии со степенью удаленности от начальной  вершины (из которой идет поиск пути). Если вершина уже имеет такой  номер, то новый номер ей назначен не будет, что фактически означает что  вершина будет пропущена. Затем, вершины, пронумерованные в текущей  итерации цикла добавляются в список (перед этим список очищается), а затем, происходит новая итерация цикла. Цикл будет выполнятся до тех пор, пока не будут пронумерованы все вершины. После нумерации вершин таким образом, начинает выполнятся следующий цикл. В этом цикле в список вершин с найденными точками пути заносятся вершины, начиная от конечной точки пути. Следующая вершина для занесения в список определяется минимальным номером соседней вершины с той вершиной, которая была занесена в список последней. Таким образом, цикл будет выполнятся пока не будет достигнута начальная вершина. Найденный маршрут будет являться кратчайшим маршрутом между двумя вершинами.

3.2 Классы и диаграмма классов

При разработке программного продукта, были реализованы следующие  классы:

• GraphNode - реализует вершину графа;
• GraphEdge - реализует ребро графа;
• Graph - реализует работу с графом (создание/удаление вершин и ребер, получение информации о них, графическое отображение графа, его сохранение в файл и загрузка из файла);
• GraphPathFinder - реализует поиск кратчайшего пути в графе и графическое отображение графа с найденным путем.

Диаграмма классов:

 

3.3 Методы класса GraphEdge

1. В конструктор класса  передаются индексы вершин, связанных данным ребром:

public GraphEdge(int n1, int n2)

        {

            node1 = n1;

            node2 = n2;

        }

2. GetLinkedNodes - устанавливает значения переданных в метод параметров, в соответствии с индексами вершин, связанных данным ребром:

public void GetLinkedNodes(out int n1, out int n2)

        {

            n1 = node1;

            n2 = node2;

        }

3.4 Методы класса GraphNode

1. В конструктор класса передаются координаты вершины, по которым данная вершина будет отображаться на форме, а также, необязательный параметр, отвечающий за видимость вершины на форме (по умолчанию, вершина будет видимой):

public GraphNode(int _x, int _y, bool _isValide = true)

        {

            x = _x;

            y = _y;

            isValide = _isValide;

        }

2. Методы GetPostionX и GetPositionY возвращают X и Y координаты вершины соответственно:

public int GetPositionX()

        {

            return x;

        }

 

public int GetPositionY()

        {

            return y;

        }

3. Метод IsExists возвращает видимость вершины:

 

public bool isExists()

        {

            return isValide;

        }

4. Метод Remove удаляет вершину (устанавливает координаты равными -1, а также устанавливает видимость вершины в false):

public void Remove()

        {

            x = -1;

            y = -1;

            isValide = false;

        }

3.5 Функции класса Graph

1. В конструктор класса  передаются имена файлов изображений  для вершин. Конструктор инициализирует списки с вершин и ребер, затем вызывается функция LoadResources:

public Graph(string nodeImage, string nodeOkImage)

        {

            nodes = new List<GraphNode>();

            edges = new List<GraphEdge>();

            LoadResources(nodeImage, nodeOkImage);

        }

2. Метод Clear отвечает за очистку списков ребер и вершин:

public void Clear()

        {

            nodes.Clear();

            edges.Clear();

        }

3. Метод Draw отвечает за графическое отображение графа на переданном в функцию графическом контексте:

public void Draw(ref Graphics g)

        {

            Pen pen = new Pen(Color.Black, 5);

            for (int i = 0; i < edges.Count; i++)

            {

                Point xFrom, xTo;

                int node1, node2;

                edges[i].GetLinkedNodes(out node1, out node2);

                xFrom = new Point(nodes[node1].GetPositionX(), nodes[node1].GetPositionY());

                xTo = new Point(nodes[node2].GetPositionX(), nodes[node2].GetPositionY());

                g.DrawLine(pen, xFrom, xTo);

            }

            for (int i = 0; i < nodes.Count; i++)

            {

                GraphNode node = nodes[i];

                if (node.isExists())

                {

                    bool isOkNode = false;

                    foreach (GraphEdge edge in edges)

                    {

                        int node1, node2;

                        edge.GetLinkedNodes(out node1, out node2);

                        if (node1 == i || node2 == i)

                        {

                            isOkNode = true;

                            break;

                        }

                    }

                    if (isOkNode)

                        g.DrawImage(imgOkNode, node.GetPositionX() - imageCenter, node.GetPositionY() - imageCenter);

                    else

                        g.DrawImage(imgNode, node.GetPositionX() - imageCenter, node.GetPositionY() - imageCenter);

                    g.DrawString((i + 1).ToString(), font, Brushes.Black, node.GetPositionX() - 12, node.GetPositionY() - 12);

                }

            }           

        }

  4. Метод EdgeAdd связывает вершины, имеющие указанные индексы (переданные в метод в качестве параметров), если вершины до этого еще не были связаны:

public int EdgeAdd(int node1, int node2)

        {

            bool canLink = true;

            foreach (GraphEdge edge in edges)

            {

                int n1, n2;

                edge.GetLinkedNodes(out n1, out n2);

                if ((n1 == node1 || n1 == node2) && (n2 == node1 || n2 == node2))

                {

                    canLink = false;

                    break;

                }

            }

            if (canLink)

            {

                edges.Add(new GraphEdge(node1, node2));

                return edges.Count - 1;

            }

            return -1;

        }

5. Метод EdgeRemove удаляет ребро с заданным индексом:

public bool EdgeRemove(int id)

        {

            if (edges.Count > id && edges.Count > -1)

            {

                edges.RemoveAt(id);

            }

            return false;

        }

6. Метод Load служит для загрузки графа из файла с заданным именем, передающимся в качестве параметра:

public bool Load(string filename)

        {

            FileStream fs = new FileStream(filename, FileMode.Open, FileAccess.Read);

            BinaryReader r = new BinaryReader(fs);

            string sign = r.ReadString();

            if (sign.Equals(signature, StringComparison.InvariantCulture))

            {

                Clear();

                int nodeCount = r.ReadInt32();

                int edgeCount = r.ReadInt32();

                for (int i = 0; i < nodeCount; i++)

                {

                    bool isValide = r.ReadBoolean();

                    NodeAdd(r.ReadInt32(), r.ReadInt32(), isValide);

                }

                for (int i = 0; i < edgeCount; i++)

                {

                    EdgeAdd(r.ReadInt32(), r.ReadInt32());

                }

                r.Close();

                return true;

            }

            r.Close();

            return false;

        }

7. Метод LoadResources загружает изображения вершин из заданных файлов картинок формата "png":

public void LoadResources(string nodeImage, string nodeOkImage)

        {

            imgNode = Image.FromFile(nodeImage);

            imgOkNode = Image.FromFile(nodeOkImage);

            imageCenter = (int)Math.Round((float)imgOkNode.Width / 2);

            font = new Font("Times New Roman", 14, FontStyle.Bold);

        }

8. Метод NodeAdd добавляет вершину с указанными координатами и видимостью в граф:

public int NodeAdd(int x, int y, bool isValide = true)

        {

            nodes.Add(new GraphNode(x, y, isValide));

            return nodes.Count - 1;

        }

9. Метод NodeGetID возвращает индекс вершины, находящейся под курсором мыши, либо -1, если под курсором нет вершин:

public int NodeGetID(int mouseX, int mouseY)

        {

            for (int i = 0; i < nodes.Count; i++)

            {

                int nX = nodes[i].GetPositionX() - 16;

                int nY = nodes[i].GetPositionY() - 16;

                if (mouseX >= nX && mouseX <= nX + imgOkNode.Width)

                    if (mouseY >= nY && mouseY <= nY + imgOkNode.Height)

                        return i;

            }

            return -1;

        }

10. Методы NodeGetX и NodeGetY возвращает x и y координаты указанной вершины соответственно:

public int NodeGetX(int id)

        {

            if (id < nodes.Count && nodes.Count > -1)

            {

                return nodes[id].GetPositionX();

            }

            return -1;

        }

 

        public int NodeGetY(int id)

        {

            if (id < nodes.Count && nodes.Count > -1)

            {

                return nodes[id].GetPositionY();

            }

            return -1;

        }

11. Метод NodeRemove удаляет указанную вершину из графа (также, удаляет все ребра, связанные с вершиной):

public bool NodeRemove(int id)

        {

            if (nodes.Count > id && nodes.Count > -1)

            {

                List<int> toRemove = new List<int>();

                for (int i = 0; i < edges.Count; i++)

                {

                    int node1, node2;

                    edges[i].GetLinkedNodes(out node1, out node2);

                    if (node1 == id || node2 == id)

                        toRemove.Add(i);

                }

                while (toRemove.Count > 0)

                {

                    EdgeRemove(toRemove[0]);

                    toRemove.RemoveAt(0);

                    for (int i = 0; i < toRemove.Count; i++)

                    {

                        toRemove[i] -= 1;

                    }

                }

                nodes[id].Remove();

                return true;

            }

            return false;

        }

10. Метод NodeSetPosition устанавливает координаты заданной вершины:

public bool NodeSetPosition(int id, int x, int y)

        {

            if (id < nodes.Count && nodes.Count > -1)

            {

                nodes[id].SetPosition(x, y);

                return true;

            }

            return false;

        }

10. Метод Save сохраняет граф в файл с заданным именем:

public void Save(string filename)

        {

            FileStream fs = new FileStream(filename, FileMode.Create, FileAccess.Write);

            BinaryWriter w = new BinaryWriter(fs);

            w.Write(signature);

            w.Write(nodes.Count);

            w.Write(edges.Count);

            for (int i = 0; i < nodes.Count; i++)

            {

                w.Write(nodes[i].isExists());

                w.Write(nodes[i].GetPositionX());

                w.Write(nodes[i].GetPositionY());

            }

            for (int i = 0; i < edges.Count; i++)

            {

                int node1, node2;

                edges[i].GetLinkedNodes(out node1, out node2);

                w.Write(node1);

                w.Write(node2);

            }

            w.Flush();

            w.Close();

        }

3.6 Методы класса GraphMaxDistanceFinder

1. В конструктор класса  передается ссылка на граф, в  котором необходимо проводить  поиск пути, а также, имя файла,  хранящего изображение вершины,  которая входит в найденный  путь:

public GraphPathFinder(ref Graph _graph, string pathNodeImage)

        {

            graph = _graph;

            imgPathNode = Image.FromFile(pathNodeImage);

        }

2. Метод Draw служит для графического отображения графа с найденным маршрутом на заданном графическом контексте (Данный метод используется вместо метода Draw класса Graph:

public void Draw(ref Graphics g)

        {

            Pen pen;

            Pen normalPen = new Pen(Color.Black, 5);

            Pen linkedPen = new Pen(Color.Red, 5);

            for (int i = 0; i < graph.edges.Count; i++)

            {

                Point xFrom, xTo;

                int node1, node2;

                graph.edges[i].GetLinkedNodes(out node1, out node2);

                xFrom = new Point(graph.nodes[node1].GetPositionX(), graph.nodes[node1].GetPositionY());

                xTo = new Point(graph.nodes[node2].GetPositionX(), graph.nodes[node2].GetPositionY());

                pen = normalPen;

                if (pathNodes.Contains(node1) && pathNodes.Contains(node2))

                    pen = linkedPen;

                g.DrawLine(pen, xFrom, xTo);

            }

            for (int i = 0; i < graph.nodes.Count; i++)

            {

                GraphNode node = graph.nodes[i];

                if (node.isExists())

                {

                    NODE_TYPE nodeType = NODE_TYPE.NOT_CONNECTED; //0 - Not connected, 1 - OK node, 2 - Path node

                    if (!pathNodes.Contains(i))

                        foreach (GraphEdge edge in graph.edges)

                        {

                            int node1, node2;

                            edge.GetLinkedNodes(out node1, out node2);

                            if (node1 == i || node2 == i)

                            {

                                nodeType = NODE_TYPE.OK;

                                break;

                            }

                        }

                    else

                        nodeType = NODE_TYPE.PATH;

                    switch (nodeType)

                    {

                        case NODE_TYPE.NOT_CONNECTED:

                            g.DrawImage(graph.imgNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);

                            break;

                        case NODE_TYPE.OK:

                            g.DrawImage(graph.imgOkNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);

                            break;

                        case NODE_TYPE.PATH:

                            g.DrawImage(imgPathNode, node.GetPositionX() - graph.imageCenter, node.GetPositionY() - graph.imageCenter);