aman_naughty's blog

By aman_naughty, history, 23 months 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

»
23 months 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.

  • »
    »
    23 months 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.

    • »
      »
      »
      23 months 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.

»
23 months 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.

  • »
    »
    23 months 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.

    • »
      »
      »
      23 months 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.

»
23 months 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.

  • »
    »
    23 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    MZuenni's approach seems a lot simpler, anyway thanks for your approach.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is the most easier solution i have got but i do not know whether it will work for non-directed graph

      code
      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What if the graph is disconnected ??? then mother vertex is -1 ... where this case is handeled by your code?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          nopes, you need to run dfs again assuming top element is mother vertex ..