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.Aim: Enumerate all superorientations (isomorphic superorientations count as one) of an undirected graph.What for: Compute all kernels (absorbing independent vertex sets) in as many digraphs as possible by using polyhedral descriptions of kernels, which are essentially linear programs (hence the problem can be solved efficiently).Current solution (for enumerating all superorientations):Given an undirected graph $G=(V,E)$,for each edge $uv\in E$ generate 3 different arc sets $\{(u,v)\},\{(v,u)\} $ and $\{(u,v),(v,u)\}$ first.Then enumerate all combinations of arc sets, which yields precisely $3^{|E|}$ digraphs in the result.Code in Mathematica: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];Problem:Current solution gives too many isomorphic digraphs, especially for highly symmetric graphs.I can delete isomorphic superorientations efficiently in Mathematica (the isomorphism test in Mathematica is implemented by NAUTY, which claims to be the fastest graph isomorphism test program in practice).But testing graph isomorphism is still quite time consuming due to the fact that graph isomorphism problem is NP-intermediate.Question:Is there a way to generate as less isomorphic graphs as possible in the enumeration before the isomorphism test?It is unlikely to have a general solution.But how about some special classes of graphs, say highly symmetric graphs.Complete graphs, or subgraphs of complete graphs with only a few edges missing might be good starts, as my isomorphism test for superorientations of $K_7$ never ends. 
Enumerating all (super)orientations of an undirected graph
graph theory;graph algorithms