What's the simplest and most efficient data structure for building acyclic dependencies?

Question

I'm trying to build a sequence that determines the order to destroy objects. We can assume there are no cycles. If an object A uses an object B during its (A's) construction, then object B should still be available during object A's destruction. Thus the desired order of destruction is A, B. If another object C uses object B during its (C's) construction as well, then the desired order is A, C, B. In general, as long as an object X is only destroyed after all other objects that used that object during their construction, the destruction is safe.

If our destruction order so far is AECDBF, and we now are given an X (we never know before hand what order the construction will initially happen in, it's discovered on the fly), that uses C and F during its construction, then we can get a new safe order by putting X before whichever is currently earlier in the list, C or F (happens to be C). So the new order would be AB**X**CDEF.

In the context of the X example, a linked list seems unsuitable because a lot of linear scanning would be involved to determine which is earlier, C or F. An array will mean slow insertions which is going to be one of the more common operations. A priority queue doesn't really have a suitable interface, there's no, "Insert this item before whichever one of these items is earliest" (we don't know the right priority before hand to make sure it's inserted before the lower priority element and without disturbing other entries).

All objects are constructed, desired order is computed, and the sequence will be iterated once and destructed in order. No other operations need to be done (in fact, after using whatever data structure to determine the order, it could be copied into a flat array and discarded).

Edit: Just to clarify, the first time an object is used is when it is constructed. So if A uses B, then E uses B, when E tries to use B it has already been created. This means a stack won't give the desired order. AB will become ABE when we want AEB.

Edit2: I'm trying to build the order 'as I go' to keep the algorithm in place. I would prefer to avoid building up a large intermediate structure and then converting that to a final structure.

Edit3: I made this too complicated ;p

Answer 1

Since dependencies are always initialised before the objects that depend on them, and remain available until after such objects are destroyed, it should always be safe to destroy objects in strictly reverse order of initialisation. So all you need is a linked list to which you prepend objects as they are initialised and walk on destruction, and for each object to request initialisation of all its dependencies that have not yet been initialised before it initialises itself.

So for initialisation of each object:

• initialise self, initialising uninitialised dependencies as we go
• add self to front of destruction list (or push self onto stack if you're using a stack)

and for destruction, just walk the linked list from the front forwards (or pop items off stack until empty), destroying as you go. The example in your first paragraph initialised in order B, A, C would thus be destroyed in order C, A, B - which is safe; the example in your edit would be initialised in order B, A, E (not A, B, E since A depends on B), and thus destroyed in order E, A, B, which is also safe.

Answer 2

It sounds like you should try to build a directed, acyclic graph with the pattern just as you described. An adjacency list representation (vector of linked lists, probably, seeing as you're getting new nodes on the fly) should do it.

One thing I'm not clear on: Do you need the computation at random times, or after you've gotten all of the information? I'm assuming the latter, that you can wait until you're graph is complete. If that's the case, your question is exactly a topological sort, for which there is time-linear-in-edges-and-vertices implementation. It is a relatively simple algorithm. I'm a bit turned around by your description (eating lunch makes me slow and sleepy, sorry), but you may in fact need a "reverse" topological sort, but the principles are identical. I won't try to explain how the algorithm works exactly (see: slow and sleepy), but I think the application should be clear. Unless if I'm entirely wrong, in which case, nevermind?

To summarize: In a sense, you're building up the data structure, a graph, in about as efficient time as you can hope for (it depends on how you're inserting). The graph reflects which objects need to wait on which other objects. Then when you're done building it you run the topological sort, and that reflects their dependencies.

Edit: It has been a while since I've mixed up "your" and "you're". :(

Answer 3

Represent it like that: a graph with an edge from A to B if A's destructor must be run after B's. Inserting X now means adding two edges, and that's O(n log n)) if you keep a sorted index of nodes. To read the destruction order: pick any node, the follow the edges until you cannot anymore. That node's destructor can be safely called. Then pick one of the remaining nodes (e.g. the previous node you traversed) and try again.

From what you say, insertions happen often but the sequence is only iterated once for destruction: this datastructure should then be suitable since it has fast insertions, at the cost of slower lookups. Maybe someone else can suggest a faster way to do lookups in this datastructure.

Answer 4

This sounds like you're building a tree from the leaves up.

Answer 5

Store it as a tree

• have a node for each resource
• have each resource keep a linked list of pointers to the resources that depend on that resource
• have each resource keep a count of the number of resources that it depends on
• keep a toplevel linked list of the resources that have no dependencies

To generate the order, go through your toplevel linked list

• for each resourced processed, add it to the order
• then decrement the counts of each resource that depends on it by one
• if any count reaches zero, push that resource onto the toplevel list.

When the toplevel list is empty, then you've created a full order.

typedef struct _dependent Dependent;
typedef struct _resource_info ResourceInfo;

struct _dependent 
{
  Dependent * next;
  ResourceInfo * rinfo;
}
struct _resource_info
{
  Resource * resource; // whatever user-defined type you're using
  size_t num_dependencies;
  Dependent * dependents;
}

//...
Resource ** generateOrdering( size_t const numResources, Dependent * freeableResources )
{
  Resource ** const ordering = malloc(numResources * sizeof(Resource *));
  Resource ** nextInOrder = ordering;

  if (ordering == NULL) return NULL;
  while (freeableResources != NULL)
  {
    Dependent * const current = freeableResources;
    Dependent * dependents = current->rinfo->dependents;

    // pop from the top of the list
    freeableResources = freeableResources->next;

    // record this as next in order
    *nextInOrder = current->rinfo->resource;
    nextInOrder++;
    free(current->rinfo);
    free(current);

    while (dependents != NULL)
    {
       Dependent * const later = dependents;

       // pop this from the list
       dependents = later->next;

       later->rinfo->num_dependencies--;
       if (later->rinfo->num_dependencies == 0)
       {
          // make eligible for freeing
          later->next = freeableResources;
          freeableResources = later;
       }
       else
       {
           free(later);
       }
    }
  }
  return ordering;
}

To help create the tree, you might also want to have a quick lookup table to map Resources to ResourceInfos.

Answer 6

It sounds to me that you have a directed acyclic graph and a topological sort will give you the order of object destruction. You will probably also need to special handle the case where the graph has cycles (circular dependencies).

Answer 7

Are you more interested in destroying first-class C++ objects in the right order to avoid dependencies, or in modeling some external, real-world behavior where you're more interested in the algorithm and repeatability?

In the first case, you can use smart, reference-counting pointers (look for shared_ptr, available in Boost and the forthcoming C++ standard) to keep track of your objects, possibly with a factory function. When object A initializes and wants to use object B, it calls B's factory function and gets a smart pointer to B, increasing B's reference count. If C also references B, B's reference count increments again. A and C can be freed in any order, and B must be freed last. If you store shared_ptrs to all of your objects in an unordered data structure, when you're done running you'll free the list of all objects, and shared_ptr will take care of the rest, in the right order. (In this example, A and C are referenced only by the list of all objects, so their reference counts are both 1, and B is referenced by each A and C and the list of all objects, so its reference count is 3. When the list of all objects releases its reference to the objects, A and C's reference counts go to 0, so they can be freed in any order. B's reference count doesn't go to 0 until A and C are each freed, so it will continue to live until all references to it are freed.)

If you're more interested in the algorithm, you can model the reference counting in your own data structures, which may end up looking something like a directed acyclic graph when you're done.