User:Mahanga/Sandbox

Graphs

A graph is a generalization of the tree structure, where instead of a strict parent/child relationship between tree nodes, any kind of complex relationships between the nodes can be represented. A graph (G) is a collection of vertices (V) that are linked by edges (E). Each edge, sometimes called an arc, consists of a pair of vertices, which are adjacent to one another. Typically, a graph is shown as a set of circles for the vertices, appropriately labelled, which are joined by lines (edges). The two most common representations of graphs are directed and undirected graphs are the two most common representations of graphs.

We will begin with directed graphs, also known as digraphs, which have the easiest to understand representation, and then undirected graphs and finally weighted graphs.

Graph Terminology

Before continuing, some knowledge of graph terms is necessary. The order of a graph is the number of its edges, i.e. |V(G)|. A common problem is trying to find the length from one vertex to another. This is called finding the path between two vertices. A path is a sequence of vertices in a graph where each vertex has an edge from it to the next vertex until reaching the final vertex. The length of a path is the number of edges used. A simple path is similar to a path, except it cannot visit the same vertex twice. A graph cycle is a path that starts and ends at the same vertex, thus it cycles back.

Graphs are an essential part of Computer Science and play a significant role in real-world applications. For example, a graph can be used to describe the airport system. For example, what is best flight, in terms of total distance, from one city to another? One can use vertices to represent airports and edges to represent the connections between any two airports. In this case, one would most likely use directed graphs with a weight or cost assigned to each edge. Weighted graphs will be explained at the end of this chapter.

Graph Representations

[TODO: picture of directed graph]

Directed Graphs

The number of edges with one endpoint on a given vertex is called that vertex's degree. In a directed graph, the number of edges that point to a given vertex is called its in-degree, and the number that point from it is called its out-degree. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph labeled.

Directed Graph Operations

make-graph(): graph

Create a new graph, initially with no nodes or edges.

make-vertex(graph G, element value): vertex

Create a new vertex, with the given value.

make-edge(vertex u, vertex v): edge

Create an edge between u and v. In a directed graph, the edge will flow from u to v.

get-edges(vertex v): edge-set

Returns the set of edges flowing from v

get-neighbors(vertex v): vertex-set

Returns the set of vertexes connected to v

[TODO: also need undirected graph abstraction in that section, and also find a better set of operations-- the key to finding good operations is seeing what the algorithms that use graphs actually need]

We can use graphs to represent relationships between objects. For example, the popular game Six Degrees of Kevin Bacon can be modeled by a graph, in particular, a labeled undirected graph. Each actor becomes a node, labeled by the actor's name. Nodes are connected by an edge when the two actors appeared together in some movie. We can label this edge by the name of the movie. Then the problem of finding a path from any actor to Kevin Bacon in six or less steps easily reduces to the Single Source Shortest Path problem found in the companion Algorithms book. The Oracle of Bacon at the University of Virginia has actually implemented this algorithm and can tell you the path from any actor to Kevin Bacon in a few clicks[1].

Adjacency Matrix Representation

An adjacency matrix is one of the two common ways to represent a graph. The adjacency matrix shows which nodes are adjacent to one another. Two nodes are adjacent if there is an edge connecting them. In the case of a directed graph, if node $j$ is adjacent to node $i$, there is an edge from $i$ to $j$. In other words, if $j$ is adjacent to $i$, you can get from $i$ to $j$ by traversing one edge. For a given graph with $n$ nodes, the adjacency matrix will have dimensions of $n\times n$. For an unweighted graph, the adjacency matrix will be populated with boolean values.

For any given node $i$, you can determine its adjacent nodes by looking at row $\left(i,\left[1..n\right]\right)$ of the adjacency matrix. A value of true at $\left(i,j\right)$ indicates that there is an edge from node $i$ to node $j$, and false indicating no edge. In an undirected graph, the values of $\left(i,j\right)$ and $\left(j,i\right)$ will be equal. In a weighted graph, the boolean values will be replaced by the weight of the edge connecting the two nodes, with a value of zero indicating no edge.

The memory use of an adjacency matrix is $O(n^{2})$.

Graph Traversals

Depth-First Search

[TODO: depth-first search -- with compelling example]

// Search in the subgraph for a node matching 'criteria'. Do not re-examine 
// nodes listed in 'visited' which have already been tested.
GraphNode depth_first_search(GraphNode node, Predicate criteria, VisitedSet visited) {
 // Check that we haven't already visited this part of the graph
 if (visited.contains(node)) {
   return null;
 }
 visited.insert(node);
 // Test to see if this node satifies the criteria
 if (criteria.apply(node.value)) {
   return node;
 }
 // Search adjacent nodes for a match
 for (adjacent in node.adjacentnodes()) {
   GraphNode ret = depth_first_search(adjacent, criteria, visited);
   if (ret != null) {
     return ret;
   }
 }
 // Give up - not in this part of the graph
 return null;
}

Breadth-First Search

[TODO: breadth-first search -- with compelling example]
[TODO: topological sort -- with compelling example]

An undirected graph with 6 vertices (nodes) and 7 edges.

Undirected Graphs

In a directed graph, the edges point from one vertex to another, while in an undirected graph, they merely connect two vertices.

Weighted Graphs

We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called weighted.