# Enumerating all orientations of an undirected graph

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;

• 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. – Kellen Myers Apr 2 '16 at 22:22