number of nodes vs speed

Anonymous
2003-04-11
2013-04-08
  • Anonymous - 2003-04-11

    Great program.  I have been creating graphs using touchgraph by extracting node and edge information from a mysql database.  A big limitation that I have experienced is the number of nodes that can be drawn/displayed.  The program is not very responsive with a graph that contains 300 or so nodes.  I am now going through the TGLayout class to see if there is anything that I can do to speed things up.  If anyone could give me some direction, I would be very appreciative.

    Thanks.

    Tom Burgoyne

     
    • Franz Achermann

      Franz Achermann - 2003-12-02

      Hi,
      I had a similar comment. Essentially the class GraphEltSet wants the whole graph in memory. The nodes and edges are stored all over the place. I tried to extract an interface representing an MutableGraph such that GraphEltSet (which sould be renamed to InMemoryGraph) implements this interface. In order to try out the interface, I implemented a class "Ladder" which creates a ladder with n dummy nodes, and initially only 4 nodes are visible. The nodes are created lazily.
      Here is how far I got:
      * I could do the refactoring but had to move several methods from GraphEltSet because the TGPanel iterates over all nodes of the graph.
      * The class Ladder raises exceptions when I try to add nodes etc.
      * Rendering the ladder works reasonable up to approx 1000 nodes (although the topology is of special).
      * Before giving the code away I would like if some "knowledgeable" can browse and comment it. As I am short of time, I would like if someone could merge my changes back to the touchgraph library if that is whished.
      Is anybody interested in helping?

       
    • mksheoran

      mksheoran - 2005-10-19

      Seem good work. Could you please show the code done by you?

       
    • whof

      whof - 2005-10-24

      Echoing some of what Franz said, I also found that in GraphEltSet the collection of nodes and edges are stored in Vectors, and there are two "contains" functions (one for nodes, one for edges) that use the Vector.contains method - this is slow (order n) for large numbers of nodes and edges, and if I remember correctly these get called everytime you add a node or edge to the graph.
      If your node ids are unique (and they should be) you can reimplement the node "contains" to use the nodeIDRegistry instead (the same as "findNodes") does, this uses a Hashtable which is much faster (order log n?).  I also created an edgeIDRegistry to do the same for the edges "contains" function.

          protected Hashtable nodeIDRegistry = null;
          protected Hashtable edgeIDRegistry = null;

          public GraphEltSet() {
              nodes = new Vector();
              edges = new Vector();
              nodeIDRegistry = new Hashtable(); // registry of Node IDs
              edgeIDRegistry = new Hashtable(); // registry of Edge IDs
          }

          public boolean contains( Node node ) {
      //      return nodes.contains(node);
              if (findNode(node.getID()) != null)
                  return true;
              return false;
          }

          public boolean contains( Edge edge ) {
      //      return edges.contains(edge);
              if (findEdge(edge.getID()) != null)
                  return true;
              return false;
          }

          public void addEdge( Edge edge ) {
              if ( edge == null ) return;
              if (edge.getID() == null)
                  edge.setID(edge.from.getID() + "@" + edge.to.getID());
              if(!contains(edge)) {
                  edgeIDRegistry.put(edge.getID(), edge);
                  edges.addElement(edge);
                  edge.from.addEdge(edge);
                  edge.to.addEdge(edge);
              }
          }

          public Node findNode( String id ) {
              if ( id == null ) return null; // ignore
              return (Node)nodeIDRegistry.get(id);
          }

          public Edge findEdge( String id ) {
              if ( id == null ) return null; // ignore
              return (Edge)edgeIDRegistry.get(id);
          }

      I also implemented a dynamic loading routine that only loads part of the graph (a radius of 2 or 3 from the starting node) and then only loads more as the user clicks on the outer nodes.

       
      • whof

        whof - 2005-10-24

        Whoops - I forgot this bit:

            public void clearAll() {
                synchronized(nodes) {
                    synchronized(edges) {
                        nodes.removeAllElements();
                        edges.removeAllElements();
                        nodeIDRegistry.clear();
                        edgeIDRegistry.clear();
                    }
                }
            }

         

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:





No, thanks