1
$\begingroup$

Given an undirected graph $G$, an orientation of $G$ is a directed graph obtained by assigning every edge a direction, a superorientation of $G$ is a directed graph obtained by orienting every edge in one direction or both ways.

I'm trying to enumerate all superorientations (isomorphic superorientations count as one) of an undirected graph. Since graph isomorphism problem is NP-intermediate, I never intended to ask digraphs in the enumeration to be pairwise non-isomorphic. But since the list can be exponentially large, I want to make it as compact as possible, or in other words, to make isomorphic graphs as less as possible.

My attempt is given below.

SuperOrientation[g_Graph]:=Module[{el,tal,al},
el=EdgeList[g];
tal=DirectedEdge@@@el;
al=Flatten/@Tuples[Subsets[#,{1,2}]&/@Thread[List[tal,Reverse/@tal]]];
Graph/@al];

But it yields too many isomorphic graphs. My question is whether we have other ways to work around. Even we cannot make any improvements in general, but how about some special classes of graphs, say symmetric graphs?

Any suggestions or comments are welcome!

Improve this question
$\endgroup$
2
  • $\begingroup$ You said "isomorphism is allowed." Do you mean isomorphic superorientations are considered the same, or counted differently? I'm not sure which is meant by "allowed." If the answer is they are counted differently, there are $3^{|E|}$. I suppose if it's not that simple, "allowed" means isomorphic graphs all count as one. $\endgroup$
    – Kellen Myers
    Apr 2, 2016 at 22:22
  • $\begingroup$ @KellenMyers Sorry for the confusion caused. When I said allowing isomorphism, I mean all isomorphic superorientations count as one. I will update the description in the post later. $\endgroup$
    – hxiao
    Apr 3, 2016 at 2:49

1 Answer 1

Reset to default
2
$\begingroup$

The directg tool from the nauty suite can do this: generate all non-isomorphic orientations of an undirected graph.

It takes its input in Graph6 format, which Mathematica can export to.

It outputs results in Digraph6 format, which the IGraph/M package can handle.

I have directg installed in /opt/local/bin, so I can use

g = CycleGraph[3]

Needs["IGraphM`"]
IGImportString[
 RunProcess["/opt/local/bin/directg", "StandardOutput", 
  ExportString[g, "Graph6"]],
 "Digraph6"
 ]

enter image description here

Pass the -o option to orient every edge in a single direction only:

IGImportString[
 RunProcess[{"/opt/local/bin/directg", "-o"}, "StandardOutput", 
  ExportString[g, "Graph6"]],
 "Digraph6"
 ]

enter image description here

If you only need to count orientations, not output them, directg has an option for that.

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.