Revision history [back]

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.