Я создаю простое программное обеспечение для сетевого рисования на C # (для ясности я напишу «сеть», а не «график»). Сети могут в конечном итоге иметь несколько направленных ребер между некоторыми вершинами / узлами. Я разработал структуру данных для этого программного обеспечения следующим образом:
- Каждый узел и ребро имеют соответствующий «интерактивный» объект, определяющий входные данные для визуализации и обработки, такие как щелчки, нацеленные на эти видимые объекты. Эти объекты могут хранить любое количество данных о соответствующих объектах, которые я выбираю, и на данный момент они содержат, например, конечные точки ребер, а также целочисленный идентификатор для каждого объекта.
- Узлы (и ребра между ними) делятся на связанные компоненты. Я хочу реализовать подпрограммы, которые объединяют эти компоненты при добавлении ребер и обнаруживают отключение при удалении ребер или узлов.
- Общие данные для сети , которые пока просто записывают количество ребер между каждой парой узлов, игнорируя направление , должны быть представлены в экземпляре интерфейса
INetwork, который содержит такие процедуры для добавления и удаления узлов и ребер, определения соседей вершины и т. д.
Мой вопрос заключается в том, как на самом деле реализовать этот IMatrix интерфейс. Реализация может варьироваться в зависимости от разреженности графика, но я хотел бы знать, что с точки зрения памяти, скорости обработки и т. Д., Что было бы наиболее эффективным.
Точнее, я знаю, что мог бы просто создать матрицу смежности для каждого компонента или аналогичным образом список смежности, но , какие типы лучше всего подходят для этих ролей в C # , учитывая, что мой узлы имеют целочисленные идентификаторы, которые, как я ожидаю, лучше всего оставлять постоянными?
Будет ли Dictionary<int,Dictionary<int,int>> когда-нибудь хорошим способом реализации счетчика смежности, чтобы иметь возможность эффективно удалять записи? Будет ли работать большой двумерный массив с учетом индексации узла? Если я вместо этого сохраню матрицу в виде 1-мерного массива, скажем, как int[] с некоторыми методами для обработки этого как 2- или 3-мерного массива, будет ли это лучше каким-либо значимым способом?
Конечно, у каждой реализации есть свои плюсы и минусы, но я ожидаю, что самой обременительной процедурой всегда будет та, которая проверяет, привело ли удаление ребра к отключению сети. Таким образом, я хочу, чтобы любая используемая реализация могла быстро проверить:
- Был ли удаленный край последним ребром между его парой вершин.
- Если это так, чтобы можно было быстро идентифицировать соседей каждого узла последовательно, чтобы определить, какие узлы лежат в каком из результирующих компонентов.
Заранее спасибо за любые предложения. В случае, если кому-то интересно, выбор C # был вызван тем, что я полагался на движок создания игр Unity для его рендеринга и (возможно, позже) физических возможностей.