Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University of | |
3 | * California All rights reserved. | |
4 | * | |
5 | * This software is open-source under the BSD license; see either "license.txt" | |
6 | * or http://jung.sourceforge.net/license.txt for a description. | |
7 | * | |
8 | * Created on Mar 3, 2004 | |
9 | */ | |
10 | package edu.uci.ics.jung.graph.impl; | |
11 | ||
12 | import java.util.*; | |
13 | import edu.uci.ics.jung.graph.*; | |
14 | ||
15 | /** | |
16 | * This fully functional class is provided as a different sort of way to think about the creation | |
17 | * and use of Vertices, and a reminder that the user is always welcome to create | |
18 | * their own vertices. While most vertex classes keep a table from neighboring vertex to edge, | |
19 | * this one keeps a linked list. This reduces the memory footprint, but makes | |
20 | * <code>findEdge()</code> (as well as most other methods) require time proportional | |
21 | * to the vertex's degree. | |
22 | * | |
23 | * @author Joshua O'Madadhain | |
24 | */ | |
25 | 0 | public class LeanSparseVertex extends AbstractSparseVertex { |
26 | ||
27 | protected List incident_edges; | |
28 | ||
29 | protected void initialize() { | |
30 | 0 | super.initialize(); |
31 | 0 | this.incident_edges = new LinkedList(); |
32 | 0 | } |
33 | ||
34 | /** | |
35 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#getNeighbors_internal() | |
36 | */ | |
37 | protected Collection getNeighbors_internal() { | |
38 | 0 | Set neighbors = new HashSet(); |
39 | 0 | for (Iterator inco_it = incident_edges.iterator(); inco_it.hasNext();) |
40 | 0 | neighbors.add(((Edge) inco_it.next()).getOpposite(this)); |
41 | 0 | return neighbors; |
42 | } | |
43 | ||
44 | /** | |
45 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#getEdges_internal() | |
46 | */ | |
47 | protected Collection getEdges_internal() { | |
48 | 0 | return incident_edges; |
49 | } | |
50 | ||
51 | /** | |
52 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#addNeighbor_internal(edu.uci.ics.jung.graph.Edge, | |
53 | * edu.uci.ics.jung.graph.Vertex) | |
54 | */ | |
55 | protected void addNeighbor_internal(Edge e, Vertex v) { | |
56 | 0 | incident_edges.add(e); |
57 | 0 | } |
58 | ||
59 | /** | |
60 | * @see edu.uci.ics.jung.graph.impl.AbstractSparseVertex#removeNeighbor_internal(edu.uci.ics.jung.graph.Edge, | |
61 | * edu.uci.ics.jung.graph.Vertex) | |
62 | */ | |
63 | protected void removeNeighbor_internal(Edge e, Vertex v) { | |
64 | 0 | incident_edges.remove(e); |
65 | 0 | } |
66 | ||
67 | /** | |
68 | * @see edu.uci.ics.jung.graph.Vertex#findEdgeSet(Vertex) | |
69 | */ | |
70 | public Set findEdgeSet(Vertex w) { | |
71 | 0 | Set edges = new HashSet(); |
72 | 0 | for (Iterator iter = incident_edges.iterator(); iter.hasNext();) { |
73 | 0 | Edge e = (Edge) iter.next(); |
74 | 0 | if (e instanceof UndirectedEdge |
75 | 0 | || ((DirectedEdge) e).getDest() == w) edges.add(e); |
76 | } | |
77 | 0 | return edges; |
78 | } | |
79 | ||
80 | /** | |
81 | * @see edu.uci.ics.jung.graph.Vertex#getPredecessors() | |
82 | */ | |
83 | public Set getPredecessors() { | |
84 | 0 | Set preds = new HashSet(); |
85 | 0 | for (Iterator iter = incident_edges.iterator(); iter.hasNext();) { |
86 | 0 | Edge e = (Edge) iter.next(); |
87 | 0 | if (e instanceof UndirectedEdge |
88 | || ((DirectedEdge) e).getDest() == this) | |
89 | 0 | preds.add(e.getOpposite(this)); |
90 | } | |
91 | 0 | return preds; |
92 | } | |
93 | ||
94 | /** | |
95 | * @see edu.uci.ics.jung.graph.Vertex#getSuccessors() | |
96 | */ | |
97 | public Set getSuccessors() { | |
98 | 0 | Set succs = new HashSet(); |
99 | 0 | for (Iterator iter = incident_edges.iterator(); iter.hasNext();) { |
100 | 0 | Edge e = (Edge) iter.next(); |
101 | 0 | if (e instanceof UndirectedEdge |
102 | || ((DirectedEdge) e).getSource() == this) | |
103 | 0 | succs.add(e.getOpposite(this)); |
104 | } | |
105 | 0 | return succs; |
106 | } | |
107 | ||
108 | /** | |
109 | * @see edu.uci.ics.jung.graph.Vertex#getInEdges() | |
110 | */ | |
111 | public Set getInEdges() { | |
112 | 0 | Set in = new HashSet(); |
113 | 0 | for (Iterator iter = incident_edges.iterator(); iter.hasNext();) { |
114 | 0 | Edge e = (Edge) iter.next(); |
115 | 0 | if (e instanceof UndirectedEdge |
116 | 0 | || ((DirectedEdge) e).getDest() == this) in.add(e); |
117 | } | |
118 | 0 | return in; |
119 | } | |
120 | ||
121 | /** | |
122 | * @see edu.uci.ics.jung.graph.Vertex#getOutEdges() | |
123 | */ | |
124 | public Set getOutEdges() { | |
125 | 0 | Set out = new HashSet(); |
126 | 0 | for (Iterator iter = incident_edges.iterator(); iter.hasNext();) { |
127 | 0 | Edge e = (Edge) iter.next(); |
128 | 0 | if (e instanceof UndirectedEdge |
129 | 0 | || ((DirectedEdge) e).getSource() == this) out.add(e); |
130 | } | |
131 | 0 | return out; |
132 | } | |
133 | ||
134 | /** | |
135 | * @see edu.uci.ics.jung.graph.Vertex#inDegree() | |
136 | */ | |
137 | public int inDegree() { | |
138 | 0 | return getInEdges().size(); |
139 | } | |
140 | ||
141 | /** | |
142 | * @see edu.uci.ics.jung.graph.Vertex#outDegree() | |
143 | */ | |
144 | public int outDegree() { | |
145 | 0 | return getOutEdges().size(); |
146 | } | |
147 | ||
148 | /** | |
149 | * @see edu.uci.ics.jung.graph.Vertex#numPredecessors() | |
150 | */ | |
151 | public int numPredecessors() { | |
152 | 0 | return getPredecessors().size(); |
153 | } | |
154 | ||
155 | /** | |
156 | * @see edu.uci.ics.jung.graph.Vertex#numSuccessors() | |
157 | */ | |
158 | public int numSuccessors() { | |
159 | 0 | return getSuccessors().size(); |
160 | } | |
161 | ||
162 | /** | |
163 | * @see edu.uci.ics.jung.graph.Vertex#isSuccessorOf(edu.uci.ics.jung.graph.Vertex) | |
164 | */ | |
165 | public boolean isSuccessorOf(Vertex v) { | |
166 | 0 | for (Iterator iter = incident_edges.iterator(); iter.hasNext();) { |
167 | 0 | Edge e = (Edge) iter.next(); |
168 | 0 | if (e.getOpposite(this) == v) { |
169 | 0 | if (e instanceof DirectedEdge) { |
170 | 0 | return ((DirectedEdge) e).getDest() == this; |
171 | } else | |
172 | 0 | return true; |
173 | } | |
174 | } | |
175 | 0 | return false; |
176 | } | |
177 | ||
178 | /** | |
179 | * @see edu.uci.ics.jung.graph.Vertex#isPredecessorOf(edu.uci.ics.jung.graph.Vertex) | |
180 | */ | |
181 | public boolean isPredecessorOf(Vertex v) { | |
182 | 0 | for (Iterator iter = incident_edges.iterator(); iter.hasNext();) { |
183 | 0 | Edge e = (Edge) iter.next(); |
184 | 0 | if (e.getOpposite(this) == v) { |
185 | 0 | if (e instanceof DirectedEdge) { |
186 | 0 | return ((DirectedEdge) e).getSource() == this; |
187 | } else | |
188 | 0 | return true; |
189 | } | |
190 | } | |
191 | 0 | return false; |
192 | } | |
193 | ||
194 | /** | |
195 | * @see edu.uci.ics.jung.graph.Vertex#isSource(edu.uci.ics.jung.graph.Edge) | |
196 | */ | |
197 | public boolean isSource(Edge e) { | |
198 | 0 | if (e instanceof DirectedEdge) |
199 | 0 | return ((DirectedEdge) e).getSource() == this; |
200 | else | |
201 | // UndirectedEdge | |
202 | 0 | return e.isIncident(this); |
203 | } | |
204 | ||
205 | /** | |
206 | * @see edu.uci.ics.jung.graph.Vertex#isDest(edu.uci.ics.jung.graph.Edge) | |
207 | */ | |
208 | public boolean isDest(Edge e) { | |
209 | 0 | if (e instanceof DirectedEdge) |
210 | 0 | return ((DirectedEdge) e).getDest() == this; |
211 | else | |
212 | // UndirectedEdge | |
213 | 0 | return e.isIncident(this); |
214 | } | |
215 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |