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
For an object
t and an integer k>0 I note
P(t,k)) the set of rank-k successors (resp. predecessors) of
t, this set being recursively defined as
P(t,1)) being the set of direct successors (resp. predecessors) of
P(t,k)) being the set of direct successors (resp. predecessors) of object from
P(t,k-1)). Finally I note
F(t,k) the union of
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' 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
G(t) that don't have any direct successor (i.e. such that
S(x,1) is empty).
X the set of all objects from the xml, and
G1,...,GN all graphs. They obviously partition
My task is the following : every day, for any object
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 ?