[ Deep copy of graph structure ]

I have a graph structure in C and want to make a deep copy of it (including nodes and edges).

The structure looks like this:

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;
};

These structs do not exist as themselves, but "inherited" in another struct, like this:

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

Is there an elegant solution of creating a deep copy such a structure, including updating references to the copies?

Note: Members of nested structs do not point to the root struct it contains, but to their related nested struct (for instance, ex_node._.pred.n.next points to a ex_edge._.pred). This implies tedious pointer arithmetic when these must be updated.

My solution up to now is

1. Memcopy all structs
2. Iterate through all copies
3. Call a bunch of macros for all fields that contain references (Due to missing RTTI in C, I probably won't come around this)
4. The macros use
   • offsetof to calculate the address of the root struct
   • Retrieve the address of the copied equivalent
   • offsetof to make the pointer point to the correct nested struct

Is there any easier way to do this? I am also afraid that I forget to add a macro call when I add more fields.

Answer 1

---

I don't think you can do a deep-copy per se, as the pointers will have a memory address assigned to the pointers, the best way I can think of a deep-copy is to simply allocate a new graph structure and copy the data (not pointers) and build it up from there by mallocing the new pointers and adjust the pointers in the ex_node structure. That would be a more thorough solution...

Hope this helps, Best regards, Tom.

Answer 2

---

Sounds ok. My $0.02:

• Not sure why you need both li_list and li_node. Further, don't you need a data member for li_node?
• The overall structure looks a bit complex (of course, I don't know your requirements) and smells of C++ style design (pardon me, if I am wrong)
• memcpy is not required. A simple assignment suffices.
• Define a function pointer member for each structure with pointer members, so that you can do:

So:

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);

and nested types call appropriate member copy methods ...

Answer 3

---

memcpy all structs and create a sorted list where each entry contains address of original struct and address of copy of struct.

Now iterate through all copies. For each pointer variables in all copied structs, search pointer in the sorted list and replace it with the address of its copy.

Answer 4

---

Yes, there is an elegant solution using spanning trees and the decorator pattern.

-First, build a spanning tree of the graph. You can use a DFS (Depth First Search) or a BFS(Breadth First Search) to achieve this. Use the decorator pattern to give each each visited node a unique identifier.

-Next, (or at the same time) traverse the spanning tree from start to finish and begin building your second tree by allocating new nodes and connecting the edges that form the spanning tree.

-Finally, take one more pass through the spanning tree, and using the synchronized identifiers, connect the remaining missing edges in the new graph, so that they match the connectivity of the old graph. (e.g. If node5 in graph1 has edges connecting to node7 and node 11, then use the ordering of graph2 to connect its node5 to its node7 and 11.)