Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Created on Apr 3, 2004 | |
3 | * | |
4 | * Copyright (c) 2004, the JUNG Project and the Regents of the University | |
5 | * of California | |
6 | * All rights reserved. | |
7 | * | |
8 | * This software is open-source under the BSD license; see either | |
9 | * "license.txt" or | |
10 | * http://jung.sourceforge.net/license.txt for a description. | |
11 | */ | |
12 | package edu.uci.ics.jung.graph.impl; | |
13 | ||
14 | import java.util.Collection; | |
15 | import java.util.Collections; | |
16 | import java.util.HashSet; | |
17 | import java.util.Iterator; | |
18 | import java.util.Map; | |
19 | import java.util.Set; | |
20 | ||
21 | import edu.uci.ics.jung.exceptions.FatalException; | |
22 | import edu.uci.ics.jung.graph.Edge; | |
23 | import edu.uci.ics.jung.graph.UndirectedEdge; | |
24 | import edu.uci.ics.jung.graph.Vertex; | |
25 | ||
26 | ||
27 | /** | |
28 | * A vertex class for instances of <code>UndirectedGraph</code> | |
29 | * that may contain parallel edges. | |
30 | * | |
31 | * {@link edu.uci.ics.jung.graph.UndirectedGraph} | |
32 | * @author Joshua O'Madadhain | |
33 | */ | |
34 | public class UndirectedSparseVertex extends SimpleUndirectedSparseVertex | |
35 | { | |
36 | /** | |
37 | * Creates a new instance of a vertex for inclusion in a | |
38 | * sparse graph. | |
39 | */ | |
40 | public UndirectedSparseVertex() | |
41 | { | |
42 | 116 | super(); |
43 | 116 | } |
44 | ||
45 | /** | |
46 | * Returns the edge that connects this | |
47 | * vertex to the specified vertex <code>v</code>, or | |
48 | * <code>null</code> if there is no such edge. | |
49 | * Implemented using a hash table for a performance | |
50 | * improvement over the implementation in | |
51 | * <code>AbstractSparseVertex</code>. | |
52 | * | |
53 | * Looks for a directed edge first, and then for an | |
54 | * undirected edge if no directed edges are found. | |
55 | * | |
56 | * @see Vertex#findEdge(Vertex) | |
57 | */ | |
58 | public Edge findEdge(Vertex v) | |
59 | { | |
60 | 2 | Set outEdges = (Set)getNeighborsToEdges().get(v); |
61 | 2 | if (outEdges == null) |
62 | 1 | return null; |
63 | 1 | return (Edge)outEdges.iterator().next(); |
64 | } | |
65 | ||
66 | /** | |
67 | * @see Vertex#findEdgeSet(Vertex) | |
68 | */ | |
69 | public Set findEdgeSet(Vertex v) | |
70 | { | |
71 | 106 | Set edgeSet = new HashSet(); |
72 | 106 | Set edges = (Set)getNeighborsToEdges().get(v); |
73 | 106 | if (edges != null) |
74 | 2 | edgeSet.addAll(edges); |
75 | 106 | return Collections.unmodifiableSet(edgeSet); |
76 | } | |
77 | ||
78 | /** | |
79 | * Returns a list of all incident edges of this vertex. | |
80 | * Requires time proportional to the number of incident edges. | |
81 | * | |
82 | * @see AbstractSparseVertex#getEdges_internal() | |
83 | */ | |
84 | protected Collection getEdges_internal() | |
85 | { | |
86 | 3166 | HashSet edges = new HashSet(); |
87 | ||
88 | 3166 | Collection edgeSets = getNeighborsToEdges().values(); |
89 | ||
90 | 3166 | for (Iterator e_iter = edgeSets.iterator(); e_iter.hasNext(); ) |
91 | 6215 | edges.addAll((Set)e_iter.next()); |
92 | ||
93 | 3166 | return edges; |
94 | } | |
95 | ||
96 | /** | |
97 | * @see AbstractSparseVertex#addNeighbor_internal(Edge, Vertex) | |
98 | */ | |
99 | protected void addNeighbor_internal(Edge e, Vertex v) | |
100 | { | |
101 | 233 | if (! (e instanceof UndirectedEdge)) |
102 | 1 | throw new IllegalArgumentException("This vertex " + |
103 | "implementation only accepts undirected edges"); | |
104 | ||
105 | 232 | Map nte = getNeighborsToEdges(); |
106 | 232 | Set edges = (Set)nte.get(v); |
107 | ||
108 | 232 | if (edges == null) |
109 | { | |
110 | 221 | edges = new HashSet(); |
111 | 221 | nte.put(v, edges); |
112 | } | |
113 | 232 | edges.add(e); |
114 | 232 | } |
115 | ||
116 | /** | |
117 | * @see AbstractSparseVertex#removeNeighbor_internal(Edge, Vertex) | |
118 | */ | |
119 | protected void removeNeighbor_internal(Edge e, Vertex v) | |
120 | { | |
121 | // if v doesn't point to e, and it's not a self-loop | |
122 | // that's been removed in a previous call to removeNeighbor... | |
123 | 8 | Map nte = getNeighborsToEdges(); |
124 | 8 | Set edges = (Set)nte.get(v); |
125 | 8 | if (edges != null) |
126 | { | |
127 | 6 | boolean removed = edges.remove(e); |
128 | 6 | if (edges.isEmpty()) |
129 | 6 | nte.remove(v); |
130 | 6 | if (!removed && this != v) |
131 | 0 | throw new FatalException("Internal error in data structure" + |
132 | "for vertex " + this); | |
133 | } | |
134 | 2 | else if (this != v) |
135 | 0 | throw new FatalException("Internal error in data structure" + |
136 | "for vertex " + this); | |
137 | ||
138 | // if it *is* a self-loop, we're already done | |
139 | 8 | } |
140 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |