5

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.

Meinersbur
  • 7,881
  • 1
  • 27
  • 29

4 Answers4

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.

t0mm13b
  • 34,087
  • 8
  • 78
  • 110
  • How is this better than the solution I outlined? – Meinersbur Feb 07 '10 at 15:52
  • @Meinersbur: I thought 'offsetof' is to evaluate the offset in bytes to the member of a structure, and return the no of bytes as a size_t value, so I am not sure if using offsetof is the way to do it...by the way, I was not disagreeing with your solution, my answer is an abstract view of what you're doing... – t0mm13b Feb 07 '10 at 16:21
1

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 ...

dirkgently
  • 108,024
  • 16
  • 131
  • 187
  • `li_list` is the "container" of `li_node`, `n` is a sentinel ### li_list, gr_graph are from a library; just ex_* is by me. It is intended to be used this way. The technique is descibed here: http://stackoverflow.com/questions/326202/generic-list-manipulation-function-in-c#327665 ### Your solution does work for trees only, not graphs. – Meinersbur Feb 07 '10 at 17:05
  • @Meinersbur: Do you mean cycles? – dirkgently Feb 07 '10 at 17:28
  • Not just cycles, also DAG's: Elements that are referenced twice would be copied twice. – Meinersbur Feb 07 '10 at 17:32
  • "memcpy is not required": Actually, all ex_* are stored in a chunk. To copy the data, the complete chunk is just memcopied, not individual structs. – Meinersbur Feb 07 '10 at 17:35
1

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.

Niraj Nawanit
  • 61
  • 4
  • I have a much simpler solution for this (which is sufficient for me): Every `ex_*` has a member `copy`, where it stores a reference to the copy. When I have a reference to the original, I also have a reference the copy, without the need to look up a (sorted) list. – Meinersbur Feb 07 '10 at 17:45
  • For structures defined for you it works. But take structures provided by library. Suppose if it is not directly referenced by your defined structures? In that case you need to store reference to copy of such structures somewhere. – Niraj Nawanit Feb 07 '10 at 19:05
0

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

optikradio
  • 81
  • 6