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

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 ?

• @Emil : I my case I will construct graphs progressively, starting from one node and no edge and filling it if other nodes have to be added. This means that I would have to expend the adjacency matrices, leading to matrixes to which I add rows/columns, which is a bad idea I would say. The set of "vertices + adjacency matrix for the edges" pov is best suited when a graph is given and won't change later and you only want to "observe" it without expanding it. Mar 13 '19 at 21:04
• The keyword you are looking for is probably connectivity in dynamic graphs (e.g., dynamic connectivity).
– D.W.
Mar 14 '19 at 6:07
• @D.W. I made a new edit defining what I intend by "end" of a weakly connected component. Thx for pointing at "connectivity in dynamic graphs" and "dynamic connectivity", it is exactly this. Mar 14 '19 at 6:36
• Rather than using "EDIT:", please edit the question to read well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755.
– D.W.
Mar 14 '19 at 6:38

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.