StopIteration raised during G.eulerian_circuit()

edit

Hello, I just ran into a raised error during an overnight computation. I found the function and line on the git hub but I feel I don't know enough python/sagemath to figure out why this error occurred.

The error in question:

if G.eulerian_circuit() is False:
  File "/opt/sagemath-8.6/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py", line 3935, in eulerian_circuit
    next_edge = next(g_edge_iter(v))
StopIteration

EDIT: Here is the code that creates the error. I am using sagemath 8.6 on windows 10.

from sage.all import Polyhedron
from sage.all import polytopes
from sage.all import Combinations
from sage.combinat.gray_codes import combinations
from sage.all import Graph
from sage.all import factorial
from sage.graphs.connectivity import is_connected
import numpy as np
from progress.bar import Bar
import pprint

def gray(flatten, all_vertex_pairs):
r"""
Uses gray code to solve the problem without memory storage. Calculate the
next combination of edges using gray code then test s. If true the return
the planar representation and the graph else continue. If all combinations
were found and there does not exist a solution then the function will
return an empty dict and None.

SEE:
    test_edges

INPUT:
    flatten {list} A list of faces of some polytope P.
    all_vertex_pairs {list} A list of every pair of vertices possible in P.

OUTPUT: A planar representation of a polytope P as a dictionary and the
undirected graph.
"""
n = len(all_vertex_pairs)
t = len(flatten) - 1
s = set([i for i in range(t)])
num_combos = factorial(n) / (factorial(t)*factorial(n-t))
with Bar('Processing', max=num_combos) as bar:
    for i, j in combinations(n, t):
        s.remove(i)
        s.add(j)
        flag, planar, G = test_edges(all_vertex_pairs, s, flatten)
        if flag:
            return planar, G
        else:
            bar.next()
return {}, None

def combo(vertices, length):
r"""
Creates a list of every combination of a certain length from the set of
possible vertices.

INPUT:
    vertices {integer} The number of vertices for a polytope.
    length {integer} The length of the noninversion set.

OUTPUT:
    A list of every combination of a set.
"""
set_of_vertices = [i for i in range(0, vertices)]
return Combinations(set_of_vertices, length).list()

def convert(data):
r"""
Converts a polyhedron object to array.
There has to be a way to convert a polyhedron face into a list.
"""
s_data = str(data)
s_data = s_data.replace('<', '')
s_data = s_data.replace('>', '')
s_data = s_data.split(",")
for i in range(len(s_data)):
    s_data[i] = float(s_data[i])
return np.array(s_data)

def poly2list(face):
r"""
Converts a polygon into an array and finds all combinations of length 2, ie
given any face, create a list of every edge possible from the vertices that
create that face. Return that list as a numpy integer array.

SEE:
    convert
INPUT:
    face {sagemath polygon} A face of some polygon P represented as a
sagemath polygon object.
OUTPUT: A numpy integer array of every edge possible inside a face.
"""
converted_face = convert(face)
edges = np.array(Combinations(converted_face, 2).list()).astype(int)
return edges

def assign_edges(values, keys):
r"""
Each potential unfolding is represented in a new vertex space so for this
set to be in a correct format each vertex in the potential unfolding will
need to be assigned the correct edge from the old vertex space. Each edge
is stored in a list then returned as a numpy array.

INPUT:
    values {list} A list of values to be used.
    keys {list} A list of keys associated with each value.

OUTPUT: A numpy array of all the edges in a potentail unfolding.
"""
edges = []
for key in keys:
    edges.append(values[key])
return np.array(edges)

def planar_representation(planar, flatten, test_case):
r"""
A planar representation of a polytope P is a dictionary of faces and edges.
The keys are the faces and the values are the edges. This loops each face
in flatten and converts each face into a list of vertices. Each list of
vertices from each face is looped and tested against the test_case.

SEE:
    poly2list

INPUT:
    planar {dict} A dictionary to store planar information.
    flatten {list} A list of faces of a polytope P.
    test_case {list} A list of edges that will unfold P.

OUTPUT: A dictionary of a potentially flattened polytope.
"""
for i in range(len(flatten)):
    key = flatten[i]
    cycle = poly2list(key)
    to_delete = []
    for j in range(len(cycle)):
        _flag = True
        for k in range(len(test_case)):
            check_test_case = np.array_equal(cycle[j], test_case[k])
            if check_test_case:
                _flag = True
                break
            else:
                _flag = False
        if not _flag:
            to_delete.append(j)
    cycle = np.delete(cycle, to_delete, axis=0)
    cycles = [str(cycle[i]) for i in range(len(cycle))]
    value = dict(zip(cycles, [1 for num in cycle]))
    planar[key] = value
return planar

def test_edges(all_v_pairs, possible_unfolding, flatten):
r"""
Create a test case by assigning a potential unfolding the correct edges
from the list of all possible vertex pairs. The test case will be attempted
to be represented as dictionary by matching faces with edges. If the planar
representation can be made into a sagemath Graph then a series of tests are
performed on the test graph. A solution will be a graph without a cycle
basis, is void of Eulerian circuits, and is connected. A boolean flag, the
planar representation, and the graph will be returned.

SEE:
    assign_edges
    planar_representation

INPUT:
    all_v_pairs {list} A list of all possible edges from a set of vertex.
    possible_unfolding {list} A list of possible edges that may unfold P.
    flatten {list} A list of the faces of P.

OUTPUT: A boolean flag, a planar representation, and a sagemath Graph.
"""
if all_v_pairs == []:
    return False, {}, None
test = assign_edges(all_v_pairs, possible_unfolding)
planar = planar_representation({}, flatten, test)
if planar == {}:
    return False, {}, None
G = Graph(planar)
basis = G.cycle_basis()
if len(basis) == 0:
    flag = False
    if G.eulerian_circuit() is False:
        if is_connected(G) is True:
            flag = True
            return flag, planar, G
        else:
            flag = False
            return False, {}, None
    else:
        flag = False
        return False, {}, None
else:
    flag = False
    return False, {}, None

def create_vertices(dimensions, length, vertices):
r"""
Creates a randomly generated list of length dimensions then stores
each list as a tuple inside another list.

INPUT:
    dimensions {integer} The number of dimensions the polytope exists in.
    length {integer} The length of each dimension.
    vertices {integer} The number of vertices of a polytope.

OUTPUT:
    A list of tuples of vertices.

"""
polyhedron_vertices = []
for i in range(vertices):
    vertex = []
    for j in range(dimensions):
        vertex.append(np.random.randint(-length, length + 1))
    polyhedron_vertices.append(tuple(vertex))
return polyhedron_vertices

def create_polyhedron(dimensions, length, vertices):
r"""
Creates a randomly generated polyhedron with a given dimension, length,
and vertices. With the polyhedron, p, the number of faces is calculated.
The polyhedron and the list of faces are returned.

SEE:
    create_vertices

INPUT:
    dimensions {integer} The number of dimensions the polytope exists in.
    length {integer} The length of each dimension.
    vertices {integer} The number of vertices of a polytope.

OUTPUT:
    A sagemath polytope object and a list of the faces.
"""
polyhedron_vertices = create_vertices(dimensions, length, vertices)
polyhedron = Polyhedron(vertices=polyhedron_vertices)
# polyhedron = polytopes.octahedron()
# polyhedron = polytopes.cube()
# polyhedron = polytopes.cuboctahedron()
# polyhedron = polytopes.great_rhombicuboctahedron()
return polyhedron

if __name__ == "__main__":
# Initial Conditions
np.random.seed(12345)
dimensions = 3
length = 10
vertices = 8

# Create Polyhedron to unfold
polyhedron = create_polyhedron(dimensions, length, vertices)
flatten = np.array(list(polyhedron.faces(2)))

p = polyhedron.plot()
p.save('full.png')
print('\n{}\nUnfold: {} faces\n{}'.format(
    polyhedron, len(flatten), flatten))
vertices = len(polyhedron.vertices())

# Combinations of length 2
print('\nFind all length 2 sets from {} vertices'.format(vertices))
all_vertex_pairs = combo(vertices, 2)

# Combinations of length flatten - 1
print('\nFind all length {} sets from {} edges\n'.format(
    len(flatten) - 1, len(all_vertex_pairs)))

# Unfold
planar, G = gray(flatten, all_vertex_pairs)
pp = pprint.PrettyPrinter(indent=4)
pp.pprint(planar)

# Plot
print('\nSaving Graph')
P = G.plot()
P.save('graph.png')
print('\nDone!\n')

I hope this kind of helps.

The code is creating a graph G and checking if there exists a Eulerian circuit but just millions of times. Is this error something that indicates the limitation of Hierholzer's algorithm or was this a random computer error?

I can post more information if needed. This is my first post and there seems to be no other threads on this topic.

EDIT 2:

Using the code sninppet from David Coudert

Traceback (most recent call last):
File "fold.sage.py", line 327, in <module>
planar, G = gray(flatten, all_vertex_pairs)
File "fold.sage.py", line 65, in gray
flag, planar, G = test_edges(all_vertex_pairs, s, flatten)
File "fold.sage.py", line 215, in test_edges
raise ValueError(G.edges())
ValueError: []

The error seems to be from an graph created without edges which means that the planar representation is a dict of only keys without values. I going to run it again in an attempt to get more information.