• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Graphs and identifying adjacent nodes

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi
I have an applet which has a graph that has a central node (root) from this comes 5 child nodes which also act as parents to 5 more child nodes (leafs) each. Initially I want only the root node and its immediate children visible (those attached direct to the root node). If one of these children is clicked then I want only the nodes directly connected to the clicked node (its children and the root node) to be viewable, but all other nodes to be invisible (change color to same as background). The best way I see to do this is the determine which nodes are within one edge (vertice) of the clicked node and make them visible while all other nodes (either two or more edges away from clicked node) become the same color as the background and therefore invisible. Does anyone know how to measure how many edges one node is from another node to do this. I have included my java and html code so far below.
Thanks

********************* JAVA *************************


import java.util.*;
import java.awt.*;
import java.applet.*;
import java.awt.event.*;

//create the class 'Node' and its variables x,y,dx,dy,fixed and lbl

class Node{
double x;
double y;

double dx;
double dy;

boolean fixed;
boolean hide;

String lbl;

String color;
}

//create class 'Edge' and declare its variables from, to and len

class Edge {
int from;
int to;

double len;
}

//create the class 'GraphPanel' which is a subclass of the superclass Panel//creates an interface to runnable, mouselistener etc//creates variables, arrays and calls relaxer thread?

class GraphPanel extends Panel
implements Runnable, MouseListener, MouseMotionListener {
Graph graph;

//creates an integer variable call nnodes (holds total number of nodes)
int nnodes;

//creates an array of 100 node objects called 'nodes'
Node nodes[] = new Node[100];


//creates an integer variable call nnodes (holds total number of nodes)
int nedges;

//creates an array of 200 edge objects called 'edges'
Edge edges[] = new Edge[200];

//references a thread call relaxer
Thread relaxer;

//sets mouse listener to the grap

GraphPanel(Graph graph) {
this.graph = graph;
addMouseListener(this);
}
//finds node by searching for them by name (lbl)
int findNode(String lbl) {
//scans array of nodes and returns index number or match
for (int i = 0 ; i < nnodes ; i++) {
if (nodes[i].lbl.equals(lbl)) {
return i;
}
}
//calls addNode function using lbl arguement
return addNode(lbl);
}
int addNode(String lbl) {
Node n = new Node();
//n.setColor(java.awt.Color.blue);
//Color(0, 0, 0);
n.x = 10 + 380*Math.random();
n.y = 10 + 380*Math.random();
n.lbl = lbl;
//n.hide = true;
nodes[nnodes] = n;
return nnodes++;
}
void addEdge(String from, String to, int len) {
//new edge of type Edge
Edge e = new Edge();
//use findnode method to locate endpoints by node name give in arguements
e.from = findNode(from);
e.to = findNode(to);
e.len = len;
edges[nedges++] = e;
}

public void run() {
Thread me = Thread.currentThread();
while (relaxer == me) {
relax();
//if (random && (Math.random() < 0.03)) {
if (Math.random() < 0.03) {
Node n = nodes[(int)(Math.random() * nnodes)];
if (!n.fixed) {
n.x += 100*Math.random() - 50;
n.y += 100*Math.random() - 50;
}
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
break;
}
}
}

synchronized void relax() {
for (int i = 0 ; i < nedges ; i++) {
Edge e = edges[i];
double vx = nodes[e.to].x - nodes[e.from].x;
double vy = nodes[e.to].y - nodes[e.from].y;
double len = Math.sqrt(vx * vx + vy * vy);
len = (len == 0) ? .0001 : len;
double f = (edges[i].len - len) / (len * 3);
double dx = f * vx;
double dy = f * vy;

nodes[e.to].dx += dx;
nodes[e.to].dy += dy;
nodes[e.from].dx += -dx;
nodes[e.from].dy += -dy;
}

for (int i = 0 ; i < nnodes ; i++) {
Node n1 = nodes[i];
double dx = 0;
double dy = 0;

for (int j = 0 ; j < nnodes ; j++) {
if (i == j) {
continue;
}
Node n2 = nodes[j];
double vx = n1.x - n2.x;
double vy = n1.y - n2.y;
double len = vx * vx + vy * vy;
if (len == 0) {
dx += Math.random();
dy += Math.random();
} else if (len < 100*100) {
dx += vx / len;
dy += vy / len;
}
}
double dlen = dx * dx + dy * dy;
if (dlen > 0) {
dlen = Math.sqrt(dlen) / 2;
n1.dx += dx / dlen;
n1.dy += dy / dlen;
}
}

Dimension d = getSize();
for (int i = 0 ; i < nnodes ; i++) {
Node n = nodes[i];
if (!n.fixed) {
n.x += Math.max(-5, Math.min(5, n.dx));
n.y += Math.max(-5, Math.min(5, n.dy));
}
if (n.x < 0) {
n.x = 0;
} else if (n.x > d.width) {
n.x = d.width;
}
if (n.y < 0) {
n.y = 0;
} else if (n.y > d.height) {
n.y = d.height;
}
n.dx /= 2;
n.dy /= 2;
}
repaint();
}

Node pick;
boolean pickfixed;
Image offscreen;
Dimension offscreensize;
Graphics offgraphics;

//fixedcolor sets color of central node
final Color fixedColor = Color.white;
//color of node when clicked
final Color selectColor = Color.blue;
final Color edgeColor = Color.gray;
//set color of node fill
final Color nodeColor = Color.yellow;
//final Color nodeColor = new Color(250, 220, 100); -----this line was replaced by the lien above
//new color type created to hide nodes on red background
final Color hideColor = Color.red;
//sets the colors of edges (edges change colors as they move around) - next 3 lines
final Color arcColor1 = Color.yellow;
final Color arcColor2 = Color.green;
final Color arcColor3 = Color.black;


//paintnode method gives color and appearance to each nodes
public void paintNodeorg(Graphics g, Node n, FontMetrics fm) {
int x = (int)n.x;
int y = (int)n.y;
//sets color for rectangle fill dependent on whether node is fixed or not
g.setColor((n == pick) ? selectColor : (n.fixed ? fixedColor : (n.hide ? hideColor : nodeColor)));
//g.setColor((n == pick) ? selectColor : (n.fixed ? fixedColor : nodeColor));-------this line was replaced by above
//length of box of node
int w = fm.stringWidth(n.lbl) + 10;
//height of nodes
int h = fm.getHeight() + 4;
//location of rectangle fill - offset
g.fillRect(x - w/2, y - h / 2, w, h);
//changes color of text in nodes and node outline
g.setColor(Color.red);
//offset of text and rectangle fill
g.drawRect(x - w/2, y - h / 2, w-1, h-1);
//offset of text only
g.drawString(n.lbl, x - (w-10)/2, (y - (h-4)/2) + fm.getAscent());
}

public void paintNode(Graphics g, Node n, FontMetrics fm) {
int x = (int)n.x;
int y = (int)n.y;
//sets color for rectangle fill dependent on whether node is fixed or not
g.setColor(Color.green);
//g.setColor((n == pick) ? selectColor : (n.fixed ? fixedColor : nodeColor));-------this line was replaced by above
//length of box of node
int w = fm.stringWidth(n.lbl) + 10;
//height of nodes
int h = fm.getHeight() + 4;
//location of rectangle fill - offset
g.fillRect(x - w/2, y - h / 2, w, h);
//changes color of text in nodes and node outline
g.setColor(Color.red);
//offset of text and rectangle fill
g.drawRect(x - w/2, y - h / 2, w-1, h-1);
//offset of text only
g.drawString(n.lbl, x - (w-10)/2, (y - (h-4)/2) + fm.getAscent());
}

public synchronized void update(Graphics g) {
Dimension d = getSize();
if ((offscreen == null) || (d.width != offscreensize.width) || (d.height != offscreensize.height)) {
offscreen = createImage(d.width, d.height);
offscreensize = d;
if (offgraphics != null) {
offgraphics.dispose();
}
offgraphics = offscreen.getGraphics();
offgraphics.setFont(getFont());
}


offgraphics.setColor(getBackground());
offgraphics.fillRect(0, 0, d.width, d.height);
for (int i = 0 ; i < nedges ; i++) {
Edge e = edges[i];
int x1 = (int)nodes[e.from].x;
int y1 = (int)nodes[e.from].y;
int x2 = (int)nodes[e.to].x;
int y2 = (int)nodes[e.to].y;
int len = (int)Math.abs(Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) - e.len);
//sets edge color dependent on length of edge at any point
offgraphics.setColor((len < 10) ? arcColor1 : (len < 20 ? arcColor2 : arcColor3)) ;
offgraphics.drawLine(x1, y1, x2, y2);
}

FontMetrics fm = offgraphics.getFontMetrics();
for (int i = 0 ; i < nnodes ; i++) {
paintNode(offgraphics, nodes[i], fm);
}
g.drawImage(offscreen, 0, 0, null);
}

//1.1 event handling
public void mouseClicked(MouseEvent e) {
}

public void mousePressed(MouseEvent e) {
addMouseMotionListener(this);
double bestdist = Double.MAX_VALUE;
int x = e.getX();
int y = e.getY();
for (int i = 0 ; i < nnodes ; i++) {
Node n = nodes[i];
double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y);
if (dist < bestdist) {
pick = n;
bestdist = dist;
}
}
pickfixed = pick.fixed;
pick.fixed = true;
pick.x = x;
pick.y = y;
repaint();
e.consume();
}

public void mouseReleased(MouseEvent e) {
removeMouseMotionListener(this);
if (pick != null) {
pick.x = e.getX();
pick.y = e.getY();
pick.fixed = pickfixed;
pick = null;
}
repaint();
e.consume();
}

public void mouseEntered(MouseEvent e) {
}

public void mouseExited(MouseEvent e) {
}

public void mouseDragged(MouseEvent e) {
pick.x = e.getX();
pick.y = e.getY();
repaint();
e.consume();
}

public void mouseMoved(MouseEvent e) {
}

public void start() {
relaxer = new Thread(this);
relaxer.start();
}

public void stop() {
relaxer = null;
}

}

public class Graph extends Applet implements ActionListener, ItemListener {

GraphPanel panel;
Panel controlPanel;

public void init() {
setLayout(new BorderLayout());

//creates applet panel
panel = new GraphPanel(this);
add("Center", panel);
controlPanel = new Panel();
setBackground(Color.red);

//imports data from html params tags
String edges = getParameter("edges");

// uses stringtokenizer to create token t by splitting edges param by , delimter and then testing of param still has more tokens to continue with
for (StringTokenizer t = new StringTokenizer(edges, ",") ; t.hasMoreTokens() ; ) {
//places value of next tohen into str eg str = The_World-Europe/90
String str = t.nextToken();
//places index number (location) of - into variable i (0=first index)
int i = str.indexOf('-');
//if - exists any except first postion
if (i > 0) {
//len = 50
int len = 50;
//places index number of / into variable j (0 = first index)
int j = str.indexOf('/');
//if / exists anywhere except first position (0)
if (j > 0) {
//len gets value given after / in params from webpage
len = Integer.valueOf(str.substring(j+1)).intValue();
//str gets the value of the section of str between 0 and location of /
//so therefore str = North_America-New York for example
str = str.substring(0, j);
}
//calls addedge (above) method from panel class with the arguements that
//identify what element of string to use (String from, String to, int len)
panel.addEdge(str.substring(0,i), str.substring(i+1), len);
}
}
//get size of applet panel and put variable 'd'
Dimension d = getSize();
//gets value of centre from html parameters
String center = getParameter("center");
if (center != null){
Node n = panel.nodes[panel.findNode(center)];
//sets location of centre node as half width and half height of panel
n.x = d.width / 2;
n.y = d.height / 2;
n.fixed = true;
}
}

public void destroy() {
remove(panel);
remove(controlPanel);
}

public void start() {
panel.start();

}

public void stop() {
panel.stop();
}

public void actionPerformed(ActionEvent e) {
Object src = e.getSource();
}

public void itemStateChanged(ItemEvent e) {
Object src = e.getSource();
boolean on = e.getStateChange() == ItemEvent.SELECTED;
}

//collect data from html parameters and place into nested array info[][]

public String[][] getParameterInfo() {
String[][] info = {
//parameter name, kind of value, description
{"edges", "delimited string", "A comma-delimited list of all the edges. It takes the form of 'C-N1,C-N2,C-N3,C-NX,N1-N2/M12,N2-N3/M23,N3-NX/M3X,...' where C is the name of center node (see 'center' parameter) and NX is a node attached to the center node. For the edges connecting nodes to eachother (and not to the center node) you may (optionally) specify a length MXY separated from the edge name by a forward slash."},
{"center", "string", "The name of the center node."}
};
return info;
}

}

**************END JAVA*******************



**************HTML*********************
<html>
<head>
<title>The World</title>
</head>
<body bgcolor=red>
<object codebase="." code="Graph.class" width=400 height=400>
<param name=edges value="The_World-Europe/90,
Europe-Moscow/40,
Europe-Paris/40,
Europe-London/40,
Europe-Rome/40,
The_World-Asia/90,
Asia-New Delhi/40,
Asia-Beijing/40,
Asia-Jakarta/40,
Asia-Manila/40,
Asia-Hong Kong/40,
Asia-Tokyo/40,
The_World-North_America/90,
North_America-Los Angeles/40,
North_America-Chicago/40,
North_America-New York/40,
North_America-San Francisco/40,
North_America-Honolulu/40,
North_America-Washington/40,
The_World-South_America/90,
South_America-Lima/40,
South_America-Santiago/40,
South_America-Rio De Janeiro/40,
The_World-Africa/90,
Africa-Cairo/40,
Africa-Capetown/40,
Africa-Cape Town/40,
The_World-Australasia/90,
Australasia-Sydney/40,
Australasia-Melbourne/40,
Australasia-Perth/40,
Australasia-Auckland/40">
<param name=center value="The_World">
alt="Your browser probably doesn't understand the <OBJECT> tag so it isn't running the applet or perhaps you need a Java Plugin"
Your browser is completely ignoring the <OBJECT> tag!
</object>
<hr>
</body>
</html>
 
Ranch Hand
Posts: 1535
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
This will hide/show the child nodes of any parent node you select with a mousePress.
I got tired of the browser/plug–in caching and set it up with a main method so I could run it from the prompt. You might consider changing the class names and running it as–is to see what it does.

[ November 20, 2004: Message edited by: Craig Wood ]
 
Don't get me started about those stupid light bulbs.
reply
    Bookmark Topic Watch Topic
  • New Topic