Graphs and identifying adjacent nodes

V

vee dub

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.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;
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.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;
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;
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;
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, 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;
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 &lt;OBJECT&gt; tag
so it isn't running the applet or perhaps you need a Java Plugin"
Your browser is completely ignoring the &lt;OBJECT&gt; tag!
</object>
<hr>
</body>
</html>
 
C

Chris Smith

vee dub said:
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.

Measuring the number of edges of distance is more difficult than merely
finding adjacent nodes. That is, a distance of one edge is much easier
to identify than a longer distance. Given your data structures, finding
adjacent nodes should be done with a simple loop through your array of
edges. There is no better way.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
 
T

Thomas Weidenfeller

vee said:
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.

If you really want to have the distance, I guess a variant of the
typical breadth-search algorithms (Google for it) for graphs should do.
But from your description you want something simpler: All direct
neighbors of some node. With your data structure, a brute force-search
over all edges should reveal this. Pseudo-code:

for all Edges {
if(edge.from == center)
edge.to is a neighbor
else if(edge.to == center)
edge.from is a neighbor

}

But I would consider changing the data structure (if possible), and
right from the beginning provide each node with a list of its five
neighbors. This costs some memory, but buys some CPU cycles.

I didn't look at your code in great detail (fare to much for a quick
check), but you maybe want to work a little bit on the object-oriented
design of the program, too.

/Thomas
 
V

vee dub

Measuring the number of edges of distance is more difficult than merely
finding adjacent nodes. That is, a distance of one edge is much easier
to identify than a longer distance. Given your data structures, finding
adjacent nodes should be done with a simple loop through your array of
edges. There is no better way.

Thanks for your input, what condition should I be testing for when I
do this loop to check if another node is adjacent or not.
Thanks
 
C

Chris Smith

vee dub said:
Thanks for your input, what condition should I be testing for when I
do this loop to check if another node is adjacent or not.

Thomas pretty much gave you exact source code in his response.

--
www.designacourse.com
The Easiest Way To Train Anyone... Anywhere.

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top