### CHAPTER II.

# GRAPHS

A **graph** is a collection of **vertices**, **edges**, and **faces**.

var graph = ear.graph ()

Graphs don't need to exist in 2D space (or any space), they are an abstract map showing connections between vertices.

### Adjacency

adjacent vertices

`graph.vertices[` ].vertices

graph.edges[ ].vertices

adjacent edges

`graph.vertices[` ].edges

graph.edges[ ].edges

### Components

`graph.`vertices

graph.edges

graph.faces

Components are referred to by their **indices**.

Component queries will return an integer; this is the component's index in its arrays.

`ear.graph.`nearest_vertex (graph )

ear.graph.nearest_edge (graph )

ear.graph.nearest_face (graph )

## FOLD

In 2016, a file format was developed specifically for origami: the FOLD format. The benefit of this being a Javascript library is that it integrates seamlessly with a JSON-based format.

FOLD graph
┃
┃ // vertices
┣━ vertices_coords
┣━ vertices_vertices
┣━ vertices_edges
┣━ vertices_faces
┃
┃ // edges
┣━ edges_vertices
┣━ edges_faces
┃
┃ // faces
┣━ faces_vertices
┗━ faces_edges
┗━ faces_faces

FOLD is JSON-based, it's not impossible to peek inside and modify the contents manually.

`{`

vertices_coords: [[0 , 0 ], [1 , 0 ], [1 , 1 ], [0 , 1 ]],

edges_vertices: [[0 , 1 ], [1 , 2 ], [2 , 3 ], [3 , 0 ], [0 , 2 ]],

edges_assignment: ["B" , "B" , "B" , "B" , "M" ]

}

This library makes it so you don't have to learn the FOLD format. We have methods to add vertices, edges, and faces.

## Creating Graphs

Our graph is simply a Javascript object.

var myGraph = {}

Every method that operates on graphs is found under this key:

`ear.`graph

Every graph method takes a similar form where the first parameter is the graph; if there are more parameters they come after.

`ear.graph.`populate (graph )

ear.graph.translate (graph , x , y )

There is also an object-oriented approach. The top-level graph key is also a constructor:

var myGraph = ear.graph ()

If you prefer the object-oriented approach, all the methods exist on your object, allowing you to leave out the first parameter.

var myGraph = {}

ear.graph.populate (myGraph)

ear.graph.translate (myGraph, 2 , 1 )

var myGraph = ear.graph ()

myGraph.populate ()

myGraph.translate (2 , 1 )

### Static Initializers

When modeling origami you tend to start with a boundary. All of the regular polygons have named static initializers.

var myGraph = ear.graph.square ()

## Adding Components

### Vertices

**add_vertices** makes sure that no two vertices exist in the same space, within an adjustable **epsilon**.

`ear.graph.`add_vertices (graph , [[x , y ], [x , y ], ... ])

If you import a FOLD file with already existing vertices, you can call **remove_duplicate_vertices** at any time to clean up vertices.

### Edges

**split_edge** adds one new vertex and carefully rebuilds the graph around it, adding new edges and updating any adjacent faces.

`ear.graph.`split_edge (graph , edge , coords )

Give an **edge index** and **coordinates for a new vertex**. If no coordinates are given, it will be split at the midpoint.

### Faces

Splitting a face is more complex; the number of all three component is altered.

`ear.graph.`split_face (graph , face , vector , origin )

Give a **face index** and a line by specifying the line's **vector** and **origin**.

## Populating arrays

Without modifying the geometry of a graph we can construct more arrays that express relationships between components.

`ear.graph.`populate (graph )

The populate method will fill out the graph to the best of its ability.

`vertices_coords: [[`0 ,0 ], [1 ,0 ], [1 ,1 ], [0 ,1 ]]
edges_vertices: [[0 ,1 ], [1 ,2 ], [2 ,3 ], [3 ,0 ], [0 ,2 ]]
edges_assignment: ["B" , "B" , "B" , "B" , "M" ]

becomes

`vertices_coords: [[`0 ,0 ], [1 ,0 ], [1 ,1 ], [0 ,1 ]]
vertices_vertices: [[1 ,2 ,3 ], [2 ,0 ], [0 ,1 ,3 ], [0 ,2 ]]
vertices_edges: [[0 ,3 ,4 ], [0 ,1 ], [1 ,2 ,4 ], [2 ,3 ]]
vertices_faces: [[0 ,1 ], [0 ], [0 ,1 ], [1 ]]
edges_vertices: [[0 ,1 ], [1 ,2 ], [2 ,3 ], [3 ,0 ], [0 ,2 ]]
edges_edges: [[3 ,4 ,1 ], [0 ,2 ,4 ], [1 ,4 ,3 ], [2 ,0 ,4 ], [0 ,3 ,1 ,2 ]]
edges_faces: [[0 ], [0 ], [1 ], [1 ], [0 ,1 ]]
edges_foldAngle: [0 , 0 , 0 , 0 , -180 ]
edges_assignment: ["B" , "B" , "B" , "B" , "M" ]
faces_vertices: [[2 ,0 ,1 ], [3 ,0 ,2 ]]
faces_edges: [[4 ,0 ,1 ], [3 ,4 ,2 ]]
faces_faces: [[1 ], [0 ]]

### Individual Methods

**Populate** calls a bunch of methods, each of which is also available for you to call individually. Prerequisites for each method vary.

var array = ear.graph.make_vertices_vertices (graph )

Unlike **populate**, these methods *do not modify the input graph*; they construct and return a new array, it's up to you to assign it to the graph if you wish.

`ear.graph.`make_vertices_edges ()
ear.graph.make_vertices_vertices ()
ear.graph.make_vertices_faces ()
ear.graph.make_vertices_to_edge_bidirectional ()
ear.graph.make_vertices_to_edge ()
ear.graph.make_vertices_vertices_vector ()
ear.graph.make_vertices_sectors ()
ear.graph.make_vertices_coords_folded ()

`ear.graph.`make_edges_vertices ()
ear.graph.make_edges_edges ()
ear.graph.make_edges_faces ()
ear.graph.make_edges_foldAngle ()
ear.graph.make_edges_assignment ()
ear.graph.make_edges_vector ()
ear.graph.make_edges_length ()
ear.graph.make_edges_collinear_vertices ()

`ear.graph.`make_planar_faces ()
ear.graph.make_faces_vertices ()
ear.graph.make_faces_edges ()
ear.graph.make_faces_faces ()
ear.graph.make_face_spanning_tree ()
ear.graph.make_faces_matrix ()
ear.graph.make_faces_center ()
ear.graph.make_faces_coloring_from_matrix ()
ear.graph.make_faces_coloring ()

## More Methods

### Minimum Spanning Tree

`ear.graph.`make_face_spanning_tree (graph , 5 )

A minimum face spanning tree finds edge-adjacent faces; any face can be the starting face.

### Boundary

Polygons are defined as a **sorted** array of vertices/edges; required for calculations like intersections.

Because edges are stored in no particular order, finding the boundary requires a sort. This method walks boundary edges until a cycle is found.

`ear.graph.`get_boundary (graph )

Both edges and vertices are included, sorted clockwise / counter-clockwise.

todo: support for multiple boundaries; a method that tests connected vertices.

### Transformations

`ear.graph.`translate (graph , x , y , z )
ear.graph.scale (graph , scale , origin )
ear.graph.rotateZ (graph , radians )
ear.graph.transform (graph , matrix )

We can transform graphs with matrices to rotate, scale, translate the entire graph. But things get more interesting if we apply transformation matrices to **subsets** of the graph.

`ear.graph.`make_faces_matrix (graph )

ear.graph.make_vertices_coords_folded (graph )

### Explode Faces

`ear.graph.`explode_faces (graph )

Because neighboring faces share vertices, separating faces requires cloning vertices, one unique occurence for every face.

## Counting Components

Because the geometry is stored in flat, separate arrays, it's possible that the faces are defined in **faces_edges** but not **faces_vertices**; and querying the number of faces by checking **faces_vertices** will break. **Count** will search all the keys that begin with "faces_" and return the longest one.

`ear.graph.count.`faces (graph )

ear.graph.count.edges (graph )

ear.graph.count.vertices (graph )

The **implied count** is useful for things like abstract graphs, a search for vertices will look inside things like "faces_vertices" for the largest index.

`ear.graph.implied.`faces (graph )

ear.graph.implied.edges (graph )

ear.graph.implied.vertices (graph )

It's possible that arrays get out of sync, in which case, the longest might not be the correct one. It's very important to watch carefully and never let a component's arrays become unsynchronized.

## Rebuilding Graphs

This library supports importing a crease pattern from any vector-based drawing program; but some clean-up is necessary.

### Clean

`ear.graph.`clean (graph )

Clean is a fast method that fixes simple issues with validity, it removes:

**circular edges:**an edge's two vertices are actually the same vertex**duplicate edges:**two or more edges are connecting the same two vertices

The method supports cleaning vertices too; the second parameter is options.

`ear.graph.`clean (graph , {
edges: true ,
vertices: true
})

Clean is meant to modify the graph as little as possible; more information on remove operations after the next section.

### Planar Graphs

In planar graphs, it's a violation for two edges to cross.

These are the typical planar graph violations that need addressing when importing from other software:

- lines cross over other lines.
- lines don't always end at
*exactly*the same point.

### Fragment

The fragment method converts a graph into a planar graph by solving the first issue: **lines crossing other lines**.

edge

face

`ear.graph.`fragment (graph )

Fragment substitutes overlapping edges with 4 edges and a new vertex, it splits an edge if another endpoint lies collinear along it, and merges duplicate vertices.

epsilon

An edge is split if vertices are collinear within an epsilon.

The final parameter in many of these methods is an **optional epsilon**. By default it is very precise (1e-6). When importing crease patterns that were made in some vector drawing program you will want to increase this.

`ear.graph.`fragment (graph , epsilon = 1e-6 )

ear.graph.remove_duplicate_vertices (graph , epsilon = 1e-6 )

### Face-Finding

The face-finding algorithm walks from edge to edge turning at each corner. This requires vertices be merged, without them corners don't exist.

epsilon

This library can build faces in 2D; it's not good with higher dimensions. Notice how faces can be built even if edges are crossing.

### Merge Vertices

`ear.graph.`remove_duplicate_vertices (graph )

Removing duplicate vertices will search all the component arrays and make sure the removed vertices are now pointing to the one remaining vertex.

Let's take a closer look at this remove operation.

## Tracking Changes

Imagine adding a crease to a crease pattern but the crease became three edges due to planar overlaps. If you intend to update mountain/valley assignments for example, you need those three indices. This section explains how indices shift and how to keep track of them.

### Removing Components

This library contains methods for removing bad geometry from graphs.

`ear.graph.`remove_circular_edges (graph )
ear.graph.remove_duplicate_edges (graph )
ear.graph.remove_isolated_vertices (graph )
ear.graph.remove_duplicate_vertices (graph , epsilon )

Each of these methods calls the **remove** method:

`ear.graph.`remove (graph , key , indices )

### Remove

Consider this, the removal of edges at index 2 and 4.

`edges_vertices: {`

[[0 ,1 ], [2 ,3 ], XXXX , [5 ,2 ], XXXX , [1 ,3 ]]

}

When a component is removed the following array elements shift up which breaks all references in other arrays. The **remove** method takes care of this.

`ear.graph.`remove (graph, "edges" , [2 , 4 ])

Calling the method modifies the input graph and returns a summary of changes as an array that relates each index to its new location.

`[`0 , 1 , undefined , 2 , undefined , 3 ]

Notice how the length matches the size of the array *before* the change. The values in the array answer the question:

"What is the new location of the old component?"

I've been calling these arrays **maps**.

### Maps

Maps are useful for keeping track of changes **from outside the graph**. Here's an example:

Imagine a game of dodge ball as a graph, where players are vertices and one of the vertices is a team leader. Players are removed after one round. The last line updates the team leader to its new index.

var teamLeader = 5 ;
var changeMap = ear.graph.remove (graph, "vertices" , playersHit);
teamLeader = changeMap[teamLeader];

Updating multiple pointers is also one line of code:

`leaders `= leaders.map (i => changeMap[i]);

### Types of maps

So far, we've only looked at methods that remove. An example of a method that *adds components* is the **fragment** method, in which a single edge can turn into multiple edges. A map to describe this change requires an array at every index.

`[ [`0 , 1 , 2 ], [3 , 4 ], [5 ], [6 , 7 , 8 , 9 ] ]

Remember a map answers the question,

"What is the new location of the old component?"

and fragment converts one edge to multiple edges. However, it is possible to represent the inverse relationship, posing and answering the question:

"What is the old location of the new component?"

These arrays have a length that matches the geometry *after* the change, better at representing changes which add entries. This kind of map with the same example above looks like:

`[`0 , 0 , 0 , 1 , 1 , 2 , 3 , 3 , 3 , 3 ]

I've been calling this kind of map a **backmap**; it looks *back* in the history, it relates the current state to the state before the change. The first kind of map we talked about is a **nextmap**.

**nextmap**: what is the new index of this old element? the length matches*before*the change.**backmap**: what is the old index of this new element? the length matches*after*the change.

All methods in this library, by default, use **nextmap**.

### Invert

The **invert** method will convert one nextmap to a backmap, or visa versa.

`ear.graph.`invert_map ([0 , [1 , 4 ], 6 ])

-> [0 , 1 , undefined , 1 , 2 ]

### Combining Maps

What makes maps really powerful is the ability to track changes across *multiple operations* on a graph.

`ear.graph.`merge_nextmaps (... maps)

If you perform multiple operations on a graph and save each map you can **merge** the maps to make one map reflecting the entire change from start to finish.

// start with 7 components
[0 , 1 , 2 , 3 , 4 , 5 , 6 ]
// merge 2 duplicate edges
[0 , 1 , 2 , 1 , 3 , 2 , 4 ]
// fragment, adds 4 edges
[0 , [1 , 2 ], 3 , [4 , 5 , 6 ], [7 , 8 ]]
// merge 2 more edges
[0 , 1 , 2 , 3 , 0 , 4 , 3 , 5 , 6 ]

The merged map relates each index before the first change to after the final change.

`[`0 , [1 , 2 ], 3 , [1 , 2 ], [0 , 4 , 3 ], 3 , [5 , 6 ]]

Parameters should be ordered from *earliest to most recent*, the first change in time should be first.

`ear.graph.`merge_nextmaps (first , second , ... , final )

### Method responses

Given a square graph with 4 vertices and edges,

attempting to add two vertices results in only one new unique vertex.

The response object is a map of *your parameters* from the method call.

Notice the second vertex parameter already existed at index 2.

`ear.`add_vertices (graph, [[0.5 , 0.5 ], [1 , 1 ]])

// returns

[4 , 2 ]

All methods that modify a graph return a response object that summarizes the changes.

Each method has a unique summary.

These remove methods return an object containing a nextmap and the indices that were removed. The indices in the **remove** array relate to indices *before* the change.

`ear.graph.`remove_circular_edges (graph )
ear.graph.remove_duplicate_edges (graph )
ear.graph.remove_isolated_vertices (graph )
ear.graph.remove_duplicate_vertices (graph , epsilon )

`{`

map: [0 , 1 , 2 , 3 , 1 , 4 , 3 , 0 , 5 , 6 ]

remove: [4 , 6 , 7 ]

}

todo: remove collinear vertices

These two **add** methods simply return a nextmap. Adding is generally more simple than removing.

`ear.graph.`add_vertices (graph , ... )
ear.graph.add_edges (graph , ... )

`[`4 , 2 ]

Splitting an edge creates one new vertex, removes one edge, and provides one edge nextmap.

`ear.graph.`split_edge (graph , ... )

```
{
vertex:
```5 ,
edges: {
map: [0 , 1 , 2 , [3 , 4 ], 5 , 6 ],
remove: 3 ,
}
}

Splitting a face creates two new vertices (or maps to one or two existing), removes one face and contains a nextmap containing two new faces, removes up to two edges, creates one new edge (which splits the face), and provides a nextmap which contains the up to four new edges that were made when splitting edges.

`ear.graph.`split_face (graph , ... )

```
{
vertices: [
```8 , 13 ],
faces: {
map: [0 , [2 , 3 ], 1 ],
remove: 1 ,
},
edges: {
map: [0 , 1 , 2 , [6 , 7 ], 3 , 4 , [8 , 9 ], 5 ],
new: 8 ,
remove: [3 , 6 ]
}
}

Fragment returns a nextmap for edges.

`ear.graph.`fragment (graph )

```
{
edges: {
map: [[
```0 , 1 ], [2 , 3 , 4 ], [5 , 6 , 7 ], [8 , 9 , 10 , 11 ]]
}
}

todo: include vertices nextmap

## Acknowledgements

Interactive graphs at the top of this page are force direct graphs from d3.js.