Ask Your Question

mqpsf's profile - activity

2019-09-04 05:29:25 -0600 received badge  Nice Question (source)
2019-09-03 08:09:02 -0600 received badge  Scholar (source)
2019-09-03 07:41:40 -0600 received badge  Supporter (source)
2019-09-03 07:41:29 -0600 answered a question StopIteration raised during G.eulerian_circuit()

Solved!

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

The output

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

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

2019-09-03 07:09:51 -0600 commented answer StopIteration raised during G.eulerian_circuit()

Updated the original post with the output.

2019-08-29 07:29:24 -0600 commented answer StopIteration raised during G.eulerian_circuit()

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

2019-08-28 14:30:06 -0600 commented answer StopIteration raised during G.eulerian_circuit()

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

2019-08-28 06:19:15 -0600 commented question StopIteration raised during G.eulerian_circuit()

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

2019-08-27 18:38:54 -0600 commented question StopIteration raised during G.eulerian_circuit()

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

2019-08-27 18:37:59 -0600 received badge  Editor (source)
2019-08-27 08:05:43 -0600 received badge  Student (source)
2019-08-27 08:02:39 -0600 asked a question StopIteration raised during G.eulerian_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.

2019-08-27 08:02:39 -0600 asked a question Stopiteration Raised

I am using gray codes to generate a set of of combinations and testing each combination for certain qualities. I have never had the code fail for any reason before this run. I kind of no idea why this would occur. There should be many more test cases. Has anyone seen G.eulerian_circuit() fail with a StopIteration before? I can post more code if needed.

Find all length 13 sets from 36 edges

Processing |                                | 4329384/2310789600
Traceback (most recent call last):
  File "fold.sage.py", line 334, in <module>
    planar, G = gray(flatten, all_vertex_pairs)
  File "fold.sage.py", line 70, in gray
    flag, planar, G = test_edges(all_vertex_pairs, s, flatten)
  File "fold.sage.py", line 243, in test_edges
    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