Enumerating all (super)orientations of an undirected graph
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 &lt; len(choices)) and not choices[i]:
    j = possibilities.index((u,v))
    if (j &lt; 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]) &lt; (min_into[i],min_out_of[i]):
   return False
 return True

numedges = n*(n-1)

def superorientations():
 if n&lt;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.