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