View Javadoc

1   /*
2    * Created on Oct 17, 2005
3    *
4    * Copyright (c) 2005, the JUNG Project and the Regents of the University 
5    * of California
6    * All rights reserved.
7    *
8    * This software is open-source under the BSD license; see either
9    * "license.txt" or
10   * http://jung.sourceforge.net/license.txt for a description.
11   */
12  package edu.uci.ics.jung.graph;
13  
14  import java.util.Collection;
15  import java.util.Collections;
16  import java.util.LinkedHashMap;
17  import java.util.LinkedHashSet;
18  import java.util.Set;
19  
20  import org.apache.commons.collections15.Factory;
21  
22  import edu.uci.ics.jung.graph.util.Pair;
23  
24  
25  /**
26   * An implementation of <code>DirectedGraph</code>, suitable for sparse graphs, 
27   * that orders its vertex and edge collections
28   * according to insertion time.
29   */
30  @SuppressWarnings("serial")
31  public class DirectedOrderedSparseMultigraph<V,E> 
32      extends DirectedSparseMultigraph<V,E>
33      implements DirectedGraph<V,E>, MultiGraph<V,E> 
34  {
35      /**
36       * Returns a {@code Factory} that creates an instance of this graph type.
37       * @param <V> the vertex type for the graph factory
38       * @param <E> the edge type for the graph factory
39       */
40  	public static <V,E> Factory<DirectedGraph<V,E>> getFactory() {
41  		return new Factory<DirectedGraph<V,E>> () {
42  			public DirectedGraph<V,E> create() {
43  				return new DirectedOrderedSparseMultigraph<V,E>();
44  			}
45  		};
46  	}
47  
48      /**
49       * Creates a new instance.
50       */
51      public DirectedOrderedSparseMultigraph() {
52          vertices = new LinkedHashMap<V, Pair<Set<E>>>();
53          edges = new LinkedHashMap<E, Pair<V>>();
54      }
55      
56      @Override
57      public boolean addVertex(V vertex) {
58      	if(vertex == null) {
59      		throw new IllegalArgumentException("vertex may not be null");
60      	}
61          if (!containsVertex(vertex)) {
62              vertices.put(vertex, new Pair<Set<E>>(new LinkedHashSet<E>(), new LinkedHashSet<E>()));
63              return true;
64          } else {
65              return false;
66          }
67      }
68  
69      @Override
70      public Collection<V> getPredecessors(V vertex) {
71          if (!containsVertex(vertex)) 
72              return null;
73          Set<V> preds = new LinkedHashSet<V>();
74          for (E edge : getIncoming_internal(vertex))
75              preds.add(this.getSource(edge));
76          
77          return Collections.unmodifiableCollection(preds);
78      }
79  
80      @Override
81      public Collection<V> getSuccessors(V vertex) {
82          if (!containsVertex(vertex)) 
83              return null;
84          Set<V> succs = new LinkedHashSet<V>();
85          for (E edge : getOutgoing_internal(vertex))
86              succs.add(this.getDest(edge));
87          
88          return Collections.unmodifiableCollection(succs);
89      }
90  
91      @Override
92      public Collection<V> getNeighbors(V vertex) {
93          if (!containsVertex(vertex)) 
94              return null;
95          Collection<V> neighbors = new LinkedHashSet<V>();
96          for (E edge : getIncoming_internal(vertex))
97              neighbors.add(this.getSource(edge));
98          for (E edge : getOutgoing_internal(vertex))
99              neighbors.add(this.getDest(edge));
100         return Collections.unmodifiableCollection(neighbors);
101     }
102 
103     @Override
104     public Collection<E> getIncidentEdges(V vertex) {
105         if (!containsVertex(vertex)) 
106             return null;
107         Collection<E> incident = new LinkedHashSet<E>();
108         incident.addAll(getIncoming_internal(vertex));
109         incident.addAll(getOutgoing_internal(vertex));
110         return incident;
111     }
112 
113 }