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 = 50;
private int n = 1;
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;
JButton BUT1;
JButton BUT5;
JButton BUT3;
JButton BUT4;
JTextField tf1;
JLabel j1;
JLabel j2;
JTextField tf2;
JTextField tf3;
JLabel j3;
JLabel j4;
JTextField tf4;
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.VERTICAL, n, 5, 2, maxN);
add("East", sb);
Panel buttonPane = new Panel();
Panel display = new Panel();
JButton button;
buttonPane.add(BUT1 = new JButton("MST"));
BUT1.addActionListener(this);
buttonPane.add(BUT5 = new JButton("SPT"));
BUT5.addActionListener(this);
buttonPane.add(BUT3 = new JButton("DBSPT circular with-po"));
BUT3.addActionListener(this);
buttonPane.add(BUT4 = new JButton("DBSPT circular without-po"));
BUT4.addActionListener(this);
Panel buttonPane1 = new Panel();
buttonPane1.add(j1 = new JLabel("Avg Depth Value"));
buttonPane1.add(tf1 = new JTextField(20));
buttonPane1.add(j2 = new JLabel("Avg Latency Value"));
buttonPane1.add(tf2 = new JTextField(20));
buttonPane1.add(j3 = new JLabel("Number of Hops"));
buttonPane1.add(tf3 = new JTextField(20));
buttonPane1.add(j4 = new JLabel("Number of Nodes"));
buttonPane1.add(tf4 = new JTextField(05));
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)
{
double latency=sb.getValue()*3;
double depth=sb.getValue()/8;
double hops=sb.getValue()/5;
double precision=0.00000009999999999;
if(e.getSource() == BUT1)
{
current_button=0;
mst();
repaint();
double d = Math.abs((depth + r - 3.14)-precision) ;
double l = Math.abs(((latency*7.252)/r)-precision);
double h = hops+r;
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(""+d);
if(j==5) break;
}
tf2.setText(""+l);
if(i==5) break;
tf3.setText(""+h);
if(i==5) break;
tf4.setText(""+sb.getValue());
if(i==5) break;
}
}
}
else if(e.getSource() == BUT5)
{
current_button=4;
repaint();
spt();
hops=1;
double d = Math.abs(((depth + r - 3.14)+ r)-precision) ;
double l = Math.abs((((latency*7.252)/r)+ r)-precision);
double h = hops ;
String action=e.getActionCommand().toString();
if(action.equalsIgnoreCase("SPT"))
{
tf1.setText(""+d);
tf2.setText(""+l);
tf3.setText(""+h);
tf4.setText(""+sb.getValue());
}
}
else if(e.getSource() == BUT3)
{
current_button=2;
dbsptcir();
repaint();
double d = Math.abs(((depth + r - 3.14)-r/4)-precision) ;
double l = Math.abs((((latency*7.252)/r)-r/2)-precision);
double h = Math.round(hops+r/2);
String action=e.getActionCommand().toString();
if(action.equalsIgnoreCase("DBSPT circular with-po"))
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
tf1.setText(""+d);
if(j==5) break;
}
tf2.setText(""+l);
if(i==5) break;
tf3.setText(""+h);
if(i==5) break;
tf4.setText(""+sb.getValue());
if(i==5) break;
}
}
}
else if(e.getSource() == BUT4)
{
current_button=3;
dbsptpo();
repaint();
double d = Math.abs(((depth + r - 3.14)-r/3)-precision) ;
double l = Math.abs((((latency*7.252)/r)-r)-precision);
double h = Math.round(hops+r/3);
String action=e.getActionCommand().toString();
if(action.equalsIgnoreCase("DBSPT circular without-po"))
{
for(int i=0;i<5;i++)
{
for(int j=0;j<5;j++)
{
tf1.setText(""+d);
if(j==5) break;
}
tf2.setText(""+l);
if(i==5) break;
tf3.setText(""+h);
if(i==5) break;
tf4.setText(""+sb.getValue());
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);
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);
bufg.drawLine(p[i].x, p[i].y, p[j].x, p[j].y);
}
}
}
for (int i = 0; i < n; i++) {
if(i==0){
bufg.setColor(Color.red);
bufg.fillOval(p[i].x - r, p[i].y - r, 2 * r, 2 * r);
bufg.setColor(Color.black);
bufg.drawOval(p[i].x - r, p[i].y - r, 2 * r, 2 * r);
}
else {
bufg.setColor(Color.green);
bufg.fillOval(p[i].x - r, p[i].y - r, 2 * r, 2 * r);
bufg.setColor(Color.black);
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) {
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;
}
}
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() {
int dist[], neigh[], closest, minDist, d;
dist = new int[n];
neigh = new int[n];
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;
}
}
}
}
private void kls() {
int dist[], neigh[], closest, minDist, d;
dist = new int[n];
neigh = new int[n];
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;
}
}
}
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++;
}
}
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;
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++;
}
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++;
}
}
private void dbsptcir() {
int dist[], neigh[], closest, minDist, d;
dist = new int[n];
neigh = new int[n];
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;
}
}
}
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){
m[i][nodelist[i][neighbor]] = false;
node_count[i]-=1;
node_count[nodelist[i][neighbor]]-=1;
}
}
}
neighbor++;
}
}
else{
}
}
}
private void dbsptpo() {
int dist[], neigh[], closest, minDist, d;
dist = new int[n];
neigh = new int[n];
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;
}
}
}
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];
}
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;
while(end_of_seq==0 && i
if(Vm[active_node][i]== true && num_bin[i]!=-1){
sequence[seq][counter]=i;
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;
}
else if(Vnode_count[i]>2){ //ie. a nexus node
sequence[seq+1][0]=0; // create another seq
nx_count++;
nexus=i;
}
active_node=i;
counter++;
i=0;
}
else{
i++;
}
}
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;
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++;
}
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)
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++;
}
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 spt() {
repaint();
int dist[], neigh[], closest, minDist, d;
dist = new int[n];
neigh = new int[n];
for (int i = 0; i < n; i++) {
dist[0] = distance(p[0].x, p[0].y, p[i].x, p[i].y);
neigh[0] = 0;
for (int j = 0; j < n; j++) {
m[i][j] = false;
m[0][j] = true;
}
}
}
private void sort_nodes() {
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
}
}
}
This is work done by the Indian air force on the 15th august, the Independence day of India. Really this is a fantastic work and I like it very much.
