Introduction to graph algorithms
Andy Novocin
Register for PA2 slots
http://doodle.com/7kryeiwfvf9ygf7u
cs.prof.ninja/programs
A new type of challenge
The UDel ACM sends out a challenge problem in their weekly email. Here is this week's:
An ascending number is a natural number in which every digit is strictly less than the next digit. What is the sum of all base 16 ascending numbers? Give your answer in base 16. For example, 123, 12358D, 6AE are all ascending numbers base 16.
To sign up for the weekly challenges visit this link (click subscribe).
To submit your solution visit THIS link.
Are these two graphs the same?
Official Graph Definition
A graph is a set of vertices \(V\) and a set of edges \(E\).
If \(v_1\) connects to \(v_2\) then \( (v_1, v_2) \in E \).
Complexities of graph algorithms will typically involve two parameters: \(|V|\) and \(|E|\).
Adjacency Matrix
Our first method of storing a graph in a computer is the adjacency matrix
Create a matrix (array of arrays) with one row and column per vertex.
If an edge exists from \(v_i\) to \(v_j\) then:
put a 1 at entry \(i,j\)
Adjacency Matrix p2
\( \left(\begin{array}{rrrrr} 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \end{array}\right) \)
In Class Understanding Problem 1:
Create the adjacency matrix of a complete binary tree with 7 nodes (number them as if they were in a heap).
Sage advice
Don't design a graph algorithm, design a graph from your problem as the algorithm.
Sock Dye
Knuth's Word Games
“gimlets”, “giblets”, “gibbets”, “gibbers”, “libbers”, “limbers”, “lumbers”, “cumbers”, “cambers”, “campers”, “carpers”, “carters”, “barters”, “batters”, “butters”, “putters”, “puttees”, “putties”, “patties”, “parties”, “parries”, “carries”, “carrier”, “currier”, “curlier”, “burlier”, “bullier”, “bullies”, “bellies”, “jellies”, “jollies”, “collies”, “collins”, “colling”, “coaling”, “coaming”, “foaming”, “flaming”, “flaking”, “fluking”, “fluxing”, “flexing”, “fleeing”, “freeing”, “treeing”, “theeing”
Additional Terms
The degree of a vertex is the number of edges eminating from there.
(For directed graphs there is in-degree and out-degree)
Directed/Undirected
Weighted/Unweighted
Dense/Sparse
Sparse/Dense
In class problem 2:
Consider the following sentence made from 10 letters:
Situation, sir. A neutron star is not neutral!
Create a directed graph of the ten (scrabble one point) letters such that
edge exists from \(x \to y\) only if \( y\) follows \(x\) in the sentence.
The weight of an edge can be the number of times it happens in the sentence.
Find a path through all letters which doesn't repeat.
Can you find two letters such that no path of length \(\leq 4\) can connect them?
cloud.sagemath.com
For solving and playing with graphs.
Please sign up tonight.
Graph data structures
If I have \(n\) vertices then an adjacency matrix has \(\mathcal{O}(n^2)\) entries.
If the graph is sparse then most of these entries are zero.
A sparse solution
An adjacency list
Concept: create an array of vertices each of which has a "next" property storing a pointer to a vertex along an edge.
Thus each vertex has a linked list of "edge partners".
(My preferred solution is to use "sparse linear algebra", ask me for details.)
Adjacency List
Implementation
insert_edge(graph *g, int x, int y, bool directed){
edgenode *p;
p = malloc(sizeof(edgenode));
p->weight = NULL;
p->y = y;
p->next = g->edges[x];
g->edges[x] = p;
g->degree[x]++;
if (directed==FALSE)
insert_edge(g, y, x, TRUE);
else
g->nedges++;
}