| 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. |