I wanted to implement an algorithm for constructing Euler circuits and paths that could take a graph and return whether or not you could traverse the graph in one continuous line without re-tracing any lines. If this traversal was found to be possible, the algorithm could then return the traversal steps in order of node visitation. This algorithm could then be applied when designing quilt stitching patterns. We can then design usable continuous-line stitching patterns for quilters constructed by nodes that represent the turning point and satisfying the conditions for Euler circuits or Euler paths.
Graph design on top of "Holiday Party" pattern by SuzyQuilts
Example of how the stitching would be applied to a finished quilt top.
Graphs must meet certain criteria to determine whether or not they can contain Eulerian paths or circuits. An Euler circuit requires each degree to be of an even degree while a path needs exactly two odd degrees. Euler circuits will end at the same vertex that it starts at while a path will end elsewhere. Both require that the graph be made up of a single connected component.
In order to check if a graph could contain an Euler path or an Euler circuit, I chose to start with depth first search to determine if a given graph was made of a single connected component.
After running depth first search (DFS), I created three functions to determine if a given graph "g" was Eulerian, and if so, does it have an Euler circuit or an Euler path?
​
Depth First Search returns the number of connected components in the given graph "g".
​
In the following three functions, we first determine if a function has a circuit. A given graph "g" has an Eulerian circuit if all nodes in the given graph are of an even degree. The function "determine_circuit" checks for this and returns true if the given graph's nodes are all of even degree, false if otherwise.
​
The next function "determine_path" checks if all but two nodes in a given graph "g" are of an even degree. If all but two are even then this function returns True, it otherwise returns False.
​
After these two conditions are checked, we then run the given graph "g" through the "is_eulerian" function.
​
If DFS returns connected components of length 1 and determine circuit returns true, function prints "Has Euler Circuit."
​
If DFS returns connected components of length 1 and determine path returns true, function prints "Has Euler Path."
If neither of the conditions above are met, prints "Does not contain Euler Circuit or Path"
From here, we can decide if we want to continue to find a path or circuit or abandon based off the "is_eulerian" funciton. If there is a possible path or circuit, we can take the given adjacency matrix and convert it to a list while remove duplicate edges from it.
Taking the edges_list that is returned from the "convert_to_list" functrion, we can either run in through "find_euler_circuit" or "find_euler_path" based off the finding from the "is_eulerian" function.
Running graph1 (entered as an adjacency matrix) through the "is_eulerian" function returns that the given graph does contain an Euler circuit. We can then confidently pass graph1 through the "find_euler_circuit" function and specify what node we want to start at. Here, I have chosen to start at node "0" for the path. It then outputs the node traversal order visualized below.
graph1 Euler circuit
Running graph2 through the "is_eulerian" function returns that the given graph contains an Euler path. This differs from the Euler circuit. Because circuits have specific start and end points, this function does not take a starting node as an argument.
graph2 Euler path
Conclusion
After successful results of Euler paths and circuits, I chose to apply these principles to modern quilt designs. Sewing machines take in fabrics moving in one direction. By applying the ideas behind Euler paths and circuits, we can think of quilting designs as graphs that either have all even degrees or two odd degrees and use these ideas to create stitching patterns.