Ask Your Question
0

Networkx algorithm

asked 2013-10-08 09:20:59 -0500

mresimulator gravatar image

Hi experts!

I know that shortest_path() function (Networkx ) uses Dijkstra algorithm.

What algorithm is based connected_components() function?

Waiting for your answers.

Thanks a lot.

Best regards!

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2013-10-08 10:05:55 -0500

tmonteil gravatar image

You can get the source code of a method using ?? as follows:

sage: G = graphs.PetersenGraph()
sage: G.connected_components??

You get the code:

    seen = set()
    components = []
    for v in self:
        if v not in seen:
            c = self.connected_component_containing_vertex(v)
            seen.update(c)
            components.append(c)
    components.sort(lambda comp1, comp2: cmp(len(comp2), len(comp1)))
    return components

As you can see, it looks, for each vertex which was not already vidited, the connected component of the vertex.

So, let us look at the source of the .connected_component_containing_vertex() method

sage: G.connected_component_containing_vertex??

And we get:

    try:
        c = list(self._backend.depth_first_search(vertex, ignore_direction=True))
    except AttributeError:
        c = list(self.depth_first_search(vertex, ignore_direction=True))

    c.sort()
    return c

Hence, the algorithm used in the .connected_components() method is a depth first search, see the wikipedia page for more details.

edit flag offensive delete link more

Comments

Thank you so much!!

mresimulator gravatar imagemresimulator ( 2013-10-09 00:59:17 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-10-08 09:20:59 -0500

Seen: 89 times

Last updated: Oct 08 '13