Determine endpoint of a graph given as a list of nodes + direct successors and predecessors

Question

EDIT @20190313

I can rephrase my question a follows : I am given everyday a non weakly-connected directed graph by its so-called adjacency list representation -- nodes are stored as objects, and every node stores a list of adjacent nodes, its direct successors and predecessors. The graph is in fact highly non weakly-connected, in the sense that the number of its weakly-connected components is quite big. I must everyday find the weakly-connected components of the graph and determine sink nodes of every weakly-connected components, and know from one day to the next any new sink node for every weakly-connected components. (From one day to the next, only new sink nodes might be added, with their associated edges.)

---

I fix a type T once for all. (Concretely, T is a c# class, but that doesn't matter.) On T I have the notion of direct successor and direct predecessor. (Imagine the two notions modelled byt two T × T --> bool functions.) The notion is nice in the sense that t' is a direct successor of t if and only if t is a direct predecessor of t'. For an object t of type T I note d(t) the set (in the usual sense) of its direct predecessors and successors.

Each day I receive an xml containing the list of all (xml representations) of objects of type t, the representation of t "containing" d(t).

For an object t and an integer k>0 I note S(t,k) (resp. P(t,k)) the set of rank-k successors (resp. predecessors) of t, this set being recursively defined as S(t,1) (resp. P(t,1)) being the set of direct successors (resp. predecessors) of t, and S(t,k) (resp. P(t,k)) being the set of direct successors (resp. predecessors) of object from S(t,k-1) (resp. P(t,k-1)). Finally I note F(t,k) the union of S(t,k) and P(t,k), and G(t) the union of all F(t,k) for k>1.

G(t) as defined is only a set, but can be turned into a graph as follows : each object of G(t) is a node, and two nodes t,t' are connected by an arrow going from t to t' if t' is a direct successor of t. The graph G(t) is connected by contruction and I note B(G(t)) its end points : the objects x in G(t) that don't have any direct successor (i.e. such that S(x,1) is empty).

I note X the set of all objects from the xml, and G1,...,GN all graphs. They obviously partition X.

My task is the following : every day, for any object t from X, I have to be able to determine the set B(G(t)) as fast as possible and the graph G(t) as fast as possible. (I can imagine that the two tasks may not necessarily be related.) Of course, every day I can save all graphs and their endpoints, if that could help for the task the next day.

(From one day to the next the only changes that occur are new direct successors added to objects that are endpoints and deaths (meaning that we know that the dead object will never have direct successors anymore until its rebirth) and rebirth (meaning that the object can now start to have direct successors.)

What are my options here ?

Answer 1

It appears this is an instance of "incremental graph connectivity". There are very efficient algorithms for this.

First, let's identify the weakly connected graph components and keep track of them as the graph changes. In undirected graphs, it's easy to keep track of connected components as you add vertices and/or edges, using a union-find data structure. In particular, each time you add a vertex, you use the MakeSet function to put it in a component of its own, and each time you add an edge, you use the Union function to merge the two associated components. You can use this to keep track of the weakly connected components in your directed graph.

This can be done $O(\alpha(n))$ time per operation (i.e., per vertex or edge added).

Your "ends" are normally called "sink vertices". You can keep track of the "ends" of each weakly connected component by associating a doubly linked list with each component; that list contains all of the sink vertices in that component. Also, each sink vertex should have a pointer to the placed in the doubly-linked list where it appears. When you merge two components, you can concatenate their lists in $O(1)$ time. Also, when you add an edge, you check if this turns a sink vertex into a non-sink; if so, you follow the pointer from that vertex to find its place in the doubly-linked list, and remove it from the doubly linked list. This too can be done in $O(1)$ time. In all, this takes an additional $O(1)$ time per vertex or edge added, which is dominated by the cost of the union-find data structure.