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.

Improve this question
$\endgroup$
11
  • 1
    $\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, 2020 at 12:58
  • 1
    $\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, 2020 at 12:59
  • $\begingroup$ See also mathematica.stackexchange.com/a/201420/12 $\endgroup$
    – Szabolcs
    Jun 30, 2020 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, 2020 at 13:07
  • 1
    $\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, 2020 at 13:11

1 Answer 1

Reset to default
3
$\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$
1
  • $\begingroup$ Thank you for this! $\endgroup$
    – math
    Jun 30, 2020 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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