# Graph

To make it possible to iterate over all points that share an edge with a given vertex, we have a `Graph`

struct that we define as follows:

```
struct Graph{I}
graph::UndirectedGraph{I}
function Graph{I}() where {I}
G = UndirectedGraph{I}()
return new{I}(G)
end
Graph() = Graph{Int}()
Graph(G::UndirectedGraph{I}) where {I} = new{I}(G)
end
```

Note that this graph is undirected.

`DelaunayTriangulation.Graph`

— Type`Graph{I}`

Struct for storing neighbourhood relationships that map vertices to all other vertices that share an edge with that vertex. The type `I`

is the integer type.

See the docs for a description of how boundary edges are handled.

**Fields**

`graph::UndirectedGraph{I}`

The `UndirectedGraph`

that maps a vertex `u`

to a list of edges, `V`

, such that `(u, v)`

is an edge of the triangulation for each `v`

in `V`

.

**Extended help**

You should not work with the `graph`

field directly. We provide the following functions for working with `Graph`

, where `G`

denotes a `Graph{I}`

type. (Type information in the function signatures is omitted.)

**Accessors**

`get_graph(G)`

`get_vertices(G)`

`each_vertex(G)`

`get_edges(G)`

`get_neighbours(G)`

`get_neighbours(G, u)`

**Mutators**

`add_vertex!(G, u...)`

`add_neighbour!(G, u, v...)`

`add_triangle!(G, i, j, k)`

or`add_triangle!(G, T)`

`add_triangle!(G, T...)`

`delete_triangle!(G, i, j, k)`

or`delete_triangle!(G, T)`

`delete_triangle!(G, T...)`

`delete_neighbour!(G, u, v...)`

`delete_vertex!(G, u...)`

`delete_boundary_vertices_from_graph!(G)`

`clear_empty_points!(G)`

**Miscellaneous**

`num_edges(G)`

`num_neighbours(G, u)`

`num_vertices(G)`

`has_vertex(G, u)`

`has_boundary_vertices(G)`

`DelaunayTriangulation.get_graph`

— Method`get_graph(G::Graph)`

Returns the field `graph`

of `G`

.

`DelaunayTriangulation.get_edges`

— Method`get_edges(G::Graph)`

Returns all the edges of the graph `G`

. Edges are unordered.

`DelaunayTriangulation.get_vertices`

— Method`get_vertices(G::Graph)`

Given a `graph`

, returns the current set of vertices.

`DelaunayTriangulation.each_vertex`

— Method`each_vertex(G::Graph)`

Given a `graph`

, returns the current set of vertices.

`DelaunayTriangulation.get_neighbours`

— Method`get_neighbours(G::Graph)`

Returns the set of neighbourhoods of the graph `G`

.

`DelaunayTriangulation.get_neighbours`

— Method`get_neighbours(G::Graph, u)`

Returns the neighbourhood of the points `u`

of the graph `G`

.

`DelaunayTriangulation.num_neighbours`

— Method`num_neighbours(G::Graph, u)`

Returns the number of neighbours of the point `u`

of the graph `G`

.

`DelaunayTriangulation.num_edges`

— Method`num_edges(G::Graph)`

Returns the number of edges `G`

. The edges `(i, j)`

and `(j, i)`

will only be counted once.

`DelaunayTriangulation.num_vertices`

— Method`num_vertices(G::Graph)`

Returns the number of vertices in the graph `G`

.

`DelaunayTriangulation.add_vertex!`

— Method`add_vertex!(G::Graph, u...)`

Given a graph `G`

and vertices `u...`

, adds these vertices into `G`

.

`DelaunayTriangulation.add_neighbour!`

— Method`add_neighbour!(G::Graph, u, v...)`

Given a graph `G`

, adds `v...`

into the neighbourhood of `u`

.

`DelaunayTriangulation.add_triangle!`

— Method`add_triangle!(G::Graph, i, j, k)`

Given a graph `G`

, adds the triangle `(i, j, k)`

into `G`

. In particular, the indices `(i, j, k)`

are added into `G`

, and the indices are all in each other's neighbourhoods.

`DelaunayTriangulation.add_triangle!`

— Method`add_triangle!(G::Graph, T...)`

Adds the triangles `T...`

into the graph `G`

.

`DelaunayTriangulation.delete_triangle!`

— Method`delete_triangle!(G::Graph, i, j, k)`

Given a graph `G`

, deletes the triangle `(i, j, k)`

deletes `G`

. In particular, the indices `(i, j, k)`

will no longer be neighbours of each other.

Be careful with using this function - you could have a triangle `(j, i, ℓ)`

, say, which will also be affected since the graph is undirected. Note also that the vertices `(i, j, k)`

will not be removed - only the neighbourhoods are affected.

`DelaunayTriangulation.delete_triangle!`

— Method`delete_triangle!(G::Graph, T...)`

Deletes the triangles `T...`

from the graph `G`

.

`DelaunayTriangulation.delete_neighbour!`

— Method`delete_neighbour!(G::Graph, u, v...)`

Given a graph `G`

and a vertex `u`

, deletes the vertices `v...`

from the neighbourhood of `u`

.

`DelaunayTriangulation.delete_vertex!`

— Method`delete_vertex!(G::Graph, u...)`

Given a graph `G`

and vertices `u...`

, deletes the vertices from `G`

.

`DelaunayTriangulation.delete_boundary_vertices_from_graph!`

— Method`delete_boundary_vertices_from_graph!(G::Graph{I}) where {I}`

Given a graph `G`

, deletes all the boundary indices from `G`

, i.e. all `u`

such that `u ≤ -1`

.

`DelaunayTriangulation.clear_empty_points!`

— Method`clear_empty_points!(G::Graph)`

Given a `graph`

, deletes any points that have empty neighbourhoods.