3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Jun 30 at 12:58
  • $\begingroup$ "Path" usually means no repeating vertices. Thus this graph has no paths of length > 1. Please clarify if you allow repeating edges / vertices. $\endgroup$ – Szabolcs Jun 30 at 12:59
  • $\begingroup$ See also mathematica.stackexchange.com/a/201420/12 $\endgroup$ – Szabolcs Jun 30 at 13:00
  • $\begingroup$ @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. $\endgroup$ – math Jun 30 at 13:07
  • $\begingroup$ 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. $\endgroup$ – Szabolcs Jun 30 at 13:11
2
$\begingroup$

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}]

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for this! $\endgroup$ – math Jun 30 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.