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.

Mannikin

How many edges would each vertex have (typically)? The searching you suggest for adjacency lists may not be too expensive if the vertex degrees are low, particularly if the adjacency lists are sorted by some kind of vertex ID to allow binary search. Remember that you would know all of the neighboring vertices for any given vertex because of the deleted vertex's own source and target lists. – Hypoglycemia

Typically, a vertex would have about 10-30 in edges and about 5-10 out edges. But a few vertices might have hundreds of out edges. The idea of keeping the adjacency lists sorted might work... although, this means I have to spend time ordering those lists when new vertices are created. – Mannikin

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

Interlope

Yes, the adjacency list looks better (although, an efficient sparse matrix algorithm might work as well). Instead of hash tables, wouldn't tries do better? Verdy_p in this post suggests so... – Mannikin

I've never heard of tries being used this way and I'm having trouble grasping what the poster in the link is referring. If you have a link to a primary source, I'd be interested in taking a look. – Interlope

No, I don't know either. I was just trying to find how to optimize the search. – Mannikin

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.

Mannikin

What programming language is used in this example? It looks like Java to me - is this correct? – Vashti