# Generate graphs from a given graph by permuting positions of directed edges

Assume that I have a mixed graph with some directed edges (the number of directed edges can be from 1 to 10).
This is an example of such graph g1 with 3 directed edges called a, b, c. Now I would like to create all possible graphs which are formed by permuting the directed edges.

From 3 directed edges, it is possible to generate 6 possible graphs below. If g1 is given, how can we create all 6 graphs from g1 to g6?
The condition of permuting directed edges are that the arrow direction should keep same and the two vertice associated with the edge should be moved together with the edge.

I'm trying to write a code to do this automatically for a graph with any number of directed edges less than 10.
Also it would be nice if it can be run quickly as I'll have to run it for billion times.
(the edge label is not important, just for presenting the problem)

myGraph[edges_] :=
Graph[edges, {EdgeStyle -> {Black},
VertexLabels -> {Placed[Automatic, Above]},
VertexLabelStyle -> {Red},
VertexStyle -> {Directive[Red, EdgeForm[None]]}}];
g1 = myGraph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3,
3 \[DirectedEdge] 4, 4 \[UndirectedEdge] 5, 6 \[DirectedEdge] 5,
6 \[UndirectedEdge] 7, 7 \[DirectedEdge] 8, 8 \[UndirectedEdge] 9,
9 \[UndirectedEdge] 10}]

• You are changing the set of undirected edges.
– Alan
Oct 27, 2022 at 15:16
• @Alan yes, that is intended. I'm trying to do something like just moving these directed edges to exchange their positions.
– hana
Oct 27, 2022 at 15:19
• If I understand correctly, you just permute the directed edges. But then 2 edges would give 2 graphs not 4? Oct 27, 2022 at 18:16
• @DanielHuber yes, you're right. Sorry for the mistake. The nodes associated with an edge would also move together with the edge.
– hana
Oct 27, 2022 at 18:29
• @user293787 I think I can consider it as path graph for now though I may want to generalise it a bit more later for a loop. You talked about some problems that I haven't thought before. Actually in my graph, two directed edges are never adjencent. They're always separated by one or more undirected edges. With that would it be possible to solve for a loop instead of path graph? If not then solving it as path graph would also be great.
– hana
Oct 29, 2022 at 8:09

Define

permuteDirected[G_]:=With[{X=EdgeList[G,_DirectedEdge]},With[{S=Map[Sort,List@@@X]},

Map[myGraph,permuteDirected[g1]] 