2
$\begingroup$

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.

enter image description here

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.

enter image description here

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}]
Improve this question
$\endgroup$
7
  • $\begingroup$ You are changing the set of undirected edges. $\endgroup$
    – Alan
    Oct 27, 2022 at 15:16
  • $\begingroup$ @Alan yes, that is intended. I'm trying to do something like just moving these directed edges to exchange their positions. $\endgroup$
    – hana
    Oct 27, 2022 at 15:19
  • $\begingroup$ If I understand correctly, you just permute the directed edges. But then 2 edges would give 2 graphs not 4? $\endgroup$
    – Daniel Huber
    Oct 27, 2022 at 18:16
  • $\begingroup$ @DanielHuber yes, you're right. Sorry for the mistake. The nodes associated with an edge would also move together with the edge. $\endgroup$
    – hana
    Oct 27, 2022 at 18:29
  • 1
    $\begingroup$ @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. $\endgroup$
    – hana
    Oct 29, 2022 at 8:09

1 Answer 1

Reset to default
2
$\begingroup$

Define

permuteDirected[G_]:=With[{X=EdgeList[G,_DirectedEdge]},With[{S=Map[Sort,List@@@X]},
    EdgeList[G]/.Map[Thread[Flatten[S]->Flatten[#]]&,Permutations[S]]
               /.Thread[Map[Reverse,X]->X]]];

Then, assuming OP's code,

Map[myGraph,permuteDirected[g1]]

gives

enter image description here

This should work for path graphs where the names of the vertices are in canonical order, and where directed edges are not adjacent.

Improve this answer
$\endgroup$

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.