CS421 - Advanced Data Structures and Algorithm Development - Chapter 5 - Graphs

• A graph is a mapping of a collection of nodes onto itself; two nodes are related if there is a link (edge) between them
• Two graphs are isomorphic if there is a 1-1 onto mapping of each node from one graph to the other
• directed graph - every edge has a direction
• network - edges have values
• rooted binary tree is a directed, connected graph
• singly linked list is a directed, connected graph
• hamiltonian cycle - path in a graph that starts at one node and visits each other node once and only once before returning to the starting node.
• Eulerian cycle - path in a graph that starts at one node and travels on every edge once and only once before returning to the starting node

1. Structures - ADTs
   • touch-based model - Cost of a structure is proportional to the number of times any element in the structure is touched, used, or accessed over a sequence of operations.
   • ex. a heap is a structure which can be used as an implementation of apriority queue and can be implemented implicitly in an array, or with explicit pointers, or with arrays to simulate pointers.
   • General Structure Operations
     • Create(S)
     • Destroy(S)
     • Copy(S)
     • Union(S1, S2)
     • Insert(x, S)
     • Delete(x, S)
     • Find(x, S)
     • IsEmpty(S)
     • IsFull(S)
     • FindSize(S)
     • FindStructure(x)
   • Operations assuming timed elements
     • FindYoungest(S)
     • FindOldest(S)
     • FindTime(i, S)
     • FindAge(x, S)
     • FindBefore(x, S)
     • FindAfter(x, S)
     • GetYoungest(S)
     • GetOldest(S)
   • Operations assuming linear structures
     • InsertBefore(x,i,S)
     • InsertAfter(x,i,S)
     • FindFirst(S)
     • FindLast(S)
     • FindPosition(i,S)
     • FindPlace(x, S)
     • FindPredecessor(x, S)
     • FindSuccessor(x, S)
     • GetFirst(S)
     • GetLast(S)
   • Operations assuming orderable elements
     • Split(x, S)
     • FindNearest(x, S)
     • FindSmallest(S)
     • FindLargest(S)
     • FindOrder(i, S)
     • FindRank(x, S)
     • FindSmaller(x, S)
     • FindLarger(x, S)
     • GetSmallest(S)
     • GetLargest(S)
   • define Join(S1, S2) = InsertAfter(GetFirst(S2), FindPlace(FindLast(S1),S1), S1)
   • PAUSE: What are some of the tradeoffs in implementing an operation to reverse the elements of a linear structure?
   • PAUSE: If a pointer is about the same size as an element, at most how much extra space does this implementation use?

   • Structure	Menu
     Stack	Insert, GetYoungest
     Queue	Insert, GetOldest
     Priority Queue	Insert, GetLargest
     Mergeable Queue	Insert, GetLargest, Union
     Dictionary	Insert, Delete, Find
     Partition	Union, FindStructure

2. Queues and Partitions
   • Stack - Create, Insert, GetYoungest
     

     {Stack is implemented as an array Stack[1..stackSize], with youngest element
      Stack[stackTop], and oldest Stack[1]; stackSize >= stackTop >= 0.
      Initially stackTop = 0 }
      
      Insert(element, Stack)
      	{ add element to Stack }
     	if Full(Stack) then
     		Error("stack is full")
     	else
     		stackTop++
     		Stack[stackTop] = element
     		
     Empty (Stack)
     	{ tests whether Stack is empty }
     	if stackTop = 0 then
     		return true
     	else
     		return false
     

     
     Stacks can also be implemented as linked lists with pointers
     Stack operations are often PUSH, POP, PEEK(TOP).
   • Queue - Create, Insert, GetOldest
   • Priority Queue - Create, Insert, GetLargest
   • Mergeable Queue - Create, Insert, GetLargest, Union
     • merging two heaps by inserting all elements from one heap into another is W(n lg n); can reduce to W(n) by building a heap new heap from both "lists"; can reduce it to W(lg n) by taking a leaf from the larger heap and making it the root of the two heaps and doing FixHeap
     • binomial heap - binomial tree where each node is at least as large as its children
     • forest - set of trees
     • binomial queue - forest of binomial heaps each with different posers of two elements
   • Partition - Create, Union, FindStructure (elements are partitioned into disjoint sets)
     

     { An implementation of two partition operations. Size[node] = size of the set with 
       root node. Parent[node] = node if node is the root of the set, otherwise
       it is the parent of node. }
       
     FindStructure (node)
     	{ find the root of the set containing node, then compress the set using
     	  any information gained. }
     	
     	next = node
     	while (Parent[next] != next)
     		next = Parent[next]
     	root = next
     	
     	next = node
     	while (next != root)
     		save = Parent[next]
     		Parent[next] = root
     		next = save
     	return root
     	
     Union(node1, node2)
     	{ merge the sets containing node1 and node2 }
     	
     	root1 = FindStructure(node1)
     	root2 = FindStructure(node2)
     	if root1 = root2 then return
     	
     	sum = Size[root1] + Size[root2]
     	if Size[root1] > Size[root2] then
     		Parent[root2] = root1
     		Size[root1] = sum
     	else
     		Parent[root1] = root2
     		Size[root2] = sum
     

3. Connecting Telephones
   • A graph is connected if from any node we can visit every other node by traversing along the edges.
   • If a graph is disconnected, we can decompose it into a number of connected components, each of which is itself a connected graph
   • What is the least and most number of edges in a connected graph with n nodes?
4. Partially Sorted
5. Exploring Graphs
6. Broadcasting Information
7. Distributing Flow
   • Find the shortest path between two nodes

     	ShortestPath ( A: n x n matrix; x, y : nodes )
     	{ Dijkstra's algorithm - A is a modified adjacency matrix for a simple, connected graph with positive weights; x and y are nodes in the graph; procedure writes out nodes in the shortest path from x to y, and the distance for that path}
     	var
     		IN : set of nodes; {shortest known path from x}
     		z, p : node;
     		d[] : array of integers; {distance from x using nodes in IN}
     		s[] : array of nodes; { previous node in shortest path}
     		OldDistance : integer;
     		
     	begin
     		{initialize set IN and arrays d and s}
     		IN = {x};
     		d[x] = 0;
     		for all nodes z not in IN do
     			d[z] = A[x,z];
     			s[z] = x;
     		
     		{process nodes into IN}
     		while Y not in IN do
     			{add minimum distance node not in IN to IN}
     			p = node z not in IN with minimum d[z];
     			IN = IN U {p};
     			{recomputer d for non-IN nodes, adjust s if necessary}
     			for all nodes z not in IN do
     				OldDistance = d[z];
     				d[z] = min (d[z], d[p] + A[p,z]);
     				if not (d[z] = OldDistance) then
     					s[z] = p;
     			
     		{write out path nodes}
     		write('In reverse order, the path is');
     		write(y);
     		z = y;
     		repeat
     			write (s[z]);
     			z = s[z];
     		until z = x;
     		
     		write ('The path distance is ', d[y]);
     	

   • Find the shortest paths for all pairs of nodes

     	AllShortestPaths ( Graph& G)
     	{ Floyd's algorithm - G is a simple, connected graph with positive weights; procedure stores all-pair shortest distances in array Dist}
     
     	int Dist[G.n()] [G.n()];
     	
     	{initialize D with the weights from G}
     	for (int i = 0; i < G.n(); i++)
     		for (int j = 0; j < G.n(); j++)
     			D[i][j] = G.weight(i,j);
     		
     	{compute all k paths}
     	for (int k = 0; k < G.n(); k++)	
     		for (int i = 0; i < G.n(); i++)
     			for (int j = 0; j < G.n(); j++)
     				if (D[i][j] > (D[i][k] + D[k][j]))
     					D[i][j] = D[i][k] + D[k][j]