Showing posts with label Graph Theory. Show all posts
Showing posts with label Graph Theory. Show all posts

Thursday, October 17, 2013

CPSIG Week 3: Basic Data Structures and Graph Theory

Knowledge and usage of Basic Data Structures are the bare minimum skills every Sport Programmer needs to be equipped with. Graph theory is another  important domain which provides an alternate view of problems and facilitates one to reduce these problems into graphs and solve them using classical algorithms. Here some basic topics, learning materials and practice problems are listed to get you started into these topics.

Learning Material
 
Basic Track:

1) C++ STL: Vector, Stack, Queue, List(Linked List), Set, Map, Priority Queue
For reference: http://www.cplusplus.com/reference/stl/ (very useful during coding if you forget something)
Pre-requisite for Graph Algorithms: Representing graphs as adjacency lists, adjacency matrices etc. 

2) Depth First Search
3) Breadth First Search

4) Floyd-Warshall

5) Single Source Shortest Paths - Dijkstra's in O(V^2)

Advanced Track:
1) Single Source Shortest Paths - Dijkstra's in O(V+E*logV) - Refer to priority queue or set approach in Advanced STL uses mentioned above or read this tutorial:
2) Single Source Shortest Paths(with negative weights) - Bellman-Ford:
3) Topological Sorting:

4) Strongly Connected Components - Kosaraju's or Tarjan's algorithm.
A) Kosaraju's:
B) Tarjan's:

5) Bi-Connected Components, finding Articulation Points and Bridges.

6) Minimum Spanning Tree - Prims or Kruskals algorithms.
A) Prims:
Implementation: 
B) Kruskals: 

Practice Problems

Basic Track:

Advanced Track:

Wednesday, October 16, 2013

All Pairs Shortest Paths - Floyd Warshall Algorithm

Learning Resource: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Short Description:
1) This algorithm finds shortest distance been every pair of nodes in a graph.
2) The implementation shared here uses adjacency matrix representation.
3) Complexity of the algorithm is O(n^3)

Working:
1) Initialize all distances between nodes (i,j) to INF (a very large value which is guaranteed to be more than the maximum distance between two nodes - here it is chosen as 10^9) where i != j and 0 where i==j.
2) Input the distances for every node (i,j) and populate the adjacency matrix.
3) Calculate all-pairs shortest paths by iterating for all i,j,k and using the result min-distance(i,j) = min(min-distance(i,j) , min-distance(i,k)+min-distance(k,j))

Implementation:

// Nodes are numbered from 1 to n
for(int i=1; i<=n; i++)
    for(int j=1;j<=n;j++)
        a[i][j]=(i==j)?(0):(1000000000);

// Input a[][] here.

for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1;j<=n;j++)
            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

Friday, January 4, 2013

Topological Sort and Strongly Connected Components

Topological Sorting and finding Strongly Connected Components are classical problems on Directed Graphs. Here we will see how we can do Topological Sorting by using DFS and Find Strongly Connected Components using Kosaraju's Algorithm.
Topological Sorting Algorithm:
1) Start with any node and perform a DFS on the graph marking visited nodes.
2) If a node has no unvisited neighbours, add it to the front of a linked list.
3) Repeat till all nodes are visited.
Instead of using a linked list we just push_back normally into a C++ vector. The final vector will give reverse of the topologically sorted order.
Strongly Connected Components Algorithm:
1) Do Topological Sort.
2) Find transpose of the graph: It is defined as - if (u,v) is an edge in original graph, (v,u) is an edge in the transpose
3) Do a DFS on the transpose of the graph in topologically sorted order.
4) Each vertex of the so formed depth-first forest is a separate strongly connected component. Mark them, count the number of them etc.
vector<int> a[1005],atr[1005],topo;
bool seen[1005];
int comp[1005],indeg[1005];
int n,c;

void dfs(int node) // Topological Sorting
{
 seen[node]=true;
 REP(i,0,a[node].size())
 {
  if(seen[a[node][i]]==false)
   dfs(a[node][i]);
 }
 topo.push_back(node);
}

void dfst(int node)
{
 seen[node]=true;
 comp[node]=c;
 REP(i,0,atr[node].size())
 {
  if(seen[atr[node][i]]==false)
   dfst(atr[node][i]);
 }
}

int SCC()
{
 int result=0;
 memset(seen, false, sizeof seen);
 REP(i,1,n+1)
 {
  if(seen[i]==false)
   dfs(i);
 }
 memset(seen,false,sizeof seen);
 memset(comp,0,sizeof comp);
 c=0;
 for(int i=topo.size()-1;i>=0;i--)
 {
  if(seen[topo[i]]==false)
   {dfst(topo[i]);c++;}
 }
 return c;
}
Practice Problem:
CAPCITY

Kruskal's Algorithm for Minimum Spanning Tree

Kruskal's Algorithm is a Greedy algorithm which calculates the Minimum Spanning Tree of an undirected graph. It works as follows:
1) Sort the edges according to their weight.
2) Choose the edge with minimum weight
3) Take the next minimum edge - if it does not form a cycle with the existing edges in the MST, add it to the MST. Else, go to the next edge and repeat this step.
To check whether the next edge does not form a cycle with the existing edges, we use a Data Structure called Union-Find or Disjoint Set Data Structure. This can be implemented using arrays. To keep complexity minimum, we use Union-By-Rank and Path Compression.
Hence overall complexity of the algorithm is O(ElogE) for sorting + O(E) for the Disjoint-Set Data Structure operations = Overall O(ElogE).
#define MAXN 10000 // number of edges

struct node
{
    int x;
    int y;
    int w;
}e[MAXN];

int id[MAXN],sz[MAXN];

int root(int i)
{
    while(i!=id[i])
    {
        id[i]=id[id[i]];
        i=id[i];
    }
    return i;
}

void qunion(int p, int q)
{
    int i = root(p), j=root(q);
    if(sz[i] < sz[j]) {id[i]=j; sz[j]+=sz[i];}
    else                {id[j]=id[i]; sz[i]+=sz[j];}
}

bool fun(const node &a, const node &b)
{
    return a.w < b.w;
}

int main()
{
    int t,n,u,v,w,ans,k,adj;
    n=GI; k=0; ans=0;
    // Take input of edges, their weights and set id[i]=i, sz[i]=1 for each vertex
    REP(i,0,n)
    {
      e[k].x=GI; e[k].y=GI; e[k].w=GI;
      id[e[k].x]=e[k].x; id[e[k].y]=e[k].y; sz[e[k].x]=1; sz[e[k].y]=1;
      k++;
    }
    sort(e,e+k,fun);
    REP(i,0,k)
    {
      if(root(e[i].x)!=root(e[i].y))
      {
        qunion(e[i].x,e[i].y);
        ans+=e[i].w;
      }
    }
 printf("%d\n",ans);
 return 0;
}
Practice Problem:
BLINNET