FInd all paths of given length n

[Selvaraja S]

Let $G$ be a finite simple graph.
Can we find all paths(induced ) of given length?


Thanks in advance.

[fidelbc]

Yes we can. Suppose the path has length k and thus k+1 vertices. Then the following command returns an iterator over all lists of vertices that induce paths on k+1 vertices in G.

G.subgraph_search_iterator(graphs.PathGraph(k+1),induced=True)

More on this may be found at [1].

[1]; http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.subgraph_search_iterator

[Selvaraja S]

Thanks for the response.

sage: g=Graph(d)
sage: for p in g.subgraph_search_iterator(graphs.PathGraph(3)):
    print(p)

This is giving the all the paths of length 3. But I have one more question.

Suppose $xyz$ is induced path of length 3. Note that $zyx$ is also induced path of length.
Can I avoid this path?

[fidelbc]

Not directly, but it shouldn't be hard to just keep track of which vertex sets you have seen so far. Eg.

seen = {}

for p in g.subgraph_search_iterator(graphs.PathGraph(3, induced=True)):
    vxs = tuple(sorted(p))

    if vxs not in seen:

        seen[vxs]=True

        print vxs

Note that you should include induced=True in the call to subgraph_search_iterator, since induced is False by default.

[fidelbc]

There is a typo in the code above. The True argument belongs to the subgraph_search_iterator function, not the PathGraph, that is,

g.subgraph_search_iterator(graphs.PathGraph(3), induced=True)