1   /****************************************************************************
2    **
3    ** This file is part of yFiles-2.6. 
4    ** 
5    ** yWorks proprietary/confidential. Use is subject to license terms.
6    **
7    ** Redistribution of this file or of an unauthorized byte-code version
8    ** of this file is strictly forbidden.
9    **
10   ** Copyright (c) 2000-2008 by yWorks GmbH, Vor dem Kreuzberg 28, 
11   ** 72070 Tuebingen, Germany. All rights reserved.
12   **
13   ***************************************************************************/
14  package demo.base;
15  
16  import java.util.HashMap;
17  import java.util.Map;
18  import y.util.Maps;
19  import y.util.Timer;
20  import y.util.D;
21  import y.base.Graph;
22  import y.base.NodeMap;
23  import y.base.NodeCursor;
24  import y.base.Node;
25  
26  
27  /**
28   * This class compares the performance of different 
29   * mechanisms to bind extra data to the nodes of a graph.
30   * In scenarios where the indices of the nodes do not change
31   * while the extra node data is needed, it is best to use array based
32   * mechanisms that use the index of a node to access the data.
33   * <br>
34   * In scenarios where the indices of the nodes will change
35   * while the extra node data is needed, it is necessary to
36   * use nodemaps that do not depend on the indices of the nodes
37   * (see {@link Node#index()}) or Map implementations like HashMap 
38   * provided by the java collections framework.
39   */
40  public class NodeMapTest
41  {
42    
43    static Timer t1 = new Timer(false);
44    static Timer t2 = new Timer(false);
45    static Timer t3 = new Timer(false);
46    static Timer t4 = new Timer(false);
47    static Timer t5 = new Timer(false);
48    
49    public static void main(String args[])
50    {
51      test1();
52    }
53    
54    static void test1()
55    {
56      Graph graph = new Graph();
57      for(int i = 0; i < 20000; i++) graph.createNode();
58      
59      for(int loop = 0; loop < 10; loop++)
60      {
61        D.bu(".");
62        
63        t1.start();
64        NodeMap map = graph.createNodeMap();
65        for(int i = 0; i < 10; i++)
66        {
67          for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next())
68          {
69            Node v = nc.node();
70            map.setInt(v,i);
71            i = map.getInt(v);
72          }
73        }
74        graph.disposeNodeMap(map);
75        t1.stop();
76        
77        
78        t2.start();
79        map = Maps.createIndexNodeMap(new int[graph.N()]);
80        for(int i = 0; i < 10; i++)
81        {
82          for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next())
83          {
84            Node v = nc.node();
85            map.setInt(v,i);
86            map.getInt(v);
87          }
88        }
89        t2.stop();
90        
91        
92        t3.start();
93        map = Maps.createHashedNodeMap(); 
94        for(int i = 0; i < 10; i++)
95        {
96          for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next())
97          {
98            Node v = nc.node();
99            map.setInt(v, i);
100           i = map.getInt(v);
101         }
102       }
103       t3.stop();
104       
105       t4.start();
106       int[] array = new int[graph.N()];
107       for(int i = 0; i < 10; i++)
108       {
109         for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next())
110         {
111           int vid = nc.node().index();
112           array[vid] = i;
113           i = array[vid];
114         }
115       }
116       t4.stop();
117 
118     
119       t5.start();
120       Map jmap = new HashMap(2*graph.N()+1); //use hash map with good initial size
121       for(int i = 0; i < 10; i++)
122       {
123         for(NodeCursor nc = graph.nodes(); nc.ok(); nc.next())
124         {
125           Node v = nc.node();
126           jmap.put(v, new Integer(i));
127           i = ((Integer)jmap.get(v)).intValue();
128         }
129       }
130       t5.stop();
131       
132     }
133     
134     D.bug("");
135     D.bug("TIME:  standard NodeMap: " + t1);
136     D.bug("TIME:  index    NodeMap: " + t2);
137     D.bug("TIME:  hashed   NodeMap: " + t3);
138     D.bug("TIME:  plain array     : " + t4);
139     D.bug("TIME:  HashMap         : " + t5);
140   }
141 }
142 
143     
144     
145     
146