Ask Your Question
2

StopIteration raised during G.eulerian_circuit()

asked 2019-08-27 14:51:20 +0100

mqpsf gravatar image

updated 2023-01-09 23:59:51 +0100

tmonteil gravatar image

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.

edit retag flag offensive close merge delete

Comments

1

Could you please provide the code that leads to the error, including the construction of the faulty graph ?

tmonteil gravatar imagetmonteil ( 2019-08-27 15:05:22 +0100 )edit
1

Also, please provide the version of Sage that you are using and your OS. It looks like Sage 8.6. Did you compile it yourself?

John Palmieri gravatar imageJohn Palmieri ( 2019-08-27 20:52:42 +0100 )edit

I updated my question with the functions primarily involved. This is sage 8.6 and I did compile it myself.

mqpsf gravatar imagemqpsf ( 2019-08-28 01:38:54 +0100 )edit
1

Thanks. Could you please also tell the "command" that lead to the error, i.e. the input you gave to the functions so that they did not work ? In particular, the values of all_v_pairs, possible_unfolding, flatten ? Also, we will need the code for assign_edges and poly2list.

tmonteil gravatar imagetmonteil ( 2019-08-28 08:11:09 +0100 )edit

I just put the entire code on the post since every function will be needed to run the code via CL compiling.

mqpsf gravatar imagemqpsf ( 2019-08-28 13:19:15 +0100 )edit

2 Answers

Sort by ยป oldest newest most voted
2

answered 2019-08-28 13:40:21 +0100

tmonteil gravatar image

updated 2019-09-03 14:56:38 +0100

EDIT : OK got it:

For the graph with a single vertex, the eulerian_circuit method is broken;

sage: G = Graph()
sage: G.add_vertex(0)
sage: G
Graph on 1 vertex
sage: G.eulerian_circuit()
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-5-0c288f8b38d6> in <module>()
----> 1 G.eulerian_circuit()

/opt/sagemath/sage-source/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in eulerian_circuit(self, return_vertices, labels, path)
   4001                     edges.append(e if labels else (e[0], e[1]))
   4002             else:
-> 4003                 next_edge = next(g_edge_iter(v))
   4004 
   4005                 if next_edge[0] == v:  # in the undirected case we want to

StopIteration:

Or more generally graphs with vertices but no edges;

sage: G = Graph()
sage: G.add_vertices(range(10))
sage: G.eulerian_circuit()
---------------------------------------------------------------------------
StopIteration                             Traceback (most recent call last)
<ipython-input-27-0c288f8b38d6> in <module>()
----> 1 G.eulerian_circuit()

/opt/sagemath/sage-source/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in eulerian_circuit(self, return_vertices, labels, path)
   4001                     edges.append(e if labels else (e[0], e[1]))
   4002             else:
-> 4003                 next_edge = next(g_edge_iter(v))
   4004 
   4005                 if next_edge[0] == v:  # in the undirected case we want to

StopIteration:

Thanks for reporting, this is now trac ticket 28451


[previous answer in trying to reproduce the issue]

I first got

---> 14 from progress.bar import Bar
     15 import pprint
     16 
ImportError: No module named progress.bar

So, i bet that you installed progress from pip, which i did. But then, i got a very different error:

A 3-dimensional polyhedron in ZZ^3 defined as the convex hull of 8 vertices
Unfold: 12 faces
[A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
 A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices]

Find all length 2 sets from 8 vertices

Find all length 11 sets from 28 edges

Processing |                                | 0/21474180
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-2-96862f2c002c> in <module>()
    263 
    264     # Unfold
--> 265     planar, G = gray(flatten, all_vertex_pairs)
    266     pp = pprint.PrettyPrinter(indent=Integer(4))
    267     pp.pprint(planar)

<ipython-input-2-96862f2c002c> in gray(flatten, all_vertex_pairs)
     37             s.remove(i)
     38             s.add(j)
---> 39             flag, planar, G = test_edges(all_vertex_pairs, s, flatten)
     40             if flag:
     41                 return planar, G

<ipython-input-2-96862f2c002c> in test_edges(all_v_pairs, possible_unfolding, flatten)
    169         return False, {}, None
    170     test = assign_edges(all_v_pairs, possible_unfolding)
--> 171     planar = planar_representation({}, flatten, test)
    172     if planar == {}:
    173         return False, {}, None

<ipython-input-2-96862f2c002c> in planar_representation(planar, flatten, test_case)
    126     for i in range(len(flatten)):
    127         key = flatten[i]
--> 128         cycle = poly2list(key)
    129         to_delete = []
    130         for j in range(len(cycle)):

<ipython-input-2-96862f2c002c> in poly2list(face)
     85     OUTPUT: A numpy integer array of every edge possible inside a face.
     86     """
---> 87     converted_face = convert(face)
     88     edges = np.array(Combinations(converted_face, Integer(2)).list()).astype(int)
     89     return edges

<ipython-input-2-96862f2c002c> in convert(data)
     69     s_data = s_data.split(",")
     70     for i in range(len(s_data)):
---> 71         s_data[i] = float(s_data[i])
     72     return np.array(s_data)
     73 

ValueError: could not convert string to float: A 2-dimensional face of a Polyhedron in ZZ^3 defined as the convex hull of 3 vertices
edit flag offensive delete link more

Comments

I have never had that error. I am compiling the code with sage standalone. Maybe this is an ipython error? The convert function only exists because I do not know how to convert a polyhedral face into a list.

mqpsf gravatar imagemqpsf ( 2019-08-28 21:30:06 +0100 )edit
1

I am using the ipython command line, but there should not be any difference. Did you compile for Python 2 or Python 3 ?

tmonteil gravatar imagetmonteil ( 2019-08-29 08:49:49 +0100 )edit

python 2.7 I am rerunning the computation and seeing if the error raises again.

mqpsf gravatar imagemqpsf ( 2019-08-29 14:29:24 +0100 )edit
1

if you still get the error, can you modify your code (the line if G.eulerian_circuit() is False:) with something like

try:
    is_eulerian = G.eulerian_circuit()
except:
    raise ValueError(G.edges())
if not is_eulerian:

and post the output so we can do tests on that specific graph. If it has too many edges, you can post instead G.graph6_string().

David Coudert gravatar imageDavid Coudert ( 2019-08-30 08:37:38 +0100 )edit

Updated the original post with the output.

mqpsf gravatar imagemqpsf ( 2019-09-03 14:09:51 +0100 )edit
0

answered 2019-09-03 14:41:29 +0100

mqpsf gravatar image

Solved!

flatten = [<0,1,2> <0,2,3> <0,1,4> <1,2,4> <0,3,4> <2,3,4>]
planar = {}
for key in flatten:
    planar[key] = {}
G = Graph(planar)
print(G.edges())
print(G.eulerian_circuit())

The output

[]
Traceback (most recent call last):
next_edge = next(g_edge_iter(v))
StopIteration

A dict where the keys are faces and the values that are just empty dicts and not edges raises a stop iteration error when the eulerian_circuit function is called. This is due to the planar representation function. I can rewrite the code or just put an if statement to catch this case.

edit flag offensive delete link more

Comments

Worse comes to worse you could also catch the StopIteration exception and return an empty list or whatever the appropriate answer should be in this case.

Iguananaut gravatar imageIguananaut ( 2019-09-04 12:31:05 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2019-08-27 14:51:20 +0100

Seen: 366 times

Last updated: Sep 03 '19