aman_naughty's blog

Mother vertex in a graph.
By aman_naughty, history, 5 years ago, In English

I was wondering if we can find the mother vertex in a directed connected graph by topological sorting. The last finished vertex will be the mother vertex.

Is this approach correct or am I thinking wrong?

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I had to google what the hell a "mother vertex" was. Apparently it's a vertex $$$v$$$ such that any other vertex can be reached from $$$v$$$.

And no, it's not correct. What if the graph has no mother vertices? Your algorithm will still try to say something is the mother vertex.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Then we can check whether the last finished vertex is mother or not by a single dfs or bfs. Is it correct now.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, but only in a DAG. (At least I think so, but from your blog the "last finished vertex" is a bit unclear.)

      If your however graph isn't acyclic, then the concept of topological sorting is meaningless.

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

This vertex can be easily found with n times a dfs. Start a dfs from each unvisited vertex and only visit unvisited vertices. The last vertex where we started a dfs is the vertex we search(if any such vertex exists). However, a topological sorting may not work.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isn't topological sort doing the same thing as you mentioned? At the end of the topological sort, the last vertex in the stack will be a candidate for mother vertex.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      its more or less the same as toposort with dfs. However there are other ways to get topological sortings kahns algorithm. This may fail. For example on a non DAG graph kahns algorithm will definitely fail.

      → Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Find strongly connected components and build the DAG of SCCs , consider the first component in topological sort if that can visit all other components then all nodes in that Strongly connected component are "mother" vertices.

→ Reply
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just to dfs and store the mother vertex in a variable, the last stored vertex in the variable might be a mother vertex, at the end you have to check if this vertex can access all the vertex, if it can then it is a mother vertex else no.

In other words: Lemma: If a mother vertex exists, it will be the last value entered in the Mother variable.

→ Reply