source: src/main/java/weka/gui/hierarchyvisualizer/HierarchyVisualizer.java @ 10

Last change on this file since 10 was 4, checked in by gnappo, 14 years ago

Import di weka.
File size: 11.8 KB
Line 
1/*
2
3 * This program is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License as published by
5 * the Free Software Foundation; either version 2 of the License, or
6 * (at your option) any later version.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * GNU General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
16 */
17/*
18 * HierarchicalClusterer.java
19 * Copyright (C) 2009 University of Waikato, Hamilton, New Zealand
20*/
21
22package weka.gui.hierarchyvisualizer;
23/**
24 * Shows cluster trees represented in Newick format as dendrograms.
25 *
26 * @author Remco Bouckaert (rrb@xm.co.nz, remco@cs.waikato.ac.nz)
27 * @version $Revision: 5996 $
28 */
29import java.awt.Color;
30import java.awt.Container;
31import java.awt.Graphics;
32import java.awt.Graphics2D;
33import java.awt.event.ComponentEvent;
34import java.awt.event.ComponentListener;
35import java.util.Vector;
36
37import javax.swing.JFrame;
38
39import weka.gui.visualize.PrintablePanel;
40
41public class HierarchyVisualizer extends PrintablePanel implements ComponentListener {
42        private static final long serialVersionUID = 1L;
43
44        String m_sNewick;
45        Node m_tree;
46        int m_nLeafs;
47        double m_fHeight;
48        double m_fScaleX = 10;
49        double m_fScaleY = 10;
50
51        public HierarchyVisualizer(String sNewick) {
52                try {
53                        parseNewick(sNewick);
54                } catch (Exception e) {
55                        e.printStackTrace();
56                        System.exit(0);
57                }
58                addComponentListener(this);
59        } // c'tor
60
61        int positionLeafs(Node node, int nPosX) {
62                if (node.isLeaf()) {
63                        node.m_fPosX = nPosX + 0.5;
64                        nPosX++;
65                        return nPosX;
66                } else {
67                        for (int i = 0; i < node.m_children.length; i++) {
68                                nPosX = positionLeafs(node.m_children[i], nPosX);
69                        }
70                }
71                return nPosX;
72        }
73        double positionRest(Node node) {
74                if (node.isLeaf()) {
75                        return node.m_fPosX;
76                } else {
77                        double fPosX = 0;
78                        for (int i = 0; i < node.m_children.length; i++) {
79                                fPosX += positionRest(node.m_children[i]);
80                        }
81                        fPosX /= node.m_children.length;
82                        node.m_fPosX = fPosX;
83                        return fPosX;
84                }
85        }
86        double positionHeight(Node node, double fOffSet) {
87                if (node.isLeaf()) {
88                        node.m_fPosY = fOffSet + node.m_fLength;
89                        return node.m_fPosY;
90                } else {
91                        double fPosY = fOffSet + node.m_fLength;
92                        double fYMax = 0;
93                        for (int i = 0; i < node.m_children.length; i++) {
94                                fYMax = Math.max(fYMax, positionHeight(node.m_children[i], fPosY));
95                        }
96                        node.m_fPosY = fPosY;
97                        return fYMax;
98                }
99        }
100
101        //Vector<String> m_sMetaDataNames;
102        /** class for nodes in building tree data structure **/
103        class Node {
104                double m_fLength = -1;
105                double m_fPosX = 0;
106                double m_fPosY = 0;
107                String m_sLabel;
108                //Vector<String> m_sMetaDataValues;
109                String m_sMetaData;
110
111
112                /** list of children of this node **/
113                Node[] m_children;
114                /** parent node in the tree, null if root **/
115                Node m_Parent = null;
116
117                Node getParent() {
118                        return m_Parent;
119                }
120
121                void setParent(Node parent) {
122                        m_Parent = parent;
123                }
124
125                /** check if current node is root node **/
126                boolean isRoot() {
127                        return m_Parent == null;
128                }
129                boolean isLeaf() {
130                        return m_children == null;
131                }
132
133                /** return nr of children **/
134                int getChildCount() {
135//                      }
136                        if (m_children == null) {return 0;}
137                        return m_children.length;
138                }
139
140                Node getChild(int iChild) {
141                        return m_children[iChild];
142                }
143
144
145                /** count number of nodes in tree, starting with current node **/
146                int getNodeCount() {
147                        if (m_children == null) {
148                                return 1;
149                        }
150                        int n = 1;
151                        for (int i = 0; i < m_children.length; i++) {
152                                n += m_children[i].getNodeCount();
153                        }
154                        return n;
155                }
156                public String toString() {
157                        StringBuffer buf = new StringBuffer();
158                        if (m_children != null) {
159                                buf.append("(");
160                                for (int i = 0; i < m_children.length-1; i++) {
161                                        buf.append(m_children[i].toString());
162                                        buf.append(',');
163                                }
164                                buf.append(m_children[m_children.length - 1].toString());
165                                buf.append(")");
166                        } else {
167                                buf.append(m_sLabel);
168                        }
169                        if (m_sMetaData != null) {
170                                buf.append('[');
171                                buf.append(m_sMetaData);
172                                buf.append(']');
173                        }
174                        buf.append(":" + m_fLength);
175                        return buf.toString();
176                }
177
178                double draw(Graphics g) {
179                        if (isLeaf()) {
180                                int x = (int)(m_fPosX * m_fScaleX);
181                                int y = (int)(m_fPosY * m_fScaleY);
182                                g.drawString(m_sLabel, x, y);
183                                g.drawLine((int)(m_fPosX * m_fScaleX), (int)(m_fPosY * m_fScaleY), (int)(m_fPosX * m_fScaleX), (int)((m_fPosY - m_fLength) * m_fScaleY));
184                        } else {
185                                double fPosX1 = Double.MAX_VALUE;
186                                double fPosX2 = -Double.MAX_VALUE;
187                                for (int i = 0; i < m_children.length; i++) {
188                                        double f = m_children[i].draw(g);
189                                        if (f < fPosX1) {fPosX1 = f;}
190                                        if (f > fPosX2) {fPosX2 = f;}
191                                }
192                                g.drawLine((int)(m_fPosX * m_fScaleX), (int)(m_fPosY * m_fScaleY), (int)(m_fPosX * m_fScaleX), (int)((m_fPosY - m_fLength) * m_fScaleY));
193                                g.drawLine((int)(fPosX1 * m_fScaleX), (int)(m_fPosY * m_fScaleY), (int)(fPosX2 * m_fScaleX), (int)(m_fPosY* m_fScaleY));
194                        }
195                        return m_fPosX;
196                }
197        } // class Node
198
199        /** helper method for parsing Newick tree **/
200        int nextNode(String sStr, int i) {
201                int nBraces = 0;
202                char c = sStr.charAt(i);
203                do {
204                        i++;
205                        if (i < sStr.length()) {
206                                c = sStr.charAt(i);
207                                // skip meta data block
208                                if (c == '[') {
209                                        while (i < sStr.length() && sStr.charAt(i)!=']') {
210                                                i++;
211                                        }
212                                        i++;
213                                        if(i < sStr.length()) {
214                                                c = sStr.charAt(i);
215                                        }
216                                }
217
218                                switch (c) {
219                                case '(':
220                                        nBraces++;
221                                        break;
222                                case ')':
223                                        nBraces--;
224                                        break;
225                                default:
226                                        break;
227                                }
228                        }
229                } while (i < sStr.length()
230                                && (nBraces > 0 || (c != ','&&c != ')'&&c != '(')));
231                if (i >= sStr.length() || nBraces < 0) {
232                        return -1;
233                } else if (sStr.charAt(i) == ')') {
234                        i++;
235                        if (sStr.charAt(i) == '[') {
236                                while (i < sStr.length() && sStr.charAt(i)!=']') {
237                                        i++;
238                                }
239                                i++;
240                                if (i >= sStr.length()) {
241                                        return -1;
242                                }
243                        }
244                        if (sStr.charAt(i) == ':') {
245                                i++;
246                                c = sStr.charAt(i);
247                                while (i < sStr.length() && (c=='.' || Character.isDigit(c))) {
248                                        i++;
249                                        if (i < sStr.length()) {
250                                                c = sStr.charAt(i);
251                                        }
252                                }
253                        }
254                }
255                return i;
256        }
257
258        /**
259         * convert string containing Newick tree into tree datastructure but only in
260         * the limited format as contained in m_sTrees
261         *
262         * @param sStr
263         * @return tree consisting of a Node
264         */
265        void parseNewick(String sNewick) throws Exception {
266                m_sNewick = sNewick;
267                int i = m_sNewick.indexOf('(');
268                if (i > 0) {
269                        m_sNewick = m_sNewick.substring(i);
270                }
271                System.err.println(m_sNewick);
272                m_tree = parseNewick2(m_sNewick);
273                System.err.println(m_tree.toString());
274                m_nLeafs = positionLeafs(m_tree, 0);
275                positionRest(m_tree);
276                m_fHeight = positionHeight(m_tree, 0);
277        }
278
279        Node parseNewick2(String sStr) throws Exception {
280                // System.out.println(sStr);
281                if (sStr == null || sStr.length() == 0) {
282                        return null;
283                }
284                Node node = new Node();
285                if (sStr.startsWith("(")) {
286                        int i1 = nextNode(sStr, 0);
287                        int i2 = nextNode(sStr, i1);
288                        node.m_children = new Node[2];
289                        node.m_children[0] = parseNewick2(sStr.substring(1, i1));
290                        node.m_children[0].m_Parent = node;
291                        String sStr2 = sStr.substring(i1+1, (i2>0?i2:sStr.length()));
292                        node.m_children[1] = parseNewick2(sStr2);
293                        node.m_children[1].m_Parent = node;
294                        if (sStr.lastIndexOf('[') > sStr.lastIndexOf(')')) {
295                                sStr = sStr.substring(sStr.lastIndexOf('['));
296                                i2 = sStr.indexOf(']');
297                                if (i2 < 0) {
298                                        throw new Exception("unbalanced square bracket found:" + sStr);
299                                }
300                                sStr2 = sStr.substring(1, i2);
301                                node.m_sMetaData = sStr2;
302                        }
303                        if (sStr.lastIndexOf(':') > sStr.lastIndexOf(')')) {
304                                sStr = sStr.substring(sStr.lastIndexOf(':'));
305                                sStr = sStr.replaceAll("[,\\):]", "");
306                                node.m_fLength = new Double(sStr);
307                        } else {
308                                node.m_fLength = 1;
309                        }
310                } else {
311                        // it is a leaf
312                        if (sStr.contains("[")) {
313                                // grab metadata
314                                int i1 = sStr.indexOf('[');
315                                int i2 = sStr.indexOf(']');
316                                if (i2 < 0) {
317                                        throw new Exception("unbalanced square bracket found:" + sStr);
318                                }
319                                String sStr2 = sStr.substring(i1+1, i2);
320                                sStr = sStr.substring(0, i1) +sStr.substring(i2+1);
321                                node.m_sMetaData = sStr2;
322                        }
323                        if (sStr.indexOf(')') >= 0) {
324                                sStr = sStr.substring(0, sStr.indexOf(')'));
325                        }
326                        sStr = sStr.replaceFirst("[,\\)]", "");
327                        // System.out.println("parsing <<"+sStr+">>");
328                        if (sStr.length() > 0) {
329                                if (sStr.indexOf(':') >= 0) {
330                                        int iColon = sStr.indexOf(':');
331                                        node.m_sLabel = sStr.substring(0, iColon);
332                                        if (sStr.indexOf(':', iColon+1) >= 0) {
333                                                int iColon2 = sStr.indexOf(':', iColon+1);
334                                                node.m_fLength = new Double(sStr.substring(iColon+1, iColon2));
335                                                m_fTmpLength = new Double(sStr.substring(iColon2+1));
336                                        } else {
337                                                node.m_fLength = new Double(sStr.substring(iColon+1));
338                                        }
339                                } else {
340                                        node.m_sLabel = sStr;
341                                        node.m_fLength = 1;
342                                }
343                        } else {
344                                return null;
345                        }
346                }
347                return node;
348        }
349        double m_fTmpLength;
350
351        /**
352         * Fits the tree to the current screen size. Call this after window has been
353         * created to get the entire tree to be in view upon launch.
354         */
355        public void fitToScreen() {
356                m_fScaleX = 10;
357                int nW = getWidth();
358                if (m_nLeafs > 0) {
359                        m_fScaleX = nW / m_nLeafs;
360                }
361                m_fScaleY = 10;
362                int nH = getHeight();
363                if (m_fHeight > 0) {
364                        m_fScaleY = (nH - 10) / m_fHeight;
365                }
366                repaint();
367        }
368
369        /**
370         * Updates the screen contents.
371         *
372         * @param g
373         *            the drawing surface.
374         */
375        public void paintComponent(Graphics g) {
376                Color oldBackground = ((Graphics2D) g).getBackground();
377                // if (m_BackgroundColor != null)
378                ((Graphics2D) g).setBackground(Color.WHITE);
379                g.clearRect(0, 0, getSize().width, getSize().height);
380                ((Graphics2D) g).setBackground(oldBackground);
381                g.setClip(3, 7, getWidth() - 6, getHeight() - 10);
382                m_tree.draw(g);
383                g.setClip(0, 0, getWidth(), getHeight());
384        }
385
386
387        public void componentHidden(ComponentEvent e) {}
388
389        public void componentMoved(ComponentEvent e) {}
390
391        public void componentResized(ComponentEvent e) {
392                fitToScreen();
393        }
394
395        public void componentShown(ComponentEvent e) {}
396
397        /**
398         * Main method for testing this class.
399         */
400        public static void main(String[] args) {
401              //HierarchyVisualizer a = new HierarchyVisualizer("((((human:2.0,(chimp:1.0,bonobo:1.0):1.0):1.0,gorilla:3.0):1.0,siamang:4.0):1.0,orangutan:5.0)");
402              //HierarchyVisualizer a = new HierarchyVisualizer("(((human:2.0,(chimp:1.0,bonobo:1.0):1.0):1.0,gorilla:3.0):1.0,siamang:4.0)");
403              HierarchyVisualizer a = new HierarchyVisualizer(" (((5[theta=0.121335,lxg=0.122437]:0.00742795,3[theta=0.0972485,lxg=0.152762]:0.00742795)[theta=0.490359,lxg=0.0746703]:0.0183076,((2[theta=0.0866056,lxg=0.2295]:0.00993801,4[theta=0.135512,lxg=0.146674]:0.00993801)[theta=0.897783,lxg=0.0200762]:0.00901206,1[theta=0.200265,lxg=0.18925]:0.0189501)[theta=0.0946195,lxg=0.143427]:0.00678551)[theta=0.185562,lxg=0.139681]:0.0129598,(7[theta=0.176022,lxg=0.364039]:0.0320395,((0[theta=0.224286,lxg=0.156485]:0.0175487,8[theta=0.223313,lxg=0.157166]:0.0175487)[theta=0.631287,lxg=0.024042]:0.00758871,6[theta=0.337871,lxg=0.148799]:0.0251374)[theta=0.33847,lxg=0.040784]:0.00690208)[theta=0.209238,lxg=0.0636202]:0.00665587)[theta=0.560453,lxg=-0.138086]:0.01");
404                  //HierarchyVisualizer a = new HierarchyVisualizer(" ((5[theta=0.121335,lxg=0.122437]:0.00742795,3[theta=0.0972485,lxg=0.152762]:0.00742795)[theta=0.490359,lxg=0.0746703]:0.0183076,2[theta=0.0866056,lxg=0.2295]:0.00993801)[theta=0.897783,lxg=0.0200762]:0.00901206");
405              a.setSize(800 ,600);
406              JFrame f;
407              f = new JFrame();
408              Container contentPane = f.getContentPane();
409              contentPane.add(a);
410              f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
411              f.setSize(800,600);
412              f.setVisible(true);
413              a.fitToScreen();
414          }
415
416} // class HierarchyVisualizer
Note: See TracBrowser for help on using the repository browser.