Блог пользователя faresbasbas

DAG to SCC
Автор faresbasbas, история, 6 лет назад, По-английски

Recently I've read about minimum number of needed edges to construct SCC from a DAG. And it was the MAX(x,y) where x is the number vertices with 0 in-degree and y is the number of vertices with 0 out-degree. But i am wondering how to find such combination of edges in O(N) time. Thanks in advance :)

edit : solved. thank you very much for all people who helped me :)

  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +6 Проголосовать: не нравится

Let $$$s_1, s_2, ..., s_n$$$ will be $$$0$$$ in-degree vertices and $$$e_1, e_2, ..., e_m$$$ vertices with $$$0$$$ out-degree. Assume that $$$m \geq n$$$ (if it's wrong we can, for example, change direction of all edges).

Notice, that out-degree of every $$$e_i$$$ vertex should be at least one after adding edges. But we can add only $$$m$$$ edges. So, every edge should begins in one of $$$e$$$ vertices and out-degree of every vertex from $$$e$$$ will be exactly $$$1$$$. Let's build these edges.

Run dfs from $$$s_1$$$ and find all $$$0$$$ out-degree vertices, which achievable from $$$s_1$$$. Let's call these vertices $$$c_1, c_2, ..., c_k$$$. Now add edges $$$(c_1, c_2)$$$, $$$(c_2, c_3), ..., (c_{k-1}, c_{k})$$$ and $$$(c_k, s_2)$$$. Then repeat this process with other vertices from $$$s$$$. On every step we shouldn't touch vertices from $$$e$$$, which were visited on previous steps. And don't forget about edge $$$(c_{nk_n}, s_1)$$$ in the end.

Total complexity is $$$O(N+M)$$$.

→ Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Any other ideas of how to make it work :)?

→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +13 Проголосовать: не нравится

    I have a solution which I think should work. Let
    Number of nodes with 0 in-degree = x
    Number of nodes with 0 out-degree = y
    I am considering y $$$\geq$$$ x. If y $$$ \lt $$$ x then we can reverse the edges.

    First, colour all the x nodes with colours from 0 to x-1. Now do a dfs from each of these x nodes. While doing dfs from ith node, colour all nodes you visit with the colour of the root node (the node with 0 in-degree from which we are running dfs currently). In dfs, whenever you encounter a node which has already been coloured, simply return as it is guaranteed that all nodes in it's subtree are already coloured. Now our graph will have these properties-

    Here,
    root node of ith colour is node which has colour i and in-degree 0 and,
    leaf nodes of ith colour are nodes which have colour i and out-degree 0.

    1. Each node will be coloured by some colour c.
    2. There will be atleast 1 node of each colour.

    Now let us consider all colours c such that there exist atleast 1 node with colour c and out-degree = 0. Let there are p such colours f1, f2....fp. Also, select one leaf node of each of these p colours. Now add edges like this-
    leaf(f1) -> root(f2), leaf(f2) -> root(f3), .... leaf(fp) -> root(f1). Total p edges would be added like this.

    Now, there are x-p colours left which do not have any leaf. Let these be c1, c2 ... cx-p. We have y-p leaf nodes left. Now out of these y-p leaves, choose any x-p leaves and let those be l1, l2....lx-p. Add edges like this-
    l1 -> root(c1), l2 -> root(c2) ... lx-p -> root(cx-p). Total x-p edges will be added like this.

    Total edges added till now = p+x-p = x.

    We still have y-x leaves left. Add edges from these leaves to root of any colour. So total y edges would be added. It can easily be shown that we can reach from any node of colour fi to any node of colour fj, from any node of colour fi to any node of colour cj and from any node of colour ci to any node of colour cj.

    I do feel that it might fail on a case like this-
    We have to go from some node of colour ci to some node of colour fj. It is possible in my algorithm that from each node of colour ci, I am only able to reach a leaf node of colour fj which is connected to a root node of colour ck and thus I won't be able to reach every node of colour fk. In this case, I will choose a colour k such that it has a leaf node connected to root(fi) and at least 1 leaf node connected to root(cj). I will swap these two leaf nodes and the problem would be solved.

    It is a very long solution, I am sorry for any typos in between or any mistake. I think this should solve your problem in linear time. Please correct me if I am wrong somewhere.

    → Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

Hello, this is known as the strong connectivity augmentation problem. You can find a solution described in this paper.

→ Ответить
»
6 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +21 Проголосовать: не нравится

There is a pretty nice and neat algorithm for this.

The algorithm implemented in Python

The basic idea of the algorithm is to greedily try to match sources with sinks using dfs. Then when no more matches can be found, the sources/sinks that never found a match must be able to reach/be reachable by some node in matched_sinks/matched_sources. You can then strongly connect everything using $$$\text{max}(\text{size}(\text{sources}), \text{size}(\text{sinks}))$$$ edges.

Properties of the greedy matching

The process of greedily matching source and sinks has the following properties:

  • matched_sources[i] can reach matched_sinks[i]
  • Every source in never_matched_sources can reach at least one sink in matched_sinks.
  • Every sink in never_matched_sinks can be reached by at least one source in matched_sources.

How to add the edges

To make the DAG strongly connected.

  1. Add edges to create one big SCC out of all of the matched sources and sinks. (Note that from the properties of the greedy matching, all of the unmatched sources can now reach this SCC, and the unmatched sinks can all be reached from this SCC.)
  2. Start adding edges to strongly connect pairs of unmatched sources and sinks. If there are more unmatched sources than sinks, or vice versa, then just strongly connect the excess to any node in the SCC.
→ Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    so as i did understand

    firstly:

    for any source i will try to connect it to exactly one sink which it can reach if not i will add it to never_matched_sources

    secondly:

    i will find all of the unmatched sinks and put them in never_matched_sinks

    thirdly:

    strongly connect the never_matched_sinks to the never_matched_sources

    fourthly:

    i have to strongly connect the rest

    is it this ?

    → Ответить
    • »
      »
      »
      6 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +8 Проголосовать: не нравится

      "firstly: for any source i will try to connect it to exactly one sink which it can reach if not i will add it to never_matched_sources"

      Note that the dfs never visits the same node twice. So the formulation should be "it can reach using unvisited nodes"

      "thirdly: strongly connect the never_matched_sinks to the never_matched_sources"

      I start by strongly connecting all of the matched sources and sinks into one big SCC. Think of it like making one big cycle. 

          ret =  [(0, P - 1)]
    ret += ((i, i - 1) for i in range(1, P))

      Once I've made the big SCC, I then strongly connect the unmatched sources and sinks to it.

          ret += ((i, i) for i in range(P, K))
    ret += ((0, i) for i in range(K, N))
    ret += ((i, 0) for i in range(K, M))
      → Ответить
  • »
    »
    6 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится

    Also how would you deal with it if the graph is made of multiple DAGs ?

    → Ответить
»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by faresbasbas (previous revision, new revision, compare).

→ Ответить
»
19 месяцев назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

[Sorry for the necroposting, but I found this method quite useful]

As the author said, to make a directed graph strongly connected with the minimum number of edges, we need to add

x = max(source SCCs, sink SCCs) number of edges.

A source SCC has no incoming edges from other SCCs, and a sink SCC has no outgoing edges. Using Kosaraju’s or Tarjan’s algorithm, we find all SCCs and classify them into:

S = {s1, s2, ..., sk} (source SCCs)
T = {t1, t2, ..., tm} (sink SCCs)

Now we run a loop from 0 to x in cyclic manner, and joining the nodes

u = sinks[i % sinks.size()] and v = sources[(i + 1) % sources.size()]

We connect the i-th sink component to the (i+1)-th source component, ensuring a directed path between SCCs. Since direct connections within the same SCC could create self-loops, shifting the index by +1 prevents this issue.

Thus, it can be done in O(n) time.

Why Self Loops?

Recommended Problem to apply the above idea: https://codeforces.me/contest/22/problem/E

Implementation: https://codeforces.me/contest/22/submission/305805098

→ Ответить