Just submitted GSoC Project Proposals : OGDF

Posted on March 21, 2014 by wijebandara

I have submitted four proposals for project ideas given by OGDF.

Computation of Treewidth
Basic Linear Algebra Support
Generators for Different Random Graph Models
Search Trees and Priority Queues

Computation of Treewidth

Short description: The treewidth measures how similar a given graph is to a tree. Tree width is widely used in various areas in Graph theory. However, already computing the treewidth of a graph is NP-complete. There exist, however, practically good heuristics which construct a tree decomposition close to the optimum.

Find the complete proposal here.

Basic Linear Algebra Support

Short description: Basic data structures for vectors and matrices are used in many graph layout algorithms that apply some kind of numerical optimization. But OGDF does not provide vector/matrix classes out-of-the-box. So the goal of this project is to provide powerful and efficient vector and matrix classes, that provide the obvious basic functionality as well as more complex operations and different storage models.

Find the complete proposal here.

Generators for Different Random Graph Models

Short description: Every good graph framework should have a standard set of random graph generators with known properties. There are many different random graph models that are used throughout theory. The task is to rework and extend the set of efficient random graph generators in the OGDF. Our target of this project is to build different random graph generators and documentation about them. Every generator should come with a documentation including a brief summary of the properties of the graph model.

Find the complete proposal here.

Search Trees and Priority Queues

Short description: The goal of this project is clearly separate abstract data types from implementing data structures, and identifying and providing various implementing data structures. An important design goal is to focus on efficiency. Implementation of data types PriorityQueue and Dictionary which can use different implementing data structures; implementation of data structures that can be used as implementing data structures for priority queues and dictionaries.

Find the complete proposal here.

Hope I will get the chance to spend summer with OGDF and make good contribution to the open source world.

Sample layout in OGDF

Posted on March 15, 2014 by wijebandara

Introduction

I have write his article while exploring OGDF features and capabilities. This will demonstrate and explain same basic layouts we can use with OGDF.

This is the source code I am going to demonstrate below graphs.


/**
*
* @author Chameera Wijebandara
* @email chameerawijebandara@gmail.com
*
* Windows 7
* Vishual stuio 2010
* OGDF Snapshot 2014-02-28
*
*/

#include <ogdf/basic/Graph.h>
#include <ogdf/basic/graph_generators.h>
#include <ogdf/layered/DfsAcyclicSubgraph.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/layered/SugiyamaLayout.h>
#include <ogdf/layered/OptimalRanking.h>
#include <ogdf/layered/MedianHeuristic.h>
#include <ogdf/layered/OptimalHierarchyLayout.h>

using namespace ogdf;

int main()
{
	Graph G;

	randomGraph(G,10,35); // grapth genarate.

	GraphAttributes GA( G, GraphAttributes::nodeGraphics |
		GraphAttributes::edgeGraphics |
		GraphAttributes::nodeLabel |
		GraphAttributes::nodeStyle |
		GraphAttributes::edgeType |
		GraphAttributes::edgeArrow |
		GraphAttributes::edgeStyle ); // Create graph attributes for this graph

	node v;
	forall_nodes( v, G ){ // iterate through all the node in the graph
		GA.fillColor( v ) = Color( "#FFFF00" ); // set node color to yellow

		GA.height( v ) = 20.0; // set the height to 20.0
		GA.width( v ) = 20.0; // set the width to 40.0
		GA.shape(v) = ogdf::Shape::shEllipse;

		string s = to_string(v->index());
		char const *pchar = s.c_str(); //use char const* as target type
		GA.label( v ) = pchar;
	}

	edge e;
	forall_edges(e ,G) // set default edge color and type
	{
		GA.bends(e);
		//GA.arrowType(e) = ogdf::EdgeArrow::eaNone;
		GA.strokeColor(e) = Color("#0000FF");
	}

	SugiyamaLayout SL; //Compute a hierarchical drawing of G (using SugiyamaLayout)
	SL.setRanking( new OptimalRanking );
	SL.setCrossMin( new MedianHeuristic );

	OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;

	SL.setLayout( ohl );
	SL.call( GA );

	GraphIO::drawSVG( GA, "C:\\Users\\Chameera\\Desktop\\Output.svg" );

	return 0;
}
//end of the main

Mixed Model Layout


randomTriconnectedGraph(G,10,1,2);

....

MixedModelLayout MML;

MML.call( GA );

Planar Straight Layout


randomTriconnectedGraph(G,10,2,3);

....
PlanarStraightLayout PSL;
PSL.call( GA );

Planar Draw Layout


randomTriconnectedGraph(G,10,2,3);

....
PlanarDrawLayout PDL;
PDL.call( GA );

Planarization Grid Layout


randomTriconnectedGraph(G,10,2,3);

....
PlanarizationGridLayout PGL;
PGL.call( GA );

FMMM Layout


randomGraph(G,12,23);

....
FMMMLayout FL;
FL.call( GA );

Sugiyama Layout


randomGraph(G,10,23);

....</pre>
SugiyamaLayout SL; //Compute a hierarchical drawing of G (using SugiyamaLayout)
 SL.setRanking( new OptimalRanking );
 SL.setCrossMin( new MedianHeuristic );

OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;

SL.setLayout( ohl );
 SL.call( GA );
<pre>

Tree Layout


randomTree(G,10);

....</pre>
TreeLayout TL;

TL.call( GA );
<pre>

Radial Tree Layout


randomTree(G,10);

....</pre>
RadialTreeLayout RTL;

RTL.call( GA );
<pre>

Circular Layout


wheelGraph(G,15);

....</pre>
CircularLayout CL;

CL.call( GA );
<pre>

Balloon Layout


wheelGraph(G,15);

....</pre>
BalloonLayout BL;

BL.call( GA );
<pre>

Hope this will help you to understand how work with OGDF graph layouts.

Basic Graph Examples with OGDF

Posted on March 15, 2014 by wijebandara

Introduction

I have write his article while exploring OGDF features. This will demonstrate and explain same basic graph genarators and layout contain in the OGDF.

This is the source code I am going to demonstrate below graphs.


/**
*
* @author Chameera Wijebandara
* @email chameerawijebandara@gmail.com
*
* Windows 7
* Vishual stuio 2010
* OGDF Snapshot 2014-02-28
*
*/

#include <ogdf/basic/Graph.h>
#include <ogdf/basic/graph_generators.h>
#include <ogdf/layered/DfsAcyclicSubgraph.h>
#include <ogdf/fileformats/GraphIO.h>
#include <ogdf/layered/SugiyamaLayout.h>
#include <ogdf/layered/OptimalRanking.h>
#include <ogdf/layered/MedianHeuristic.h>
#include <ogdf/layered/OptimalHierarchyLayout.h>

using namespace ogdf;

int main()
{
	Graph G;

	randomSimpleGraph(G, 10, 20); // grapth genarate.

	GraphAttributes GA( G, GraphAttributes::nodeGraphics |
		GraphAttributes::edgeGraphics |
		GraphAttributes::nodeLabel |
		GraphAttributes::nodeStyle |
		GraphAttributes::edgeType |
		GraphAttributes::edgeArrow |
		GraphAttributes::edgeStyle ); // Create graph attributes for this graph

	node v;
	forall_nodes( v, G ){ // iterate through all the node in the graph
		GA.fillColor( v ) = Color( "#FFFF00" ); // set node color to yellow

		GA.height( v ) = 20.0; // set the height to 20.0
		GA.width( v ) = 20.0; // set the width to 40.0
		GA.shape(v) = ogdf::Shape::shEllipse;

		string s = to_string(v->index());
		char const *pchar = s.c_str(); //use char const* as target type
		GA.label( v ) = pchar;
	}

	edge e;
	forall_edges(e ,G) // set default edge color and type
	{
		GA.bends(e);
		GA.arrowType(e) = ogdf::EdgeArrow::eaNone;
		GA.strokeColor(e) = Color("#0000FF");
	}

	SugiyamaLayout SL; //Compute a hierarchical drawing of G (using SugiyamaLayout)
	SL.setRanking( new OptimalRanking );
	SL.setCrossMin( new MedianHeuristic );

	OptimalHierarchyLayout *ohl = new OptimalHierarchyLayout;

	SL.setLayout( ohl );
	SL.call( GA );

	GraphIO::drawSVG( GA, "C:\\Users\\Chameera\\Desktop\\Output.svg" );

	return 0;
}
//end of the main

Complete Bipartite Graph

Creates t complete bipartite graph Kn,m.

For the demostration i have use completeBipartiteGraph with SugiyamaLayout,OptimalRanking, MedianHeuristic and OptimalHierarchyLayout.


completeBipartiteGraph( G, 8, 10 );

Complete Graph

Creates the complete graph Kn.

For the demonstration I have use completeGraph with SugiyamaLayout,OptimalRanking, MedianHeuristic and OptimalHierarchyLayout.


completeGraph( G, 4);

Cube Graph

Creates the complete graph Kn.

For the demonstration I have use cubeGraph with SugiyamaLayout,OptimalRanking, MedianHeuristic and OptimalHierarchyLayout.


cubeGraph( G, 4);

Grid Graph

Creates a (toroidal) grid graph on n x m nodes.

For the demonstration I have use gridGraph with SugiyamaLayout,OptimalRanking, MedianHeuristic and OptimalHierarchyLayout.


gridGraph (G,4,2,false,false);

Petersen Graph

Creates a generalized Petersen graph.

For the demonstration I have use petersenGraph with SugiyamaLayout,OptimalRanking, MedianHeuristic and OptimalHierarchyLayout.


petersenGraph (G,3,4);

Planar Biconnected Graph

Creates a planar biconnected (embedded) graph.


planarBiconnectedGraph (G,5,10);

Planar CNB Graph

Creates a planar graph, that is connected, but not biconnected.


planarCNBGraph (G,5,10,3);

Planar Connected Graph

Creates a connected (simple) planar (embedded) graph.


planarConnectedGraph (G,6,10);

Planar Triconnected Graph

Creates a planar triconnected (and simple) graph.

This graph generator works in two steps.

A planar triconnected 3-regular graph is constructed using successive splitting of pairs of nodes. The constructed graph has n nodes and 1.5n edges.
The remaining edges are inserted by successive splitting of faces with degree four or greater. The resulting graph also represents a combinatorial embedding.


planarTriconnectedGraph(G,6,10);

Random Biconnected Graph

Creates a random biconnected graph.


randomBiconnectedGraph(G,4,7);

Random Tree

Creates a random tree.


randomTree(G,15);

Regular Tree

Creates a regular tree.


regularTree(G,18,3);

Wheel Graph

Creates the graph W(d)n: A wheel graph.


wheelGraph(G,4);

Hope this will help you t understand how work with OGDF graph generators.

Prim’s Algorithm in Java

Posted on March 14, 2014 by wijebandara

In computer science, Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is also sometimes called the DJP algorithm, the Jarník algorithm, or the Prim–Jarník algorithm.

Find more here.

This is simple java implementation of Prim’s Algorithm.

package myclass.Graphs;

/**
 *
 * @author wijebandara
 */
public class MST_Prim
{
    private int data[][];
    private int [][] mstpdata;
    MST_Prim(int data[][])
    {
        this.data=new int [data.length][data.length];
        this.data=data;        
        this.mstpdata =new int [data.length][data.length];
    }

    private void  MST_Prim()
    {
        java.util.LinkedList<Integer> set =new java.util.LinkedList<Integer>();
        java.util.LinkedList<Edge> q =new java.util.LinkedList<Edge>();
        set.add(0);
        int hold=0;
        while(set.size()<data.length)
        {
            for(int i=0;i<data.length;i++)
            {
                if(data[hold][i]!=0)
                {
                    boolean a=true;
                    for(int j=0;j<set.size();j++)
                    {
                        if(set.get(j)==i)
                        {
                           a=false;
                           break;
                        }
                    }
                    if(a)
                    {
                        q.add(new Edge(hold,i,data[hold][i]));
                    }
                }
            }

            for(int i=q.size()-1;i>=0;i--)
            {
                for(int j=0;j<i;j++)
                {
                    if(q.get(j).weight>q.get(j+1).weight)
                    {
                        Edge ehold=new Edge();
                        ehold=q.remove(j);
                        q.add(j+1,ehold);
                    }
                }
            }
            Edge h =new Edge();
            h=q.removeFirst();
            mstpdata[h.u][h.v]=h.weight;
            hold=h.v;
            set.add(h.v);
        }
    }
    public int getcost()
    {
        int answer=0;
        MST_Prim();
        for(int i=0;i<mstpdata.length;i++)
        {
            for(int j=0;j<data[i].length;j++)
            {
                answer+=mstpdata[i][j]; 
            }
        }
        return answer;
    }
    class Edge
    {
        int weight,u,v;
        Edge(int u,int v,int weight)
        {
            this.u=u;
            this.v=v;
            this.weight=weight;
        }
        Edge(){}   
    }
}

Hope you will enjoy…!

Kruskal’s Algorithm in Java

Posted on March 14, 2014 by wijebandara

Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Find more here.

This is simple java implementation of Kruskal’s Algorithm.

package myclass.Graphs;

/**
 *
 * @author wijebandara
 */
public class MST_Kruskal
{
    private int [][] data;
    private int [][] mstkdata;
    private int [] state;
    private int [] d;
    private int [] pi;
    private char c;

    MST_Kruskal(int[][] data,char c)
    {
        this.data =new int[data.length][data.length];
        this.data=data;
        this.d=new int[data.length];
        this.pi=new int[data.length];
        this.state=new int [data.length];
        this.mstkdata =new int [data.length][data.length];
        this.c=c;
    }
    public void MST_Kruskal()
    {
        java.util.LinkedList<Edge> l =new java.util.LinkedList<Edge>();
        for(int i=0;i<data.length;i++)
        {
            for(int j=0;j<data[i].length;j++)
            {
                if(i==j || data[i][j]==0)
                {
                    continue;
                }
                l.add(new Edge(i,j,data[i][j]));                
            }
        }
        for(int i=l.size()-1;i>=0;i--)
        {
            for(int j=0;j<i;j++)
            {
                if(l.get(j).weight>l.get(j+1).weight)
                {
                    Edge hold =new Edge();
                    hold= l.remove(j);
                    l.add(j+1,hold);
                }
            }
        }
        while(l.size()!=0)
        {
            Edge hold =new Edge();
            hold = l.removeFirst();
            if(!isPathBetween(hold.u,hold.v))
            {
                mstkdata[hold.u][hold.v]=hold.weight;
                if(c!='d')
                {
                    mstkdata[hold.v][hold.u]=hold.weight;
                }

                System.out.println(hold.u+" "+hold.v+" "+hold.weight);
            }
        }
    }
    public int getcost()
    {
        int answer=0;
        MST_Kruskal();
        for(int i=0;i<mstkdata.length;i++)
        {
            for(int j=0;j<data[i].length;j++)
            {
               answer+=mstkdata[i][j]; 
            }
        }
        if(c=='d')
        {
            return answer;
        }
        else
        {
            return answer/2;
        }
    }
    private void breadthFirstSearch(int s)
    {

        java.util.LinkedList<Integer>  q=new java.util.LinkedList<Integer>();
        for(int i=0;i<mstkdata.length;i++)
        {
            state[i]=-1;
            d[i]=0;
        }
        q.add(s);
        state[s]=0;

        while(q.size()!=0)
        {
            int hold= q.removeFirst();

            for(int i=0;i<mstkdata.length;i++)
            {
                if(mstkdata[hold][i]!=0 && state[i]==-1)
                {
                    q.add(i);
                    state[i]=0;
                    d[i]=d[hold]+1;
                    pi[i]=hold;
                }
            }
            state[hold]=1;
        }
    }
    private boolean isPathBetween(int u,int v)
    {
        breadthFirstSearch(u);
        if(d[v]!=0)
        {
            return true;
        }
        return false;
    }
    class Edge
    {
        int weight,u,v;
        Edge(int u,int v,int weight)
        {
            this.u=u;
            this.v=v;
            this.weight=weight;
        }
        Edge(){}   
    }
}

Hope you will enjoy…!

Dijkstra’s algorithm in Java

Posted on March 14, 2014 by wijebandara

Dijkstra’s algorithm, conceived by computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms.Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Find more here.

This is simple java implementation of Dijkstra’s algorithm.

package myclass.Graphs;

import myclass.PrintArray;

/**
 *
 * @author Wijebandara
 */
public class DijkstrasAlgorithm
{
    private int data[][];
    private int d[];
    private int pi[];
    private boolean h[];

    public DijkstrasAlgorithm(int data[][])
    {
        this.data=new int[data.length][data.length];
        this.data=data;
        this.d=new int[data.length];
        this.pi=new int[data.length];
        h=new boolean[data.length];
    }
    public void DijkstrasAlgorithm(int s)
    {
        initialize();

        d[s]=0;
        pi[s]=0;
        h[s]=true;
        java.util.LinkedList<Node> q =new java.util.LinkedList<Node>();
        for(int i=0;i<data.length;i++)
        {
            if(data[s][i]!=0)
            {
                q.add(new Node(s,i,data[s][i]));
            }
        }       

        for(int i=0;i<data.length;i++)
        {
            if(data[s][i]!=0)
            {
                relaxation(s,i);
            }
        }

        while(q.size()!=0)
        {
            for(int i=q.size()-1;i>=0;i--)
            {
                for(int j=0;j<i;j++)
                {
                    if(q.get(j).w>q.get(j+1).w)
                    {
                        Node hold=new Node();
                        hold=q.remove(j);
                        q.add(j+1,hold);
                    }
                }
           }
            Node hold=q.removeFirst();
            for(int i=0;i<data.length;i++)
            {
                if(data[hold.v][i]!=0 && d[i]==-1)
                {
                    q.add(new Node(hold.v,i,data[hold.v][i]));
                }
            }
            for(int i=0;i<data.length;i++)
            {
                if(data[hold.v][i]!=0)
                {
                    relaxation(hold.v,i);
                }
            }
        }   
        PrintArray.printArray(d," ");
        System.out.println();
        PrintArray.printArray(pi," ");
        System.out.println();
    }

    private void initialize()
    {
        for(int i=0;i<data.length;i++)
        {
            d[i]=-1;
            pi[i]=-1;
            h[i]=false;
        }
    }

    private void relaxation(int u ,int v)
    {
        if(!h[v] || d[v]>d[u]+data[u][v])
        {
            d[v]=d[u]+data[u][v];
            pi[v]=u;
            h[v]=true;
        }
    }

    class Node
    {
        int u;
        int v;
        int w;
        Node(int u,int v,int w)
        {
            this.u=u;
            this.v=v;
            this.w=w;
        }
        Node(){}
    }
}

Hope you will enjoy…!

Depth-first search in Java

Posted on March 14, 2014 by wijebandara

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

Find more here.

This is simple java implementation of Depth-first search.

package myclass.Graphs;

/**
 *
 * @author wijebandara
 */
public class DepthFirstSearch
{
    private int [][] data;
    private int [] s;
    private int [] f;
    private int [] state;
    private int time=0;
    DepthFirstSearch(int[][] data)
    {
        this.data =new int[data.length][data.length];
        this.data=data;
        this.s=new int[data.length];
        this.f=new int[data.length];
        this.state=new int [data.length];
    }


    public void depthFirstSearch(int u)
    {
        for(int i=0;i<data.length;i++)
        {
            state[i]=-1;
        }
        time=0;
        for(int i=0;i<data.length;i++)
        {
            if(state[i]==-1)
            {
                dfs(i);
            }
        }
        

        myclass.PrintArray.printArray(s," ");
        System.out.println();
        myclass.PrintArray.printArray(f, " ");

    }
    private void dfs(int u)
    {
        time++;
        state[u]=0;
        s[u]=time;
        for(int i=0;i<data.length;i++)
        {
            if(data[u][i]!=0 && state[i]==-1)
            {
                dfs(i);
            }
        }
        state[u]=1;
        time++;
        f[u]=time;
    }
    
}

Hope you will enjoy…!

Breadth-first search in Java

Posted on March 14, 2014 by wijebandara

In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations:

Visit and inspect a node of a graph;
Gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes.

Find more here.

This is simple java implementation of Breadth-first search.

package myclass.Graphs;

import myclass.PrintArray;

/**
 *
 * @author wijebandara
 */
public class BreadthFirstSearch
{
    private int [][] data;
    private int [] d;
    private int [] pi;
    private int [] state;

    BreadthFirstSearch(int data[][])
    {
        this.data = new int[data.length][data.length];
        this.data=data;
        this.d=new int[data.length];
        this.pi=new int[data.length];
        this.state=new int [data.length];

    }
    public void breadthFirstSearch(int s)
    {

        java.util.LinkedList<Integer>  q=new java.util.LinkedList<Integer>();
        for(int i=0;i<data.length;i++)
        {
            state[i]=-1;
            d[i]=0;
        }
        q.add(s);
        state[s]=0;

        while(q.size()!=0)
        {
            int hold= q.removeFirst();

            for(int i=0;i<data.length;i++)
            {
                if(data[hold][i]!=0 && state[i]==-1)
                {
                    q.add(i);
                    state[i]=0;
                    d[i]=d[hold]+1;
                    pi[i]=hold;
                }
            }
            state[hold]=1;
        }
        PrintArray.printArray(d," ");
    }
    public boolean isPathBetween(int u,int v)
    {
        breadthFirstSearch(u);
        if(d[v]!=0)
        {
            return true;
        }
        return false;
    }

}

Hope you will enjoy…!

Bellman–Ford algorithm in Java

Posted on March 14, 2014 by wijebandara

The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

Find more here.

This is simple java implementation of Bellman–Ford algorithm.

package myclass.Graphs;

import myclass.PrintArray;

/**
 *
 * @author wijebandara
 */
public class BellmanFord 
{
    private int data[][];
    private int d[];
    private int pi[];
    private boolean h[];
    
    BellmanFord(int data[][])
    {
        this.data=new int[data.length][data.length];
        this.data=data;
        this.d=new int[data.length];
        this.pi=new int[data.length];
        h=new boolean[data.length];
        
    }
    public boolean bellmanFord(int s)
    {
        initialize();
        d[s]=0;
        pi[s]=0;
        for(int i=0;i<data.length;i++)
        {
            for(int u=0;u<data.length;u++)
            {
                for(int v=0;v<data.length;v++)
                {
                    if(data[u][v]!=0)
                    {
                        relaxation(u,v);
                    }
                }
            }
        }
        PrintArray.printArray(d," ");
        System.out.println();
        PrintArray.printArray(pi," ");
        System.out.println();
        for(int u=0;u<data.length;u++)
        {
            for(int v=0;v<data.length;v++)
            {
                if(data[u][v]!=0 && d[v]>d[u]+data[u][v])
                {
                    System.out.println(v+" "+u);
                    return false;
                }
            }
        }
        return true;
    }
    
    private void initialize()
    {
        for(int i=0;i<data.length;i++)
        {
            pi[i]=-1;
            h[i]=false;
        }
    }

    
    private void relaxation(int u ,int v)
    {
        if(!h[v] || d[v]>d[u]+data[u][v])
        {
            d[v]=d[u]+data[u][v];
            pi[v]=u;
            h[v]=true;
        }
    }

}

Hope you will enjoy…!

Build “Rock, Paper, Scissors” in java script

Posted on March 6, 2014 by wijebandara

This is very simple program developed using java scripts.

Rock paper scissors is a classic 2 player game. Each player chooses either rock, paper or scissors. The possible outcomes:

Rock destroys scissors.
Scissors cut paper.
Paper covers rock.

Our code will break the game into 3 phases:
a. User makes a choice
b. Computer makes a choice
c. A compare function will determine who wins

</pre>
var userChoice = prompt("Do you choose rock, paper or scissors?");
var computerChoice = Math.random();
if (computerChoice < 0.34) {
 computerChoice = "rock";
} else if (computerChoice <= 0.67) {
 computerChoice = "paper";
} else {
 computerChoice = "scissors";
}
console.log("Computer: " + computerChoice);

compare(userChoice, computerChoice);

var compare = function(choice1, choice2)
{
 if (choice1 === choice2)
 {
 return "The result is a tie!";
 }
 else if (choice1 === "rock")
 {
 if (choice2 === "scissors")
 {
 return "rock wins";
 }
 else
 {
 return "paper wins";
 }
 }
 else if (choice1 === "paper")
 {
 if (choice2 === "rock")
 {
 return "paper wins";
 }
 else
 {
 return "scissors wins";
 }
 }
 else
 {
 if (choice2 === "rock")
 {
 return "rock wins";
 }
 else
 {
 return "scissors wins";
 }
 }
};
<pre>

Computation of Treewidth

Basic Linear Algebra Support

Generators for Different Random Graph Models

Search Trees and Priority Queues

Share this:

Introduction

Mixed Model Layout

Planar Straight Layout

Planar Draw Layout

Planarization Grid Layout

FMMM Layout

Sugiyama Layout

Tree Layout

Radial Tree Layout

Circular Layout

Balloon Layout

Share this:

Introduction

Complete Bipartite Graph

Complete Graph

Cube Graph

Grid Graph

Petersen Graph

Planar Biconnected Graph

Planar CNB Graph

Planar Connected Graph

Planar Triconnected Graph

Random Biconnected Graph

Random Tree

Regular Tree

Wheel Graph

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this:

Share this: