View Javadoc

1   /*
2    * Copyright 2004 Ronald Blaschke.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    *      http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  package org.rblasch.convert.graph;
17  
18  import java.util.Collections;
19  import java.util.HashSet;
20  import java.util.Iterator;
21  import java.util.Set;
22  
23  public final class SparseWeightedDirectedGraph implements WeightedDirectedGraph {
24      private final Set /* of Vertex */ vertices = new HashSet();
25      private final Set /* of WeightedDirectedEdge */ edges = new HashSet();
26      private final Set /* of Connection */ connections = new HashSet();
27  
28      public Set /* of Vertex */ getVertices() {
29          return Collections.unmodifiableSet(vertices);
30      }
31  
32      public Set /* of WeightedDirectedEdge */ getEdges() {
33          return Collections.unmodifiableSet(edges);
34      }
35  
36      public void addVertex(final Vertex v) {
37          vertices.add(v);
38      }
39  
40      /***
41       * Enter a new segment in the graph.
42       */
43      public void addConnection(final Vertex start, final Edge edge, final Vertex end) {
44          vertices.add(start);
45          edges.add(edge);
46          vertices.add(end);
47          connections.add(new Connection(start, edge, end));
48      }
49  
50      public Set/*<Connection>*/ getAllConnections() {
51          return Collections.unmodifiableSet(connections);
52      }
53  
54      public Set /* of Connection */ getConnections(final Vertex start, final Vertex end) {
55          final Set /* of Connection */ cons = new HashSet();
56          for (final Iterator i = connections.iterator(); i.hasNext();) {
57              final Connection c = (Connection) i.next();
58              if (c.getStart().equals(start) && c.getEnd().equals(end)) {
59                  cons.add(c);
60              }
61          }
62          return cons;
63      }
64  
65      /***
66       * Get the list of vertices that can be reached from the given vertex.
67       */
68      public Set /* Vertex */ getOutbound(final Vertex vertex) {
69          final Set destinations = new HashSet();
70  
71          for (final Iterator i = connections.iterator(); i.hasNext();) {
72              final Connection c = (Connection) i.next();
73              if (c.getStart().equals(vertex)) {
74                  destinations.add(c.getEnd());
75              }
76          }
77  
78          return destinations;
79      }
80  
81      /***
82       * Get the list of vertices that lead to the given vertex.
83       */
84      public Set /* of Vertex */ getInbound(final Vertex vertex) {
85          final Set predecessors = new HashSet();
86  
87          for (final Iterator i = connections.iterator(); i.hasNext();) {
88              final Connection c = (Connection) i.next();
89              if (c.getEnd().equals(vertex)) {
90                  predecessors.add(c.getStart());
91              }
92          }
93  
94          return predecessors;
95      }
96  
97      public boolean equals(final Object obj) {
98          if (this == obj) return true;
99          if (!(obj instanceof SparseWeightedDirectedGraph)) return false;
100 
101         final SparseWeightedDirectedGraph rhs = (SparseWeightedDirectedGraph) obj;
102         if (!edges.equals(rhs.edges)) return false;
103         if (!vertices.equals(rhs.vertices)) return false;
104 
105         return true;
106     }
107 
108     public int hashCode() {
109         int result = vertices.hashCode();
110         result = 29 * result + edges.hashCode();
111         return result;
112     }
113 
114     public String toString() {
115         return connections.toString();
116     }
117 }