## Monday, November 30, 2015

### Bellman-Ford Single Source Shortest Paths Algorithm - Java

The idea is simple - relax all the edges V-1 number of times.

Proof -

Path-relaxation property - If p = {v0, v1, ..., vk) is a shortest path from s = v0 to vk, and we relax the edges of p in the order (v0, v1), (v1, v2), ..., (vk-1, vk), then vk.d = f(s, vk). This property holds regardless of any other relaxation steps that occur, even if they are intermixed with relaxations of the edges of p.

Let us consider we have a graph with 5 vertices and 8 edges. Relaxations are as follows (we set the source as vertex 0 from where we have to find the shortest path to all other vertices):

Let us say

The shortest path from Vertex 0 to Vertex 1 needs relaxations in the order E2 E4 E1 E0
The shortest path from Vertex 0 to Vertex 2 needs relaxations in the order E3 E8 E6
The shortest path from Vertex 0 to Vertex 3 needs relaxations in the order E2 E0 E8
The shortest path from Vertex 0 to Vertex 4 needs relaxations in the order E3 E1

Pass 1 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 2 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 3 E0 E1 E2 E3 E4 E5 E6 E7 E8
Pass 4 E0 E1 E2 E3 E4 E5 E6 E7 E8

The highlighted edges shows that the shortest path edges for vertex 0 to vertex 1 has been relaxed. You can trace out the edge relaxations for other paths as well.

Example for Worst Case (Wikipedia) -

Source:

```import java.util.ArrayList;
import java.util.Arrays;

public class BellmanFord {

class DWEdge{
int from, to;
double weight;

DWEdge(int from, int to, double weight){
this.from = from;
this.to = to;
this.weight = weight;
}
}

private ArrayList<ArrayList<DWEdge>> graph;
private int edgeTo[];
private double distTo[];
private int V;

BellmanFord(int V){
graph = new ArrayList<>();
edgeTo = new int[V];
distTo = new double[V]; Arrays.fill(distTo, Double.POSITIVE_INFINITY);
this.V = V;

graph.ensureCapacity(V);
}

public void addEdge(int from, int to, double weight){
}

public void relax(DWEdge e){
if(distTo[e.to] > distTo[e.from] + e.weight){
distTo[e.to] = distTo[e.from] + e.weight;
edgeTo[e.to] = e.from;
}
}

public void BellmanFord(int source){
distTo[source] = 0;

for(int i=0;i<V-1;++i){
for(int j=0;j<V;++j){
for(DWEdge e:graph.get(j)){
relax(e);
}
}
}
}

public static void main(String[] args){
BellmanFord bf = new BellmanFord(6);

int source = 0;
bf.BellmanFord(source);

System.out.println("Results : ");
for(int i=0;i<bf.V;++i){
if(i==source)continue;
System.out.println(bf.edgeTo[i]+" - "+i+" : distTo["+i+"] -> "+bf.distTo[i]);
}
}
}```

Output:

Results :
0 - 1 : distTo -> 4.0
0 - 2 : distTo -> 2.0
2 - 3 : distTo -> 1.0
3 - 4 : distTo -> -3.0
3 - 5 : distTo -> 4.0

### Parallel Job Scheduling using Topological Sort - Java

The Problem - Parallel job scheduling - Given a set of jobs with durations and precedence
constraints, schedule the jobs (by finding a start time for each) so as to
achieve the minimum completion time, while respecting the constraints.

JobID Duration (current job must complete before these jobIDs)
0     41.0     1 7 9
1     51.0     2
2     50.0
3     36.0
4     38.0
5     45.0
6     21.0     3 8
7     32.0     3 8
8     32.0     2
9     29.0     4 6

We construct a directed graph for this problem (it needs to be acyclic otherwise the constrians would be impossible to satisfy. If job1 requires job2 to be done, job2 must not require job1 to be done before it). We use topological sort but reverse the edge weights so that the spanning tree gives the length of the longest path from source to any other vertex (maximum work is ensured to be done before another job is taken).

Each node represents a job. There are two additional source and sink nodes. The source has edges to all other job nodes with 0 weights. All job nodes have edges terminating on sink nodes with weights that are required to complete that particular job. Topological sort results are stored in edgeTo[] parent link array to reconstruct the spanning tree. The results are then extracted.

Code:

```import java.io.BufferedReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

//Directed + Weighted
class DWEdge implements Comparable<DWEdge>{
int from, to;
double weight;

DWEdge(int from, int to, double weight){
this.from = from;
this.to = to;
this.weight = weight;
}

@Override
public int compareTo(DWEdge o) {
if(this.weight < o.weight)return 1;
else if(this.weight > o.weight)return -1;
else return 0;
}
}

class TopologicalSorter {

private int E, V;
private ArrayList<ArrayList<DWEdge>> al;
private boolean marked[];
private Stack<Integer> stack;

TopologicalSorter(int V){
this.V = V;
marked = new boolean[V];
stack = new Stack<>();
}

public void dfs(int vertex){
if(!marked[vertex]){
marked[vertex] = true;
for(DWEdge e:al.get(vertex)){
int v = e.to;
dfs(v);
}
stack.push(vertex);
}
}

public static Stack<Integer> sort(ArrayList<ArrayList<DWEdge>> graph, int sourceID){
TopologicalSorter ts = new TopologicalSorter(graph.size());
ts.al = graph;
ts.dfs(sourceID);
return ts.stack;
}
}

class SSSPTopologicalOrder {

int id;
double duration;
ArrayList<Integer> completeBefore;

Task(int id, double duration, ArrayList<Integer> a){
this.id = id;
this.duration = duration;
completeBefore = new ArrayList<>();
}
}

private ArrayList<ArrayList<DWEdge>> graph;
private int edgeTo[], edgeToR[];
private double distTo[];
private int V;
private int sourceID, sinkID;
private ArrayList<ArrayList<Integer>> paths;

SSSPTopologicalOrder(int vertices){
V = vertices+2;
graph = new ArrayList<>();
graph.ensureCapacity(V);

sourceID = V-2;
sinkID = V-1;
edgeTo = new int[V];
distTo = new double[V];
}

for(int i:t.completeBefore){
}
}
}

public void relax(DWEdge e){
if(distTo[e.to] > distTo[e.from] + e.weight){
distTo[e.to] = distTo[e.from] + e.weight;
edgeTo[e.to] = e.from;
}
}

public void findShortestPaths(){

Arrays.fill(distTo, Double.POSITIVE_INFINITY);
distTo[sourceID] = 0;

Stack<Integer> sortedVertices = TopologicalSorter.sort(graph, sourceID);

while(!sortedVertices.isEmpty()){
int v = sortedVertices.pop();
for(DWEdge e : graph.get(v))  relax(e);
}
}

public static void main(String[] args)throws Exception{

//INPUT BEGIN

int count = 0;
String s ="";

String d[] = s.split(" ");
double[] data = new double[d.length];
for(int i=0;i<d.length;++i){
data[i] = Double.parseDouble(d[i]);
}

int id = (int)data;
double duration = data;
ArrayList<Integer> al = new ArrayList<>();
}
//INPUT PROCESSING ENDS

SSSPTopologicalOrder d = new SSSPTopologicalOrder(n);

/*
Construct Graph for Input
Each job has an edge to source vertex and sink vertex both with 0 weigths.
*/

/*
Call the routine
*/
d.findShortestPaths();

/*
Display the results
*/
System.out.println("edgeTo contents -> "+Arrays.toString(d.edgeTo));
System.out.println("Results: ");

ArrayList<DWEdge> timings = new ArrayList<>();

for(int i=0;i<d.V-2;++i){
}

Collections.sort(timings);
for(DWEdge e:timings){
System.out.println("At time ("+(-e.weight)+") transition from "+(e.from==d.sourceID?"Start ":e.from)+" to "+e.to+" ");
}
}
}
```

Output:

edgeTo contents -> [10, 0, 8, 6, 9, 10, 9, 0, 6, 0, 0, 2]
Results:
At time (-0.0) transition from Start  to 0
At time (-0.0) transition from Start  to 5
At time (41.0) transition from 0 to 1
At time (41.0) transition from 0 to 7
At time (41.0) transition from 0 to 9
At time (70.0) transition from 9 to 4
At time (70.0) transition from 9 to 6
At time (91.0) transition from 6 to 3
At time (91.0) transition from 6 to 8
At time (123.0) transition from 8 to 2

Input (from source file: )
10
0 41.0 1 7 9
1 51.0 2
2 50.0
3 36.0
4 38.0
5 45.0
6 21.0 3 8
7 32.0 3 8
8 32.0 2
9 29.0 4 6

Solution Image (Algorithms Part II : coursera.com):

## Sunday, November 29, 2015

### Single source shortest paths using Topological Sort

This program finds the shortest paths to all vertices from a given source vertex.

The algorithm is based on first topologically sorting the vertices and then using
the topological order for relaxing edges connected to the current vertex in the order
until the last vertex is done. The result is the shortest distances from the source
vertex to all other vertices.

Source:

```import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

//Directed + Weighted

class DWEdge{
int from, to;
double weight;

DWEdge(int from, int to, double weight){
this.from = from;
this.to = to;
this.weight = weight;
}
}

class TopologicalSorter {

private int E, V;
private ArrayList<ArrayList<DWEdge>> al;
private boolean marked[];
private Stack<Integer> stack;

TopologicalSorter(int V){
this.V = V;
marked = new boolean[V];
stack = new Stack<>();
}

public void dfs(int vertex){
if(!marked[vertex]){
marked[vertex] = true;
for(DWEdge e:al.get(vertex)){
int v = e.to;
dfs(v);
}
stack.push(vertex);
}
}

public static Stack<Integer> sort(ArrayList<ArrayList<DWEdge>> graph){
TopologicalSorter ts = new TopologicalSorter(graph.size());
ts.al = graph;
for(int i=0;i<ts.V;++i) ts.dfs(i);

return ts.stack;
}
}

public class SSSPTopologicalOrder {

private ArrayList<ArrayList<DWEdge>> graph;
private int edgeTo[];
private double distTo[];
private int V;

SSSPTopologicalOrder(int V){
graph = new ArrayList<>();
graph.ensureCapacity(V);
edgeTo = new int[V];
distTo = new double[V];
this.V = V;
}

public void addEdge(int from, int to, double weight){
}

public void findShortestPaths(int s){

Arrays.fill(distTo, Double.POSITIVE_INFINITY);
distTo[s] = 0;

Stack<Integer> sortedVertices = TopologicalSorter.sort(graph);

while(!sortedVertices.isEmpty()){
int v = sortedVertices.pop();
for(DWEdge e : graph.get(v)){
relax(e);
}
}
}

public void relax(DWEdge e){
if(distTo[e.to] > distTo[e.from] + e.weight){
distTo[e.to] = distTo[e.from] + e.weight;
edgeTo[e.to] = e.from;
}
}

public static void main(String[] args){

double startTime = System.nanoTime();
SSSPTopologicalOrder d = new SSSPTopologicalOrder(8);

d.findShortestPaths(0);

double endTime = System.nanoTime();

System.out.println("Results: ");
for(int i=0;i<d.V;++i){
System.out.println("Vertex "+i+" edgeTo["+i+"] = "+d.edgeTo[i]+" distTo["+i+"] = "+d.distTo[i]);
}

System.out.println("\nTime Taken : "+(endTime-startTime)/10E9+"s");

}
}```

Output:

Results:
Vertex 0 edgeTo = 0 distTo = 0.0
Vertex 1 edgeTo = 0 distTo = 5.0
Vertex 2 edgeTo = 5 distTo = 14.0
Vertex 3 edgeTo = 2 distTo = 17.0
Vertex 4 edgeTo = 0 distTo = 9.0
Vertex 5 edgeTo = 4 distTo = 13.0
Vertex 6 edgeTo = 2 distTo = 25.0
Vertex 7 edgeTo = 0 distTo = 8.0

Time Taken : 8.9406E-5s

### Dijkstra's Algorithm using Fibonacci Heap Priority Queue implementation : Java

This code uses Fibonacci heap for the priority queue used which is faster than other priority queue implementations (binary heap, d-way heap or linear).

Fibonacci Heap source : graphstream-project.org

Code:

```import java.util.ArrayList;
import java.util.Arrays;
import org.graphstream.algorithm.util.FibonacciHeap;

public class Dijkstras {
class Edge{
int to, from;
double weight;

Edge(int from, int to, double weight){
this.to = to;
this.from = from;
this.weight = weight;
}

public String toString(){
return "["+from+", "+to+" : "+weight+"]";
}
}

private ArrayList<ArrayList<Edge>> graph;
private int edgeTo[];
private double distTo[];
private boolean inQ[];
private FibonacciHeap.Node nodeRef[];
private int V;

FibonacciHeap<Double, Integer> pq;

Dijkstras(int V){
graph = new ArrayList<>();
graph.ensureCapacity(V);
edgeTo = new int[V];
distTo = new double[V];
this.V = V;
}

public void addEdge(int from, int to, double weight){
}

public void runDijkstra(int s){
pq = new FibonacciHeap<>();
inQ = new boolean[V];
nodeRef = new FibonacciHeap.Node[V];

Arrays.fill(distTo, Double.POSITIVE_INFINITY);
distTo[s] = 0;

inQ[s] = true;

while(!pq.isEmpty()){
int v = pq.extractMin();
for(Edge e : graph.get(v)){
relax(e);
}
}
}

public void relax(Edge e){
if(!inQ[e.to]){
distTo[e.to] = distTo[e.from]+e.weight;
inQ[e.to] = true;
edgeTo[e.to] = e.from;
}else if(distTo[e.to] > distTo[e.from] + e.weight){
distTo[e.to] = distTo[e.from] + e.weight;
edgeTo[e.to] = e.from;
pq.decreaseKey(nodeRef[e.to], distTo[e.to]);
}
}

public static void main(String[] args){
Dijkstras d = new Dijkstras(8);

d.runDijkstra(0);

System.out.println("Results: ");
for(int i=0;i<d.V;++i){
System.out.println("Vertex "+i+" edgeTo["+i+"] = "+d.edgeTo[i]+" distTo["+i+"] = "+d.distTo[i]);
}
}

}```

Output:

Results:
Vertex 0 edgeTo = 0 distTo = 0.0
Vertex 1 edgeTo = 0 distTo = 5.0
Vertex 2 edgeTo = 5 distTo = 14.0
Vertex 3 edgeTo = 2 distTo = 17.0
Vertex 4 edgeTo = 0 distTo = 9.0
Vertex 5 edgeTo = 4 distTo = 13.0
Vertex 6 edgeTo = 2 distTo = 25.0
Vertex 7 edgeTo = 0 distTo = 8.0

### Perceptron Learning using the Delta rule - Gradient Descent - Java (Training for the boolean AND function)

The delta rule uses gradient descent to approximate the target function. It is guaranteed to converge even if the function is not linearly separable, unlike the perceptron learning rule.

We'll be training the perceptron to learn the boolean AND function. We'll use two weights w1, w2. These weights are approximated by the delta rule to fit the training examples most closely. Next we need to find the threshold value (w0) which we will use to classify the training examples accurately.

I've represented 0 with -1, 1 with 1 itself.

Code:

```class Example{
int x1, x2;
double o;
Example(int x1, int x2, double o){
this.x1 = x1;
this.x2 = x2;
this.o = o;
}
}

public class DeltaRulePerceptron {
double w1, w2;
double dw1, dw2;
double n;

DeltaRulePerceptron(){
//Random values
w1 = 0.1;
w2 = 0.7;
n = 0.05;
}

public double computeOutput(Example example){
return example.x1 * w1 + example.x2*w2;
}

public void trainWithDelta(Example[] examples){
for(int i=0;i<1000;++i){

//            System.out.println("Iteration #"+i);
dw1 = 0;
dw2 = 0;

for(Example ex:examples){
double o = computeOutput(ex);
double t = ex.o;
//                System.out.println("o = "+o+" t = "+t);

dw1 = dw1 + n*(t-o)*ex.x1;
dw2 = dw2 + n*(t-o)*ex.x2;
}

w1 += dw1;
w2 += dw2;
}
}

public static void main(String[] args){
DeltaRulePerceptron d = new DeltaRulePerceptron();

//AND boolean function
Example[] examples = new Example[]{
new Example(-1, -1, -1),
new Example(-1 , 1, -1),
new Example( 1, -1, -1),
new Example( 1,  1, 1)
};
d.trainWithDelta(examples);
System.out.println("(AND) Trained weights : "+d.w1+" "+d.w2);

//bias
double w0 = 0.5;
System.out.println("w0 = "+w0);

//Test
System.out.println(d.sign(w0, d.computeOutput(examples)));
System.out.println(d.sign(w0, d.computeOutput(examples)));
System.out.println(d.sign(w0, d.computeOutput(examples)));
System.out.println(d.sign(w0, d.computeOutput(examples)));

//XOR - fails - A single layer perceptron can't represent a XOR function
examples = new Example[]{
new Example(-1, -1, 1),
new Example(-1 , 1, -1),
new Example( 1, -1, -1),
new Example( 1,  1, 1)
};
d.trainWithDelta(examples);
System.out.println("(XOR) Trained weights : "+d.w1+" "+d.w2);
System.out.println("w0 = "+w0);

System.out.println(d.sign(w0, d.computeOutput(examples)));
System.out.println(d.sign(w0, d.computeOutput(examples)));
System.out.println(d.sign(w0, d.computeOutput(examples)));
System.out.println(d.sign(w0, d.computeOutput(examples)));
}

public int sign(double w0, double output){
return output-w0>0?+1:-1;
}
}

```
Output:

(AND) Trained weights : 0.49999999999999994 0.5000000000000002
w0 = 0.5
-1
-1
-1
1

(XOR) Trained weights : 0.0 5.551115123125783E-17
w0 = 0.5
-1
-1
-1
-1

### Perceptron leaning to classify boolean AND function with the perceptron training rule - Java

A perceptron can be trained to classify inputs according to the AND boolean function.

You need to set the bias accurately, otherwise the learning function will never converge. The code only contains the AND function, you can modify the input for other functions accordingly.

I've represented 0 with -1, 1 with 1 itself.

```class Example{
int x1,x2;
int o;

Example(int a, int b, int c){
x1 = a;x2 = b;o = c;
}
}

class Perceptron {
double w[];
double n = 0.1;

Perceptron(){
w = new double[]{-0.1, -0.9, 0.7};
}

//Getting the perceptron's output
int processInput(double x1, double x2){
double result = 1*w + x1*w+x2*w;
if(result>0)return 1;
else return -1;
}

//Train using perceptron training rule
void train(Example[] examples){
while(true){
int count=0;
for(Example e:examples){
int o = processInput(e.x1, e.x2);
int t = e.o;

if(o!=t)System.out.println("\n"+e.x1+" "+e.x2+" : "+o);
if(t==o)count++;

w = w + n*(t-o)*e.x1;
w = w + n*(t-o)*e.x2;

if(o!=t)System.out.println("New weights = "+w+" "+w);
}
if(count==4)break;
}
System.out.println("Perceptron training complete.");
System.out.println("Learned weights : [w1, w2] = ["+w+", "+w+"]");
}

public static void main(String[] args){
Perceptron perceptron = new Perceptron();

Example[] examples = new Example;
examples = new Example(-1, -1, -1);
examples = new Example(-1, 1, -1);
examples = new Example(1, -1, -1);
examples = new Example(1, 1, 1);

perceptron.train(examples);
}
}

class Example{
int x1,x2;
int o;

Example(int a, int b, int c){
x1 = a;x2 = b;o = c;
}
}

class Perceptron {
double w[];
double n = 0.1;

Perceptron(){
w = new double[]{-0.1, -0.9, 0.7};
}

//Getting the perceptron's output
int processInput(double x1, double x2){
double result = 1*w + x1*w+x2*w;
if(result>0)return 1;
else return -1;
}

//Train using perceptron training rule
void train(Example[] examples){
while(true){
int count=0;
for(Example e:examples){
int o = processInput(e.x1, e.x2);
int t = e.o;

if(o!=t)System.out.println("\n"+e.x1+" "+e.x2+" : "+o);
if(t==o)count++;

w = w + n*(t-o)*e.x1;
w = w + n*(t-o)*e.x2;

if(o!=t)System.out.println("New weights = "+w+" "+w);
}
if(count==4)break;
}
System.out.println("Perceptron training complete.");
System.out.println("Learned weights : [w1, w2] = ["+w+", "+w+"]");
}

public static void main(String[] args){
Perceptron perceptron = new Perceptron();

Example[] examples = new Example;
examples = new Example(-1, -1, -1);
examples = new Example(-1, 1, -1);
examples = new Example(1, -1, -1);
examples = new Example(1, 1, 1);

perceptron.train(examples);
}
}```

Output:

-1 -1 : 1
New weights = -0.7 0.8999999999999999

-1 1 : 1
New weights = -0.49999999999999994 0.7

-1 1 : 1
New weights = -0.29999999999999993 0.49999999999999994

-1 1 : 1
New weights = -0.09999999999999992 0.29999999999999993

-1 1 : 1
New weights = 0.10000000000000009 0.09999999999999992
Perceptron training complete.
Learned weights : [w1, w2] = [0.10000000000000009, 0.09999999999999992]

## Saturday, November 28, 2015

### Prim's Algorithm : Eager Implementation using Fibonacci Heap - Java

Fibonacci Heap source from : http://graphstream-project.org/api/gs-algo/org/graphstream/algorithm/util/FibonacciHeap.html#decreaseKey(org.graphstream.algorithm.util.FibonacciHeap.Node, K)

Eager Implementation :

```import java.util.ArrayList;
import org.graphstream.algorithm.util.FibonacciHeap;

public class PrimsEager {
boolean marked[];
ArrayList<ArrayList<Edge>> graph;
ArrayList<Edge> mst;

double distTo[];
int edgeTo[];

int E, V;

PrimsEager(int v){
V = v;
graph = new ArrayList<>();
distTo = new double[V];
edgeTo = new int[V];
mst = new ArrayList<>();
marked = new boolean[V];
}

public void applyPrims(int start){
marked[start] = true;
distTo[start] = 0;
FibonacciHeap<Double, Integer> pq = new FibonacciHeap<>();
FibonacciHeap.Node nodes[] = new FibonacciHeap.Node[V];
nodes[start] = n;

while(!pq.isEmpty()){
int node = pq.extractMin();

/*
The statement below is necessary, otherwise
some node may wrongly update the new shorter path
for a node that has been already processed and
discarded from the priority queue. (Node 3 in this graph, for example.)
*/

System.out.println("\nRemoved "+node);

for(Edge w:graph.get(node)){
int V = w.other(node);
if(!marked[V]){
marked[V] = true;

/*
Save the reference to the PriorityQueue Node so that
decreaseKey can be performed
*/

/*
distance to the nearest MST node.
*/
distTo[V] = w.weight();

/*
what node is it.
*/
edgeTo[V] = node;

System.out.println("\nSet distTo["+V+"] to "+distTo[V]);
}else if(!checkAddedNode[V] && distTo[V] > w.weight()){
//A better path to this node has been found
//Need to update (decrease) priority (distanceTo value)

System.out.println("\n V = "+V+" old = "+distTo[V]+" new = "+w.weight());
//
distTo[V] = w.weight();

System.out.println("distTo["+V+"] = "+distTo[V]+" new value = "+distTo[V]);

pq.decreaseKey(nodes[V], distTo[V]);
edgeTo[V] = node;

System.out.println("edgeTo["+V+"] = "+node);
}
}
}

System.out.println("MST Edges : ");
for(int i=0;i<V;++i){
if(i==start)continue;
System.out.println(i+" - "+edgeTo[i]);
}
}

public void addEdge(int v, int w, double weight){
Edge e = new Edge(v, w, weight);
E++;
}

public static void main(String[] args){
PrimsEager prims = new PrimsEager(8);

prims.applyPrims(0);
}
}
```

Output :

Removed 0

Set distTo to 0.16

Set distTo to 0.26

Set distTo to 0.38

Set distTo to 0.58

Removed 7

Set distTo to 0.19

Set distTo to 0.28

V = 4 old = 0.38 new = 0.37
distTo = 0.37 new value = 0.37
edgeTo = 7

Removed 1

Set distTo to 0.29

Removed 2

V = 3 old = 0.29 new = 0.17
distTo = 0.17 new value = 0.17
edgeTo = 2

V = 6 old = 0.58 new = 0.4
distTo = 0.4 new value = 0.4
edgeTo = 2

Removed 3

Removed 5

V = 4 old = 0.37 new = 0.35
distTo = 0.35 new value = 0.35
edgeTo = 5

Removed 4

Removed 6
MST Edges :
1 - 7
2 - 0
3 - 2
4 - 5
5 - 7
6 - 2
7 - 0

## Friday, November 27, 2015

### Topological Sort using DFS - Java

Implementing topological sort using DFS in Java.

Source:

```import java.util.ArrayList;
import java.util.Stack;

public class TopologicalSort {

private int E, V;
private ArrayList<ArrayList<Integer>> al;
private boolean marked[];
private Stack<Integer> stack;

TopologicalSort(int V){
this.V = V;
al = new ArrayList<>();
marked = new boolean[V];
stack = new Stack<>();
for(int i=0;i<V;++i){
}
}

public void dfs(int vertex){
if(!marked[vertex]){
marked[vertex] = true;
for(int v:al.get(vertex)){
dfs(v);
}
stack.push(vertex);
}
}

public void addEdge(int from, int to){
}

public static void main(String[] args){
//7 vertices in example digraph
TopologicalSort ts = new TopologicalSort(7);

for(int i=0;i<ts.V;++i) ts.dfs(i);

System.out.println("Topological Order : ");
while(!ts.stack.isEmpty()){
System.out.print(ts.stack.pop()+" ");
}
}
}```

Output:

Topological Order :
3 6 0 1 4 5 2

### Simple Web Crawler using BFS - Java

Making a simple web crawler using BFS in Java.

root
regex
- the regular expression pattern to extract web site links from html content downloaded form a web page

```import java.io.BufferedReader;
import java.io.IOException;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class WebCrawler {
//Queue for BFS
static Queue<String> q = new LinkedList<>();

static Set<String> marked = new HashSet<>();

//URL Pattern regex
static String regex = "http[s]*://(\\w+\\.)*(\\w+)";

//Start from here
static String root = "http://www.codebytes.in";

//BFS Routine
public static void bfs() throws IOException{
while(!q.isEmpty()){
String s = q.poll();

//Find only almost 100 websites.
if(marked.size()>100)return;

boolean ok = false;
URL url = null;

while(!ok){
try{
url = new URL(s);
ok = true;
}catch(MalformedURLException e){
System.out.println("\nMalformedURL : "+s+"\n");
//Get next URL from queue
s = q.poll();
ok = false;
}catch(IOException e){
System.out.println("\nIOException for URL : "+s+"\n");
//Get next URL from queue
s = q.poll();
ok = false;
}
}

StringBuilder sb = new StringBuilder();

sb.append(s);
}
s = sb.toString();
Pattern pattern = Pattern.compile(regex);
Matcher matcher = pattern.matcher(s);

while(matcher.find()){
String w = matcher.group();

if(!marked.contains(w)){
System.out.println("Site : "+w);
}
}
}
}

//Display results from SET marked
public static void displayResults(){
System.out.println("\n\nResults: ");
System.out.println("\nWeb sites crawled : "+marked.size()+"\n");
for(String s:marked){
System.out.println(s);
}
}

//Run
public static void main(String[] args){
try{
bfs();
displayResults();
}catch(IOException e){
System.out.println("IOException caught : "+e);
}
}
}```

Output :

Site : http://www.w3.org
Site : http://www.codebytes.in
Site : https://www.blogger.com
Site : http://schema.org
Site : http://2.bp.blogspot.com
Site : http://www.webplatform.org
Site : https://www.edx.org
Site : http://www.w3devcampus.com
Site : http://testthewebforward.org
Site : https://www.w3.org
Site : https://github.com
Site : https://www.ldc.upenn.edu
Site : http://devvar.org
Site : http://www.industryofthingsworldusa.com
Site : http://webaudio.gatech.edu
Site : http://www2016.ca
Site : http://validator.w3.org
Site : http://jigsaw.w3.org
Site : http://vimeo.com
Site : http://www.fundaciononce.es
Site : http://lists.w3.org
Site : http://www.csail.mit.edu
Site : http://www.ercim.eu
Site : http://www.keio.ac.jp
Site : http://ev.buaa.edu.cn
Site : https://ssl.gstatic.com

Site : http://github.com
Site : http://blog.schema.org

IOException for URL : http://2.bp.blogspot.com

Site : http://docs.webplatform.org
Site : http://en.wikipedia.org
Site : http://blog.webplatform.org
Site : http://webchat.freenode.net
Site : http://richard.esplins.org
Site : http://5by5.tv
Site : https://stats.webplatform.org

IOException for URL : https://www.edx.org

Site : http://yoast.com
Site : http://wp.me
Site : http://wordpress.org
Site : https://classroom.w3devcampus.com
Site : http://classroom.w3devcampus.com
Site : http://eepurl.com
Site : http://ssl.gstatic.com
Site : https://t.co
Site : http://stats.wordpress.com
Site : http://ogp.me
Site : https://assets
Site : https://api.github.com
Site : https://enterprise.github.com
Site : https://help.github.com
Site : https://desktop.github.com
Site : https://status.github.com
Site : https://developer.github.com
Site : https://training.github.com
Site : https://shop.github.com
Site : http://purl.org
Site : http://xmlns.com
Site : http://rdfs.org
Site : http://drupal.org
Site : http://ldc
Site : http://www.upenn.edu
Site : http://catalog.ldc.upenn.edu
Site : https://catalog.ldc.upenn.edu
Site : http://www.ldc.upenn.edu
Site : https://ssl
Site : http://www
Site : https://freenode.net
Site : http://www.brownbaglunch.fr
Site : http://clermontech.org
Site : http://www.meetup.com
Site : http://afpyro.afpy.org
Site : http://www.aperoweb.fr
Site : http://www.lacantine
Site : http://www.43117.tl
Site : http://toulonux.org
Site : http://gullivar.org
Site : http://tedxtoulon.com
Site : http://e1
Site : https://www.xing.com
Site : http://www.deliveryofthingsworld.com
Site : http://www.securityofthingsworld.com
Site : http://www.industryofthingsworld.com
Site : http://www.we

Results:

Web sites crawled : 107

http://catalog.ldc.upenn.edu
http://www
https://www.blogger.com
https://catalog.ldc.upenn.edu
http://jigsaw.w3.org
https://ssl
http://docs.webplatform.org
https://t.co
http://www.webplatform.org
https://assets
http://www.csail.mit.edu
http://drupal.org
http://www.upenn.edu
http://www.deliveryofthingsworld.com
http://devvar.org
http://www.aperoweb.fr
https://classroom.w3devcampus.com
https://ssl.gstatic.com
https://shop.github.com
http://blog.schema.org
http://ssl.gstatic.com
http://rdfs.org
http://www2016.ca
http://yoast.com
http://clermontech.org
http://afpyro.afpy.org
http://en.wikipedia.org
http://www.lacantine
http://www.fundaciononce.es
http://www.codebytes.in
http://blog.webplatform.org
http://eepurl.com
https://status.github.com
https://help.github.com
http://purl.org
http://www.industryofthingsworld.com
http://stats.wordpress.com
http://e1
http://validator.w3.org
http://www.we
https://training.github.com
http://toulonux.org
https://github.com
http://wordpress.org
http://webchat.freenode.net
http://www.w3.org
http://www.43117.tl
https://developer.github.com
http://www.ercim.eu
http://github.com
http://ogp.me
http://www.brownbaglunch.fr
http://schema.org
http://xmlns.com
http://www.securityofthingsworld.com
https://freenode.net
http://vimeo.com
http://2.bp.blogspot.com
http://ev.buaa.edu.cn
https://stats.webplatform.org
http://www.ldc.upenn.edu
http://tedxtoulon.com
http://wp.me
http://www.w3devcampus.com
http://richard.esplins.org
http://webaudio.gatech.edu
https://www.ldc.upenn.edu
http://lists.w3.org
http://classroom.w3devcampus.com
https://www.edx.org
http://testthewebforward.org
http://ldc
http://gullivar.org
https://enterprise.github.com
https://api.github.com
https://www.xing.com
https://www.w3.org
http://www.industryofthingsworldusa.com