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);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
    }
    
    public void addEdge(int from, int to, double weight){
        graph.get(from).add(new DWEdge(from, to, 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);
        bf.addEdge(0,1,4);bf.addEdge(0,2,2);
        bf.addEdge(3,4,-4);bf.addEdge(0,3,2);
        bf.addEdge(2,3,-1);bf.addEdge(1,2,3);
        bf.addEdge(1,4,1);bf.addEdge(4,2,6);
        bf.addEdge(1,5,5);bf.addEdge(3,5,3);
        bf.addEdge(5,4,7);
        
        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[1] -> 4.0
0 - 2 : distTo[2] -> 2.0
2 - 3 : distTo[3] -> 1.0
3 - 4 : distTo[4] -> -3.0
3 - 5 : distTo[5] -> 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.io.FileReader;
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 {
    
    static class Task{
        int id;
        double duration;
        ArrayList<Integer> completeBefore;
        
        Task(int id, double duration, ArrayList<Integer> a){
            this.id = id;
            this.duration = duration;
            completeBefore = new ArrayList<>();
            for(int i:a)completeBefore.add(i);
        }
    }
    
    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;
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
        edgeTo = new int[V];  
        distTo = new double[V];
    }
     
    public void constructGraph(Task[] tasks){ 
        for(Task t:tasks){ 
            graph.get(sourceID).add(new DWEdge(sourceID, t.id, 0));
            graph.get(t.id).add(new DWEdge(t.id, sinkID, -t.duration));
            
            for(int i:t.completeBefore){ 
                graph.get(t.id).add(new DWEdge(t.id, i, -t.duration));
            }
        }
    }
    
    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
        BufferedReader br = new BufferedReader(new FileReader("d:\\input2.txt"));
        int n = Integer.parseInt(br.readLine());
          
        Task[] tasks = new Task[n];
        int count = 0;
        String s ="";
        
        while((s=br.readLine())!=null){
            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[0];
            double duration = data[1];
            ArrayList<Integer> al = new ArrayList<>(); 
            for(int i=2;i<d.length;++i)al.add((int)data[i]); 
            tasks[count++] = new Task(id, duration, al);
        }  
        //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.
        */
        d.constructGraph(tasks); 
        
        /*
            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){
            timings.add(new DWEdge(d.edgeTo[i], i, d.distTo[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);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
        edgeTo = new int[V];
        distTo = new double[V];
        this.V = V;
    }
    
    public void addEdge(int from, int to, double weight){
        graph.get(from).add(new DWEdge(from, to, 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.addEdge(0,1,5);   d.addEdge(3,6,9);   
        d.addEdge(0,4,9);   d.addEdge(4,5,4);
        d.addEdge(0,7,8);   d.addEdge(4,6,20);
        d.addEdge(1,2,12);  d.addEdge(4,7,5);
        d.addEdge(1,3,15);  d.addEdge(5,2,1);
        d.addEdge(1,7,4);   d.addEdge(5,6,13);
        d.addEdge(2,3,3);   d.addEdge(7,5,6);
        d.addEdge(2,6,11);  d.addEdge(7,2,7);
        
        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] = 0 distTo[0] = 0.0
Vertex 1 edgeTo[1] = 0 distTo[1] = 5.0
Vertex 2 edgeTo[2] = 5 distTo[2] = 14.0
Vertex 3 edgeTo[3] = 2 distTo[3] = 17.0
Vertex 4 edgeTo[4] = 0 distTo[4] = 9.0
Vertex 5 edgeTo[5] = 4 distTo[5] = 13.0
Vertex 6 edgeTo[6] = 2 distTo[6] = 25.0
Vertex 7 edgeTo[7] = 0 distTo[7] = 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);
        for(int i=0;i<V;++i)graph.add(new ArrayList<>());
        edgeTo = new int[V];
        distTo = new double[V];
        this.V = V;
    }
    
    public void addEdge(int from, int to, double weight){
        graph.get(from).add(new Edge(from, to, 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;
        
        nodeRef[s] = pq.add(0.0, s);
        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;
            nodeRef[e.to] = pq.add(distTo[e.to], e.to);
            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.addEdge(0,1,5);   d.addEdge(3,6,9);   
        d.addEdge(0,4,9);   d.addEdge(4,5,4);
        d.addEdge(0,7,8);   d.addEdge(4,6,20);
        d.addEdge(1,2,12);  d.addEdge(4,7,5);
        d.addEdge(1,3,15);  d.addEdge(5,2,1);
        d.addEdge(1,7,4);   d.addEdge(5,6,13);
        d.addEdge(2,3,3);   d.addEdge(7,5,6);
        d.addEdge(2,6,11);  d.addEdge(7,2,7);
        
        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] = 0 distTo[0] = 0.0
Vertex 1 edgeTo[1] = 0 distTo[1] = 5.0
Vertex 2 edgeTo[2] = 5 distTo[2] = 14.0
Vertex 3 edgeTo[3] = 2 distTo[3] = 17.0
Vertex 4 edgeTo[4] = 0 distTo[4] = 9.0
Vertex 5 edgeTo[5] = 4 distTo[5] = 13.0
Vertex 6 edgeTo[6] = 2 distTo[6] = 25.0
Vertex 7 edgeTo[7] = 0 distTo[7] = 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[0])));
        System.out.println(d.sign(w0, d.computeOutput(examples[1])));
        System.out.println(d.sign(w0, d.computeOutput(examples[2])));
        System.out.println(d.sign(w0, d.computeOutput(examples[3])));
        
        
        //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[0])));
        System.out.println(d.sign(w0, d.computeOutput(examples[1])));
        System.out.println(d.sign(w0, d.computeOutput(examples[2])));
        System.out.println(d.sign(w0, d.computeOutput(examples[3])));
    }
    
    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[0] + x1*w[1]+x2*w[2];
        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[1] = w[1] + n*(t-o)*e.x1;        
                w[2] = w[2] + n*(t-o)*e.x2;
                
                if(o!=t)System.out.println("New weights = "+w[1]+" "+w[2]);
            }
            if(count==4)break;
        }
        System.out.println("Perceptron training complete.");
        System.out.println("Learned weights : [w1, w2] = ["+w[1]+", "+w[2]+"]");
    }
    
    public static void main(String[] args){
        Perceptron perceptron = new Perceptron();
        
        Example[] examples = new Example[4];
        examples[0] = new Example(-1, -1, -1);
        examples[1] = new Example(-1, 1, -1);
        examples[2] = new Example(1, -1, -1);
        examples[3] = 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[0] + x1*w[1]+x2*w[2];
        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[1] = w[1] + n*(t-o)*e.x1;        
                w[2] = w[2] + n*(t-o)*e.x2;
                
                if(o!=t)System.out.println("New weights = "+w[1]+" "+w[2]);
            }
            if(count==4)break;
        }
        System.out.println("Perceptron training complete.");
        System.out.println("Learned weights : [w1, w2] = ["+w[1]+", "+w[2]+"]");
    }
    
    public static void main(String[] args){
        Perceptron perceptron = new Perceptron();
        
        Example[] examples = new Example[4];
        examples[0] = new Example(-1, -1, -1);
        examples[1] = new Example(-1, 1, -1);
        examples[2] = new Example(1, -1, -1);
        examples[3] = 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<>();
        for(int i=0;i<v;++i)graph.add(new ArrayList<>());
        distTo = new double[V];
        edgeTo = new int[V];
        mst = new ArrayList<>();
        marked = new boolean[V];
    }
    
    public void applyPrims(int start){
        boolean[] checkAddedNode = new boolean[V];
        marked[start] = true;
        distTo[start] = 0;
        FibonacciHeap<Double, Integer> pq = new FibonacciHeap<>();
        FibonacciHeap.Node n = pq.add(0.0, start);
        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.)
            */
            checkAddedNode[node] = true;
            
            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 
                    */
                    nodes[V] = pq.add(w.weight(), V);  
                    
                    /*
                       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]);
                    System.out.println("Added "+V+" : "+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);
        graph.get(v).add(e);
        graph.get(w).add(e);
        E++;
    }
    
    public static void main(String[] args){
        PrimsEager prims = new PrimsEager(8);
        prims.addEdge(0, 7, 0.16);
        prims.addEdge(2, 3, 0.17);
        prims.addEdge(1, 7, 0.19);
        prims.addEdge(0, 2, 0.26);
        prims.addEdge(5, 7, 0.28);
        prims.addEdge(1, 3, 0.29);
        prims.addEdge(1, 5, 0.32);
        prims.addEdge(2, 7, 0.34);
        prims.addEdge(4, 5, 0.35);
        prims.addEdge(1, 2, 0.36);
        prims.addEdge(4, 7, 0.37);
        prims.addEdge(0, 4, 0.38);
        prims.addEdge(6, 2, 0.40);
        prims.addEdge(3, 6, 0.52);
        prims.addEdge(6, 0, 0.58);
        prims.addEdge(6, 4, 0.93);
         
        prims.applyPrims(0);
    }
}

Output :

Removed 0

Set distTo[7] to 0.16
Added 7 : 0.16

Set distTo[2] to 0.26
Added 2 : 0.26

Set distTo[4] to 0.38
Added 4 : 0.38

Set distTo[6] to 0.58
Added 6 : 0.58

Removed 7

Set distTo[1] to 0.19
Added 1 : 0.19

Set distTo[5] to 0.28
Added 5 : 0.28

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

Removed 1

Set distTo[3] to 0.29
Added 3 : 0.29

Removed 2

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

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

Removed 3

Removed 5

 V = 4 old = 0.37 new = 0.35
distTo[4] = 0.35 new value = 0.35
edgeTo[4] = 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){
            al.add(new ArrayList<>());
        }
    }
    
    
    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){
        al.get(from).add(to);
    }
    
    public static void main(String[] args){
        //7 vertices in example digraph
        TopologicalSort ts = new TopologicalSort(7);
        ts.addEdge(0, 2);
        ts.addEdge(0, 5);
        ts.addEdge(0, 1);
        
        ts.addEdge(3, 2);
        ts.addEdge(3, 5);
        ts.addEdge(3, 6);
        
        ts.addEdge(6, 4);
        ts.addEdge(6, 0);
        
        ts.addEdge(1, 4);
        
        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     
         - the starting web address
regex 
         - the regular expression pattern to extract web site links from html content downloaded form a web page

HTML content is downloaded using the URL class at java.net.URL

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.net.MalformedURLException;
import java.net.URL;
import java.util.HashSet;
import java.util.LinkedList;
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<>();
    
    //URLs already visited
    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{
        q.add(root);
        while(!q.isEmpty()){ 
            String s = q.poll();
            
            //Find only almost 100 websites.
            if(marked.size()>100)return;
            
            boolean ok = false;
            URL url = null;
            BufferedReader br = null;
            
            while(!ok){ 
                try{
                    url = new URL(s);
                    br = new BufferedReader(new InputStreamReader(url.openStream()));
                    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();
            
            while((s = br.readLine())!=null){
                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)){
                    marked.add(w);
                    System.out.println("Site : "+w);
                    q.add(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.google.com
Site : http://www.codebytes.in
Site : https://www.blogger.com
Site : http://google
Site : http://schema.org
Site : https://plus.google.com
Site : http://2.bp.blogspot.com
Site : https://apis.google.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://twitter.com
Site : http://www.csail.mit.edu
Site : http://www.ercim.eu
Site : http://www.keio.ac.jp
Site : http://ev.buaa.edu.cn
Site : http://www.google.co.in
Site : https://play.google.com
Site : http://www.youtube.com
Site : http://news.google.co.in
Site : https://mail.google.com
Site : https://drive.google.com
Site : https://www.google.co.in
Site : https://accounts.google.com
Site : https://ssl.gstatic.com
Site : https://support.google.com
Site : https://www.google.com

IOException for URL : http://google

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

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


IOException for URL : https://apis.google.com

Site : http://docs.webplatform.org
Site : http://en.wikipedia.org
Site : http://blog.webplatform.org
Site : https://twitter.com
Site : https://www.facebook.com
Site : http://webchat.freenode.net
Site : http://richard.esplins.org
Site : https://developers.google.com
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 : http://www.linkedin.com
Site : https://classroom.w3devcampus.com
Site : http://classroom.w3devcampus.com
Site : http://w3cshop.spreadshirt.net
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 : https://www.youtube.com
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 : http://fonts.googleapis.com
Site : http://html5shiv.googlecode.com
Site : https://www.linkedin.com
Site : https://www.xing.com
Site : http://www.deliveryofthingsworld.com
Site : http://www.securityofthingsworld.com
Site : http://www.industryofthingsworld.com
Site : http://www.we
Site : http://www.facebook.com


Results:

Web sites crawled : 107

http://catalog.ldc.upenn.edu
https://www.linkedin.com
http://www
https://www.blogger.com
https://support.google.com
http://twitter.com
https://catalog.ldc.upenn.edu
http://jigsaw.w3.org
https://ssl
https://www.youtube.com
http://www.google.co.in
https://www.google.com
http://docs.webplatform.org
https://mail.google.com
https://t.co
http://www.webplatform.org
https://assets
http://www.csail.mit.edu
https://twitter.com
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://www.linkedin.com
http://yoast.com
http://clermontech.org
http://afpyro.afpy.org
http://en.wikipedia.org
http://www.lacantine
http://www.fundaciononce.es
http://news.google.co.in
http://www.codebytes.in
http://html5shiv.googlecode.com
http://blog.webplatform.org
http://eepurl.com
https://plus.google.com
https://status.github.com
https://help.github.com
http://purl.org
http://google
http://www.industryofthingsworld.com
http://stats.wordpress.com
http://e1
https://drive.google.com
https://developers.google.com
http://validator.w3.org
http://www.we
http://www.facebook.com
https://training.github.com
http://toulonux.org
https://www.facebook.com
https://github.com
https://play.google.com
http://wordpress.org
http://webchat.freenode.net
http://w3cshop.spreadshirt.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://fonts.googleapis.com
https://accounts.google.com
http://xmlns.com
http://www.google.com
http://www.securityofthingsworld.com
https://apis.google.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://www.youtube.com
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
https://www.google.co.in
http://5by5.tv
https://desktop.github.com
http://www.meetup.com
http://www.keio.ac.jp