extract_subgraph

[kuvshinovdr]

Пусть заданы (ориентированный) граф и последовательность индексов вершин в нём. Мы хотим извлечь подграф, натянутый на вершины, перечисленные в последовательности, выполнив заодно перенумерацию вершин с нуля.

Итак, создать файл source/extract_subgraph.cpp. В нём определить функцию

#include <ogxx/iterator.hpp>
#include <ogxx/graph_view.hpp>

namespace ogxx::directed
{
  auto extract_subgraph(Index_iterator_uptr vertices, Graph_view const& from, Graph_view& subgraph)
    -> Scalar_size { ... }
}

При реализации удобно воспользоваться std::vector или std::unordered_map для перевода индексов между графом и подграфом. Например, vertices перечисляет вершины 4, 5, 1, 7 -- это номера вершин в графе from. В графе subgraph этим номерам соответствуют 0, 1, 2, 3.

Итак, нужно перебрать всех соседей каждой из перечисленных вершин в графе from. Если сосед является вершиной из перечисленных (вершиной подграфа), то записываем соответствующее ребро в subgraph.

Продолжим наш пример. Пусть окрестности перечисленных выше вершин во from следующие:

4: 0, 1, 2 5: 0, 1, 7 1: 2, 4 7: 8, 9

Тогда подграфу принадлежат рёбра 4-1, 5-1, 5-7, 1-4. После перенумерации в подграфе это будут рёбра 0-2, 1-2, 1-3, 2-0, которые и надо добавить.

Пусть функция возвращает общее число добавленных рёбер.

[NasonenkoID]

Дмитрий Рустамович, я попытался реализовать первую половину задания: добавил необходимый файл, в котором не реализована перенумерация. Проверьте, пожалуйста, это то, что вы имели в виду? (Пока не удалось придумать, как осуществить перенумерацию)

[kuvshinovdr]

Так писать не надо, поскольку здесь auto выведется как int:

for (auto i = 0; i < vertices->size(); ++i)

В данном случае тип i -- Scalar_index. Но далее, с итератором из OGxx так работать не получится, у него есть только метод next, причём возможен лишь единственный проход по нему. Поэтому вместо

    for (auto i = 0; i < vertices->size(); ++i)
      index_map[(*vertices)[i]] = i;

следует написать

std::vector<Vertex_index> subgraph_to_from;
for (Vertex_index vertex; vertices->next(vertex);)
  subgraph_to_from.push_back(vertex);

Теперь все номера вершин сложены в subgraph_to_from и этот вектор можно использовать в качестве отображения номера вершины в подграфе (subgraph) в номер той же вершины в исходном графе (from), от этого такое название (subgraph_to_from). Т.е. отображение в одну сторону у нас есть. Ну и subgraph_to_from можно использовать далее вместо *vertices, сам vertices теперь использовать нельзя (он одноразовый).

Обратное преобразование номера можно организовать через unordered_map:

std::unordered_map<Vertex_index, Vertex_index> index_map;
for (size_t i = 0; i < subgraph_to_from.size(); ++i)
  index_map[subgraph_to_from[i]] = i;

Теперь index_map отображает номер вершины из исходного графа в подграф. Через subgraph_to_from и index_map реализована перенумерация.