ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 04 Sep 2019 12:31:05 +0200StopIteration raised during G.eulerian_circuit()https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/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.Tue, 27 Aug 2019 14:51:20 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/Comment by John Palmieri for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47627#post-id-47627Also, please provide the version of Sage that you are using and your OS. It looks like Sage 8.6. Did you compile it yourself?Tue, 27 Aug 2019 20:52:42 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47627#post-id-47627Comment by tmonteil for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47621#post-id-47621Could you please provide the code that leads to the error, including the construction of the faulty graph ?Tue, 27 Aug 2019 15:05:22 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47621#post-id-47621Comment by mqpsf for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47632#post-id-47632I updated my question with the functions primarily involved. This is sage 8.6 and I did compile it myself.Wed, 28 Aug 2019 01:38:54 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47632#post-id-47632Comment by tmonteil for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47634#post-id-47634Thanks. 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`.Wed, 28 Aug 2019 08:11:09 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47634#post-id-47634Comment by mqpsf for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47638#post-id-47638I just put the entire code on the post since every function will be needed to run the code via CL compiling.Wed, 28 Aug 2019 13:19:15 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47638#post-id-47638Comment by tmonteil for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47640#post-id-47640I got
ImportError: No module named progress.bar
Where did you get that module from ?Wed, 28 Aug 2019 13:33:09 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47640#post-id-47640Answer by tmonteil for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?answer=47641#post-id-47641**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](https://trac.sagemath.org/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 verticesWed, 28 Aug 2019 13:40:21 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?answer=47641#post-id-47641Comment by mqpsf for <p><strong>EDIT</strong> : OK got it:</p>
<p>For the graph with a single vertex, the <code>eulerian_circuit</code> method is broken;</p>
<pre><code>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:
</code></pre>
<p>Or more generally graphs with vertices but no edges;</p>
<pre><code>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:
</code></pre>
<p>Thanks for reporting, this is now <a href="https://trac.sagemath.org/ticket/28451">trac ticket 28451</a></p>
<hr>
<p>[previous answer in trying to reproduce the issue]</p>
<p>I first got </p>
<pre><code>---> 14 from progress.bar import Bar
15 import pprint
16
ImportError: No module named progress.bar
</code></pre>
<p>So, i bet that you installed <code>progress</code> from pip, which i did. But then, i got a very different error:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47653#post-id-47653I 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.Wed, 28 Aug 2019 21:30:06 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47653#post-id-47653Comment by tmonteil for <p><strong>EDIT</strong> : OK got it:</p>
<p>For the graph with a single vertex, the <code>eulerian_circuit</code> method is broken;</p>
<pre><code>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:
</code></pre>
<p>Or more generally graphs with vertices but no edges;</p>
<pre><code>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:
</code></pre>
<p>Thanks for reporting, this is now <a href="https://trac.sagemath.org/ticket/28451">trac ticket 28451</a></p>
<hr>
<p>[previous answer in trying to reproduce the issue]</p>
<p>I first got </p>
<pre><code>---> 14 from progress.bar import Bar
15 import pprint
16
ImportError: No module named progress.bar
</code></pre>
<p>So, i bet that you installed <code>progress</code> from pip, which i did. But then, i got a very different error:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47655#post-id-47655I am using the ipython command line, but there should not be any difference. Did you compile for Python 2 or Python 3 ?Thu, 29 Aug 2019 08:49:49 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47655#post-id-47655Comment by mqpsf for <p><strong>EDIT</strong> : OK got it:</p>
<p>For the graph with a single vertex, the <code>eulerian_circuit</code> method is broken;</p>
<pre><code>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:
</code></pre>
<p>Or more generally graphs with vertices but no edges;</p>
<pre><code>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:
</code></pre>
<p>Thanks for reporting, this is now <a href="https://trac.sagemath.org/ticket/28451">trac ticket 28451</a></p>
<hr>
<p>[previous answer in trying to reproduce the issue]</p>
<p>I first got </p>
<pre><code>---> 14 from progress.bar import Bar
15 import pprint
16
ImportError: No module named progress.bar
</code></pre>
<p>So, i bet that you installed <code>progress</code> from pip, which i did. But then, i got a very different error:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47658#post-id-47658python 2.7 I am rerunning the computation and seeing if the error raises again.Thu, 29 Aug 2019 14:29:24 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47658#post-id-47658Comment by mqpsf for <p><strong>EDIT</strong> : OK got it:</p>
<p>For the graph with a single vertex, the <code>eulerian_circuit</code> method is broken;</p>
<pre><code>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:
</code></pre>
<p>Or more generally graphs with vertices but no edges;</p>
<pre><code>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:
</code></pre>
<p>Thanks for reporting, this is now <a href="https://trac.sagemath.org/ticket/28451">trac ticket 28451</a></p>
<hr>
<p>[previous answer in trying to reproduce the issue]</p>
<p>I first got </p>
<pre><code>---> 14 from progress.bar import Bar
15 import pprint
16
ImportError: No module named progress.bar
</code></pre>
<p>So, i bet that you installed <code>progress</code> from pip, which i did. But then, i got a very different error:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47749#post-id-47749Updated the original post with the output.Tue, 03 Sep 2019 14:09:51 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47749#post-id-47749Comment by David Coudert for <p><strong>EDIT</strong> : OK got it:</p>
<p>For the graph with a single vertex, the <code>eulerian_circuit</code> method is broken;</p>
<pre><code>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:
</code></pre>
<p>Or more generally graphs with vertices but no edges;</p>
<pre><code>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:
</code></pre>
<p>Thanks for reporting, this is now <a href="https://trac.sagemath.org/ticket/28451">trac ticket 28451</a></p>
<hr>
<p>[previous answer in trying to reproduce the issue]</p>
<p>I first got </p>
<pre><code>---> 14 from progress.bar import Bar
15 import pprint
16
ImportError: No module named progress.bar
</code></pre>
<p>So, i bet that you installed <code>progress</code> from pip, which i did. But then, i got a very different error:</p>
<pre><code>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
</code></pre>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47666#post-id-47666if 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()`.Fri, 30 Aug 2019 08:37:38 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47666#post-id-47666Answer by mqpsf for <p>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.</p>
<p>The error in question:</p>
<pre><code>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
</code></pre>
<p>EDIT:
Here is the code that creates the error. I am using sagemath 8.6 on windows 10.</p>
<pre><code>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')
</code></pre>
<p>I hope this kind of helps.</p>
<p>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?</p>
<p>I can post more information if needed. This is my first post and there seems to be no other threads on this topic.</p>
<p>EDIT 2:</p>
<p>Using the code sninppet from David Coudert</p>
<pre><code>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: []
</code></pre>
<p>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.</p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?answer=47750#post-id-47750Solved!
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.
Tue, 03 Sep 2019 14:41:29 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?answer=47750#post-id-47750Comment by Iguananaut for <p>Solved!</p>
<pre><code>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())
</code></pre>
<p>The output</p>
<pre><code>[]
Traceback (most recent call last):
next_edge = next(g_edge_iter(v))
StopIteration
</code></pre>
<p>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. </p>
https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47757#post-id-47757Worse 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.Wed, 04 Sep 2019 12:31:05 +0200https://ask.sagemath.org/question/47620/stopiteration-raised-during-geulerian_circuit/?comment=47757#post-id-47757