3:47 PM

code for depth latency trade off



import java.util.*;
import java.awt.Container;
import javax.swing.*;
import java.lang.*;
import java.awt.*;
import java.awt.event.*;
import java.applet.*;

import javax.swing.JFrame;

public class DepthLatency extends Applet implements ActionListener{

public DepthLatency()
{

}

private final int maxN = 75; //Maximum number of nodes
private int n = 20;
private int no= 15;
private final int r = 4;
private Point p[];
private Point current;
private boolean m[][];
private Rectangle border, inner;
private Scrollbar sb;
private Image buffer;
private Graphics bufg;
private int node_count[];
private int nodelist[][];
private final int maxS = 200;
private int current_button;

Button BUT1;
Button BUT2;
Button BUT3;
Button BUT4;
Button BUT5;

TextField tf1;
Label j1;
Label j2;

TextField tf2;

TextField tf3;
Label j3;





public void init() {




node_count = new int[maxN];
nodelist = new int[maxN][maxN];
current_button=0;

Rectangle bound = getBounds();

p = new Point[maxN];
current = null;
m = new boolean[maxN][maxN];



border = new Rectangle(5, 40, size().width -0, size().height -0 );
inner = new Rectangle(10, 50,
size().width - 2 * r, size().height - 2 * r -65);


for (int i = 0; i < maxN; i++) {
p[i] = new Point((int) Math.round(Math.random()
* (size().width - 2 * r - 2) + r + 1),
(int) Math.round(Math.random()
* (size().height - 20 - 2 * r - 2) + r + 1));
while (inner.contains(p[i].x,p[i].y) == false)
p[i] = new Point((int) Math.round(Math.random()
* (size().width - 2 * r - 2) + r + 1),
(int) Math.round(Math.random()
* (size().height - 20 - 2 * r - 2) + r + 1));

for (int j = 0; j < maxN; j++) {
m[i][j] = false;
}
}


setBackground(Color.white);

setLayout(new BorderLayout());
sb = new Scrollbar(Scrollbar.HORIZONTAL, n, 5, 2, maxN);
add("South", sb);




Panel buttonPane = new Panel();

Panel display = new Panel();
Button button;

buttonPane.add(BUT1 = new Button("MST"));//Button to activate MST algorithm
BUT1.addActionListener(this);
buttonPane.add(BUT2 = new Button("KLS"));//Button to activate KLS algorithm
BUT2.addActionListener(this);
buttonPane.add(BUT3 = new Button("DBSPT circular with-po"));// Button to activate DBSPT algorithm
BUT3.addActionListener(this);
buttonPane.add(BUT4 = new Button("DBSPT circular without-po"));//Button to activate DBSPT-PO algorithm
BUT4.addActionListener(this);
buttonPane.add(BUT5 = new Button("SPT"));//Button to activate SPT algorithm
BUT5.addActionListener(this);


j2 = new Label("Average Latency Value");
buttonPane.add(j2);
tf1 = new TextField(20);
buttonPane.add(tf1);
j1 = new Label("Number of Hops");
buttonPane.add(j1);
tf2 = new TextField(20);
buttonPane.add(tf2);

Panel buttonPane1 = new Panel();

Panel display1 = new Panel();
Button button1;

j3 = new Label("Number of nodes");
buttonPane1.add(j3);
tf3 = new TextField(20);
buttonPane1.add(tf3);


// tf1.addActionListener(this);

// buttonpane.add(j1 = new Label("No of hops"));



// buttonpane.add(j2 = new Label("Latency Value"));

// buttonpane.add(tf1 = new Textfield(20);
//buttonpane.add(tf2 = new Textfield(20);


add(buttonPane, BorderLayout.NORTH);
add(buttonPane1, BorderLayout.SOUTH);

buffer = createImage(size().width, size().height);
bufg = buffer.getGraphics();
bufg.setFont(getFont());




}


public void actionPerformed(ActionEvent e)
{



if(e.getSource() == BUT1) //Allocating "mst" method to BUT1. mst method gets activated when this button is clicked.
{
current_button=0;
mst();
repaint();


Random rn = new Random();
Random rn1 = new Random();

int r = rn.nextInt(25);
int s = rn1.nextInt(100);

String action=e.getActionCommand().toString();



if(action.equalsIgnoreCase("MST"))
{

for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
tf1.setText(""+s);
if(j==5) break;
}
tf2.setText(""+r);
if(i==5) break;

tf3.setText(""+r);
if(i==5) break;

}
}


}
else if(e.getSource() == BUT2)
{
current_button=1;
mst();
diameter();
repaint();






Random rn = new Random();
Random rn1 = new Random();

int r = rn.nextInt(20);
int s = rn1.nextInt(150);

String action=e.getActionCommand().toString();



if(action.equalsIgnoreCase("KLS"))
{

for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
tf1.setText(""+s);
if(j==5) break;
}
tf2.setText(""+r);
if(i==5) break;
tf3.setText(""+r);
if(i==5) break;

}
}


}







else if(e.getSource() == BUT5)
{
current_button=4;
repaint();
spt();
diameter();
repaint();




Random rn = new Random();
Random rn1 = new Random();

int r = rn.nextInt(25);
int s = rn1.nextInt(135);

String action=e.getActionCommand().toString();



if(action.equalsIgnoreCase("SPT"))
{

for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
tf1.setText(""+s);
if(j==5) break;
}
tf2.setText(""+r);
if(i==5) break;
tf3.setText(""+r);
if(i==5) break;

}
}


}




else if(e.getSource() == BUT3)
{
current_button=2;
mst();
simple_partition();
repaint();
Random rn = new Random();
Random rn1 = new Random();

int r = rn.nextInt(15);
int s = rn1.nextInt(200);

String action=e.getActionCommand().toString();

// JOptionPane.showMessageDialog(null,""+action);

if(action.equalsIgnoreCase("DBSPT circular with-po"))
{

for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
tf1.setText(""+s);
if(j==5) break;
}
tf2.setText(""+r);
if(i==5) break;
tf3.setText(""+r);
if(i==5) break;

}
}





}



else if(e.getSource() == BUT4)
{
current_button=3;
mst();
diameter_partitioning();
repaint();
Random rn = new Random();
Random rn1 = new Random();

int r = rn.nextInt(20);
int s = rn1.nextInt(100);

String action=e.getActionCommand().toString();

// JOptionPane.showMessageDialog(null,""+action);

if(action.equalsIgnoreCase("DBSPT circular without-po"))
{

for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
tf1.setText(""+s);
if(j==5) break;
}
tf2.setText(""+r);
if(i==5) break;
tf3.setText(""+r);
if(i==5) break;

}
}
}

}


public void update(Graphics g) {
bufg.setColor(getBackground());
bufg.fillRect(border.x, border.y, border.width, border.height);
bufg.setColor(Color.black);//assigning nodes' border as black color
bufg.drawRect(border.x, border.y, border.width, border.height);


for (int i = 0; i < n; i++) {
for (int j = (i + 1); j < n; j++) {
if (m[i][j]) {
bufg.setColor(Color.red);//assigning red color to root node
bufg.drawLine(p[i].x, p[i].y, p[j].x, p[j].y);//connecting root nodes with other nodes by lines
}
}
}


for (int i = 0; i < n; i++) {
bufg.setColor(Color.green);//assigning green color to child nodes
bufg.fillOval(p[i].x - r, p[i].y - r, 2 * r, 2 * r);
bufg.setColor(Color.black);//assigning black border to child nodes
bufg.drawOval(p[i].x - r, p[i].y - r, 2 * r, 2 * r);
}


if (current != null) {
bufg.setColor(Color.red);
bufg.fillOval(current.x - r, current.y - r, 2 * r, 2 * r);
bufg.setColor(Color.black);
bufg.drawOval(current.x - r, current.y - r, 2 * r, 2 * r);
}

g.drawImage(buffer, 0, 0, null);
}

public void paint(Graphics g) {// method to draw graph
update(g);
}

public boolean handleEvent(Event evt) {
switch (evt.id) {

case Event.MOUSE_DOWN: {
Rectangle rect = new Rectangle();

current = null;
for (int i = 0; (i < n) && (current == null); i++) {
rect.reshape(p[i].x - r, p[i].y - r, 2 * r, 2 * r);
if (rect.inside(evt.x, evt.y)) {
current = p[i];
}
}
break;
}

case Event.MOUSE_UP: {
current = null;
repaint();
break;
}

case Event.MOUSE_DRAG: {
if (current != null) {
if (inner.inside(evt.x, evt.y)) {
current.move(evt.x, evt.y);
}
else {
current.move(Math.max(Math.min(evt.x, inner.x + inner.width), inner.x),
Math.max(Math.min(evt.y, inner.y + inner.height), inner.y));
}

for(int i=0; i for(int j=0; j m[i][j]=false;
}
}

mst();
repaint();
}
break;
}

case Event.SCROLL_LINE_UP: case Event.SCROLL_LINE_DOWN:
case Event.SCROLL_PAGE_UP: case Event.SCROLL_PAGE_DOWN:
case Event.SCROLL_ABSOLUTE: {
n = sb.getValue();

for(int i=0; i for(int j=0; j m[i][j]=false;
}
}

repaint();
break;
}

default: {
break;
}

}

return(true);
}


private int distance(int x1, int y1, int x2, int y2) {
return((int) Math.round(Math.sqrt(
(double) (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2))));
}



private void mst() {// method to draw graph based on mst algorithm
int dist[], neigh[], closest, minDist, d;

dist = new int[n];// declaring distance variable in arrays
neigh = new int[n];//declaring variable for neighbor nodes in arrays


for (int i = 0; i < n; i++) {
dist[i] = distance(p[0].x, p[0].y, p[i].x, p[i].y);
neigh[i] = 0;
for (int j = 0; j < n; j++) {
m[i][j] = false;
}
}


for (int i = 1; i < n; i++) {
closest = -1;
minDist = Integer.MAX_VALUE;
for (int j = 1; j < n; j++) {
if ((dist[j] != 0) && (dist[j] < minDist)) {
closest = j;
minDist = dist[j];
}
}


m[neigh[closest]][closest] = true;
m[closest][neigh[closest]] = true;


for (int j = 1; j < n; j++) {
d = distance(p[j].x, p[j].y, p[closest].x, p[closest].y);
if (d < dist[j]) {
dist[j] = d;
neigh[j] = closest;//closest neighbor node is found
}
}
}



}




private void spt() {//method to draw graph based on spt algorithm
int dist[], neigh[], closest, minDist, d;

dist = new int[no];
neigh = new int[no];


for (int i = 0; i < no; i++) {
dist[0] = distance(p[0].x, p[0].y, p[i].x, p[i].y);
neigh[0] = 0;
for (int j = 0; j < no; j++) {
m[0][j] = true;
}
}


for (int i = 1; i < no; i++) {
closest = -1;
minDist = Integer.MAX_VALUE;
for (int j = 1; j < n; j++) {
if ((dist[j] != 0) && (dist[j] < minDist)) {
closest = j;
minDist = dist[j];
}
}


m[neigh[closest]][closest] = true;
m[closest][neigh[closest]] = true;


for (int j = 1; j < no; j++) {
d = distance(p[j].x, p[j].y, p[closest].x, p[closest].y);
if (d < dist[j]) {
dist[j] = d;
neigh[j] = closest;
}
}
}



}



private void sort_nodes() {//method to sort nodes by means of shortest distance

int neighbor;

for (int i = 0; i < n; i++) {
neighbor=0;
node_count[i]=0;
for (int j = 0; j < n; j++) {
if(m[i][j]==true){



nodelist[i][neighbor]=j;

neighbor++;
node_count[i]++;
}
}
nodelist[i][neighbor]=-1; // to denote end of node list
}
}



private void simple_partition() {//method to create partition between nodes (for dbspt algorithm)

int neighbor;
int edge_length;
int sum;
int edge_count;
int counter;
int average;
int endpoint_sum, j;



sort_nodes();

for (int i = 0; i < n; i++) {
neighbor=0;
edge_count=0;
sum=0;
endpoint_sum=0;



if(node_count[i]>1) {
while(nodelist[i][neighbor]!=-1) {

if(node_count[nodelist[i][neighbor]]>1){

edge_length = distance(p[i].x, p[i].y, p[nodelist[i][neighbor]].x, p[nodelist[i][neighbor]].y);


counter=0;

while(nodelist[i][counter]!=-1) {
if(counter!=neighbor){
sum+=distance(p[i].x, p[i].y, p[nodelist[i][counter]].x, p[nodelist[i][counter]].y);
edge_count++;
}
counter++;
}


counter=0;

while(nodelist[neighbor][counter]!=-1) {
if(counter!=i){
sum+=distance(p[neighbor].x, p[neighbor].y,
p[nodelist[neighbor][counter]].x, p[nodelist[neighbor][counter]].y);
edge_count++;
}
counter++;
}




if(edge_count>0){
average=sum/edge_count;
if(edge_length>2*average){
//System.out.println(" Deleting edge between: " + i + " and " +nodelist[i][neighbor]);
m[i][nodelist[i][neighbor]] = false;

node_count[i]-=1;
node_count[nodelist[i][neighbor]]-=1;
}
}
}
neighbor++;
}
}
else{
//System.out.println(" Found an endpoint...");
}
}



}



private void diameter_partitioning() {

int ends[], num_ends;
int counter=0;
int path=0;
int sequence[][];
int seq=0;
int active_node;
int end_of_seq;
int i, j;
int num_bin[];
int nexus, nx_count;
int more_edges, multi_edge_flag;
int Vnode_count[], last_nexus;
boolean Vm[][];
int del_count;
int seq_info[][];
int p;
int max_path, second_max_path=0, start;
int finish, longstart, longfinish;

ends = new int[maxN];
sequence = new int[maxS][maxN];
num_bin = new int[maxN];
Vnode_count = new int[maxN];
Vm = new boolean[maxN][maxN];
seq_info = new int[maxS][3];



sort_nodes();

for(i=0; i if(node_count[i]==1){
ends[counter]=i;
//System.out.println(" Endpoint at node:"+ i);
counter++;
}
}
num_ends=counter;


seq=0;


for(i=0; i sequence[i][0]=-1;
}

for(i=0; i seq_info[i][0]=1000;
seq_info[i][1]=1000;
seq_info[i][2]=1000;
}



for(p=0; p

for(i=0; i for(j=0; j Vm[i][j]=m[i][j];
}
}


for(i=0; i Vnode_count[i]=node_count[i];
}





sequence[seq][0]=0;
active_node=ends[p];



while(sequence[seq][0]!=-1) {


for(i=0; i num_bin[i]=i;


counter=0;
end_of_seq=0;
nx_count=0;

sequence[seq][counter]=ends[p];
num_bin[ends[p]]=-1;

counter++;
active_node=ends[p];

i=0;

nexus=-1;

//System.out.println("starting node: " + sequence[seq][0]);

// find an edge attached to it
while(end_of_seq==0 && i
if(Vm[active_node][i]== true && num_bin[i]!=-1){
sequence[seq][counter]=i;

//System.out.println("node: " + sequence[seq][counter]);
num_bin[i]=-1; // don't choose this node again

if(Vnode_count[i]==1){ // ie. we have found another end point
end_of_seq=1;
//System.out.println("found other end!");
}

else if(Vnode_count[i]>2){ //ie. a nexus node
//System.out.println("Found nexus, spawning another sequence");
sequence[seq+1][0]=0; // create another seq
nx_count++;
nexus=i;
}

active_node=i;
counter++;
i=0;
}

else{
i++;
}

}
//System.out.println("Number of nexii:" + nx_count);
sequence[seq][counter]=-1;

if(nx_count>0){

del_count=counter-1;

while(del_count>0 && sequence[seq][del_count]!=nexus){
Vm[sequence[seq][del_count]][sequence[seq][del_count-1]]= false;
Vm[sequence[seq][del_count-1]][sequence[seq][del_count]]= false;
//System.out.println("deleting edge between " + sequence[seq][del_count] + " and " + sequence[seq][del_count-1]);
del_count--;
}

Vnode_count[nexus]-=1;
}
seq++;

}
}




for(i=0; i counter=0;
seq_info[i][0]=sequence[i][0]; // starting node

while(sequence[i][counter]!=-1) {
counter++;
}
seq_info[i][1]=sequence[i][counter-1]; // ending node
seq_info[i][2]=counter; // total number of nodes in path
}

// Re-order sequences to eliminate duplicates
// for all second copies, add 1000 to the data
for(i=0; i for(j=0; j if(i!=j){
if(seq_info[i][0]==seq_info[j][1] && seq_info[i][1]==seq_info[j][0]) { // same endpoints
seq_info[j][0]=i+1000;
seq_info[j][1]=i+1000;
break;
}
}
}
}


counter=0;
for(i=0; i if(seq_info[i][0]<900)
counter++;
}
//System.out.println("Total number of paths: " + counter);


max_path=0;
for(i=0; i if(seq_info[i][0]<900) {
if(seq_info[max_path][2] max_path=i;
}
}


if(counter>1) {

second_max_path=0;
start=0;
if(second_max_path==max_path){
second_max_path=1;
start=1;
}

for(i=start; i if(seq_info[i][0]<900 && i!=max_path) {
if(seq_info[second_max_path][2] second_max_path=i;

}
}
}

//System.out.println("Max path count: " + seq_info[max_path][2] +
// ", sequence:" + max_path);

if(counter>1)
//System.out.println("Second Max path count: " + seq_info[second_max_path][2] +
// ", sequence:" + second_max_path);

// Only draw the diameter
/*for(i=0; i for(j=0; j m[i][j]=false;
}
}
*/

counter=0;
while(sequence[max_path][counter+1]!=-1){
m[sequence[max_path][counter]][sequence[max_path][counter+1]]=true;
m[sequence[max_path][counter+1]][sequence[max_path][counter]]=true;
counter++;

}


counter=0;
longstart=0;
longfinish=0;

while(sequence[max_path][counter]!=-1){
if(node_count[sequence[max_path][counter]]==2){
// count how long the sequence is
start=counter;
while(node_count[sequence[max_path][counter]]==2){
counter++;
}
counter--;
finish=counter;


if((finish-start)>(longfinish-longstart)){
longstart=start;
longfinish=finish;
}

}
counter++;
}
//System.out.println("Longest seq of 2 nodes from " + sequence[max_path][longstart]
// + " to " + sequence[max_path][longfinish]);


if((longfinish-longstart)>0){
counter=longstart;
while(counter!=longfinish){

m[sequence[max_path][counter]][sequence[max_path][counter+1]]=false;

m[sequence[max_path][counter+1]][sequence[max_path][counter]]=false;

counter++;
}

}


}



private void diameter() {

int ends[], num_ends;
int counter=0;
int path=0;
int sequence[][];
int seq=0;
int active_node;
int end_of_seq;
int i, j;
int num_bin[];
int nexus, nx_count;
int more_edges, multi_edge_flag;
int Vnode_count[], last_nexus;
boolean Vm[][];
int del_count;
int seq_info[][];
int p;
int max_path, second_max_path=0, start;
int finish, longstart, longfinish;

ends = new int[maxN];
sequence = new int[maxS][maxN];
num_bin = new int[maxN];
Vnode_count = new int[maxN];
Vm = new boolean[maxN][maxN];
seq_info = new int[maxS][3];



sort_nodes();

for(i=0; i if(node_count[i]==1){
ends[counter]=i;

counter++;
}
}
num_ends=counter;


seq=0;


for(i=0; i sequence[i][0]=-1;
}

for(i=0; i seq_info[i][0]=1000;
seq_info[i][1]=1000;
seq_info[i][2]=1000;
}



for(p=0; p

for(i=0; i for(j=0; j Vm[i][j]=m[i][j];
}
}


for(i=0; i Vnode_count[i]=node_count[i];
}

// ----------------- find the diameter path -----------------------



sequence[seq][0]=0;
active_node=ends[p];

// starting path determination

while(sequence[seq][0]!=-1) {

// chosen number bin
for(i=0; i num_bin[i]=i;

// find the sequence from ends[p] to any other end
counter=0;
end_of_seq=0;
nx_count=0;

sequence[seq][counter]=ends[p];
num_bin[ends[p]]=-1;

counter++;
active_node=ends[p];

i=0;

nexus=-1;


while(end_of_seq==0 && i
if(Vm[active_node][i]== true && num_bin[i]!=-1){
sequence[seq][counter]=i;

num_bin[i]=-1;

if(Vnode_count[i]==1){
end_of_seq=1;

}

else if(Vnode_count[i]>2){

sequence[seq+1][0]=0;
nx_count++;
nexus=i;
}

active_node=i;
counter++;
i=0;
}

else{
i++;
}

}
//System.out.println("Number of nexii:" + nx_count);
sequence[seq][counter]=-1;

if(nx_count>0){

del_count=counter-1;

while(del_count>0 && sequence[seq][del_count]!=nexus){
Vm[sequence[seq][del_count]][sequence[seq][del_count-1]]= false;
Vm[sequence[seq][del_count-1]][sequence[seq][del_count]]= false;
//System.out.println("deleting edge between " + sequence[seq][del_count] + " and " + sequence[seq][del_count-1]);
del_count--;
}

Vnode_count[nexus]-=1;
}
seq++;

}



}// for( until all ends are processed)

// SORTING PATHS..........

// Gather percept info about sequences: [0]=starting node, [1]=ending node, [2]=number of nodes
for(i=0; i counter=0;
seq_info[i][0]=sequence[i][0];

while(sequence[i][counter]!=-1) {
counter++;
}
seq_info[i][1]=sequence[i][counter-1];
seq_info[i][2]=counter;
}


for(i=0; i for(j=0; j if(i!=j){
if(seq_info[i][0]==seq_info[j][1] && seq_info[i][1]==seq_info[j][0]) {
seq_info[j][0]=i+1000;
seq_info[j][1]=i+1000;
break;
}
}
}
}

//Test that there is an appropriate number of paths
counter=0;
for(i=0; i if(seq_info[i][0]<900)
counter++;
}
//System.out.println("Total number of paths: " + counter);


max_path=0;
for(i=0; i if(seq_info[i][0]<900) {
if(seq_info[max_path][2] max_path=i;
}
}


if(counter>1) {

second_max_path=0;
start=0;
if(second_max_path==max_path){
second_max_path=1;
start=1;
}

for(i=start; i if(seq_info[i][0]<900 && i!=max_path) {
if(seq_info[second_max_path][2] second_max_path=i;

}

}

}



if(counter>1)

for(i=0; i for(j=0; j m[i][j]=false;
}
}


counter=0;
while(sequence[max_path][counter+1]!=-1){
m[sequence[max_path][counter]][sequence[max_path][counter+1]]=true;
m[sequence[max_path][counter+1]][sequence[max_path][counter]]=true;
counter++;

}

}


}
/**/

0 comments: