Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Проектирование программной коллекции "Простой, статический граф"
Проектирование программной коллекции "Простой, статический граф"
Разработка и реализация универсальной программной коллекции для абстрактного типа данных (АТД) "Простой статический граф" с графическим интерфейсом. Особенности использование ее для решения задач для неориентированных, ориентированных и взвешенных графов.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 24.09.2013 |
| Размер файла | 502,3 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
}
}
public MGraph(int cVertex, int cEdge, bool cDirected)
: base(cVertex, cDirected)
{
adjacencyMatrix = new Edge<W, D>[cVertex * 2, cVertex * 2];
dictionary = new SortedDictionary<int, int>();
for (int i = 0; i < cVertex; i++)
{
dictionary.Add(i, i);
}
Random rand = new Random();
for (int i = 0; i < cEdge; )
{
int vertex1 = rand.Next(cVertex);
int vertex2 = rand.Next(cVertex);
bool edgeInserted = addEdge(vertex1, vertex2);
if (edgeInserted) i++;
}
}
public MGraph(int cVertex, int cEdge, Edge<W, D>[,] cAdjacencyMatrix, bool cDirected)
: base(cVertex, cEdge, cDirected)
{
adjacencyMatrix = cAdjacencyMatrix;
}
public override bool getType()
{
return false;
}
public override bool addVertex(int vertexNumber)
{
if (vertexNumber < 0) return false;
dictionary.Add(vertexNumber, getVerticesCount());
int length = adjacencyMatrix.GetLength(0);
if (getVerticesCount() == length) growArray();
increaseVerticesCount();
return true;
}
private void growArray()
{
int newLength;
int oldLength = adjacencyMatrix.GetLength(0);
if (oldLength == 0) newLength = 2;
else newLength = oldLength * 2;
Edge<W, D>[,] newAdjacencyMatrix = new Edge<W, D>[newLength, newLength];
for (int i = 0; i < oldLength; i++)
{
for (int j = 0; j < oldLength; j++)
newAdjacencyMatrix[i, j] = adjacencyMatrix[i, j];
}
adjacencyMatrix = newAdjacencyMatrix;
}
public override bool removeVertex(int vertexNumber)
{
if (vertexNumber < 0) return false;
int deleteIndex = dictionary[vertexNumber];
int deleteEdgesCount = 0;
for (int i = 0; i < getVerticesCount(); i++)
{
if (adjacencyMatrix[deleteIndex, i] != null) deleteEdgesCount++;
if (adjacencyMatrix[i, deleteIndex] != null) deleteEdgesCount++;
}
decreaseEdgesCount(deleteEdgesCount);
decreaseVerticesCount();
for (int i = deleteIndex; i < getVerticesCount(); i++)
for (int j = 0; j < getVerticesCount() + 1; j++)
{
adjacencyMatrix[i, j] = adjacencyMatrix[i + 1, j];
if (adjacencyMatrix[i, j] != null)
{
adjacencyMatrix[i, j].Vertex1 = i;
adjacencyMatrix[i, j].Vertex2 = j;
}
}
for (int i = 0; i < getVerticesCount() + 1; i++)
for (int j = deleteIndex; j < getVerticesCount(); j++)
{
adjacencyMatrix[i, j] = adjacencyMatrix[i, j + 1];
if (adjacencyMatrix[i, j] != null)
{
adjacencyMatrix[i, j].Vertex1 = i;
adjacencyMatrix[i, j].Vertex2 = j;
}
}
int clearIndex = getVerticesCount();
for (int i = 0; i < getVerticesCount() ; i++)
{
adjacencyMatrix[clearIndex, i] = null;
adjacencyMatrix[i, clearIndex] = null;
}
dictionary.Remove(vertexNumber);
for (int key = 0; key <= MAXVERTICESCOUNT; key++)
{
int value;
if (dictionary.TryGetValue(key, out value))
{
if (value > vertexNumber)
{
dictionary.Remove(key);
dictionary.Add(key, value - 1);
}
}
}
return true;
}
public override bool addEdge(int vertex1, int vertex2)
{
if (hasEdge(vertex1, vertex2)) return false;
if (vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source < 0 || destanation < 0 || source == destanation) return false;
if (adjacencyMatrix[source, destanation] != null) return false;
adjacencyMatrix[source, destanation] = new Edge<W, D>(source, destanation);
increaseEdgesCount();
if (!isDirected())
{
adjacencyMatrix[destanation, source] = new Edge<W, D>(destanation, source);
}
return true;
}
public override bool addEdge(Edge<W, D> edge)
{
if (edge == null) return false;
adjacencyMatrix[edge.Vertex1, edge.Vertex2] = edge;
increaseEdgesCount();
if (!isDirected())
{
Edge<W, D> reverseEdge = new Edge<W, D>(edge.Vertex2, edge.Vertex1, edge.Weight, edge.Data);
adjacencyMatrix[edge.Vertex2, edge.Vertex1] = reverseEdge;
}
return true;
}
public override bool removeEdge(int vertex1, int vertex2)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) return false;
if (!hasEdge(vertex1, vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source < 0 || destanation < 0 || source == destanation) return false;
if (adjacencyMatrix[source, destanation] == null) return false;
adjacencyMatrix[source, destanation] = null;
decreaseEdgesCount();
if (!isDirected())
{
adjacencyMatrix[destanation, source] = null;
}
return true;
}
public override bool hasEdge(int vertex1, int vertex2)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) return false;
int source;
int destanation;
if (dictionary.TryGetValue(vertex1, out source) && dictionary.TryGetValue(vertex2, out destanation))
{
if (source < 0 || destanation < 0 || source == destanation) return false;
if(adjacencyMatrix[source, destanation] != null) return true;
}
return false;
}
public override W getEdgeWeight(int vertex1, int vertex2)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) throw new ArgumentException();
if (!hasEdge(vertex1, vertex2)) throw new ArgumentException();
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source < 0 || destanation < 0 || source == destanation) new ArgumentOutOfRangeException("Ребро не существует");
if (adjacencyMatrix[source, destanation] != null)
return adjacencyMatrix[source, destanation].Weight;
throw new ArgumentOutOfRangeException("Ребро не существует");
}
public override bool setEdgeWeight(int vertex1, int vertex2, W weight)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) return false;
if (!hasEdge(vertex1, vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source > getVerticesCount() - 1 || destanation > getVerticesCount() - 1 || source < 0 || destanation < 0) return false;
if (adjacencyMatrix[source, destanation] != null)
{
adjacencyMatrix[source, destanation].Weight = weight;
if (!isDirected()) adjacencyMatrix[destanation, source].Weight = weight;
return true;
}
return false;
}
public override D getEdgeData(int vertex1, int vertex2)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) throw new ArgumentException();
if (!hasEdge(vertex1, vertex2)) throw new ArgumentException();
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source > getVerticesCount() - 1 || destanation > getVerticesCount() - 1 || source < 0 || destanation < 0) throw new ArgumentOutOfRangeException("this edge does not exist");
if (adjacencyMatrix[source, destanation] != null)
return adjacencyMatrix[source, destanation].Data;
throw new ArgumentOutOfRangeException("Ребро не существует");
}
public override bool setEdgeData(int vertex1, int vertex2, D data)
{
if (vertex1 == vertex2 || !dictionary.ContainsKey(vertex1) || !dictionary.ContainsKey(vertex2)) return false;
if (!hasEdge(vertex1, vertex2)) return false;
int source = dictionary[vertex1];
int destanation = dictionary[vertex2];
if (source > getVerticesCount() - 1 || destanation > getVerticesCount() - 1 || source < 0 || destanation < 0) return false;
if (adjacencyMatrix[source, destanation] != null)
{
adjacencyMatrix[source, destanation].Data = data;
if (!isDirected()) adjacencyMatrix[destanation, source].Data = data;
return true;
}
return false;
}
public Object Clone()
{
return new MGraph<W, D>(getVerticesCount(), getEdgesCount(), adjacencyMatrix, isDirected());
}
public override Graph<W, D> toMatrixGraph()
{
return this;
}
public override Graph<W, D> toListGraph()
{
LGraph<W, D> lGraph = new LGraph<W, D>(getVerticesCount(), isDirected());
if (isDirected())
{
for (int i = 0; i < getVerticesCount(); i++)
for (int j = 0; j < getVerticesCount(); j++)
{
if (adjacencyMatrix[i, j] != null)
{
lGraph.addEdge(adjacencyMatrix[i, j]);
}
}
}
else
{
for (int i = 0; i < getVerticesCount(); i++)
for (int j = i + 1; j < getVerticesCount(); j++)
{
if (adjacencyMatrix[i, j] != null)
{
lGraph.addEdge(adjacencyMatrix[i, j]);
}
}
}
lGraph.dictionary = dictionary;
return lGraph;
}
public override List<int> getNeighbors(int vertexNumber)
{
int currentVertexNeighbor = 0;
List<int> result = new List<int>();
while (true)
{
while (adjacencyMatrix[vertexNumber, currentVertexNeighbor] == null)
{
if (currentVertexNeighbor == getVerticesCount())
{
return result;
}
currentVertexNeighbor++;
}
result.Add(adjacencyMatrix[vertexNumber, currentVertexNeighbor++].Vertex2);
}
}
public class VertexIterator<W, D> : Iterator<W, D>
{
public VertexIterator(Graph<W, D> graphC)
: base(graphC)
{
}
public override void begin()
{
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
int min = 100;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Key < min) min = entry.Key;
}
currentPosition = new Edge<W, D>(min, 100);
}
public override void end()
{
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
int max = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Key > max) max = entry.Key;
}
currentPosition = new Edge<W, D>(max, 100);
}
public override void next()
{
if (currentPosition == null)
{
return;
}
int min = 100;
int old = currentPosition.Vertex1;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Key < min && entry.Key > old) min = entry.Key;
}
if (min != 100)
{
currentPosition = new Edge<W, D>(min, 100);
}
else
{
currentPosition = null;
}
}
public override Edge<W, D> state()
{
return currentPosition;
}
}
public class EdgeIterator<W, D> : Iterator<W, D>
{
int lastI = 0;
int lastJ = 0;
int edgesCount = 0;
public EdgeIterator(Graph<W, D> graphC)
: base(graphC)
{
}
public override void begin()
{
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
if (graph.isDirected())
{
for (int i = 0; i < graph.getVerticesCount(); i++)
for (int j = 0; j < graph.getVerticesCount(); j++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == j) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
lastJ = j;
edgesCount = 1;
return;
}
}
}
else
{
for (int i = 0; i < graph.getVerticesCount(); i++)
for (int j = i; j < graph.getVerticesCount(); j++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == j) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
lastJ = j;
edgesCount = 1;
return;
}
}
}
}
public override void end()
{
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
if (graph.isDirected())
{
for (int i = graph.getVerticesCount() - 1; i >= 0; i--)
for (int j = graph.getVerticesCount() - 1; j >= 0; j--)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == j) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
lastJ = j;
edgesCount = 1;
return;
}
}
}
else
{
for (int i = graph.getVerticesCount() - 1; i >= 0; i--)
for (int j = graph.getVerticesCount() - 1; j >= i; j--)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == j) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
lastJ = j;
edgesCount = 1;
return;
}
}
}
}
public override void next()
{
if (currentPosition == null)
{
return;
}
if (edgesCount == graph.getEdgesCount())
{
currentPosition = null;
return;
}
if (graph.isDirected())
{
for (int i = lastI; i < graph.getVerticesCount(); i++)
{
for (int j = lastJ + 1; j < graph.getVerticesCount(); j++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == j) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
lastJ = j;
edgesCount++;
return;
}
}
lastJ = -1;
}
}
else
{
for (int i = lastI; i < graph.getVerticesCount(); i++)
{
for (int j = lastJ + 1; j < graph.getVerticesCount(); j++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == j) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
lastJ = j;
edgesCount = 1;
return;
}
}
lastJ = i;
}
}
}
public override Edge<W, D> state()
{
return currentPosition;
}
}
public class IncomingEdgesIterator<W, D> : Iterator<W, D>
{
int lastI = 0;
int vertexNumb = -2;
public IncomingEdgesIterator(Graph<W, D> graphC, int vertexNumbC)
: base(graphC)
{
vertexNumb = graph.dictionary[vertexNumbC];
begin();
}
public override void begin()
{
if (vertexNumb == -2) return;
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
int i;
for (i = 0; i < graph.getVerticesCount(); i++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == vertexNumb) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
return;
}
}
if (i == graph.getVerticesCount())
{
currentPosition = null;
}
}
public override void end()
{
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
int i;
for (i = graph.getVerticesCount() - 1; i >= 0; i--)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == vertexNumb) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
return;
}
}
if (i == 0)
{
currentPosition = null;
}
}
public override void next()
{
if (currentPosition == null)
{
return;
}
int i;
for (i = lastI + 1; i < graph.getVerticesCount(); i++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == i) source = entry.Key;
if (entry.Value == vertexNumb) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
return;
}
}
if (i == graph.getVerticesCount())
{
currentPosition = null;
}
}
public override Edge<W, D> state()
{
return currentPosition;
}
}
public class OutGoingEdgesIterator<W, D> : Iterator<W, D>
{
int lastI = 0;
int vertexNumb;
public OutGoingEdgesIterator(Graph<W, D> graphC, int vertexNumbC)
: base(graphC)
{
vertexNumb = graph.dictionary[vertexNumbC];
begin();
}
public override void begin()
{
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
int i;
for (i = 0; i < graph.getVerticesCount(); i++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == vertexNumb) source = entry.Key;
if (entry.Value == i) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
return;
}
}
if (i == graph.getVerticesCount())
{
currentPosition = null;
}
}
public override void end()
{
if (graph.getVerticesCount() == 0)
{
currentPosition = null;
return;
}
int i;
for (i = graph.getVerticesCount() - 1; i >= 0; i--)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == vertexNumb) source = entry.Key;
if (entry.Value == i) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
return;
}
if (i == 0)
{
currentPosition = null;
}
}
}
public override void next()
{
if (currentPosition == null)
{
return;
}
int i;
for (i = lastI + 1; i < graph.getVerticesCount(); i++)
{
int source = 0;
int destanation = 0;
foreach (KeyValuePair<int, int> entry in graph.dictionary)
{
if (entry.Value == vertexNumb) source = entry.Key;
if (entry.Value == i) destanation = entry.Key;
}
if (graph.hasEdge(source, destanation))
{
currentPosition = new Edge<W, D>(source, destanation, graph.getEdgeWeight(source, destanation), graph.getEdgeData(source, destanation));
lastI = i;
return;
}
}
if (i == graph.getVerticesCount())
{
currentPosition = null;
}
}
public override Edge<W, D> state()
{
return currentPosition;
}
}
}
}
Размещено на Allbest.ru
Подобные документы
Использование теории графов для решения задач. Информационные структуры входных и выходных данных. Иерархическая схема программы. Руководство оператора: назначение и условия выполнения программы. Граф-схема FormCreate, Found, RassUpdate и Search.
курсовая работа [2,5 M], добавлен 07.08.2013Изучение способов решения линейных и квадратных уравнений методом простой итерации: доказательство теоремы о сходимости и геометрическая интерпретация. Анализ математического решения задачи, ее функциональной модели, блок-схемы и программной реализации.
реферат [411,5 K], добавлен 25.01.2010Поиск источников ориентированного графа. Использование динамических структур при работе с графами. Способы представления графов, операции над ними, описание программной реализации. Процедуры и функции языка. Функции работы с динамической памятью, графами.
курсовая работа [58,6 K], добавлен 29.01.2009Применение теории графов и алгоритмов на графах среди дисциплин и методов дискретной математики. Граф как совокупность двух множеств. Основные способы численного представления графа. Элементы и изоморфизмы графов. Требования к представлению графов в ЭВМ.
курсовая работа [162,2 K], добавлен 04.02.2011Интерфейсы, используемые коллекциями. Применение перечислителя типа IDictionaryEnumerator. Специальные и наблюдаемые коллекции. Итераторы и оператор yield. Основные обобщенные коллекции. Реализация интерфейсов IComparer, IEnumerable и IEnumerator.
курсовая работа [1,2 M], добавлен 17.05.2015Разработка программной реализации решения задачи о минимальном покрывающем дереве графа (построение минимального остова), используя алгоритмы Прима и Крускала. Подсчет времени работы алгоритмов. Их программная реализация на практике с помощью Delphi 7.
курсовая работа [538,1 K], добавлен 29.08.2010Области применения теории графов. Алгоритм решения задачи поиска инвариантного и полного графа. Реализация программы с графическим интерфейсом пользователя на основе алгоритма. Реализация редактора графа и вывод полученных результатов в понятной форме.
курсовая работа [493,3 K], добавлен 27.12.2008Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Представление графов в ЭВМ. Составление алгоритм Краскала с использованием графов с оперделением оптимального пути прокладки телефонного кабеля в каждый из 8 городов.
курсовая работа [241,5 K], добавлен 23.12.2009Основные понятия и определения теории графов: теоремы и способы задания графа, сильная связность графов. Построение блок-схем алгоритма, тестирование разработанного программного обеспечения, подбор тестовых данных, анализ и исправление ошибок программы.
курсовая работа [525,6 K], добавлен 14.07.2012Алгоритм декомпозиции графов и расчеты динамики логических сетей. Преобразование пространства булевых векторов. Описание блоков программной реализации и их взаимодействие. Разработка программы "слияния" статистик на основе алгоритма объединения.
дипломная работа [111,8 K], добавлен 07.03.2012
