| 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 | 496 | if (currentLatticeRow == 0) |
| 117 | { | |
| 118 | 100 | return mLatticeSize * (mLatticeSize - 1) + currentLatticeColumn; |
| 119 | } | |
| 120 | else | |
| 121 | { | |
| 122 | 396 | return (currentLatticeRow - 1) * mLatticeSize |
| 123 | + currentLatticeColumn; | |
| 124 | } | |
| 125 | } | |
| 126 | ||
| 127 | protected int downIndex(int currentLatticeRow, int currentLatticeColumn) | |
| 128 | { | |
| 129 | 412 | if (currentLatticeRow == mLatticeSize - 1) |
| 130 | { | |
| 131 | 81 | return currentLatticeColumn; |
| 132 | } | |
| 133 | else | |
| 134 | { | |
| 135 | 331 | return (currentLatticeRow + 1) * mLatticeSize |
| 136 | + currentLatticeColumn; | |
| 137 | } | |
| 138 | } | |
| 139 | ||
| 140 | protected int leftIndex(int currentLatticeRow, int currentLatticeColumn) | |
| 141 | { | |
| 142 | 455 | if (currentLatticeColumn == 0) |
| 143 | { | |
| 144 | 92 | return currentLatticeRow * mLatticeSize + mLatticeSize - 1; |
| 145 | } | |
| 146 | else | |
| 147 | { | |
| 148 | 363 | return currentLatticeRow * mLatticeSize + currentLatticeColumn - 1; |
| 149 | } | |
| 150 | } | |
| 151 | ||
| 152 | protected int rightIndex(int currentLatticeRow, int currentLatticeColumn) | |
| 153 | { | |
| 154 | 356 | if (currentLatticeColumn == mLatticeSize - 1) |
| 155 | { | |
| 156 | 69 | return currentLatticeRow * mLatticeSize; |
| 157 | } | |
| 158 | else | |
| 159 | { | |
| 160 | 287 | 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 | 1788 | return mLatticeSize; |
| 170 | } | |
| 171 | ||
| 172 | } |
|
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |