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
}
}
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
}
}
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
ends[counter]=i;
//System.out.println(" Endpoint at node:"+ i);
counter++;
}
}
num_ends=counter;
seq=0;
for(i=0; i
}
for(i=0; i
seq_info[i][1]=1000;
seq_info[i][2]=1000;
}
for(p=0; p
for(i=0; i
}
}
for(i=0; i
}
sequence[seq][0]=0;
active_node=ends[p];
while(sequence[seq][0]!=-1) {
for(i=0; 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
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
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
counter++;
}
//System.out.println("Total number of paths: " + counter);
max_path=0;
for(i=0; i
if(seq_info[max_path][2]
}
}
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[second_max_path][2]
}
}
}
//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
}
}
*/
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
ends[counter]=i;
counter++;
}
}
num_ends=counter;
seq=0;
for(i=0; i
}
for(i=0; i
seq_info[i][1]=1000;
seq_info[i][2]=1000;
}
for(p=0; p
for(i=0; i
}
}
for(i=0; 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
// 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
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
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
counter++;
}
//System.out.println("Total number of paths: " + counter);
max_path=0;
for(i=0; i
if(seq_info[max_path][2]
}
}
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[second_max_path][2]
}
}
}
if(counter>1)
for(i=0; i
}
}
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++;
}
}
}
/**/
3:47 PM
Subscribe to:
Post Comments (Atom)
0 comments:
Post a Comment