Enumerating all (super)orientations of an undirected graph

Question

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.

Answer 1

For complete graphs:

Order the possible-directed-edges as [[1,0],[2,0],...,[|V|-1,0],[0,1],[2,1],...,[|V|-1,1],[0,2],[1,2],...,[|V|-1,2],...,[0,|V|-1],[1,|V|-1]],[2,|V|-1],...,[|V|-2,|V|-1]], and imagine the perfect binary rooted tree whose levels correspond to initial segments of the possible-edges under that ordering,
and whose nodes correspond to which of those possible edges are/aren't present.
Do roughly a depth-first search on that tree without actually constructing the tree,
where you do ignore tree-edges that would make neither [u,v] nor [v,u] be present
and you can ignore tree-edges that would necessarily make [number_of_superorientation_edges_to_(i+1),number_of_superorientation_edges_from_(i+1)] lexicographically less than [number_of_superorientation_edges_to_(i),number_of_superorientation_edges_from_(i)].
Output the leaves that search reaches. ​ In Python:

n  =  number of vertices
possibilities = tuple([(i,j) for j in range(n) for i in range(n) if j!=i])

def might_be_valid_and_canonical_(choices):
 for v in range(n):
  for u in range(v):
   i = possibilities.index((v,u))
   if (i < len(choices)) and not choices[i]:
    j = possibilities.index((u,v))
    if (j < len(choices)) and not choices[j]:
     return False
 max_out_of,max_into,min_out_of,min_into = [0]*n,[0]*n,[0]*n,[0]*n
 for i in range(len(choices)):
  if choices[i]:
   u,v = possibilites[i]
   max_out_of[u] += 1
   max_into[v] += 1
   min_out_of[u] += 1
   min_into[v] += 1
 for (u,v) in possibilities[len(choices):]
   max_out_of[u] += 1
   max_into[v] += 1
 for i in range(n-1):
  if (max_into[i+1],max_out_of[i+1]) < (min_into[i],min_out_of[i]):
   return False
 return True

numedges = n*(n-1)

def superorientations():
 if n<2:
  raise NotImplemented
 choices,try_child = tuple(),0
 while True:
  LofC = len(choices)
  if LofC == numedges:
   yield [possibilities[i] for i in range(numedges) if choices[i]]
   try_child = int(choices[LofC-1])+1
   choices = choices[:LofC-1]
   continue
  if try_child == 0:
   if might_be_valid_and_canonical_(choices+(False,)):
    choices += (False,)
    continue
   try_child = 1
  if try_child == 1:
   if might_be_valid_and_canonical_(choices+(True,)):
    choices += (True,)
    try_child = 0
    continue
   try_child = 2
  if try_child == 2:
   LofC = len(choices)
   if LofC == 0:
    return
   try_child = int(choices[LofC-1])+1
   choices = choices[:LofC-1]

For nearly-complete graphs, you can do that to the subgraph consisting of the
vertices with degree |V|-1, and output the extensions of those to the whole graph.