View Javadoc

    1   package baseCode.dataStructure.graph;
    2
    3   import java.util.Iterator;
    4   import java.util.LinkedHashSet;
    5   import java.util.Set;
    6
    7   /***
    8    * A graph node that has the concept of parents and children. Keys can be anything, but probably Strings or Integers.
    9    * <p>
    10   * Copyright (c) Columbia University
    11   *
    12   * @author Paul Pavlidis
    13   * @version $Id: DirectedGraphNode.java,v 1.10 2004/07/27 03:18:58 pavlidis Exp $
    14   */
    15  public class DirectedGraphNode extends AbstractGraphNode implements Comparable {
    16
    17     protected Set parents;
    18     // immeddiate parents, references to other GraphNodes by keys.
    19     protected Set children;
    20     // immediate children, references to other GraphNodes by keys.
    21
    22     protected int topoSortOrder = 0;
    23
    24     /***
    25      * @param key Object
    26      * @param value Object
    27      * @param graph Graph
    28      */
    29     public DirectedGraphNode( Object key, Object value, Graph graph ) {
    30        super( key, value, graph );
    31        parents = new LinkedHashSet();
    32        children = new LinkedHashSet();
    33     }
    34
    35     /***
    36      * @param i int
    37      */
    38     public void setTopoSortOrder( int i ) {
    39        topoSortOrder = i;
    40     }
    41
    42     /***
    43      * @return int
    44      */
    45     public int getTopoSortOrder() {
    46        return topoSortOrder;
    47     }
    48
    49     /***
    50      * @param newChildKey Object
    51      */
    52     public void addChild( Object newChildKey ) {
    53        children.add( newChildKey );
    54     }
    55
    56     /***
    57      * @param newParentKey Object
    58      */
    59     public void addParent( Object newParentKey ) {
    60        parents.add( newParentKey );
    61     }
    62
    63     /***
    64      * @return Object
    65      */
    66     public Object getParentKeys() {
    67        return parents;
    68     }
    69
    70     /***
    71      * @return Object
    72      */
    73     public Object getChildKeys() {
    74        return children;
    75     }
    76
    77     /***
    78      * Get the immediate children of this node. References to the DirectedGraphNodes are given, as opposed to key values.
    79      *
    80      * @return Set containing the child nodes of this node.
    81      */
    82     public Set getChildNodes() {
    83        Set f = new LinkedHashSet();
    84        for ( Iterator i = this.getChildIterator(); i.hasNext(); ) {
    85           Object k = i.next();
    86           f.add( getGraph().get( k ) );
    87        }
    88        return f;
    89     }
    90
    91     /***
    92      * Get the immediate parents of this node. References to the DirectedGraphNodes are given, as opposed to key values.
    93      *
    94      * @return Set
    95      */
    96     public Set getParentNodes() {
    97        Set f = new LinkedHashSet();
    98        for ( Iterator i = this.getParentIterator(); i.hasNext(); ) {
    99           Object k = i.next();
    100          f.add( getGraph().get( k ) );
    101       }
    102       return f;
    103    }
    104
    105    /***
    106     * Get the subgraph starting from this node, including this node.
    107     *
    108     * @return Graph
    109     */
    110    public Graph getChildGraph() {
    111       Set k = this.getAllChildNodes();
    112       k.add( this );
    113
    114       DirectedGraph returnVal = new DirectedGraph();
    115       for ( Iterator it = k.iterator(); it.hasNext(); ) {
    116          DirectedGraphNode m = ( DirectedGraphNode ) it.next();
    117          returnVal.addNode( ( DirectedGraphNode ) m.clone() );
    118       }
    119       returnVal.prune(); // failing to do this will cause all kinds of problems
    120       return returnVal;
    121    }
    122
    123
    124
    125    /***
    126     * @return
    127     */
    128    public boolean isLeaf() {
    129       return children.size() == 0;
    130    }
    131
    132    /***
    133     * @return int number of immediate children this node has.
    134     */
    135    public int outDegree() {
    136       return children.size();
    137    }
    138
    139    /***
    140     * @return int number of immediate parents this node has.
    141     */
    142    public int inDegree() {
    143       return parents.size();
    144    }
    145
    146    /***
    147     * @return int how many children this node has, determined recursively.
    148     */
    149    public int numChildren() {
    150       return getAllChildNodes( null ).size();
    151    }
    152
    153    /***
    154     * @return int how many parents this node has, determined recursively.
    155     */
    156    public int numParents() {
    157       return getAllParentNodes( null ).size();
    158    }
    159
    160    /***
    161     * Get all the children of this node, recursively.
    162     */
    163    public Set getAllChildNodes() {
    164       return this.getAllChildNodes( null );
    165    }
    166
    167    /***
    168     * Get all the parents of this node, recursively.
    169     *
    170     * @return
    171     */
    172    public Set getAllParentNodes() {
    173       return this.getAllParentNodes( null );
    174    }
    175
    176    /***
    177     * Check to see if this node has a particular immediate child.
    178     *
    179     * @param j Object
    180     * @return boolean
    181     */
    182    public boolean hasChild( Object j ) {
    183       return children.contains( j );
    184    }
    185
    186    /***
    187     * Check to see if this node has a particular immediate parent.
    188     *
    189     * @param j Object
    190     * @return boolean
    191     */
    192    public boolean hasParent( Object j ) {
    193       return parents.contains( j );
    194    }
    195
    196    public String toString() {
    197       return this.getItem().toString();
    198    }
    199
    200    /***
    201     * Remove connections that are to nodes not contained in this graph
    202     */
    203    public void prune() {
    204       for ( Iterator it = this.getChildIterator(); it.hasNext(); ) {
    205          Object j = it.next();
    206          DirectedGraphNode k = ( DirectedGraphNode ) getGraph().get( j );
    207          if ( k == null ) {
    208             if ( log.isDebugEnabled() ) {
    209                log.debug( "Pruned child " + j + " from " + this );
    210             }
    211             children.remove( j );
    212          }
    213
    214       }
    215
    216       for ( Iterator it = this.getParentIterator(); it.hasNext(); ) {
    217          Object j = it.next();
    218          DirectedGraphNode k = ( DirectedGraphNode ) getGraph().get( j );
    219          if ( k == null ) {
    220             if ( log.isDebugEnabled() ) {
    221                log.debug( "Pruned parent " + j + " from " + this );
    222             }
    223             parents.remove( j );
    224          }
    225
    226       }
    227
    228    }
    229
    230    /*** ************* private methods *************** */
    231
    232    private Set getAllChildNodes( Set list ) {
    233       if ( list == null ) {
    234          list = new LinkedHashSet();
    235       }
    236
    237       for ( Iterator it = this.getChildIterator(); it.hasNext(); ) {
    238          Object j = it.next();
    239          list.add( getGraph().get( j ) );
    240          ( ( DirectedGraphNode ) getGraph().get( j ) ).getAllChildNodes( list );
    241       }
    242       return list;
    243    }
    244
    245    private Set getAllParentNodes( Set list ) {
    246       if ( list == null ) {
    247          list = new LinkedHashSet();
    248       }
    249
    250       for ( Iterator it = this.getParentIterator(); it.hasNext(); ) {
    251          Object j = it.next();
    252          list.add( getGraph().get( j ) );
    253          ( ( DirectedGraphNode ) getGraph().get( j ) ).getAllParentNodes( list );
    254       }
    255       return list;
    256    }
    257
    258    private Iterator getChildIterator() {
    259       return children.iterator();
    260    }
    261
    262    private Iterator getParentIterator() {
    263       return parents.iterator();
    264    }
    265
    266    /***
    267     * Uses the topological sort order.
    268     *
    269     * @param o Object
    270     * @return int
    271     */
    272    public int compareTo( Object o ) {
    273       DirectedGraphNode k = ( DirectedGraphNode ) o;
    274       int ord = k.getTopoSortOrder();
    275       if ( ord < this.topoSortOrder ) {
    276          return 1;
    277       } else if ( ord > this.topoSortOrder ) {
    278          return -1;
    279       }
    280       return 0;
    281    }
    282
    283    /***
    284     * Makes a copy of this node. It does not make a deep copy of the contents. This should be used when making
    285     * subgraphs.
    286     *
    287     * @return Object
    288     */
    289    public Object clone() {
    290       DirectedGraphNode r = new DirectedGraphNode( key, item, graph );
    291       for ( Iterator it = this.getParentIterator(); it.hasNext(); ) {
    292          Object j = it.next();
    293          r.addParent( j );
    294       }
    295
    296       for ( Iterator it = this.getChildIterator(); it.hasNext(); ) {
    297          Object j = it.next();
    298          r.addChild( j );
    299       }
    300       return r;
    301    }
    302
    303 }