# Graph Basics

## Contents

# 16.1. Graph Basics¶

```
using PyPlot # Packages used
```

## 16.1.1. Graphs¶

A *graph* is a set of objects, represented as *vertices*, which may be connected (or related)
to other vertices through *edges*. In a *directed graph*, there connections are ordered
(that is, a vertex can be connected to another vertex, but not the opposite). In *undirected graphs*,
all edges are simply seen as a connected between the two vertices.

There are many ways to represent a graph, and here we will use an *adjancency list*. The
vertices will be numbered \(1,2,\ldots\) and represented in an array. Each vertex contains
an integer arrays, which lists their “neighbors” - that is, whether the two vertices have
a (directed) edge between them. For undirected graphs, we simply ensure that the edge
appears in both vertices neighbor lists.

To begin with, we define a new type to represent a vertex. The most important field is
`neighbors`

, which is a vector of integers. We also include a `coordinates`

field which
is optional, but useful for plotting the graph. The `Base.show`

function is overloaded
to make the screen output of a vertex look good.

```
struct Vertex
neighbors::Vector{Int} # Indices of neighbors of this Vertex
coordinates::Vector{Float64} # 2D coordinates of this Vertex - only for plotting
Vertex(neighbors; coordinates=[0,0]) = new(neighbors, coordinates)
end
function Base.show(io::IO, v::Vertex)
print(io, "Neighbors = ", v.neighbors)
end
```

The entire graph can not be represented as a simple list of `Vertex`

elements. Again we implement
a simple custom `Base.show`

function for viewing the graph.

```
struct Graph
vertices::Vector{Vertex}
end
function Base.show(io::IO, g::Graph)
for i = 1:length(g.vertices)
println(io, "Vertex $i, ", g.vertices[i])
end
end
```

As an example, the code below creates a graph with 4 vertices, connected as follows:

```
Vertex 1 -> Vertex 4
Vertex 2 -> Vertices 1,4
Vertex 3 -> No vertices
Vertex 4 -> Vertex 2
```

We also include some \(x,y\) coordinates for plotting later.

```
v1 = Vertex([4], coordinates=[1,0.5])
v2 = Vertex([1,4], coordinates=[0,2])
v3 = Vertex([], coordinates=[-1,1])
v4 = Vertex([2], coordinates=[2,2])
g = Graph([v1,v2,v3,v4])
```

```
Vertex 1, Neighbors = [4]
Vertex 2, Neighbors = [1, 4]
Vertex 3, Neighbors = Int64[]
Vertex 4, Neighbors = [2]
```

## 16.1.2. Plotting a graph¶

If \(x,y\) coordinates are provided for all vertices, we can plot graphs with circles
connected by arrows. The code below is not perfect but should work for many of our
examples. If the items appear in wrong sizes, the `scale`

argument can be used to
tweak it.

```
function PyPlot.plot(g::Graph; scale=1.0)
fig, ax = subplots()
ax.set_aspect("equal")
xmin = minimum(v.coordinates[1] for v in g.vertices)
xmax = maximum(v.coordinates[1] for v in g.vertices)
ymin = minimum(v.coordinates[2] for v in g.vertices)
ymax = maximum(v.coordinates[2] for v in g.vertices)
sz = max(xmax-xmin, ymax-ymin)
cr = scale*0.05sz
hw = cr/2
axis([xmin-2cr,xmax+2cr,ymin-2cr,ymax+2cr])
axis("off")
for i in 1:length(g.vertices)
c = g.vertices[i].coordinates
ax.add_artist(matplotlib.patches.Circle(c, cr, facecolor="none", edgecolor="k"))
ax.text(c[1], c[2], string(i),
horizontalalignment="center", verticalalignment="center", fontsize=round(Int, 14*scale))
for nb in g.vertices[i].neighbors
cnb = g.vertices[nb].coordinates
dc = cnb .- c
L = sqrt(sum(dc.^2))
c1 = c .+ cr/L * dc
c2 = cnb .- cr/L * dc
arrow(c1[1], c1[2], c2[1]-c1[1], c2[2]-c1[2],
head_width=hw, length_includes_head=true, facecolor="k")
end
end
end
plot(g)
```

## 16.1.3. Creating graphs¶

We can create graphs using standard Julia array functions. For example, the
functin below creates an undirected *cycle graph* with vertices positioned
along the unit circle:

```
function circle_graph(nv=8)
g = Graph([])
for i = 1:nv
th = 2π*i/nv
v = Vertex([mod(i,nv)+1, mod(i-2,nv)+1], coordinates=[cos(th), sin(th)])
push!(g.vertices, v)
end
return g
end
```

```
circle_graph (generic function with 2 methods)
```

```
g = circle_graph(10)
plot(g)
```

The graph can be modified in a number of ways, see examples below:

```
g = circle_graph(10)
# Add edges by growing the neighbors array
push!(g.vertices[1].neighbors, 6); # Add edge 1->6
append!(g.vertices[4].neighbors, [2,7]); # Add 2 new edges
# Change edges by modifying the neighbors array
g.vertices[3].neighbors[1] = 1 # Change edge, 3->1 instead of 3->4
pop!(g.vertices[5].neighbors) # Remove edge
# Add a new vertex by growing the vertices array, and if needed
# updating some of the existing neighbors array
# Note that the new vertex should be numbered last, otherwise
# all node numbers must be reordered
newv = Vertex([1,4,9], coordinates=[-.1,.3])
push!(g.vertices, newv)
push!(g.vertices[2].neighbors, 11)
# Deleting a vertex is difficult using adjancency lists
# (unless it is the last vertex), since it requires renumbering
# of the vertices. But as a compromise, we can remove all edges
# to/from a vertex:
resize!(g.vertices[8].neighbors,0)
for v in g.vertices
filter!(i -> i != 8, v.neighbors)
end
plot(g)
```