Data structure for directed graphs, allowing fast node deletion?

Question

I need to store a directed graph (not necessarily acyclic), so that node deletion is as fast as possible. I wouldn't mind storing additional data in order to know exactly which edges have to go when a node is deleted.

If I store a list of edges (as pairs of node indexes), then when killing some node n I have to search the whole list for edges whose source or target is n. This is too costly for my application. Can this search be avoided by storing some additional data in the nodes?

One idea would be to have each node store its own sources and targets, as two separate lists. When node n is killed, its lists are killed too. But then, how would all the targets/sources linked to node n know to update their own lists (i.e., to eliminate the defunct node from their lists)? This would require some costly searching...

Can it be avoided?

Thx.

Answer 1

You have two choices without getting too fancy are Adjacency List and Adjacency Matrix. The former is probably best for what you're doing. To remove a node, simply eliminate the list for that node for all of its out edges. For the in-edges, you might consider keeping a hash-table for each list for O(1) lookups.

This is a good overview http://www.algorithmist.com/index.php/Graph_data_structures

Answer 2

I solved it! This is the solution for undirected graphs, adding direction is easy afterwards.

In each vertex I keep a special adjacency list. It is a list (double linked, for easy insertion/deletion) whose elements are "slots":

class Slot {
  Slot prev, next; // pointers to the other slots in the list
  Slot other_end; // the other end of the edge: not a vertex, but a Slot!
  Vertex other_vertex; // the actual vertex at the other end

  void kill() {
    if (next!=null) next.kill(); // recursion
    other_end.pop_out();
  }

  void pop_out() {
    if (next!=null) next.prev = prev;
    if (prev!=null) prev.next = next;
    else other_end.other_vertex.slot_list = next; // in case this slot is the
                                                  // first in its list, I need
                                                  // to adjust the vertex's
                                                  // slot_list pointer.
    // other_end.other_vertex is actually the vertex to which this slot belongs;
    // but this slot doesn't know it, so I have to go around like this.
  }

}

So basically each edge is represented by two slots, cross-pointing one to each other. And each vertex has a list of such slots.

When a vertex is killed, it sends recursively a "kill" signal up its slot list. Each slot responds by destroying its other_end (which graciously pops out from the neighbor's list, mending the prev/next pointers behind).

This way a vertex plus all its edges are deleted without any searching. The price I have to pay is memory: instead of 3 pointers (prev, next and vertex for a regular double linked adjacency list), I have to keep 4 pointers (prev, next, vertex and other_end).

This is the basic idea. For directed graphs, I only have to distinguish somehow between IN slots and OUT slots. Probably by dividing each vertex's adjacency list in two separate lists: IN_slot_list and OUT_slot_list.