Synergise 2021-Final Report

Synergise is an initiative by Neuromancers and Google Developer Student Club IIT Bhubaneswar to nurture students with minimal experience in Free and Open-Source Software (FOSS) development. This program aims at providing an environment to learn and collaborate through various stellar projects, thereby eliminating the fear of open-source contributions.

Here are the list of projects I have worked on during the program:-

• Beta-Algo a project focusing on bringing all data structures and algorithm in one place.
• Quora Clone a web-project designed to implement basic functionalities of quora-app.

Beta-Algo

• Implementing Floyd-Warshall Algorithm in Different Languages

Project : Implementing Floyd-Warshall algorithm in different Languages

Issue : Beta-Algo/issues/25

Branch : Synergise-IIT-Bhubaneswar/Beta-Algo:main

PR : Beta-Algo/pull/37

Introduction

In Floyd-Warshall algorithm we characterize the structure of a shortest path. The Floyd-Warshall algoruthm considers the intermediate vertices of a shortest path, where an intermediate vertex of a path p=<v1,v2,….,vl> is any vertex of p other than v1 or vl , that is , any vertex in the set {v2,v3,…v(l-1)}.

Let the vertices of G be V = {1, 2……..n} and consider a subset {1, 2……..k} of vertices for some k. For any pair of vertices i, j ∈ V, considered all paths from i to j whose intermediate vertices are all drawn from {1, 2…….k}, and let p be a minimum weight path from amongst them. The Floyd-Warshall algorithm exploits a link between path p and shortest paths from i to j with all intermediate vertices in the set {1, 2…….k-1}. The link depends on whether or not k is an intermediate vertex of path p.

If k is not an intermediate vertex of path p, then all intermediate vertices of path p are in the set {1, 2……..k-1}. Thus, the shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2…….k-1} is also the shortest path i to j with all intermediate vertices in the set {1, 2…….k}.

If k is an intermediate vertex of path p, then we break p down into i → k → j.

A recursive solution to all-pairs shortest-paths problem

Let dij(k) be the weight of the shortest path from vertex i to vertex j with all intermediate vertices in the set {1, 2…….k}.When k=0, a path from vertex i to vertex j with no intermediate vertex numbered higher than 0 has no intermediate vertices at all. Such a path has at most one edge, and hence dij(0)=Wij.

A recursive definition is given by

Computing the shortest-path weights bottom up

We can use the following bottom-up procedure to compute the values dij(k) in order of increasing values of k. Its Input is an n X n matrix W. The procedure returns the matrix Dⁿ of shortest path weights.

n = W.rows
D⁰= W
for k=1 to n
    let Dᵏ = (dij)ᵏ be new nxn matrix
    for i=1 to n
        for j=1 to n
           (dij)ᵏ= min((dij)ᵏ-¹.(dik)ᵏ-¹ + (dkj)ᵏ-¹)
return Dⁿ

The running time for Floyd-Warshall algorithm is determined by the triply nested for loops. Because of each execution of line 7 takes O(1) time, the algorithm runs in O(n³).

Constructing a shortest path

For constructing the shortest path , we compute the matrix D of shortest-path weights and then construct the predecessor matrix Π from D matrix . Given the predecessor matrix Π, the PRINT -ALL-PAIRS-SHORTEST-PATH procedure will print the vertices on a given shortest path.

Recursive formulation

Transitive closure of a directed graph

Given a directed graph G =(V, E) with vertex set V ={1, 2, …,n}, we might wish to determine whether G contains a path from i to j for all vertex pairs i,j ∈ V . We define the transitive closure of G as the graph G* = (V, E*), where E*={(i, j) : there is a path from vertex i to vertex j in G}.

The transitive closure procedure, like Floyd-Warshall Algorithm runs in O(n³).On some computers ,though ,logical operations on single bit values execute faster than arithmetic operations on integer words of data.

n = |V|
	t(0) = the adjacency matrix for G

	// there is always an empty path from a vertex to itself,
	// make sure the adjacency matrix reflects this

	for i =1 to n 
		t(0)[i,i] = True
	

	// step through the t(k)'s

	for k =1 to n
		for i =1 to n
			for j = 1 to n
				t(k)[i,j] = t(k-1)[i,j] OR
				(t(k-1)[i,k] AND t(k-1)[k,j])
	return t(n)

Beta-Algo/warshall.cpp at 28ef090fca18f4ea7125606de6b0ab410aaaf7e4 ·…

Quora Clone

• Implementing Facebook Login Feature

Project : Implementing Facebook Login Feature

Issue : Quora-clone/issues/1

Branch : Synergise-IIT-Bhubaneswar/Quora-clone:master

PR : Quora-clone/pull/6

Facebook App is required for Facebook Login

The aim of the issue is to integrate Facebook Login into a website or application you need to create a Facebook App at https://developers.facebook.com/apps/ and set up the Facebook Login product under the App. Creating a Facebook App will provide you with a Facebook App ID which is required when initializing the Facebook JavaScript SDK (FB.init(...)). For more info see the Facebook Login docs at https://developers.facebook.com/docs/facebook-login/web.

The example React app uses a Facebook App that I created for this tutorial (App ID: 596198351468465). I have successfully implemented and setup this pop-up action for the login page.

Issues that are needed to be solved

• Updates only affect data in the React app

Updating or deleting account information in the React app will only change the data at the client side, it won’t (and can’t) change anything associated with users account in the backend.

• Authentication flow with Facebook access tokens and JWT tokens

Authentication is implemented with Facebook access tokens and JWT tokens. On successful login to Facebook an access token is returned to the React app, which is then used to authenticate with the API which returns a short lived JWT token that expires after 15 minutes, but this issue hasn’t been solved.

Implemented Facebook Login Feature by vidit21srivastava · Pull Request #6 ·…