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!

$\endgroup$
  • $\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 '16 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 '16 at 2:49
1
$\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, privacy policy and cookie policy

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