MATEMATIKA DISKRIT
5.17
Graf
dalam gambar 5P.5 menunjukkan saluran-saluran komunikasi dan tertahannya waktu
komunikasi di dalam saluran di antara delapan pusat komunikasi. Pusat
komunikasi dipresentasikan oleh verteks, saluran dipresentasikan oleh rusuk,
dan tertahannya waktu komunikasi ( dalam menit ) dalam setiap saluran
dipresentasikan oleh pembobot rusuk bersangkutan. Misalkan bahwa pada jam
15.00, pusat komunikasi a memancarkan ke semua salurannya berita bahwa
seseorang telah menemukan cara untuk membuat perangkap tikus yang lebih baik.
Pusat-pusat komunikasi lainnya segera menyebarluaskan berita ini ke semua
salurannya begitu mereka menerimanya. Untuk pusat-pusat komunikasi b, c, d, e,
f, g, dan h, tentukan kapan pertama kali mereka menerima berita ini ?
 |
Gambar
5P.5
Jawab :
 |
Lintasannya adalah a ke b = 3
Jadi : Pusat komunikasi b menerima berita pertama kali pada pukul 15.03
 |
Lintasannya adalah a,b,c = 3 + 1 = 4
Jadi : Pusat komunikasi c menerima berita pertama kali pada pukul 15.04
 |
Lintasannya adalah a,b,f,d = 3 + 1 +
1 = 5
Jadi : Pusat komunikasi d menerima berita pertama kali pada pukul 15.05
 |
Lintasannya adalah a,b,f,e = 3 + 1
+ 2
= 6
Jadi : Pusat komunikasi e menerima berita pertama kali pada pukul 15.06
 |
Lintasannya adalah a,b,f = 3 + 1 = 4
Jadi : Pusat komunikasi f menerima berita pertama kali pada pukul 15.04
 |
Lintasannya adalah a,b,f,d,g = 3 + 1
+ 1 + 2 = 7
Jadi : Pusat komunikasi g menerima berita pertama kali pada pukul 15.07
 |
Lintasannya adalah a,b,f,g ,h = 3 +
1 + 4 + 1 = 9
Jadi : Pusat komunikasi h menerima berita pertama kali pada pukul 15.09
5.18
|
 |
Jawab :
 |
|||
 |
|||
Panjang lintasan dari a sampai z adalah 1 + 10 + 5 = 16
 |
Panjang lintasan dari a sampai z adalah 10 + 4 + 2 = 16
 |
|||
|
|||
Panjang lintasan dari a sampai z adalah 6 + 3 + 8 = 17
 |
Panjang lintasan dari a sampai z adalah 3 + 8 + 5 = 16
 |
Panjang lintasan dari a sampai z adalah 1 + 10 + 1 + 2 + 2 = 16
 |
|
|
|
|
|
|
5.19
G
5.20
G
5.21
G
5.22
G
5.23
G
MATHEMATIC DISCRETE
EXERCISES 1-3.5
1. Write equivalent forms for the following
formulas in which negations are applied to the
variables only.
(a). ¬(PVQ)
(b). ¬(PΛQ)
Obtain the principal conjunctive
normal forms of (a), (c), and (d).
Solution:
(a). ¬(PVQ)↔ (¬PΛ¬Q)
(b). ¬(PΛQ)↔ (¬PV¬Q)
Principal conjunctive normal forms of :
(a). ¬(PVQ)↔ (¬PΛ¬Q)
↔ (¬PVF) Λ(FV¬Q)
↔ (¬PV(QΛ¬Q)) Λ((PΛ¬P)V¬Q)
↔ (¬PVQ)Λ(¬PV¬Q)Λ(PV¬Q)Λ(¬PV¬Q)
↔ (¬PVQ)Λ(¬PV¬Q)Λ(PV¬Q)
↔ (PV¬Q)Λ(¬PVQ)Λ(¬PV¬Q)
(c). ¬(P→Q)↔ ¬(¬PVQ)
↔ (PΛ¬Q)
↔ (PVF) Λ(FV¬Q)
↔ (PV(QΛ¬Q))Λ(PΛ¬P)V¬Q)
↔ (PVQ)Λ(PV¬Q)Λ(PV¬Q)Λ(¬PV¬Q)
↔ (PVQ)Λ(PV¬Q)Λ(¬PV¬Q)
(d). ¬(P Q)↔ ¬((P→Q)Λ(Q→P))
↔ ¬((¬PVQ)Λ(¬QVP))
↔ ¬(¬PVQ)V¬(¬QVP)
↔ (PΛ¬Q)V(QΛ¬P)
↔ (PΛ¬Q)V(¬PΛQ)
↔ (PV(¬PΛQ))Λ(¬QV(¬PΛQ))
↔ (PV¬P)Λ(PVQ)Λ(¬PV¬Q)Λ(QV¬Q)
↔ TΛ(PVQ)Λ(¬PV¬Q)ΛT
↔ (PVQ)Λ(¬PV¬Q)
2. Obtain the
product-of-sums canonical forms of the following formulas.
(a). (PΛQΛR)V(¬PΛRΛQ)V(¬PΛ¬QΛ¬R)
(c). (PΛQ)V(¬PΛQ)V(PΛ¬Q)
Solution:
(a). (PΛQΛR)V(¬PΛRΛQ)V(¬PΛ¬QΛ¬R)
↔
((QΛR)Λ(PV¬P))V(¬PΛ¬QΛ¬R)
↔ ((QΛR)ΛT)V(¬PΛ¬QΛ¬R)
↔ (QΛR)V(¬PΛ¬QΛ¬R)
↔ (¬PVQ)Λ(QV¬Q)Λ(QV¬R)Λ(¬PV¬R)Λ(¬QVR)Λ(RV¬R)
↔ (¬PVQ)ΛTΛ(QV¬R)Λ(¬PV¬R)Λ(¬QVR)ΛT
↔
(¬PVQ)Λ(QV¬R)Λ(¬PV¬R)Λ(¬QVR)
↔ (¬PVQVF)Λ(FVQV¬R)Λ(¬PV¬RVF)Λ(FV¬QVR)
↔((¬PVQ)V(RΛ¬R))Λ((PΛ¬P)V(QV¬R))Λ((¬PV¬R)V(QV¬Q))Λ((PΛ¬P)V(¬QVR))
↔(¬PVQVR)Λ(¬PVQV¬R)Λ(PVQV¬R)Λ(¬PVQV¬R)Λ(¬PVQV¬R)Λ(¬PV¬QVR)
Λ(PV¬QVR)Λ(¬PV¬QVR)
↔(¬PVQVR)Λ(¬PVQV¬R)Λ(PVQV¬R)Λ(¬PV¬QVR) Λ(PV¬QVR)
↔(PVQV¬R)Λ(PV¬QVR)Λ(¬PVQVR)Λ(¬PVQV¬R) Λ(¬PV¬QVR)
↔Π 1,2,4,5,6
(c).
(PΛQ)V(¬PΛQ)V(PΛ¬Q)
↔(PΛQ)V(PΛ¬Q)V(¬PΛQ)
↔(PΛ(QV¬Q))V(¬PΛQ)
↔(PΛT)V(¬PΛQ)
↔PV(¬PΛQ)
↔(PV¬P)Λ(PVQ)
↔TΛ(PVQ)
↔(PVQ)
↔Π 0
3. Obtain the principal disjunctive and
conjunctive normal forms of the following formulas.
(b).
QΛ(PV¬Q)
(e).
P→ (PΛ(Q→ P))
(f).
(Q→ P)Λ(¬PΛQ)
Which of the above formulas are
tautologies?
Solution:
(b). QΛ(PV¬Q)
Principal
disjunctive normal forms
QΛ(PV¬Q)
↔(QΛP)V(QΛ¬Q)
↔(QΛP)VF
↔(QΛP)
↔(PΛQ) (Tautologi)
Principal
conjunctive normal forms
QΛ(PV¬Q)
↔(QΛT)Λ(PV¬Q)
↔(QΛ(PV¬P))Λ(PV¬Q)
↔(QVP)Λ(QV¬P)Λ(PV¬Q)
↔(PVQ)Λ(PV¬Q)Λ(¬PVQ) (Tautologi)
(e). P→
(PΛ(Q→ P))
Principal
disjunctive normal forms
P→ (PΛ(Q→ P))
↔ P→ (PΛ(¬QVP))
↔ ¬PV(PΛ(¬QVP))
↔ (¬PVP)Λ(¬PV(¬QVP))
↔ TΛ((PV¬P)V(¬PV¬Q))
↔ TΛ(TV(¬PV¬Q))
↔ TΛT
↔ T (Tautologi)
Principal
conjunctive normal forms
P→ (PΛ(Q→ P))
↔ ¬PV(PΛ(¬QVP))
↔ ¬PV((PΛ¬Q)V(PΛP))
↔ ¬PV((PΛ¬Q)VP)
↔ (¬PΛT)V(PΛ¬Q)V(PΛT)
↔ (¬PΛ(QV¬Q))V(PΛ¬Q)V(PΛ(QV¬Q))
↔ (¬PΛQ)V(¬PΛ¬Q)V(PΛ¬Q)V(PΛQ)V(PΛ¬Q)
↔ (PΛQ)V(PΛ¬Q)V(¬PΛQ)V(¬PΛ¬Q) (tautologi)
(f). (Q→
P)Λ(¬PΛQ)
Principal disjunctive normal
forms
(Q→ P)Λ(¬PΛQ)
↔(¬QVP)Λ(¬PΛQ)
↔(¬QΛ(¬PΛQ))V(PΛ(¬PΛQ))
↔(¬QΛ¬PΛQ)V(PΛ¬PΛQ)
↔( ¬PΛQΛ¬Q)V(PΛ¬PΛQ)
↔( ¬PΛF)V(FΛQ)
↔FVF
↔F (Kontradiksi)
Principal
conjunctive normal forms
(Q→ P)Λ(¬PΛQ)
↔(¬QVP)Λ(¬PΛQ)
↔(¬QVP)Λ(¬PVF)Λ(FVQ)
↔(¬QVP)Λ((¬PV(QΛ¬Q)Λ((PΛ¬P)VQ)
↔(¬QVP)Λ(¬PVQ)Λ(¬PV¬Q)Λ(PVQ)Λ(¬PVQ)
↔(PVQ)Λ(PV¬Q)Λ(¬PVQ)Λ(¬PV¬Q) (Kontradiksi)
Program to display posets, Peter Jipsen, Version 0.2 6/11/99,
// Graphics part adapted from JDK demo GraphLayout
import java.util.*;
import java.awt.*;
import java.applet.Applet;
class Node {
double x;
double y;
double dx;
double dy;
String name;
String label;
Color color;
boolean fixed;
}
class Edge {
int from;
int to;
Color color;
double len;
byte arrow;
}
class GraphPanel extends Panel implements Runnable {
Poset graph;
int nnodes;
Node nodes[] = new Node[10]; // initial max size; doubles as needed
int nedges;
Edge edges[] = new Edge[20]; // initial max size; doubles as needed
boolean noGrid;
boolean noVerticalMove;
boolean fixed;
boolean showLabels;
int repel;
int attract;
int gridX;
int gridY;
int bottom=38;
double edgeLength;
Thread relaxer;
GraphPanel(Poset graph) {
this.graph = graph;
}
int addNode(double x, double y, Color color, String name, String label) {
Node n = new Node();
n.x = x;
n.y = y;
n.color = color;
n.name = name;
n.label = label;
if (nodes.length==nnodes) {
Node newnodes[] = new Node[2*nnodes];
for (int i=0; inodes=newnodes;}nodes[nnodes] = n;return nnodes++;}void updateNode(int i, double x, double y, Color color, String label) {Node n = nodes[i];n.x = x;n.y = y;n.color = color;n.label = label;}int findNode(String name) {for (int i = nnodes-1 ; i >=0 ; i--) {if (nodes[i].name.equals(name)) {return i;}}return addNode(0,0,Color.black,name,"");}void addEdge(String fromName, String toName, Color color,double len, byte arrow) {Edge e = new Edge();e.from = findNode(fromName);e.to = findNode(toName);e.color = color;e.len = len;e.arrow = arrow;if (edges.length==nedges) {Edge newedges[] = new Edge[2*nedges];for (int i=0; iedges=newedges;}edges[nedges++] = e;}public void run() {while (true) {if (!fixed) relax();try {Thread.sleep(100);} catch (InterruptedException e) {break;}}}synchronized void relax() {if (edgeLength!=0)for (int i = 0 ; i < nedges ; i++) {//tension along edgesEdge 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); //true lengthdouble dx = 0;double dy = 0;if (len == 0) {dx += Math.random(); // don't superimpose nodesdy += Math.random(); // allows nodes to pass eachother} else {double f = (edges[i].len - len) / (len * 3) ;dx = f * vx; // change in direction of desired lengthdy = 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++) { // repulsion between nodesNode 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;if (vy==0){double len = vx * vx + vy * vy;if (len == 0) {dx += Math.random(); // don't superimpose nodesdy += Math.random(); // allows nodes to pass eachother} else if (len < 100*100) {dx += vx / len; // increment by scaled x-dist.dy += vy / len; // elements further away have less impact} // because len is the squared distance}}double dlen = dx * dx + dy * dy;if (dlen > 0) {dlen = Math.sqrt(dlen);n1.dx += (dx / dlen)*repel;n1.dy += (dy / dlen)*repel;}// provide tension towards grid pointsdouble rx = n1.x-gridX*Math.floor((n1.x-Poset.border)/gridX)-Poset.border;rx = ( rx < gridX/2 ? -rx : gridX-rx );n1.dx += (rx/gridX)*attract;}Dimension d = size();for (int i = 0 ; i < nnodes ; i++) {Node n = nodes[i];if (!n.fixed && !fixed) {n.x += Math.max(-5, Math.min(5, n.dx));// change n.x by at most 5if (n.x < Poset.border) {n.x = Poset.border;} else if (n.x > d.width-Poset.border) {n.x = d.width-Poset.border;}/* 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;final Color selectColor = Color.pink;final Color nodeColor = new Color(250, 220, 100);public void paintNode(Graphics g, Node n, int i, FontMetrics fm) {int x = (int)n.x;int y = (int)n.y;if (n==pick || showLabels){g.setColor((n==pick?selectColor:n.color));int w = fm.stringWidth(n.label) + 6;int h = fm.getHeight();w=2*(w/2);h=2*(h/2);g.fillOval(x - w/2, y - h / 2, w, h);// g.drawOval(x - w/2, y - h / 2, w, h);if (n.fixed) {g.setColor(Color.red);g.drawOval(x - w/2-1, y - h/2-1, w+2, h+2);}g.setColor(Color.black);g.drawString(n.label, x - (w-6)/2, (y - (h-5)/2-2) + fm.getAscent());}else{g.setColor(n.color);int w = fm.stringWidth(n.name) + 6;int h = fm.getHeight();w=2*(w/2); h=2*(h/2);g.fillOval(x - w/2, y - h / 2, w, h);g.setColor((n.fixed?Color.red:Color.black));g.drawOval(x - w/2, y - h / 2, w, h);if (n.fixed) {g.drawOval(x - w/2-1, y - h/2-1, w+2, h+2);}g.setColor(Color.black);g.drawString(n.name, x - (w-6)/2,(y - (h-5)/2-2) + fm.getAscent());}}public void drawArrow(Graphics g, int x1, int y1, int x2, int y2) {int c = 10; //distance from arrow head to node centerint a = 10; //length of arrow headdouble dd = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));int ax = (int)(x2 - (c/dd)*(x2-x1));int ay = (int)(y2 - (c/dd)*(y2-y1));double bx = x2 - ((c+a)/dd)*(x2-x1);double by = y2 - ((c+a)/dd)*(y2-y1);double ox = a/(1.73*dd)*(y2-y1);double oy = a/(1.73*dd)*(x2-x1);g.drawLine((int)(bx-ox),(int)(by+oy),ax,ay);g.drawLine((int)(bx+ox),(int)(by-oy),ax,ay);}public synchronized void update(Graphics g) {Dimension d = size();if ((offscreen == null) || (d.width != offscreensize.width)|| (d.height != offscreensize.height)) {offscreen = createImage(d.width, d.height);offscreensize = d;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;offgraphics.setColor(e.color);offgraphics.drawLine(x1, y1, x2, y2);if (e.arrow==1 || e.arrow==3)drawArrow(offgraphics, x1, y1, x2, y2);if (e.arrow==2 || e.arrow==3)drawArrow(offgraphics, x2, y2, x1, y1);}FontMetrics fm = offgraphics.getFontMetrics();for (int i = 0 ; i < nnodes ; i++) {paintNode(offgraphics, nodes[i], i+1, fm);}offgraphics.setColor(Color.black);if (!noGrid)for (int px=Poset.border; px<=d.width-Poset.border; px+=gridX)for (int py=Poset.border; py<=d.height-Poset.border+2; py+=gridY)offgraphics.drawLine(px,py,px,py);g.drawImage(offscreen, 0, 0, null);}public synchronized void paint(Graphics g) {// seemingly needed for printingupdate(g);}public synchronized boolean mouseDown(Event evt, int x, int y) {double bestdist = Double.MAX_VALUE;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-Poset.border+gridX/2)/gridX*gridX+Poset.border;if (pick.x < Poset.border) pick.x = Poset.border;else if (pick.x > size().width-Poset.border)pick.x = size().width-Poset.border;if (!noVerticalMove) {pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;if (pick.y < Poset.border) pick.y = Poset.border;else if (pick.y > size().height-Poset.border)pick.y = size().height-Poset.border;}repaint();return true;}public synchronized boolean mouseDrag(Event evt, int x, int y) {pick.x = (x-Poset.border+gridX/2)/gridX*gridX+Poset.border;if (pick.x < Poset.border) pick.x = Poset.border;else if (pick.x > size().width-Poset.border)pick.x = size().width-Poset.border;if (!noVerticalMove) {pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;if (pick.y < Poset.border) pick.y = Poset.border;else if (pick.y > size().height-Poset.border)pick.y = size().height-Poset.border;}pickfixed = false;repaint();return true;}public synchronized boolean mouseUp(Event evt, int x, int y) {pick.x = (x-Poset.border+gridX/2)/gridX*gridX+Poset.border;if (pick.x < Poset.border) pick.x = Poset.border;else if (pick.x > size().width-Poset.border)pick.x = size().width-Poset.border;if (!noVerticalMove) {pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;if (pick.y < Poset.border) pick.y = Poset.border;else if (pick.y > size().height-Poset.border)pick.y = size().height-Poset.border;}pick.fixed = !pickfixed;pick = null;repaint();return true;}public void start() {relaxer = new Thread(this);relaxer.start();}public void stop() {relaxer.stop();}}public class Poset extends Applet {GraphPanel panel;TextField edgeLen;TextField repel;TextField attract;TextField gX;Button start;static int border=20;static int str2int(String s) {return Integer.valueOf(s.trim()).intValue();}static String str2name(String s) {int i = s.indexOf('"');if (i>=0) {int j = s.substring(i+1).indexOf('"');if (j>=0)return s.substring(i+1).substring(0,j);System.out.println("Warning: \",\" in nameString or missing \" ");return s.substring(i+1);}return s.trim();}static Color str2color(String s) {Color col;if (s.equals("black")) col = Color.black;else if (s.equals("blue")) col = Color.blue;else if (s.equals("cyan")) col = Color.cyan;else if (s.equals("darkGray")) col = Color.darkGray;else if (s.equals("gray")) col = Color.gray;else if (s.equals("green")) col = Color.green;else if (s.equals("lightGray")) col = Color.lightGray;else if (s.equals("magenta")) col = Color.magenta;else if (s.equals("orange")) col = Color.orange;else if (s.equals("pink")) col = Color.pink;else if (s.equals("red")) col = Color.red;else if (s.equals("white")) col = Color.white;else if (s.equals("yellow")) col = Color.yellow;else col = Color.decode(s);return col;}public void init() {setLayout(new BorderLayout());panel = new GraphPanel(this);setBackground(Color.white);add("Center", panel);Dimension d = size();int maxX = str2int(getParameter("maxX"));int maxY = str2int(getParameter("maxY"));panel.gridX = (int)Math.floor((d.width-2*border)/maxX);panel.gridY = (int)Math.floor((d.height-2*border-panel.bottom)/maxY);edgeLen = new TextField(String.valueOf(panel.gridY-5),3);panel.edgeLength = (double)str2int(edgeLen.getText());String param = getParameter("noGrid");if (param!=null) panel.noGrid=param.equals("true");else panel.noGrid=true;param = getParameter("noVerticalMove");if (param!=null) panel.noVerticalMove=param.equals("true");else panel.noVerticalMove=true;param = getParameter("showLabels");if (param!=null) panel.showLabels=param.equals("true");else panel.showLabels=false;param = getParameter("showControls");if (param == null || param.equals("true")) {Panel p = new Panel();add("South", p);param = getParameter("fix");if (param!=null) panel.fixed=param.equals("true");else panel.fixed=true;if (panel.fixed) start = new Button("Start");else start = new Button("Stop");p.add(start);p.add(new Label("Repel:"));param = getParameter("repel");if (param==null) param="0";repel = new TextField(param,3);p.add(repel);panel.repel = str2int(repel.getText());p.add(new Label("Attract:"));param = getParameter("attract");if (param==null) param="0";attract = new TextField(param,3);p.add(attract);panel.attract = str2int(attract.getText());p.add(new Label("Grid X:"));gX = new TextField(String.valueOf(panel.gridX),3);p.add(gX);p.add(new Label("Edge L:"));p.add(edgeLen);p.add(new Button("Adjust"));p.add(new Button("Output"));p.add(new Checkbox("Labels"));} else {panel.bottom = 0;panel.fixed = true;panel.gridY = (int)Math.floor((d.height-2*border-panel.bottom)/maxY);}Color color;String poset = getParameter("poset");for (StringTokenizer t = new StringTokenizer(poset, ",") ;t.hasMoreTokens() ; ) {String str = t.nextToken();int i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);String nname = str2name(str);int nx = str2int(t.nextToken());int ny = str2int(t.nextToken());str = t.nextToken();i = str.indexOf('"');String nl="";boolean ok=true;color = Color.yellow;if (i >= 0) { //read the labelstr = str.substring(i+1);i = str.indexOf('"');if (i >= 0) nl = str.substring(0,i);else {nl = str;for (; t.hasMoreTokens() && ok ; ) {str = t.nextToken();i = str.indexOf('"');if (i >= 0) {ok = false;nl = nl.concat(str.substring(0,i));} else nl = nl.concat(str);}}i = nl.indexOf('#'); //look for colorif (i >= 0) {color = str2color(nl.substring(i+1));nl = nl.substring(0,i);}} else nl = str.trim();panel.updateNode(panel.findNode(nname),nx*panel.gridX+border,(maxY-ny)*panel.gridY+border,color,nl);ok=true;color = Color.black;byte arrow = 0;for (; t.hasMoreTokens() && ok ; ) {str = t.nextToken();i = str.indexOf(']');if (i >= 0) {ok = false;str = str.substring(0, i);}i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);if (!str.trim().equals("")) {i = str.indexOf('#');if (i >= 0) {str = str.substring(i+1);i = str.indexOf('"');if (i >= 0) str = str.substring(0,i);i = str.indexOf('>');if (i >= 0) {arrow = 1;str = str.substring(0,i);}i = str.indexOf('<');if (i >= 0) {arrow = (byte)(arrow + 2);str = str.substring(0,i);}color = str2color(str);} else {String mname = str2name(str);panel.addEdge(nname, mname, color,panel.edgeLength, arrow);color = Color.black;arrow = 0;}}}}int c = 0;String newEmbedding = getParameter("newEmbedding");if (newEmbedding!=null)for (StringTokenizer t = new StringTokenizer(newEmbedding, ",") ;t.hasMoreTokens() ; ) {String str = t.nextToken();int i = str.indexOf('[');if (i >= 0) {str=str.substring(i+1);i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);c = panel.findNode(str2name(str));str = t.nextToken();panel.nodes[c].x=str2int(str)*panel.gridX+border;str = t.nextToken();i = str.indexOf(']');if (i>=0) str=str.substring(0,i);panel.nodes[c].y=(maxY-str2int(str))*panel.gridY+border;}}panel.repaint();}public void start() {panel.start();}public void stop() {panel.stop();}public boolean action(Event evt, Object arg) {if (arg instanceof Boolean) {if (((Checkbox)evt.target).getLabel().equals("Labels")) {panel.showLabels = ((Boolean)arg).booleanValue();panel.repaint();}return true;}if ("Start".equals(arg)) {panel.fixed=false;start.setLabel("Stop");return true;}if ("Stop".equals(arg)) {panel.fixed=true;start.setLabel("Start");return true;}if ("Adjust".equals(arg)) {for (int i = 0 ; i < panel.nedges ; i++) {Edge e = panel.edges[i];double vx = panel.nodes[e.from].x-panel.nodes[e.to].x;double vy = panel.nodes[e.from].y-panel.nodes[e.to].y;e.len = Math.sqrt(vx*vx + vy*vy);}panel.repaint();return true;}if ("Output".equals(arg)) {System.out.print("");else System.out.print(",");}return true;}if (evt.target == repel){panel.repel = str2int(repel.getText());return true;}if (evt.target == attract){panel.attract = str2int(attract.getText());return true;}if (evt.target == gX){int tgX = str2int(gX.getText());if (tgX == 0) panel.noGrid=true;else {panel.noGrid=false;panel.gridX=tgX;}panel.repaint();return true;}if (evt.target == edgeLen){panel.edgeLength = (double)str2int(edgeLen.getText());for(int i=0; iEdge f = panel.edges[i];f.len = panel.edgeLength*Math.abs(panel.nodes[f.from].y-panel.nodes[f.to].y)/panel.gridY;}return true;}return false;}}// Program to display posets, Peter Jipsen, Version 0.2 6/11/99,// Graphics part adapted from JDK demo GraphLayoutimport java.util.*;import java.awt.*;import java.applet.Applet;class Node {double x;double y;double dx;double dy;String name;String label;Color color;boolean fixed;}class Edge {int from;int to;Color color;double len;byte arrow;}class GraphPanel extends Panel implements Runnable {Poset graph;int nnodes;Node nodes[] = new Node[10]; // initial max size; doubles as neededint nedges;Edge edges[] = new Edge[20]; // initial max size; doubles as neededboolean noGrid;boolean noVerticalMove;boolean fixed;boolean showLabels;int repel;int attract;int gridX;int gridY;int bottom=38;double edgeLength;Thread relaxer;GraphPanel(Poset graph) {this.graph = graph;}int addNode(double x, double y, Color color, String name, String label) {Node n = new Node();n.x = x;n.y = y;n.color = color;n.name = name;n.label = label;if (nodes.length==nnodes) {Node newnodes[] = new Node[2*nnodes];for (int i=0; inodes=newnodes;}nodes[nnodes] = n;return nnodes++;}void updateNode(int i, double x, double y, Color color, String label) {Node n = nodes[i];n.x = x;n.y = y;n.color = color;n.label = label;}int findNode(String name) {for (int i = nnodes-1 ; i >=0 ; i--) {if (nodes[i].name.equals(name)) {return i;}}return addNode(0,0,Color.black,name,"");}void addEdge(String fromName, String toName, Color color,double len, byte arrow) {Edge e = new Edge();e.from = findNode(fromName);e.to = findNode(toName);e.color = color;e.len = len;e.arrow = arrow;if (edges.length==nedges) {Edge newedges[] = new Edge[2*nedges];for (int i=0; iedges=newedges;}edges[nedges++] = e;}public void run() {while (true) {if (!fixed) relax();try {Thread.sleep(100);} catch (InterruptedException e) {break;}}}synchronized void relax() {if (edgeLength!=0)for (int i = 0 ; i < nedges ; i++) {//tension along edgesEdge 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); //true lengthdouble dx = 0;double dy = 0;if (len == 0) {dx += Math.random(); // don't superimpose nodesdy += Math.random(); // allows nodes to pass eachother} else {double f = (edges[i].len - len) / (len * 3) ;dx = f * vx; // change in direction of desired lengthdy = 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++) { // repulsion between nodesNode 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;if (vy==0){double len = vx * vx + vy * vy;if (len == 0) {dx += Math.random(); // don't superimpose nodesdy += Math.random(); // allows nodes to pass eachother} else if (len < 100*100) {dx += vx / len; // increment by scaled x-dist.dy += vy / len; // elements further away have less impact} // because len is the squared distance}}double dlen = dx * dx + dy * dy;if (dlen > 0) {dlen = Math.sqrt(dlen);n1.dx += (dx / dlen)*repel;n1.dy += (dy / dlen)*repel;}// provide tension towards grid pointsdouble rx = n1.x-gridX*Math.floor((n1.x-Poset.border)/gridX)-Poset.border;rx = ( rx < gridX/2 ? -rx : gridX-rx );n1.dx += (rx/gridX)*attract;}Dimension d = size();for (int i = 0 ; i < nnodes ; i++) {Node n = nodes[i];if (!n.fixed && !fixed) {n.x += Math.max(-5, Math.min(5, n.dx));// change n.x by at most 5if (n.x < Poset.border) {n.x = Poset.border;} else if (n.x > d.width-Poset.border) {n.x = d.width-Poset.border;}/* 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;final Color selectColor = Color.pink;final Color nodeColor = new Color(250, 220, 100);public void paintNode(Graphics g, Node n, int i, FontMetrics fm) {int x = (int)n.x;int y = (int)n.y;if (n==pick || showLabels){g.setColor((n==pick?selectColor:n.color));int w = fm.stringWidth(n.label) + 6;int h = fm.getHeight();w=2*(w/2);h=2*(h/2);g.fillOval(x - w/2, y - h / 2, w, h);// g.drawOval(x - w/2, y - h / 2, w, h);if (n.fixed) {g.setColor(Color.red);g.drawOval(x - w/2-1, y - h/2-1, w+2, h+2);}g.setColor(Color.black);g.drawString(n.label, x - (w-6)/2, (y - (h-5)/2-2) + fm.getAscent());}else{g.setColor(n.color);int w = fm.stringWidth(n.name) + 6;int h = fm.getHeight();w=2*(w/2); h=2*(h/2);g.fillOval(x - w/2, y - h / 2, w, h);g.setColor((n.fixed?Color.red:Color.black));g.drawOval(x - w/2, y - h / 2, w, h);if (n.fixed) {g.drawOval(x - w/2-1, y - h/2-1, w+2, h+2);}g.setColor(Color.black);g.drawString(n.name, x - (w-6)/2,(y - (h-5)/2-2) + fm.getAscent());}}public void drawArrow(Graphics g, int x1, int y1, int x2, int y2) {int c = 10; //distance from arrow head to node centerint a = 10; //length of arrow headdouble dd = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));int ax = (int)(x2 - (c/dd)*(x2-x1));int ay = (int)(y2 - (c/dd)*(y2-y1));double bx = x2 - ((c+a)/dd)*(x2-x1);double by = y2 - ((c+a)/dd)*(y2-y1);double ox = a/(1.73*dd)*(y2-y1);double oy = a/(1.73*dd)*(x2-x1);g.drawLine((int)(bx-ox),(int)(by+oy),ax,ay);g.drawLine((int)(bx+ox),(int)(by-oy),ax,ay);}public synchronized void update(Graphics g) {Dimension d = size();if ((offscreen == null) || (d.width != offscreensize.width)|| (d.height != offscreensize.height)) {offscreen = createImage(d.width, d.height);offscreensize = d;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;offgraphics.setColor(e.color);offgraphics.drawLine(x1, y1, x2, y2);if (e.arrow==1 || e.arrow==3)drawArrow(offgraphics, x1, y1, x2, y2);if (e.arrow==2 || e.arrow==3)drawArrow(offgraphics, x2, y2, x1, y1);}FontMetrics fm = offgraphics.getFontMetrics();for (int i = 0 ; i < nnodes ; i++) {paintNode(offgraphics, nodes[i], i+1, fm);}offgraphics.setColor(Color.black);if (!noGrid)for (int px=Poset.border; px<=d.width-Poset.border; px+=gridX)for (int py=Poset.border; py<=d.height-Poset.border+2; py+=gridY)offgraphics.drawLine(px,py,px,py);g.drawImage(offscreen, 0, 0, null);}public synchronized void paint(Graphics g) {// seemingly needed for printingupdate(g);}public synchronized boolean mouseDown(Event evt, int x, int y) {double bestdist = Double.MAX_VALUE;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-Poset.border+gridX/2)/gridX*gridX+Poset.border;if (pick.x < Poset.border) pick.x = Poset.border;else if (pick.x > size().width-Poset.border)pick.x = size().width-Poset.border;if (!noVerticalMove) {pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;if (pick.y < Poset.border) pick.y = Poset.border;else if (pick.y > size().height-Poset.border)pick.y = size().height-Poset.border;}repaint();return true;}public synchronized boolean mouseDrag(Event evt, int x, int y) {pick.x = (x-Poset.border+gridX/2)/gridX*gridX+Poset.border;if (pick.x < Poset.border) pick.x = Poset.border;else if (pick.x > size().width-Poset.border)pick.x = size().width-Poset.border;if (!noVerticalMove) {pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;if (pick.y < Poset.border) pick.y = Poset.border;else if (pick.y > size().height-Poset.border)pick.y = size().height-Poset.border;}pickfixed = false;repaint();return true;}public synchronized boolean mouseUp(Event evt, int x, int y) {pick.x = (x-Poset.border+gridX/2)/gridX*gridX+Poset.border;if (pick.x < Poset.border) pick.x = Poset.border;else if (pick.x > size().width-Poset.border)pick.x = size().width-Poset.border;if (!noVerticalMove) {pick.y = (y-Poset.border+gridY/2)/gridY*gridY+Poset.border;if (pick.y < Poset.border) pick.y = Poset.border;else if (pick.y > size().height-Poset.border)pick.y = size().height-Poset.border;}pick.fixed = !pickfixed;pick = null;repaint();return true;}public void start() {relaxer = new Thread(this);relaxer.start();}public void stop() {relaxer.stop();}}public class Poset extends Applet {GraphPanel panel;TextField edgeLen;TextField repel;TextField attract;TextField gX;Button start;static int border=20;static int str2int(String s) {return Integer.valueOf(s.trim()).intValue();}static String str2name(String s) {int i = s.indexOf('"');if (i>=0) {int j = s.substring(i+1).indexOf('"');if (j>=0)return s.substring(i+1).substring(0,j);System.out.println("Warning: \",\" in nameString or missing \" ");return s.substring(i+1);}return s.trim();}static Color str2color(String s) {Color col;if (s.equals("black")) col = Color.black;else if (s.equals("blue")) col = Color.blue;else if (s.equals("cyan")) col = Color.cyan;else if (s.equals("darkGray")) col = Color.darkGray;else if (s.equals("gray")) col = Color.gray;else if (s.equals("green")) col = Color.green;else if (s.equals("lightGray")) col = Color.lightGray;else if (s.equals("magenta")) col = Color.magenta;else if (s.equals("orange")) col = Color.orange;else if (s.equals("pink")) col = Color.pink;else if (s.equals("red")) col = Color.red;else if (s.equals("white")) col = Color.white;else if (s.equals("yellow")) col = Color.yellow;else col = Color.decode(s);return col;}public void init() {setLayout(new BorderLayout());panel = new GraphPanel(this);setBackground(Color.white);add("Center", panel);Dimension d = size();int maxX = str2int(getParameter("maxX"));int maxY = str2int(getParameter("maxY"));panel.gridX = (int)Math.floor((d.width-2*border)/maxX);panel.gridY = (int)Math.floor((d.height-2*border-panel.bottom)/maxY);edgeLen = new TextField(String.valueOf(panel.gridY-5),3);panel.edgeLength = (double)str2int(edgeLen.getText());String param = getParameter("noGrid");if (param!=null) panel.noGrid=param.equals("true");else panel.noGrid=true;param = getParameter("noVerticalMove");if (param!=null) panel.noVerticalMove=param.equals("true");else panel.noVerticalMove=true;param = getParameter("showLabels");if (param!=null) panel.showLabels=param.equals("true");else panel.showLabels=false;param = getParameter("showControls");if (param == null || param.equals("true")) {Panel p = new Panel();add("South", p);param = getParameter("fix");if (param!=null) panel.fixed=param.equals("true");else panel.fixed=true;if (panel.fixed) start = new Button("Start");else start = new Button("Stop");p.add(start);p.add(new Label("Repel:"));param = getParameter("repel");if (param==null) param="0";repel = new TextField(param,3);p.add(repel);panel.repel = str2int(repel.getText());p.add(new Label("Attract:"));param = getParameter("attract");if (param==null) param="0";attract = new TextField(param,3);p.add(attract);panel.attract = str2int(attract.getText());p.add(new Label("Grid X:"));gX = new TextField(String.valueOf(panel.gridX),3);p.add(gX);p.add(new Label("Edge L:"));p.add(edgeLen);p.add(new Button("Adjust"));p.add(new Button("Output"));p.add(new Checkbox("Labels"));} else {panel.bottom = 0;panel.fixed = true;panel.gridY = (int)Math.floor((d.height-2*border-panel.bottom)/maxY);}Color color;String poset = getParameter("poset");for (StringTokenizer t = new StringTokenizer(poset, ",") ;t.hasMoreTokens() ; ) {String str = t.nextToken();int i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);String nname = str2name(str);int nx = str2int(t.nextToken());int ny = str2int(t.nextToken());str = t.nextToken();i = str.indexOf('"');String nl="";boolean ok=true;color = Color.yellow;if (i >= 0) { //read the labelstr = str.substring(i+1);i = str.indexOf('"');if (i >= 0) nl = str.substring(0,i);else {nl = str;for (; t.hasMoreTokens() && ok ; ) {str = t.nextToken();i = str.indexOf('"');if (i >= 0) {ok = false;nl = nl.concat(str.substring(0,i));} else nl = nl.concat(str);}}i = nl.indexOf('#'); //look for colorif (i >= 0) {color = str2color(nl.substring(i+1));nl = nl.substring(0,i);}} else nl = str.trim();panel.updateNode(panel.findNode(nname),nx*panel.gridX+border,(maxY-ny)*panel.gridY+border,color,nl);ok=true;color = Color.black;byte arrow = 0;for (; t.hasMoreTokens() && ok ; ) {str = t.nextToken();i = str.indexOf(']');if (i >= 0) {ok = false;str = str.substring(0, i);}i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);if (!str.trim().equals("")) {i = str.indexOf('#');if (i >= 0) {str = str.substring(i+1);i = str.indexOf('"');if (i >= 0) str = str.substring(0,i);i = str.indexOf('>');if (i >= 0) {arrow = 1;str = str.substring(0,i);}i = str.indexOf('<');if (i >= 0) {arrow = (byte)(arrow + 2);str = str.substring(0,i);}color = str2color(str);} else {String mname = str2name(str);panel.addEdge(nname, mname, color,panel.edgeLength, arrow);color = Color.black;arrow = 0;}}}}int c = 0;String newEmbedding = getParameter("newEmbedding");if (newEmbedding!=null)for (StringTokenizer t = new StringTokenizer(newEmbedding, ",") ;t.hasMoreTokens() ; ) {String str = t.nextToken();int i = str.indexOf('[');if (i >= 0) {str=str.substring(i+1);i = str.indexOf('[');if (i >= 0) str=str.substring(i+1);c = panel.findNode(str2name(str));str = t.nextToken();panel.nodes[c].x=str2int(str)*panel.gridX+border;str = t.nextToken();i = str.indexOf(']');if (i>=0) str=str.substring(0,i);panel.nodes[c].y=(maxY-str2int(str))*panel.gridY+border;}}panel.repaint();}public void start() {panel.start();}public void stop() {panel.stop();}public boolean action(Event evt, Object arg) {if (arg instanceof Boolean) {if (((Checkbox)evt.target).getLabel().equals("Labels")) {panel.showLabels = ((Boolean)arg).booleanValue();panel.repaint();}return true;}if ("Start".equals(arg)) {panel.fixed=false;start.setLabel("Stop");return true;}if ("Stop".equals(arg)) {panel.fixed=true;start.setLabel("Start");return true;}if ("Adjust".equals(arg)) {for (int i = 0 ; i < panel.nedges ; i++) {Edge e = panel.edges[i];double vx = panel.nodes[e.from].x-panel.nodes[e.to].x;double vy = panel.nodes[e.from].y-panel.nodes[e.to].y;e.len = Math.sqrt(vx*vx + vy*vy);}panel.repaint();return true;}if ("Output".equals(arg)) {System.out.print("");else System.out.print(",");}return true;}if (evt.target == repel){panel.repel = str2int(repel.getText());return true;}if (evt.target == attract){panel.attract = str2int(attract.getText());return true;}if (evt.target == gX){int tgX = str2int(gX.getText());if (tgX == 0) panel.noGrid=true;else {panel.noGrid=false;panel.gridX=tgX;}panel.repaint();return true;}if (evt.target == edgeLen){panel.edgeLength = (double)str2int(edgeLen.getText());for(int i=0; iEdge f = panel.edges[i];f.len = panel.edgeLength*Math.abs(panel.nodes[f.from].y-panel.nodes[f.to].y)/panel.gridY;}return true;}return false;}}
No comments:
Post a Comment