View Javadoc

    1   package baseCode.dataStructure.graph;
    2
    3   import java.util.ArrayList;
    4   import java.util.Collections;
    5   import java.util.HashMap;
    6   import java.util.Iterator;
    7   import java.util.LinkedHashMap;
    8   import java.util.List;
    9   import java.util.Map;
    10  import java.util.Set;
    11
    12  import javax.swing.JTree;
    13  import javax.swing.tree.DefaultMutableTreeNode;
    14
    15  import baseCode.dataStructure.Queue;
    16
    17  /***
    18   * A graph that contains DirectedGraphNodes. It can be cyclic. Small unconnected parts of the graph will be ignored for
    19   * many operation. Tree traversals start from the root node, which is defined as the node with the most children.
    20   * <p>
    21   * Copyright (c) Columbia University
    22   *
    23   * @todo do something about cyclicity; make this a dag or a subclass...
    24   * @author Paul Pavlidis
    25   * @version $Id: DirectedGraph.java,v 1.8 2004/07/27 03:18:58 pavlidis Exp $
    26   */
    27  public class DirectedGraph extends AbstractGraph {
    28
    29     public DirectedGraph() {
    30        super();
    31     }
    32
    33     /***
    34      * @param nodes Set of DirectedGraphNodes
    35      */
    36     public DirectedGraph( Set nodes ) {
    37        items = new LinkedHashMap();
    38        for ( Iterator it = nodes.iterator(); it.hasNext(); ) {
    39           DirectedGraphNode a = ( DirectedGraphNode ) it.next();
    40           this.addNode( a );
    41        }
    42     }
    43
    44     /***
    45      * @param key Object
    46      * @param item Object
    47      */
    48     public void addNode( Object key, Object item ) {
    49        if ( !items.containsKey( key ) ) {
    50           items.put( key, new DirectedGraphNode( key, item, this ) );
    51        }
    52     }
    53
    54     /***
    55      * Add a child to a particualar node identified by key.
    56      *
    57      * @param key Object
    58      * @param newChildKey Object
    59      * @param newChild Object
    60      */
    61     public void addChildTo( Object key, Object newChildKey, Object newChild ) {
    62        if ( !items.containsKey( newChild ) ) {
    63           this.addNode( newChildKey, newChild );
    64        }
    65
    66        this.addChildTo( key, newChildKey );
    67        this.addParentTo( newChildKey, key );
    68     }
    69
    70     /***
    71      * Add a child to a particular node identified by key; if the node is not in the graph, an exception is thrown.
    72      *
    73      * @param key Object
    74      * @param newChildKey Object
    75      * @throws IllegalStateException if the graph doesn't contain the child node.
    76      */
    77     public void addChildTo( Object key, Object newChildKey )
    78           throws IllegalStateException {
    79        if ( !items.containsKey( newChildKey ) ) {
    80           throw new IllegalStateException(
    81                 "Attempt to add link to node that is not in the graph" );
    82        }
    83
    84        if ( items.containsKey( key ) ) {
    85           ( ( DirectedGraphNode ) items.get( key ) ).addChild( newChildKey );
    86           ( ( DirectedGraphNode ) items.get( newChildKey ) ).addParent( key );
    87        }
    88
    89     }
    90
    91     /***
    92      * @param key Object
    93      * @param newParentKey Object
    94      * @param newParent Object
    95      */
    96     public void addParentTo( Object key, Object newParentKey, Object newParent ) {
    97        if ( !items.containsKey( newParent ) ) {
    98           this.addNode( newParentKey, newParent );
    99        }
    100
    101       this.addChildTo( key, newParentKey );
    102       this.addParentTo( newParentKey, key );
    103    }
    104
    105    /***
    106     * @param key Object
    107     * @param newParentKey Object
    108     * @throws IllegalStateException
    109     */
    110    public void addParentTo( Object key, Object newParentKey )
    111          throws IllegalStateException {
    112       if ( !items.containsKey( newParentKey ) ) {
    113          throw new IllegalStateException(
    114                "Attempt to add link to node that is not in the graph" );
    115       }
    116
    117       if ( items.containsKey( key ) ) {
    118          ( ( DirectedGraphNode ) items.get( key ) ).addParent( newParentKey );
    119          ( ( DirectedGraphNode ) items.get( newParentKey ) ).addChild( key );
    120       }
    121
    122    }
    123
    124    /***
    125     * Shows the tree as a tabbed list. Items that have no parents are shown at the 'highest' level.
    126     *
    127     * @return String
    128     */
    129    public String toString() {
    130       prune();
    131       this.topoSort();
    132       List nodes = new ArrayList( items.values() );
    133       Collections.sort( nodes );
    134       DirectedGraphNode root = ( DirectedGraphNode ) nodes.get( 0 );
    135       StringBuffer buf = new StringBuffer();
    136       int tablevel = 0;
    137       makeString( root, buf, tablevel );
    138       return ( buf.toString() );
    139    }
    140
    141    /*
    142     * Helper for toString. Together with toString, demonstrates how to iterate over the tree
    143     */
    144    private String makeString( DirectedGraphNode startNode, StringBuffer buf,
    145          int tabLevel ) {
    146
    147       if ( buf == null ) {
    148          buf = new StringBuffer();
    149       }
    150
    151       Set children = startNode.getChildNodes();
    152
    153       if ( !startNode.isVisited() ) {
    154          buf.append( startNode + "\n" );
    155          startNode.mark();
    156       }
    157       tabLevel++;
    158       for ( Iterator it = children.iterator(); it.hasNext(); ) {
    159          DirectedGraphNode f = ( DirectedGraphNode ) it.next();
    160          if ( !f.isVisited() ) {
    161             for ( int i = 0; i < tabLevel; i++ ) {
    162                buf.append( "\t" );
    163             }
    164             buf.append( f + "\n" );
    165             f.mark();
    166             this.makeString( f, buf, tabLevel );
    167          }
    168       }
    169
    170       return buf.toString();
    171    }
    172
    173    /***
    174     * Remove vertices to nodes that aren't in the graph.
    175     */
    176    public void prune() {
    177       for ( Iterator it = this.items.keySet().iterator(); it.hasNext(); ) {
    178          DirectedGraphNode v = ( DirectedGraphNode ) items.get( it.next() );
    179          v.prune();
    180       }
    181    }
    182
    183    /***
    184     * Fills in the topoSortOrder for each node.
    185     */
    186    public void topoSort() {
    187       Queue q = new Queue();
    188       int counter = 0;
    189       DirectedGraphNode v;
    190       Map degrees = new HashMap();
    191
    192       /* Get the degrees of all items, and enqueue zero-indegree nodes */
    193       for ( Iterator it = this.items.keySet().iterator(); it.hasNext(); ) {
    194          v = ( DirectedGraphNode ) items.get( it.next() );
    195          degrees.put( v, new Integer( v.inDegree() ) );
    196          if ( ( ( Integer ) degrees.get( v ) ).intValue() == 0 ) {
    197             q.enqueue( v );
    198          }
    199       }
    200
    201       while ( !q.isEmpty() ) {
    202          v = ( DirectedGraphNode ) q.dequeue();
    203          v.setTopoSortOrder( ++counter );
    204          for ( Iterator vit = v.getChildNodes().iterator(); vit.hasNext(); ) {
    205             DirectedGraphNode w = ( DirectedGraphNode ) vit.next();
    206             /* decrement the degree of this node */
    207             int inDegree = ( ( Integer ) degrees.get( w ) ).intValue();
    208             inDegree--;
    209             degrees.put( w, new Integer( inDegree ) );
    210
    211             /* see if this now is one of the zero-indegree nodes */
    212             if ( inDegree == 0 ) {
    213                q.enqueue( w );
    214             }
    215          }
    216       }
    217
    218       if ( counter != items.size() ) {
    219          throw new IllegalStateException( "Graph contains a cycle; " + counter
    220                + " items found, " + items.size() + " expected" );
    221       }
    222
    223    }
    224
    225    /***
    226     * Generate a JTree corresponding to this graph.
    227     *
    228     * @todo note that nodes are only allowed to have one parent in DefaultMutableTreeNodes
    229     * @return javax.swing.JTree
    230     */
    231    public JTree treeView() {
    232       this.topoSort();
    233       List nodes = new ArrayList( items.values() );
    234       Collections.sort( nodes );
    235       DirectedGraphNode root = ( DirectedGraphNode ) nodes.get( 0 );
    236       DefaultMutableTreeNode top = new DefaultMutableTreeNode( root );
    237       root.mark();
    238       addJTreeNode( top, root );
    239       JTree tree = new JTree( top );
    240       return tree;
    241    }
    242
    243    private void addJTreeNode( DefaultMutableTreeNode startJTreeNode,
    244          DirectedGraphNode startNode ) {
    245       Set children = startNode.getChildNodes();
    246
    247       for ( Iterator it = children.iterator(); it.hasNext(); ) {
    248          DirectedGraphNode nextNode = ( DirectedGraphNode ) it.next();
    249          if ( !nextNode.isVisited() ) {
    250             DefaultMutableTreeNode newJTreeNode = new DefaultMutableTreeNode(
    251                   nextNode );
    252             startJTreeNode.add( newJTreeNode );
    253             nextNode.mark();
    254             this.addJTreeNode( newJTreeNode, nextNode );
    255          }
    256       }
    257
    258    }
    259
    260 }