0
$\begingroup$

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 ?

$\endgroup$
4
  • $\begingroup$ @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. $\endgroup$
    – Olórin
    Mar 13, 2019 at 21:04
  • $\begingroup$ The keyword you are looking for is probably connectivity in dynamic graphs (e.g., dynamic connectivity). $\endgroup$
    – D.W.
    Mar 14, 2019 at 6:07
  • $\begingroup$ @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. $\endgroup$
    – Olórin
    Mar 14, 2019 at 6:36
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 14, 2019 at 6:38

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ "let's identify the weakly connected graph components" --> is there a standard way of doing it for a graph in the "adjacency list" representation ? $\endgroup$
    – Olórin
    Mar 14, 2019 at 9:44
  • $\begingroup$ @ujsgeyrr1f0d0d0r0h1h0j0j_juj, yes, exactly the method that I described. If you want to do it once on a graph that will never change, the fastest is probably to use DFS. If you want to do it on a graph that is changing (with vertices and/or edges added), use Union-Find. All of these work fine with adjacency list representation. $\endgroup$
    – D.W.
    Mar 14, 2019 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.