---
jupytext:
  formats: ipynb,md:myst
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.13.6
kernelspec:
  display_name: Python 3 (phys-581)
  language: python
  name: phys-581
---

```{code-cell}
:tags: [hide-cell]

import mmf_setup;mmf_setup.nbinit()
import logging;logging.getLogger('matplotlib').setLevel(logging.CRITICAL)
%matplotlib inline
import numpy as np, matplotlib.pyplot as plt
```

(sec:Graphs)=
Graphs and Networks
===================

A graph is a collection of nodes $N$ and edges $E \subset N\times N$.  Depending on the
interpretation, one might consider the edges directed $(a, b) \not\equiv (b, a)$ (sometimes
called a [directed graph][] or **digraph**) or simply connections $(a, b) \equiv (b,
a)$.  Edges may also have weights $w$ associated with them, corresponding, e.g., to the
length of the edge or time it takes to travel.

Here we will consider weighed digraphs where the weight of each edge represents the
distance or travel time for the edge..

## Representing Graphs

There are several ways one can represent a graph.  Each has some advantages and disadvantages:
* As sets of nodes, edges and weights.  This is very simple and economical, but
  algorithms on the graph can be expensive.
* As a collection of nodes, each of which link to other nodes. This is not quite as
  compact or simple, but allows one to directly traverse the graph.  Local operations
  are efficient.
* As an [adjacency matrix][] $\mat{A}$.  This is generally not as economical (though sparse
  representations are not bad), but allows for some very nice analysis.  For example, if
  the entries in the matrix tell you how many paths connect each pair of nodes, then
  raising the matrix to a power $\mat{A}^p$ give you the adjacency matrix for a path of
  length $p$.  If you include the diagonals -- i.e. each node is connected to itself --
  then this can be used to find all the connected components.

```{code-cell}
import graphviz
dot = graphviz.Digraph(comment='The Round Table')
dot.node('A', 'King Arthur')  # doctest: +NO_EXE
dot.node('B', 'Sir Bedevere the Wise')
dot.node('L', 'Sir Lancelot the Brave')
dot.edges(['AB', 'AL'])
dot.edge('B', 'L', constraint='false')
dot
```

## Graph Algorithms

Given a graph, we might like to ask questions like the following:
* Can we get from node $a$ to node $b$?
* If so, what is the shortest path from $a$ to $b$?
* How many connected components are there in the graph?

These are "easy" problems in the sense that they have efficient solutions using
e.g. [Dijkstra's algorithm][].

Harder questions include:

* Is there a [Hamiltonian path][]?  I.e., a path that visits each vertex exactly once.
  This is an [NP-complete][] problem.
* What is the shortest cycle that visits each vertex exactly once?  This is the famous
  [Travelling salesman problem][].  This is an [NP-hard][] problem.



[Hamiltonian path]: <https://en.wikipedia.org/wiki/Hamiltonian_path_problem>
[Dijkstra's algorithm]: <https://en.wikipedia.org/wiki/Dijkstra's_algorithm>
[directed graph]: <https://en.wikipedia.org/wiki/Directed_graph>
[adjacency matrix]: <https://en.wikipedia.org/wiki/Adjacency_matrix>
[Travelling salesman problem]: <https://en.wikipedia.org/wiki/Travelling_salesman_problem>
[NP-hard]: <https://en.wikipedia.org/wiki/NP-hardness>
[NP-complete]: <https://en.wikipedia.org/wiki/NP-completeness>