Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University | |
3 | * of California | |
4 | * All rights reserved. | |
5 | * | |
6 | * This software is open-source under the BSD license; see either | |
7 | * "license.txt" or | |
8 | * http://jung.sourceforge.net/license.txt for a description. | |
9 | */ | |
10 | /* | |
11 | * Created on Jan 8, 2004 | |
12 | * | |
13 | */ | |
14 | package edu.uci.ics.jung.random.generators; | |
15 | ||
16 | import edu.uci.ics.jung.graph.ArchetypeGraph; | |
17 | import edu.uci.ics.jung.graph.Vertex; | |
18 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
19 | import edu.uci.ics.jung.graph.impl.DirectedSparseGraph; | |
20 | import edu.uci.ics.jung.utils.GraphUtils; | |
21 | ||
22 | /** | |
23 | * Simple generator of an n x n lattice where each vertex | |
24 | * is incident with each of its 4 neighbors (except possibly | |
25 | * for the vertices on the edge depending upon whether the lattice | |
26 | * is specified to be toroidal or not). | |
27 | * @author Scott | |
28 | * | |
29 | */ | |
30 | public class Lattice2DGenerator implements GraphGenerator | |
31 | { | |
32 | private int mLatticeSize; | |
33 | private boolean mIsToroidal; | |
34 | ||
35 | /** | |
36 | * Constructs an instance of the lattice generator | |
37 | * @param latticeSize the size of the lattice, n, thus creating an n x n lattice. | |
38 | * @param isToroidal whether the lattice wraps around or not | |
39 | */ | |
40 | public Lattice2DGenerator(int latticeSize, boolean isToroidal) | |
41 | 21 | { |
42 | 21 | if (latticeSize < 2) |
43 | { | |
44 | 0 | throw new IllegalArgumentException("Lattice size must be at least 2."); |
45 | } | |
46 | ||
47 | 21 | mLatticeSize = latticeSize; |
48 | 21 | mIsToroidal = isToroidal; |
49 | ||
50 | 21 | } |
51 | ||
52 | /* (non-Javadoc) | |
53 | * @see edu.uci.ics.jung.random.generators.GraphGenerator#generateGraph() | |
54 | */ | |
55 | public ArchetypeGraph generateGraph() | |
56 | { | |
57 | 11 | int numNodes = (int) Math.pow(mLatticeSize, 2); |
58 | 11 | DirectedSparseGraph graph = new DirectedSparseGraph(); |
59 | 11 | GraphUtils.addVertices(graph, numNodes); |
60 | ||
61 | 11 | int currentLatticeRow = 0, currentLatticeColumn = 0; |
62 | 11 | int upIndex = 0, downIndex = 0, leftIndex = 0, rightIndex = 0; |
63 | ||
64 | 11 | Indexer id = Indexer.getIndexer(graph); |
65 | ||
66 | 286 | for (int i = 0; i < numNodes; i++) |
67 | { | |
68 | 275 | currentLatticeRow = i / mLatticeSize; |
69 | 275 | currentLatticeColumn = i % mLatticeSize; |
70 | ||
71 | 275 | upIndex = upIndex(currentLatticeRow, currentLatticeColumn); |
72 | 275 | leftIndex = leftIndex(currentLatticeRow, currentLatticeColumn); |
73 | 275 | downIndex = downIndex(currentLatticeRow, currentLatticeColumn); |
74 | 275 | rightIndex = rightIndex(currentLatticeRow, currentLatticeColumn); |
75 | ||
76 | //Add short range connections | |
77 | 275 | if (currentLatticeRow != 0 |
78 | || (currentLatticeRow == 0 && mIsToroidal)) | |
79 | { | |
80 | 275 | GraphUtils.addEdge( |
81 | graph, | |
82 | (Vertex) id.getVertex(i), | |
83 | (Vertex) id.getVertex(upIndex)); | |
84 | } | |
85 | 275 | if (currentLatticeColumn != 0 |
86 | || (currentLatticeColumn == 0 && mIsToroidal)) | |
87 | { | |
88 | 275 | GraphUtils.addEdge( |
89 | graph, | |
90 | (Vertex) id.getVertex(i), | |
91 | (Vertex) id.getVertex(leftIndex)); | |
92 | } | |
93 | 275 | if (currentLatticeRow != mLatticeSize-1 |
94 | || (currentLatticeRow == mLatticeSize-1 && mIsToroidal)) | |
95 | { | |
96 | 275 | GraphUtils.addEdge( |
97 | graph, | |
98 | (Vertex) id.getVertex(i), | |
99 | (Vertex) id.getVertex(downIndex)); | |
100 | } | |
101 | 275 | if (currentLatticeColumn != mLatticeSize-1 |
102 | || (currentLatticeColumn == mLatticeSize-1 && mIsToroidal)) | |
103 | { | |
104 | 275 | GraphUtils.addEdge( |
105 | graph, | |
106 | (Vertex) id.getVertex(i), | |
107 | (Vertex) id.getVertex(rightIndex)); | |
108 | } | |
109 | } | |
110 | ||
111 | 11 | return graph; |
112 | } | |
113 | ||
114 | protected int upIndex(int currentLatticeRow, int currentLatticeColumn) | |
115 | { | |
116 | 505 | if (currentLatticeRow == 0) |
117 | { | |
118 | 99 | return mLatticeSize * (mLatticeSize - 1) + currentLatticeColumn; |
119 | } | |
120 | else | |
121 | { | |
122 | 406 | return (currentLatticeRow - 1) * mLatticeSize |
123 | + currentLatticeColumn; | |
124 | } | |
125 | } | |
126 | ||
127 | protected int downIndex(int currentLatticeRow, int currentLatticeColumn) | |
128 | { | |
129 | 401 | if (currentLatticeRow == mLatticeSize - 1) |
130 | { | |
131 | 76 | return currentLatticeColumn; |
132 | } | |
133 | else | |
134 | { | |
135 | 325 | return (currentLatticeRow + 1) * mLatticeSize |
136 | + currentLatticeColumn; | |
137 | } | |
138 | } | |
139 | ||
140 | protected int leftIndex(int currentLatticeRow, int currentLatticeColumn) | |
141 | { | |
142 | 477 | if (currentLatticeColumn == 0) |
143 | { | |
144 | 102 | return currentLatticeRow * mLatticeSize + mLatticeSize - 1; |
145 | } | |
146 | else | |
147 | { | |
148 | 375 | return currentLatticeRow * mLatticeSize + currentLatticeColumn - 1; |
149 | } | |
150 | } | |
151 | ||
152 | protected int rightIndex(int currentLatticeRow, int currentLatticeColumn) | |
153 | { | |
154 | 376 | if (currentLatticeColumn == mLatticeSize - 1) |
155 | { | |
156 | 80 | return currentLatticeRow * mLatticeSize; |
157 | } | |
158 | else | |
159 | { | |
160 | 296 | return currentLatticeRow * mLatticeSize + currentLatticeColumn + 1; |
161 | } | |
162 | } | |
163 | ||
164 | /** | |
165 | * @return the size of the lattice, as specified by the constructor | |
166 | */ | |
167 | public int getLatticeSize() | |
168 | { | |
169 | 1870 | return mLatticeSize; |
170 | } | |
171 | ||
172 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |