DS-Graph

Graph Representations

1. Adjacency Matrix : struct G{ int V; int E; int **Adj; };
    Adj[u,v] = Adj[v,u] =1 (For Edge u-v, undirected graph)
    O(V^2) time to init and space to store.
    + Recommended when graphs are dense as number of edges is proportional to V^2.
    - Not recommended for sparse graphs.
Uses O(n^2) memory, recommended when less than few thousands node and graph is dense.

2. Adjacency List: All vertices connected to a vertex are listed on an adjacency list of that vertex.
struct G{int V; int E; int *Adj;};
struct ALNode{ int vertex_num; struct ALNode*next};

Order in which edges are placed in AL, affects order of edge processing in algo.

    - Operations like node delete, is difficult. Can be solved by making AL doubly list.
Uses O(n+E) memory.

AL can be implemented using
Linked List: too much memory/time overhead
Array of vectors: easy to code but very slow
Arrays: When total edges are known, very fast and memory efficient.

3. Adjacency Set: Disjoint-set [union-find] are used instead of linked list, otherwise similar to AL.

For below graph:

Adjacency Matrix:

	A	B	C	D
A	0	1	0	1
B	0	0	1	0
C	1	0	0	1
D	0	0	0	0

Adjacency List:

Array based Implementation of AL
ArrayE: contains edges
ArrayLE: contains starting pointer of edge list

Init ArrayLE[i]=-1 for all i
Insert Edge u->v with ID=k:
    arrayE[k]=v;  arrayE[k].nextID=arrayLE[u];  arrayLE[u]=k;
Iterating over edges from u:
    for(ID=arrayLE[u]; ID!=-1; ID=arrayE[ID].nextId)  //arrayE[ID] is edge staring at u.

Adding edge is easy, but modifying edge is difficult. Thus good for static graph.

Graph using AL
#include <iostream>
#include <cstdlib>
using namespace std;

struct ALNode{int dst; int wt; struct ALNode *next;};
struct AL{ struct ALNode *head;};
struct G{ int V; struct AL *arr;};

struct ALNode *newALNode(int dst, int wt)
{  struct ALNode *n=(struct ALNode*) malloc(sizeof(struct ALNode));
    n->dst=dst; n->wt=wt;  n->next=NULL;
    return n;
}

struct G *createG(int V)
{
  struct G *g=(struct G*)malloc(sizeof(struct G));
  g->V=V;
  g->arr=(struct AL*)malloc(sizeof(struct AL));
  for(int i=0;i<V;i++)   g->arr[i].head=NULL;
  return g;
}

void addEdge(struct G *g, int src, int dst, int wt)
{
    struct ALNode *n=newALNode(dst, wt);
    n->next=g->arr[src].head;        g->arr[src].head=n;
    //undirected graph, add dst-src
    n=newALNode(src, wt);
    n->next=g->arr[dst].head;        g->arr[dst].head=n;
}

Graph Traversal
DFS: (like preorder tree traversal, internally uses stack).
Traverses graph in depthward motion using stack to remember to get to next vertex when search hits dead end.
Algo

• Visit adjacent vertex, mark visited, display, push it in stack
• If no adjacent vertex found, pop from stack
• Repeat 1 and 2 until stack not empty.

int Visited[G->V];
void DFS(struct G *g, int u)
{
    Visited[u]=1;
    for(int v; v< g->V; v++)
      foreach unvisited adjacency node v of u:
         DFS(G, v);
}
Use non-recursive version when recursion depth is too big. Replace recursive call with stack.

Explaination:
For below graph:

• Start with P, push to stack, goes to output.    Out:P, Stack:P
• P has Q, S unvisited adjacent nodes, alphabetically Q goes in stack. Out:P Q, stack P Q
• Q has none adjacent, pop it. Out: PQ. Stack:P
• P has Q(visited), S(unvisited) node. Out: P Q S. Stack: PS
• S has R, W unvisited adj node. R goes in alphabetically. Out: P Q S R. Stack: PSR
• R has T, U, V unvisited adj node. T goes in alphabetically. Out: PQSRT, Stack:PSRT
• T has none, pop it. Out:PQSRT. Stack:PSR
• R has U, V unvisited adj node. U goes in alphabetically. Out: PQSRTU. Stack:PSRU
• U has X unvisited adj node. Out: PQSRTUX, Stack:PSRUX
• X has W unvisited adj node. Out: PQSRTUXW, Stack: PSRUXW
• W has S,X(visited), V(unvisited) adj node. Out: PQSRTUXWV. Stack:PSRUXWV
• Keep popping stack as no more unvisited node.

Stack :
Output:
BFS: (like level-order tree traversal, uses queue).
Traverses graph in breadthward motion using queue to remember to get to next vertex when search hits dead end.
Algo

• Visit adjacent vertex, mark visited, display and push to queue
• If no adjacent vertex found, remove first vertex from queue
• Repeat 1 and 2 until queue not empty.

void BFS(struct G *g, int u)
{
   int v; struct Queue *q=createQ(); Enqueue(q, u);
   while(!isEmptyQ(q){
       v=DeQ(q);
       Process u; //e.g. print
       Visited[u]=1;
       if(!Visited[v] && g->Adj[u][v])
          for each unvisited adjacent node v of u
             EnQ(q, v);
}

For same graph as above:
Visit all unvisited adj node of current node, enqueue all alphabetically.
Start with P, Output P, Queue:QS
Move to Q(first elem of Q),   Output:PQ, Queue:QS
deQ Q has only P visited adj node. dequeue Q. Output:PQ, Queue:S
deQ S has R and W unvisited adj node. Output:PQS, Queue:RW
deQ R has T, U V(unvisited) adj node. Output:PQSR, Queue: WTUV
deQ W has V, X unvisited adj node. Output: PQSRW, Queue: TUV
deQ T has R(visited) Output: PQSRWT, Queue:UV
deQ U has R(visited), X(unvisited) adj node. Output:PQSRWTU, Queue:V
deQ V has R and W(visited), Output: PQSRWTUV. Queue:Empty

void DFS/BFS_Traverse(struct G *g)
{  for(i=0; i < g->V; i++) Visited[i]=0;
    for(i=0; i < g->V; i++)   if(Visited[i]==0)    DFS/BFS(G, v);
}

DFS vs BFS

• stack (pending vertices processed in LIFO) vs queue (pending vertices processed in FIFO)
• backtracking vs no_backtracking_possible
• search in a direction vs vertices at same level processed first

DFS more memory efficient than BFS as can backtrack sooner
For directed graph, with BFS need to remember whether visited a node and how to reach there, else we might detect false cycles.
With DFS, the stack remembers how we reach to a node, so no extra work to print cycle.

Usage:
BFS: Find shortest path in unweighted graph, Detect cycle, Find shortest path between two nodes, Find all nodes within one connected component.
DFS: Find path from u to v, Topological sorting, Find strongly connected components, solving puzzles like maze.

Can't be used
DFS:
Not to find shortest path

BFS:


Topological Sort
Ordering of nodes such that for each edge u->v, u comes before v.
There can be many answers to this problem.
Idea: O(n^2+m) very slow.

• Node without incoming edge can be first element
• Then, remove outgoing edges from first node.
• Repeat above.

Idea: O(n+m) very slow.
Precompute number of incoming edges, deg(u), for each node u
Put all nodes u with deg(u)=0 into Q
Repeat until Q is not empty:
    Take u from Q
    For each edge u->v,
        Decrement deg(v) [i.e. remove edge u->v)
        If deg(v)=0, push v to Q

Minimum Spanning Tree
Given undirected graph, wish to find subset with minimum total weight that connects all nodes into a tree.

Kruskal algo   O(mlogm) easy to code, slower than Prim
Idea:
Edge e with smallest weight must be in MST
Once edge e is chosen, end point nodes can be merged into single node

Algo
Sort edges in increasing order of weight
Repeat until there is one merged node left
     Take min weight edge e
     If e contains two different mergednodes, connect them and merge using union-find
Else ignore e and try next edge

Prim's MST Algo  Greedy
O(V^2) AdhMatrix based 
O(ElogV)- AdjList based 
O(m + n log n) Binary Heap
Idea

• Maintain set S that start with single node s
• find smallest edge e (u->v) connecting u (element of S) and v (not element of S)
• Add e to MST and v to S
• Repeat until S has all vertices

In Prim, we grow single merged node S, instead of growing multiple ones at same time(Kruskal).

Algo: O(ElogV)
Create minheap of size V with each node having vertex number and key value
Init minheap with first vertex as root (key to first vertex=0, rest=infinite)
While minheap not empty
    Extract minval node u from minheap
    For every adj vertex v of u, check if v in minheap. If in minheap and key val is more than weight of u-v, update key val of v as weight of u-v.

PseudoCode:
for each u in V:
    key[u]=infinity;  color[u]=white; pred[u]=NULL;  //color white=unvisited, black=visited
key[root]=0
Q=new PriorityQ(V) //add all vertices in Q.
while(Q.notEmpty()):
    u=extractMin();
    for each v in adj[u])
        if(color[v]==white  &&  wt(u-v)<key([v])
            key[v]=wt(u-v);  Q.decreasekey(v, key[v]);   prev[v]=u;
    color[u]=black;

For below graph:

Depending on min edge picked (when multiple edges are min), we may have different MSTs(due to which node we choose on tie). If all edges have unique weight, the generated MST will always be unique.
E.g.,
we start with vertex H, min edge H-I(3)
I: minedge I-G(2)
G: minedge G-A(4)
A: minedge A-B(2)
B: minedge B-D(2)
D: minedge D-C(3)
C: no adj unvisited node.
D: minedge D-F(3)
F: minedge F-E(3)

void PrimMSTAlgo(struct G *g)   //O(ElogV)  AL implementation
{
    int V=g->V, parent[V], key[V];

    struct MinHeap *minheap=createMinHeap(V);
    for(int v=1; v<V;v++)
    {  parent[v]=-1;  key[v]=INT_MAX;  minheap->hnodearr[v]=newMinHeapNode(v, key[v]);
        minheap->pos[v]=v;  }

    key[0]=0;   minheap->hnodearr[0]=newMinHeapNode(0, key[0]);   minheap->pos[0]=0;

    minheap->size=V; //initially

    while(!isEmpty(minheap))
    {
         struct MinHeapNode *minheapnode=getMin(minheap);
         int u=minheapnode->v;

        struct ALNode *pCrawl=g->arr[u].head;
        while(pCrawl!=NULL)
        {
            int v=pCrawl->dst;
            if(isInMinHeap(minheap, v) && pCrawl->wt<key[v])
            { key[v]=pCrawl->wt;  parent[v]=u;  decrementKey(minheap, v, key[v]);  }
             pCrawl=pCrawl->next;
        }
    }
    //print parent array.
}

Heap Code
struct MinHeapNode{ int v; int key; };

struct MinHeap{int size; int capacity; int *pos; struct MinHeapNode **hnodearr;};

struct MinHeapNode *newMinHeapNode(int v, int key)
{
    struct MinHeapNode *n=(struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));
    n->v=v;  n->key=key;
    return n;
}

struct MinHeap *createMinHeap(int capacity)
{
    struct MinHeap *n=(struct MinHeap*)malloc(sizeof(struct MinHeap));
    n->pos=(int*)malloc(capacity*sizeof(int));
    n->size=0;  n->capacity=capacity;
    n->hnodearr=(struct MinHeapNode**) malloc(capacity*sizeof(struct MinHeapNode*));
    return n;
}

void swapMinHeapNode(struct MinHeapNode **a, struct MinHeapNode **b)
{
    struct MinHeapNode *t=*a;
    *a=*b;  *b=t;
}

void minHeapify(struct MinHeap *minheap, int idx)
{
    int smallest=idx, left=2*idx+1, right=2*idx+2;
    if(left<minheap->size && minheap->hnodearr[left]->key < minheap->hnodearr[smallest]->key)
        smallest=left;

    if(right<minheap->size && minheap->hnodearr[right]->key < minheap->hnodearr[smallest]->key)
        smallest=right;

    if(smallest!=idx){
        MinHeapNode *smallestnode=minheap->hnodearr[smallest];
        MinHeapNode *idxnode=minheap->hnodearr[idx];
        minheap->pos[smallestnode->v]=idx;
        minheap->pos[idxnode->v]=smallest;
        swapMinHeapNode(&minheap->hnodearr[smallest], &minheap->hnodearr[idx]);
        minHeapify(minheap, smallest);
    }
}

int isEmpty(struct MinHeap *minheap)
{    return minheap->size==0;  }

struct MinHeapNode *getMin(struct MinHeap *minheap)
{
    if(isEmpty(minheap)) return NULL;
    struct MinHeapNode *root = minheap->hnodearr[0];
    struct MinHeapNode *lastnode=minheap->hnodearr[minheap->size-1];

    minheap->pos[root->v] = minheap->size-1;
    minheap->pos[lastnode->v] = 0;

    (minheap->size)--;
    minHeapify(minheap, 0);
    return root;
}

void decrementKey(struct MinHeap *minheap, int v, int key)
{
    int i=minheap->pos[v];
    minheap->hnodearr[i]->key=key;

    while(i && minheap->hnodearr[i]->key < minheap->hnodearr[(i-1)/2]->key)
    {
        minheap->pos[minheap->hnodearr[i]->v] = (i-1)/2;
        minheap->pos[minheap->hnodearr[(i-1)/2]->v] = i;
        swapMinHeapNode(&minheap->hnodearr[i], &minheap->hnodearr[(i-1)/2]);
         i=(i-1)/2; //move to parent index
    }
}

bool isInMinHeap(struct MinHeap *minheap, int v)
{
    if(minheap->pos[v]<minheap->size)  return true;
    return false;
}

Steiner Min Tree(SMT): Sometimes adding dummy node can help reduce cost of network.
SMT is NP-hard problem.

Red node is steiner dummy node.

Strongly Connected Component
Given directed graph, it is strongly connected if all nodes are reachable from every single node V.

Kosaraju Algo  O(V+E)
Init counter=0
While all nodes are not labelled:
    choose arbitary unlabelled node v
    Start DFS(v)
        Check current node y as visited, recurse on all unvisited neighbours, After DFS finished, increment counter and set of label of y=counter.
Reverse direction of all edges
For node with label a,a-1,..1
    Find all reachable node from v and group them as SCC.

C++ Implementation
using namespace std;

class G{
    int V;
    list<int> *adjl;  //array of ALs
    void fillOrder(int v, bool visited[], stack<int> &S);
    void DFSUtil(int v, bool visited[])
    {
        visited[v]=true;  cout<<v<<" ";
        list<int>::iterator i;
        for(i=adjl[v].begin(); i!=adjl[v].end(); i++)  if(!visited[*i])  DFSUtil(*i, visited);
     }
public:
    G(int V){ this->V=V;   adjl=new list<int>[V]; }

    void addEdge(int v, int w) { adjl[v].push_back(w); };

    void printSCC();
    G getTranspose(){
        G g(V);
        for(int v=0;v<V;v++)
        {
            list<int>::iterator i;
            for(i=adjl[v].begin(); i!=adjl[v].end(); i++)
                g.adjl[*i].push_back(v);
        }
        return g;
    }
};

void G::fillOrder(int v, bool visited[], stack<int> &S)
{
    visited[v]=true; //mark current node visited
    list<int>::iterator i;  //recur for vertices adj to current v
    for(i=adjl[v].begin(); i!=adjl[v].end(); i++)   if(!visited[*i])   fillOrder(*i, visited, S);
    S.push(v);
}

void G::printSCC()
{
    stack<int> S;
    bool *visited=new bool[V];
    for(int i=0;i<V;i++)  visited[i]=false;
    for(int i=0;i<V;i++)  if(visited[i]==false)  fillOrder(i, visited, S);
    G gT=getTranspose();
    for(int i=0;i<V;i++) visited[i]=false;  //mark all unvisited for second DFS.
    while(S.empty()==false)
    {   int v=S.top();  S.pop();   if(visited[v]==false){ gT.DFSUtil(v, visited); cout<<endl;}  }
}

//Test

G g(5); g.addEdge()..

g.printSCC();

Other Good Tricks:
? How to find max-weght spanning tree
    Change sign of all weights. Use Min-spanning tree algo.

? Graph with n vertices, E edges
   Has n! different AM, Has E! different AL, Has max n(n-1)/2 edges(undirected simple graph)

?

DFS can not find shortest way in graph because it takes a path and keep moving till it finds a way. This may or may not be best path.
But on trees, DFS finds shortest path, because in trees there is only one way to reach a node.

HeapSort O(nlogn), QuickSort O(n^2). Practically Quicksort is faster.

Path Planning Problem:
1. Search Based: A grid represent configuration space, Goal and Robot location is known within grid, search is run on grid to find point-to-point find-path problem
2. Sampling Based: To solve generate-graph problem. A new vertex, v, generated, Check if v is interior of an obstacle, When good vertex is found, add edges between v and mutually visible immediate neighbours. When good path is known, A* search executed over graph to solve find-path problem
3. Combinational:

Reference
http://www.geeksforgeeks.org/greedy-algorithms-set-5-prims-mst-for-adjacency-list-representation/
http://www.geeksforgeeks.org/