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.HashSet; | |
13 | import java.util.Iterator; | |
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 | ||
23 | /** | |
24 | * This class provides a skeletal implementation of the <code>Vertex</code> | |
25 | * interface to minimize the effort required to implement this interface. | |
26 | * It is appropriate for sparse graphs (those in which each vertex | |
27 | * is connected to only a few other vertices); for dense graphs (those in | |
28 | * which each vertex is connected to most other vertices), another | |
29 | * implementation might be more appropriate. | |
30 | * <P> | |
31 | * This class extends <code>UserData</code>, which provides storage and | |
32 | * retrieval mechanisms for user-defined data for each edge instance. | |
33 | * This allows users to attach data to edges without having to extend | |
34 | * this class. | |
35 | * | |
36 | * @author Scott White | |
37 | * @author Danyel Fisher | |
38 | * @author Joshua O'Madadhain | |
39 | * | |
40 | * @see AbstractSparseGraph | |
41 | * @see AbstractSparseEdge | |
42 | */ | |
43 | public abstract class AbstractSparseVertex extends AbstractArchetypeVertex | |
44 | implements Vertex, Cloneable | |
45 | { | |
46 | /** | |
47 | * The next vertex ID. | |
48 | */ | |
49 | 74 | private static int nextGlobalVertexID = 0; |
50 | ||
51 | /** | |
52 | * Creates a new instance of a vertex for inclusion | |
53 | * in a sparse graph. | |
54 | * Sets up the data necessary for definition of | |
55 | * vertex equivalence, and initializes the internal | |
56 | * data structures. | |
57 | * | |
58 | * @see #initialize() | |
59 | */ | |
60 | protected AbstractSparseVertex() { | |
61 | 31676 | super(); |
62 | 31676 | this.id = nextGlobalVertexID++; |
63 | 31676 | initialize(); |
64 | 31676 | } |
65 | ||
66 | ||
67 | ||
68 | /** | |
69 | * Returns the edge that connects this vertex to the specified | |
70 | * vertex <code>v</code>. This is a | |
71 | * simple implementation which checks the opposite vertex of | |
72 | * each outgoing edge of this vertex; this solution is general, | |
73 | * but not efficient. | |
74 | * | |
75 | * @see Vertex#findEdge(Vertex) | |
76 | */ | |
77 | public Edge findEdge(Vertex v) | |
78 | { | |
79 | 0 | for (Iterator iter = getOutEdges().iterator(); iter.hasNext();) { |
80 | 0 | Edge element = (Edge) iter.next(); |
81 | 0 | if (element.getOpposite(this).equals(v)) |
82 | 0 | return element; |
83 | } | |
84 | 0 | return null; |
85 | } | |
86 | ||
87 | public ArchetypeEdge findEdge(ArchetypeVertex v) | |
88 | { | |
89 | 0 | return this.findEdge((Vertex)v); |
90 | } | |
91 | ||
92 | /** | |
93 | * @see Vertex#findEdgeSet(Vertex) | |
94 | */ | |
95 | public Set findEdgeSet(Vertex v) | |
96 | { | |
97 | 0 | Set edgeSet = new HashSet(); |
98 | 0 | for (Iterator iter = getOutEdges().iterator(); iter.hasNext();) { |
99 | 0 | Edge element = (Edge) iter.next(); |
100 | 0 | if (element.getOpposite(this).equals(v)) |
101 | 0 | edgeSet.add( element ); |
102 | } | |
103 | 0 | return edgeSet; |
104 | } | |
105 | ||
106 | /** | |
107 | * @see ArchetypeVertex#findEdgeSet(ArchetypeVertex) | |
108 | */ | |
109 | public Set findEdgeSet(ArchetypeVertex v) | |
110 | { | |
111 | 0 | return this.findEdgeSet((Vertex)v); |
112 | } | |
113 | ||
114 | /** | |
115 | * @see Vertex#copy(ArchetypeGraph) | |
116 | */ | |
117 | public ArchetypeVertex copy(ArchetypeGraph newGraph) | |
118 | { | |
119 | 729 | AbstractSparseVertex v = (AbstractSparseVertex)super.copy(newGraph); |
120 | 728 | ((Graph)newGraph).addVertex(v); |
121 | 726 | return v; |
122 | } | |
123 | ||
124 | ||
125 | /** | |
126 | * Adds the specified edge <code>e</code> and vertex <code>v</code> | |
127 | * to the internal data structures of this vertex. | |
128 | * | |
129 | * @param e the new incident edge of this vertex | |
130 | * @param v the new neighbor of this vertex | |
131 | */ | |
132 | protected abstract void addNeighbor_internal(Edge e, Vertex v); | |
133 | ||
134 | /** | |
135 | * Removes the specified edge <code>e</code> and vertex <code>v</code> | |
136 | * from the internal data structures of this vertex. | |
137 | * | |
138 | * @param e the incident edge of this vertex which is being removed | |
139 | * @param v the neighbor of this vertex which is being removed | |
140 | */ | |
141 | protected abstract void removeNeighbor_internal(Edge e, Vertex v); | |
142 | ||
143 | ||
144 | /** | |
145 | * Returns a human-readable representation of this vertex. | |
146 | * | |
147 | * @see java.lang.Object#toString() | |
148 | */ | |
149 | public String toString() { | |
150 | 363 | return "V" + String.valueOf(id); |
151 | } | |
152 | ||
153 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |