# Finding paths of length $n$ on a directed graph

Suppose I have the following directed graph

g = Graph[{DirectedEdge[v1, v1, a], DirectedEdge[v1, v1, OverBar[a]],
DirectedEdge[v1, v2, b], DirectedEdge[v2, v2, c],
DirectedEdge[v1, v3, OverBar[b]],
DirectedEdge[v3, v3, OverBar[c]]}, VertexLabels -> "Name",
EdgeLabels -> "Index"]


First of all, I would prefer to label the edges with the tag of the directed edge, but I'm not sure how to do this.

The main question is, can Mathematica give me all possible paths of length $$n$$ on this graph starting from, say, $$v1$$? Here repeated edges and vertices are allowed $$(1,5,\cdots,5)$$ where we pass through the edge $$5$$ $$n-1$$ times would be a valid length $$n$$ path.

• Tags are not for labelling. They are for distinguishing parallel edges. A use for labelling is IMO a misuse. That said, the EdgeLabels docs lists the "EdgeTag" specification. Jun 30, 2020 at 12:58
• "Path" usually means no repeating vertices. Thus this graph has no paths of length > 1. Please clarify if you allow repeating edges / vertices. Jun 30, 2020 at 12:59
• Jun 30, 2020 at 13:00
• @Szabolcs Thanks for your answer, I have changed the question to be clear I allow repeating edges. I did see the answer in the comments but I had some problems with the package. The output gives KeyAbsent and I'm not really sure how to fix this.
– math
Jun 30, 2020 at 13:07
• If you have a specific problem with installing the package, please either post on igraph.discourse.group or ask a new question here and tag it with igraphm. Jun 30, 2020 at 13:11

To visualize the edge tags, use EdgeLabels -> "EdgeTag".

This is a modification of the answer from https://mathematica.stackexchange.com/a/201420/12. It returns the edges (not vertices) and it does not require the IGraph/M package.

Return the outgoing edges of a given vertex in a directed graph:

inclist[graph_?DirectedGraphQ][vertex_] := EdgeList[graph, DirectedEdge[vertex, __]]


Return the target vertex of a directed edge:

target[edge_] := edge[[2]]


One step of the iterative / recursive algorithm: take all outgoing edges of the last vertex, and follow each of them.

step[graph_][{most___, last_}] := {most, last, #} & /@ inclist[graph][target[last]]


Iterate this step as many times as we need:

Nest[Join @@ step[g] /@ # &, List /@ inclist[g][v1], 3 (* length of walks - 1 *)]


If you want just the tags, add this to the end:

Map[Last, %, {2}]


• Thank you for this!
– math
Jun 30, 2020 at 14:00