Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | package edu.uci.ics.jung.graph.impl; | |
11 | ||
12 | import java.util.Collections; | |
13 | import java.util.LinkedHashSet; | |
14 | import java.util.Set; | |
15 | ||
16 | import edu.uci.ics.jung.graph.ArchetypeEdge; | |
17 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
18 | import edu.uci.ics.jung.graph.ArchetypeVertex; | |
19 | import edu.uci.ics.jung.graph.Edge; | |
20 | import edu.uci.ics.jung.graph.Graph; | |
21 | import edu.uci.ics.jung.graph.Vertex; | |
22 | import edu.uci.ics.jung.utils.Pair; | |
23 | ||
24 | /** | |
25 | * This class provides a skeletal implementation of the <code>Edge</code> | |
26 | * interface to minimize the effort required to implement this interface. | |
27 | * It is appropriate for sparse graphs (those in which each vertex | |
28 | * is connected to only a few other vertices); for dense graphs (those in | |
29 | * which each vertex is connected to most other vertices), another | |
30 | * implementation might be more appropriate. | |
31 | * <P> | |
32 | * This class extends <code>UserData</code>, which provides storage and | |
33 | * retrieval mechanisms for user-defined data for each edge instance. | |
34 | * This allows users to attach data to edges without having to extend | |
35 | * this class. | |
36 | * | |
37 | * @author Joshua O'Madadhain | |
38 | * @author Danyel Fisher | |
39 | * @author Scott White | |
40 | * | |
41 | * @see AbstractSparseGraph | |
42 | * @see AbstractSparseVertex | |
43 | */ | |
44 | public abstract class AbstractSparseEdge extends AbstractArchetypeEdge implements Edge | |
45 | { | |
46 | /** | |
47 | * One of the two incident vertices of this edge. If this edge is | |
48 | * directed, this is its source. | |
49 | */ | |
50 | protected Vertex mFrom; | |
51 | ||
52 | /** | |
53 | * One of the two incident vertices of this edge. If this edge is | |
54 | * directed, this is its destination. | |
55 | */ | |
56 | protected Vertex mTo; | |
57 | ||
58 | /** | |
59 | * The next edge ID. | |
60 | */ | |
61 | 67 | private static int nextGlobalEdgeID = 0; |
62 | ||
63 | ||
64 | /** | |
65 | * Creates an edge connecting vertices <code>from</code> and | |
66 | * <code>to</code>. The order of the arguments is significant for | |
67 | * implementations of | |
68 | * <code>DirectedEdge</code> which extend this class, and is not | |
69 | * significant for implementations of <code>UndirectedEdge</code> | |
70 | * which extend this class. | |
71 | * <P> | |
72 | * Disallows the following: | |
73 | * <ul> | |
74 | * <li>null arguments | |
75 | * <li>arguments which are not elements of the same graph | |
76 | * <li>arguments which are not elements of any graph (orphaned vertices) | |
77 | * <li>parallel edges (> 1 edge connecting vertex <code>from<code> to | |
78 | * vertex <code>to</code>) | |
79 | * </ul> | |
80 | * Any of these will cause an <code>IllegalArgumentException</code> to | |
81 | * be thrown. | |
82 | * | |
83 | * @param from one incident vertex (if edge is directed, the source) | |
84 | * @param to the other incident vertex (if edge is directed, the destination) | |
85 | * @throws IllegalArgumentException | |
86 | */ | |
87 | public AbstractSparseEdge(Vertex from, Vertex to) | |
88 | { | |
89 | 147361 | super(); |
90 | 147361 | if (from == null || to == null) |
91 | 2 | throw new IllegalArgumentException("Vertices passed in can not be null"); |
92 | ||
93 | 147359 | if( from.getGraph() != to.getGraph()) |
94 | 3 | throw new IllegalArgumentException("Vertices must be from same graph"); |
95 | ||
96 | 147356 | if (from.getGraph() == null || to.getGraph() == null) |
97 | 0 | throw new IllegalArgumentException("Orphaned vertices can not " + |
98 | "be connected by an edge"); | |
99 | ||
100 | 147356 | mFrom = from; |
101 | 147356 | mTo = to; |
102 | ||
103 | 147356 | this.id = nextGlobalEdgeID++; |
104 | 147356 | } |
105 | ||
106 | ||
107 | /** | |
108 | * Returns a human-readable representation of this edge. | |
109 | * | |
110 | * @see java.lang.Object#toString() | |
111 | */ | |
112 | public String toString() | |
113 | { | |
114 | 58 | return "E" + String.valueOf(id) + "(" + mFrom.toString() + "," + mTo.toString() + ")"; |
115 | } | |
116 | ||
117 | /** | |
118 | * Attaches this edge to the specified graph, and invokes the methods that | |
119 | * add this edge to the incident vertices' data structures. | |
120 | * <P> | |
121 | * <b>Note</b>: this method will not properly update the incident | |
122 | * vertices' data structures unless the vertices are instances of | |
123 | * <code>AbstractSparseVertex</code>. | |
124 | * | |
125 | * @param graph the graph to which this edge is being added | |
126 | */ | |
127 | void addGraph_internal(AbstractSparseGraph graph) { | |
128 | ||
129 | // we already checked for null in the constructor, so we don't need to check here | |
130 | 148248 | if (graph != mFrom.getGraph() ) |
131 | 2 | throw new IllegalArgumentException("graph to which edge " + |
132 | "is being added does not match graph of incident vertices " + | |
133 | mFrom + " " + mTo ); | |
134 | ||
135 | 148246 | super.addGraph_internal(graph); |
136 | ||
137 | // In theory, we could do this in the constructor. The problem with | |
138 | // doing so is that we'd have to figure out a way for neighbors, etc. | |
139 | // to be removed automatically via garbage collection. (Which we | |
140 | // could probably do with WeakReferences, but that puts the burden on the | |
141 | // vertex implementor to cope.) | |
142 | 148246 | if (mFrom instanceof AbstractSparseVertex) |
143 | 148246 | ((AbstractSparseVertex)mFrom).addNeighbor_internal( this, mTo ); |
144 | ||
145 | 148239 | if (mTo instanceof AbstractSparseVertex) |
146 | 148239 | ((AbstractSparseVertex)mTo).addNeighbor_internal( this, mFrom ); |
147 | 148239 | } |
148 | ||
149 | /** | |
150 | * @see edu.uci.ics.jung.graph.ArchetypeEdge#getIncidentVertices() | |
151 | */ | |
152 | public Set getIncidentVertices() { | |
153 | 126521 | Set vertices = new LinkedHashSet(2); |
154 | 126521 | vertices.add(mFrom); |
155 | 126521 | vertices.add(mTo); |
156 | ||
157 | 126521 | return Collections.unmodifiableSet(vertices); |
158 | } | |
159 | ||
160 | /** | |
161 | * @see edu.uci.ics.jung.graph.Edge#getOpposite(Vertex) | |
162 | */ | |
163 | public Vertex getOpposite(Vertex vertex) { | |
164 | 116373 | if (vertex == mFrom) |
165 | 114268 | return mTo; |
166 | 2105 | if (vertex == mTo) |
167 | 2103 | return mFrom; |
168 | ||
169 | 2 | throw new IllegalArgumentException("Vertex " + vertex + |
170 | " is not incident to this edge " + this ); | |
171 | } | |
172 | ||
173 | ||
174 | ||
175 | ||
176 | /** | |
177 | * @see edu.uci.ics.jung.graph.ArchetypeEdge#numVertices() | |
178 | */ | |
179 | public int numVertices() { | |
180 | 2 | return 2; |
181 | } | |
182 | ||
183 | /** | |
184 | * @see edu.uci.ics.jung.graph.ArchetypeEdge#isIncident(ArchetypeVertex) | |
185 | */ | |
186 | public boolean isIncident(ArchetypeVertex v) { | |
187 | 10 | return (v == mFrom) || (v == mTo); |
188 | } | |
189 | ||
190 | ||
191 | /** | |
192 | * Creates a copy of this edge in the specified graph <code>newGraph</code>, | |
193 | * and copies this edge's user data to the new edge. | |
194 | * | |
195 | * @see edu.uci.ics.jung.graph.ArchetypeEdge#copy(edu.uci.ics.jung.graph.ArchetypeGraph) | |
196 | */ | |
197 | public ArchetypeEdge copy(ArchetypeGraph newGraph) | |
198 | { | |
199 | 895 | AbstractSparseEdge e = (AbstractSparseEdge)super.copy(newGraph); |
200 | 893 | e.mFrom = (Vertex)mFrom.getEqualVertex(newGraph); |
201 | 893 | e.mTo = (Vertex)mTo.getEqualVertex(newGraph); |
202 | 893 | ((Graph)newGraph).addEdge(e); |
203 | 890 | return e; |
204 | } | |
205 | ||
206 | ||
207 | /** | |
208 | * @see edu.uci.ics.jung.graph.Edge#getEndpoints() | |
209 | */ | |
210 | public Pair getEndpoints() { | |
211 | 276559 | return new Pair( mFrom, mTo ); |
212 | } | |
213 | ||
214 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |