| 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 | package edu.uci.ics.jung.graph.filters; | |
| 9 | ||
| 10 | import java.util.Iterator; | |
| 11 | import java.util.Set; | |
| 12 | ||
| 13 | import edu.uci.ics.jung.exceptions.FatalException; | |
| 14 | import edu.uci.ics.jung.graph.*; | |
| 15 | import edu.uci.ics.jung.utils.UserData; | |
| 16 | ||
| 17 | /** | |
| 18 | * This class represents an unassembled graph. It does not implement Graph. It | |
| 19 | * represents the collection of vertices and edges that were generated by the | |
| 20 | * filter. VERTICES that are members of this DO NOT fulfill the vertex contract, | |
| 21 | * as they claim their graph is the source graph. | |
| 22 | * <p> | |
| 23 | * The filter process looks like this: <br> | |
| 24 | * | |
| 25 | * <pre> | |
| 26 | * | |
| 27 | * SOURCE GRAPH - [ Filter1 ] - UnassembledGraph - [Filter2] - UnassembledGraph - [Assemble] - Graph | |
| 28 | * | |
| 29 | * </pre> | |
| 30 | * | |
| 31 | * @author danyelf | |
| 32 | */ | |
| 33 | public class UnassembledGraph { | |
| 34 | ||
| 35 | protected String name; | |
| 36 | ||
| 37 | /** | |
| 38 | * Holds a reference to the filter that generated this UnassembledGraph | |
| 39 | */ | |
| 40 | protected Filter filter; | |
| 41 | ||
| 42 | // CONSTRAINT: all vertices in these sets are members of OriginalGraph | |
| 43 | /** | |
| 44 | * Holds a reference to the filter that generated this UnassembledGraph | |
| 45 | */ | |
| 46 | protected Set vertexSet; | |
| 47 | ||
| 48 | protected Set edgeSet; | |
| 49 | ||
| 50 | // If there was a graph before this one, this is it | |
| 51 | protected UnassembledGraph previousGraph; | |
| 52 | ||
| 53 | // This is the last real graph in the sequence | |
| 54 | protected Graph originalGraph; | |
| 55 | ||
| 56 | 75 | public UnassembledGraph(Filter f, Set vertices, Set edges, Graph original) { |
| 57 | 75 | this.filter = f; |
| 58 | 75 | this.vertexSet = vertices; |
| 59 | 75 | this.edgeSet = edges; |
| 60 | 75 | this.previousGraph = null; |
| 61 | 75 | this.originalGraph = original; |
| 62 | 75 | this.name = filter.getName(); |
| 63 | 75 | checkData(); |
| 64 | 75 | } |
| 65 | ||
| 66 | /** | |
| 67 | * A constructor that uses non-Filters (for example, GraphCluterers) to | |
| 68 | * build themselves. | |
| 69 | * | |
| 70 | * @param name | |
| 71 | * A name to refer to the caller (e.g. | |
| 72 | * "EdgeBetweenessCluster(3)") | |
| 73 | * @param vertices | |
| 74 | * The set of vertices in this UnassembledGraph | |
| 75 | * @param edges | |
| 76 | * The set of edges in this UnassembledGraph | |
| 77 | * @param original | |
| 78 | * The graph from which this data comes | |
| 79 | */ | |
| 80 | 0 | public UnassembledGraph(String name, Set vertices, Set edges, Graph original) { |
| 81 | 0 | this.filter = null; |
| 82 | 0 | this.vertexSet = vertices; |
| 83 | 0 | this.edgeSet = edges; |
| 84 | 0 | this.previousGraph = null; |
| 85 | 0 | this.originalGraph = original; |
| 86 | 0 | this.name = name; |
| 87 | 0 | checkData(); |
| 88 | 0 | } |
| 89 | ||
| 90 | public UnassembledGraph(Filter f, Set vertices, Set edges, | |
| 91 | 4 | UnassembledGraph previous) { |
| 92 | 4 | this.filter = f; |
| 93 | 4 | this.vertexSet = vertices; |
| 94 | 4 | this.edgeSet = edges; |
| 95 | 4 | this.previousGraph = previous; |
| 96 | 4 | this.originalGraph = previous.getOriginalGraph(); |
| 97 | 4 | this.name = filter.getName(); |
| 98 | 4 | checkData(); |
| 99 | 4 | } |
| 100 | ||
| 101 | /** | |
| 102 | * Returns the name of the filter that generated this UnassembledGraph. | |
| 103 | */ | |
| 104 | public String getFilterName() { | |
| 105 | 7 | String rv = name; |
| 106 | 7 | if (previousGraph != null) { |
| 107 | 2 | rv += ":" + previousGraph.getFilterName(); |
| 108 | } | |
| 109 | 7 | return rv; |
| 110 | } | |
| 111 | ||
| 112 | private void checkData() { | |
| 113 | 79 | for (Iterator iter = vertexSet.iterator(); iter.hasNext();) { |
| 114 | 586 | Vertex e = (Vertex) iter.next(); |
| 115 | 586 | if (e.getGraph() != originalGraph) |
| 116 | 0 | throw new FatalException("Vertex not in original"); |
| 117 | } | |
| 118 | ||
| 119 | 79 | for (Iterator iter = edgeSet.iterator(); iter.hasNext();) { |
| 120 | 1474 | Edge e = (Edge) iter.next(); |
| 121 | 1474 | if (e.getGraph() != originalGraph) |
| 122 | 0 | throw new FatalException("Edge not in original"); |
| 123 | } | |
| 124 | 79 | } |
| 125 | ||
| 126 | /** | |
| 127 | * Returns the original graph that was subsetted for this UnsassembledGraph. | |
| 128 | */ | |
| 129 | public Graph getOriginalGraph() { | |
| 130 | 9 | return originalGraph; |
| 131 | } | |
| 132 | ||
| 133 | /** | |
| 134 | * Returns the set of vertices (from <tt>getOriginalGraph()</tt>) that | |
| 135 | * passed the filter. | |
| 136 | */ | |
| 137 | public Set getUntouchedVertices() { | |
| 138 | 98 | return vertexSet; |
| 139 | } | |
| 140 | ||
| 141 | /** | |
| 142 | * Returns the set of edges (from <tt>getOriginalGraph()</tt>) that | |
| 143 | * passed the filter. | |
| 144 | */ | |
| 145 | public Set getUntouchedEdges() { | |
| 146 | 239 | return edgeSet; |
| 147 | } | |
| 148 | ||
| 149 | public String toString() { | |
| 150 | 0 | if (previousGraph == null) { |
| 151 | 0 | return "UNASSEMBLED" + "<" + originalGraph + ">"; |
| 152 | } else { | |
| 153 | 0 | return "UNASSEMBLED" + "<" + previousGraph + ">"; |
| 154 | } | |
| 155 | } | |
| 156 | ||
| 157 | /** | |
| 158 | * Constructs a new graph based on the source graph. Assumes that edges | |
| 159 | * should only be copied if they contain all the original edge's vertices; | |
| 160 | * all vertices that pass the filter are copied. | |
| 161 | * <p> | |
| 162 | * Here's the general theory: | |
| 163 | * <ul> | |
| 164 | * <li>A Graph object of the appropriate type can be obtained by calling | |
| 165 | * <tt>{@link edu.uci.ics.jung.graph.ArchetypeGraph#newInstance() Graph.newInstance()}</tt> | |
| 166 | * on the original.</li> | |
| 167 | * <li>Then, the graph is populated with all vertices that the filters have | |
| 168 | * passed (that is, the vertices in | |
| 169 | * <tt>{@link #getUntouchedVertices() getUntouchedVertices()}</tt>. | |
| 170 | * Vertices are copied in with | |
| 171 | * <tt>{@link edu.uci.ics.jung.graph.ArchetypeVertex#copy( ArchetypeGraph ) copy(Graph)}</tt>. | |
| 172 | * </li> | |
| 173 | * <li>Last, the graph is populated with all edges that have both passed, | |
| 174 | * and have both ends in vertices that passed.</li> | |
| 175 | * </ul> | |
| 176 | */ | |
| 177 | public Graph assemble(boolean shouldPreserveRecord) { | |
| 178 | // constructs AG from the various edges | |
| 179 | 52 | Graph subgraph = (Graph) originalGraph.newInstance(); |
| 180 | ||
| 181 | 52 | if (shouldPreserveRecord) { |
| 182 | 5 | subgraph.addUserDatum(GraphAssemblyRecord.FILTER_GRAPH_KEY, |
| 183 | new GraphAssemblyRecord(this), UserData.REMOVE); | |
| 184 | } | |
| 185 | ||
| 186 | 52 | Set localVertices = getUntouchedVertices(); |
| 187 | ||
| 188 | // now, we scoop up vertices | |
| 189 | 52 | for (Iterator iter = localVertices.iterator(); iter.hasNext();) { |
| 190 | 415 | ArchetypeVertex newV = (ArchetypeVertex) iter.next(); |
| 191 | 415 | newV.copy(subgraph); |
| 192 | } | |
| 193 | ||
| 194 | // and only the edges that actually match | |
| 195 | 52 | for (Iterator iter = getUntouchedEdges().iterator(); iter.hasNext();) { |
| 196 | 1287 | ArchetypeEdge newE = (ArchetypeEdge) iter.next(); |
| 197 | 1287 | if (localVertices.containsAll(newE.getIncidentVertices())) { |
| 198 | 486 | newE.copy(subgraph); |
| 199 | } | |
| 200 | } | |
| 201 | ||
| 202 | 52 | return subgraph; |
| 203 | } | |
| 204 | ||
| 205 | public Graph assemble() { | |
| 206 | 47 | return assemble(false); |
| 207 | } | |
| 208 | ||
| 209 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |