Разработка и реализация универсальной программной коллекции для абстрактного типа данных (АТД) "Простой статический граф" с графическим интерфейсом. Особенности использование ее для решения задач для неориентированных, ориентированных и взвешенных графов.
Аннотация к работе
Интерфейс АТД «Простой, статический граф» включает операции: Конструктор () по умолчанию: создает пустой L - граф с нулевым числом вершин и ребер, Конструктор(V, D, F) создает граф с V вершинами, без ребер, типа D(ориентированный / неориентированный), формы представления F(L-граф/M-граф), Конструктор(V, E, D, F) создает граф с V вершинами, с E случайными ребрами, типа Dense( ) - возвращает форму представления графа (L-граф / M-граф), K( ) - возвращает коэффициент насыщенности графа, TOLISTGRAPH()преобразует граф к L-графу, TOMATRIXGRAPH()преобразует граф к M-графу, INSERTV(v)добавляет к графу вершину c заданным номером v, DELETEV (v)-удаляет из графа вершину c заданным номером v, INSERTE(v1, v2) - добавляет ребро (v1, v2) к графу, соединяющую вершины, заданные номерами v1 и v2, DELETEE (v1, v2)удаляет ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2, Is_Edge(v1, v2)возвращает признак существования в графе ребра соединяющего вершины, заданные номерами v1 и v2, GETEDGEWEIGHT(v1,v2)возвращает вес ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2, SETEDGEWEIGHT (v1,v2, w)задает вес ребра (v1, v2), соединяющего вершины, заданные номерами v1 и v2, равным w. Интерфейс АТД «Итератор ребер графа» включает операции: Конструктор () - создает итератор ребер графа, beg( ) - возвращает итератор, установленный на первое ребро графа, end( ) - возвращает итератор, соответствующий окончанию переходов итератора, operator - переход к следующему ребру графа, operator * - возвращает дескриптор ребра графа, на которое указывает итератор. Интерфейс АТД «Итератор исходящих ребер вершины» включает операции: Конструктор (v) - создает итератор исходящих ребер графа для вершины, заданной номером v, beg( ) - возвращает итератор, установленный на первое исходящее ребро вершины, end( ) - возвращает итератор, соответствующий окончанию переходов итератора, operator - переход к следующему исходящему ребру, operator * - возвращает дескриптор исходящего ребра вершины, на которое указывает итератор. Интерфейс АТД «Итератор входящих ребер вершины» включает операции: Конструктор (v) - создает итератор входящих ребер графа для вершины, заданной номером v, beg( ) - возвращает итератор, установленный на первое входящее ребро вершины, end( ) - возвращает итератор, соответствующий окончанию переходов итератора, operator - переход к следующему входящему ребру, operator * - возвращает дескриптор входящего ребра вершины, на которое указывает итератор..
Список литературы
1. Р. Сэджвик, «Фундаментальные алгоритмы на C . Часть 5. Алгоритмы на графах», 2002 г. - 496 с.
Приложение
Исходные коды
Edge.cs using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace RGR
{ public class Edge : ICLONEABLE
{ private int vertex1;
private int vertex2;
private W weight;
private D data;
public Edge()
{ vertex1 = -1;
vertex2 = -1;
} public Edge(int v1, int v2)
{ vertex1 = v1;
vertex2 = v2;
} public Edge(int v1, int v2, W w)
{ vertex1 = v1;
vertex2 = v2;
weight = w;
} public Edge(int v1, int v2, W w, D d)
{ vertex1 = v1;
vertex2 = v2;
weight = w;
data = d;
} public Object Clone()
{ return new Edge(Vertex1, Vertex2, Weight, Data);
} public int Vertex1
{ set
{ vertex1 = value;
} get
{ return vertex1;
}
} public int Vertex2
{ set
{ vertex2 = value;
} get
{ return vertex2;
}
} public W Weight
{ set
{ weight =value;
} get
{ return weight;
}
} public D Data
{ set
{ data = value;
} get
{ return data;
}
}
}
}
Graph.cs using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace RGR
{ public abstract class Graph
{ public static int MAXVERTICESCOUNT = 10;
private int VERTICESCOUNT;
private int EDGESCOUNT;
private bool directed;
public SORTEDDICTIONARY dictionary;
public Graph()
{
VERTICESCOUNT = 0;
EDGESCOUNT = 0;
directed = false;
} public Graph(int CVERTEX, bool CDIRECTED)
{
VERTICESCOUNT = CVERTEX;
EDGESCOUNT = 0;
directed = CDIRECTED;
} public Graph(int CVERTEX, int CEDGE, bool CDIRECTED)