| 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 | 147163 | super(); |
| 90 | 147163 | if (from == null || to == null) |
| 91 | 2 | throw new IllegalArgumentException("Vertices passed in can not be null"); |
| 92 | ||
| 93 | 147161 | if( from.getGraph() != to.getGraph()) |
| 94 | 3 | throw new IllegalArgumentException("Vertices must be from same graph"); |
| 95 | ||
| 96 | 147158 | if (from.getGraph() == null || to.getGraph() == null) |
| 97 | 0 | throw new IllegalArgumentException("Orphaned vertices can not " + |
| 98 | "be connected by an edge"); | |
| 99 | ||
| 100 | 147158 | mFrom = from; |
| 101 | 147158 | mTo = to; |
| 102 | ||
| 103 | 147158 | this.id = nextGlobalEdgeID++; |
| 104 | 147158 | } |
| 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 | 148062 | 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 | 148060 | 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 | 148060 | if (mFrom instanceof AbstractSparseVertex) |
| 143 | 148060 | ((AbstractSparseVertex)mFrom).addNeighbor_internal( this, mTo ); |
| 144 | ||
| 145 | 148053 | if (mTo instanceof AbstractSparseVertex) |
| 146 | 148053 | ((AbstractSparseVertex)mTo).addNeighbor_internal( this, mFrom ); |
| 147 | 148053 | } |
| 148 | ||
| 149 | /** | |
| 150 | * @see edu.uci.ics.jung.graph.ArchetypeEdge#getIncidentVertices() | |
| 151 | */ | |
| 152 | public Set getIncidentVertices() { | |
| 153 | 33869 | Set vertices = new LinkedHashSet(2); |
| 154 | 33869 | vertices.add(mFrom); |
| 155 | 33869 | vertices.add(mTo); |
| 156 | ||
| 157 | 33869 | 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 | 23709 | if (vertex == mFrom) |
| 165 | 21604 | 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 | 907 | AbstractSparseEdge e = (AbstractSparseEdge)super.copy(newGraph); |
| 200 | 905 | e.mFrom = (Vertex)mFrom.getEqualVertex(newGraph); |
| 201 | 905 | e.mTo = (Vertex)mTo.getEqualVertex(newGraph); |
| 202 | 905 | ((Graph)newGraph).addEdge(e); |
| 203 | 902 | return e; |
| 204 | } | |
| 205 | ||
| 206 | ||
| 207 | /** | |
| 208 | * @see edu.uci.ics.jung.graph.Edge#getEndpoints() | |
| 209 | */ | |
| 210 | public Pair getEndpoints() { | |
| 211 | 368947 | 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. |