Глубокая копия структуры графа

Question

У меня есть структура графа в C, и я хочу сделать ее полную копию (включая узлы и ребра).

Структура выглядит так:

struct li_list {
    struct li_node n;
};

struct li_node {
    struct li_node *next, *prev;
};

struct gr_graph {
    struct li_list nodes;
    int nodecount;
};

struct gr_node {
    struct li_node node;
    struct gr_graph *graph;
    int pred_count, succ_count;
    struct li_list pred, succ;
};

struct gr_edge {
    struct li_node succ, pred;
    struct gr_node *from, *to;
    unsigned long marks;
};

Эти структуры существуют не сами по себе, а "наследуются" в другой структуре, например:

struct ex_node {
    struct gr_node _; // "Superclass"
    int id;
    struct ex_node *union_find_parent;
    ...
}

Существует ли элегантное решение для создания глубокой копии такой структуры, включая обновление ссылок на копии?

Примечание. Члены вложенных структур указывают не на корневую структуру, которая в них содержится, а на связанные с ними вложенные структуры (например, ex_node._.pred.n.next указывает на ex_edge._.pred). Это подразумевает утомительную арифметику указателей, когда они должны быть обновлены.

Мое решение до сих пор -

1. Memcopy все структуры
2. Итерация по всем копиям
3. Вызвать кучу макросов для всех полей, которые содержат ссылки (из-за отсутствия RTTI в C, я, вероятно, не схожу с этим)
4. Использование макросов
   • offsetof для вычисления адреса корневой структуры
   • Получить адрес скопированного эквивалента
   • offsetof чтобы указатель указывал на правильную вложенную структуру

Есть ли более простой способ сделать это? Я также боюсь, что забуду добавить вызов макроса, когда добавлю больше полей.

Answer 1

Звучит нормально. Мои $ 0,02:

• Не знаю, зачем вам нужны li_list и li_node. Кроме того, вам не нужен элемент данных для li_node?
• Общая структура выглядит несколько сложной (конечно, я не знаю ваших требований) и пахнет дизайном в стиле C ++ (простите, если я ошибаюсь)
• memcpy не требуется. Достаточно простого назначения.
• Определите член-указатель функции для каждой структуры с указателями-членами, так что вы можете сделать:

Итак:

struct foo {
   int datum;
   int *p;
   foo_copy pfoo;
};

typedef void (*foo_copy)(const struct foo *src, struct foo *dst);

void foo_cp(const struct foo *src, struct foo *dst)
{ 
    *dst = *src; // copy non-pointer data
    dst->p = malloc(sizeof *dst->p);
    dst->p = *src->p;
}


// somewhere else
struct foo s;
// initalize
struct foo *t = malloc(sizeof *t);  
s.copy(&s, &t);

и вложенные типы вызывают соответствующие методы копирования членов ...

Answer 2

memcpy все структуры и создайте отсортированный список, где каждая запись содержит адрес оригинальной структуры и адрес копии структуры.

Теперь перебираем все копии. Для каждой переменной указателя во всех скопированных структурах найдите указатель в отсортированном списке и замените его адресом его копии.

Answer 3

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

Надеюсь, это поможет, С наилучшими пожеланиями, Том.

Answer 4

Да, есть элегантное решение с использованием связующих деревьев и шаблона декоратора.

-Первый, построить связующее дерево графа. Вы можете использовать DFS (Поиск в глубину) или BFS (поиск в ширину) для достижения этой цели. Используйте шаблон декоратора, чтобы дать каждый посещенный узел имеет уникальный идентификатор.

-Следующий (или одновременно) обход связующего дерева от начала до конца и начать строить ваше второе дерево, выделив новые узлы и подключив ребра, которые образуют остовное дерево.

-Наконец, сделайте еще один проход через связующее дерево и используйте синхронизированный идентификаторы, соедините оставшиеся недостающие ребра в новом графе, чтобы они соответствовали связность старого графа. (Например, если узел 5 в графе 1 имеет ребра, соединяющиеся с узлом 7 и узлом 11, то используйте порядок graph2, чтобы соединить его узел 5 с его узлом 7 и 11.)