эффективная структура данных C ++ для рассмотрения в этом случае

Question

Привет код-гуру!

Я пишу алгоритм, который связывает, например, node_A Region_A с node_D Region_D. (node_A и node_D - просто целые числа). Таких узлов может быть более 100 тыс.

Предположим, что отрезок между A и D проходит через ряд других областей, B, C, Z. Между этими двумя узлами будет максимум 20 регионов.

Каждый регион имеет свои свойства, которые могут различаться в зависимости от соединения A-D. Я хочу получить доступ к ним позже.

Я ищу хорошую структуру данных (возможно, контейнер STL), которая может хранить эту информацию для определенного соединения.

Например, для соединения A - D я хочу сохранить:

node_A, 
node_D, 
crosssectional area (computed elsewhere) , 
regionB, 
regionB_thickness, 
regionB other properties, 
regionC, ....

Данные могут быть double, int, string, а также могут быть массивом / вектором и т. Д.

1. Сначала я подумал о создании структур или классов для regionB, regionC и т. Д. Но для каждого соединения A-D определенные свойства, такие как толщина области, через которую проходит это соединение, различны. Там будет только 3 или 4 разных вещи, которые мне нужно хранить, относящиеся к региону. Какую структуру данных мне следует рассмотреть здесь (любой контейнер STL, например, вектор?). Не могли бы вы предложить одну? (был бы признателен за фрагмент кода)

2. Чтобы получить доступ к соединению между узлами A-D, я хочу использовать int node_A (индекс). Это, вероятно, означает, что мне нужно использовать хэш-карту или аналогичную структуру данных. Может кто-нибудь, пожалуйста, предложите хорошую структуру данных в C ++, которая может эффективно держать данные такого рода для соединения A -D, описанного выше? (был бы признателен за фрагмент кода)

спасибо!

UPDATE по некоторым причинам я не могу использовать pkgs как boost. Поэтому хочу узнать, могу ли я использовать какие-либо библиотеки из STL

Answer 1

Ну, как все заметили, это график. Вопрос в том, является ли это разреженным или плотным графом? Обычно существует два способа представления графиков (больше, но вам, вероятно, нужно будет рассмотреть только эти два):

• матрица смежности
• список смежностей

Матрица смежности - это, в основном, матрица NxN, в которой все узлы в первой строке и столбце хранятся, а данные соединения (ребра) представлены в виде ячеек, поэтому вы можете индексировать ребра по вершинам. Извините, если мой английский отстой, а не мой родной язык. В любом случае, вам следует учитывать матрицу смежности только в том случае, если у вас плотный граф и вам нужно очень быстро найти соединения узел-> ребро-> узел. Однако итерация по соседям или добавление / удаление вершин в матрице смежности выполняется медленно, первая требует N итераций, а вторая изменяет размер массива / вектора, который вы используете для хранения матрицы.

Другой вариант - использовать список смежности. По сути, у вас есть класс, представляющий узел, и класс, представляющий ребро, в котором хранятся все данные для этого ребра, и два указателя, которые указывают на узлы, к которым он подключен. Класс узла имеет некоторую коллекцию (список подойдет) и отслеживает все ребра, к которым он подключен. Тогда вам понадобится класс менеджера или просто набор функций, которые работают на ваших узлах. Добавление / соединение узлов в этом случае тривиально, как и перечисление соседей или связанных ребер. Однако итерировать по всем краям сложнее. Эта структура более гибкая, чем матрица смежности, и она лучше для разреженных графов.

Я не уверен, что полностью понял ваш вопрос, но если бы я понял, вам лучше воспользоваться матрицей смежности, похоже, у вас плотный граф с множеством взаимосвязанных узлов и вам нужна только информация о соединении .

В Википедии есть хорошая статья о графиках как структуре данных, а также хорошие ссылки и ссылки, и поиск примеров не должен быть трудным. Надеюсь, это поможет:
Ссылка

Answer 2

boost имеет библиотеку графов: boost.graph . Проверьте это, если это полезно в вашем случае.

Answer 3

Вы должны попытаться сгруппировать вещи вместе, когда сможете. Вы можете сгруппировать информацию по каждому региону вместе с чем-то вроде следующего:

class Region_Info {
  Region *ptr;
  int thickness;
  // Put other properties here.
};

Затем вы можете легче создать структуру данных для вашего линейного сегмента, возможно, что-то вроде следующего:

class Line_Segment {
  int node_A;
  int node_D;
  int crosssectional_area;
  std::list<Region_Info>;
};

Если вы ограничены только 20 регионами, тогда список должен работать нормально. Вектор также подойдет, если вы предпочитаете.

Answer 4

Рассматривали ли вы массив смежности для каждого узла, в котором хранятся узлы, к которым он подключен, наряду с другими данными?

Сначала определите узел

class Node
{
   int id_;
   std::vector<AdjacencyInfo> adjacency_;

}

Где класс AdjacencyInfo может хранить множество нужных вам данных. Вы можете изменить Вектор на hashmap с идентификатором узла в качестве ключа, если скорость поиска является проблемой. Для необычного доступа вы можете захотеть перегрузить оператор [], если это является обязательным требованием.

Так как пример

class Graph
{
     std::map<int, Node> graph_;
}