2 * Copyright (c) 2009, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
11 package edu.uci.ics.jung.algorithms.generators;
13 import java.util.ArrayList;
14 import java.util.List;
16 import org.apache.commons.collections15.Factory;
18 import edu.uci.ics.jung.graph.Graph;
19 import edu.uci.ics.jung.graph.util.EdgeType;
22 * Simple generator of an m x n lattice where each vertex
23 * is incident with each of its neighbors (to the left, right, up, and down).
24 * May be toroidal, in which case the vertices on the edges are connected to
25 * their counterparts on the opposite edges as well.
27 * <p>If the graph factory supplied has a default edge type of {@code EdgeType.DIRECTED},
28 * then edges will be created in both directions between adjacent vertices.
30 * @author Joshua O'Madadhain
32 public class Lattice2DGenerator<V,E> implements GraphGenerator<V,E>
34 protected int row_count;
35 protected int col_count;
36 protected boolean is_toroidal;
37 protected boolean is_directed;
38 protected Factory<? extends Graph<V, E>> graph_factory;
39 protected Factory<V> vertex_factory;
40 protected Factory<E> edge_factory;
41 private List<V> v_array;
44 * Constructs a generator of square lattices of size {@code latticeSize}
45 * with the specified parameters.
47 * @param graph_factory used to create the {@code Graph} for the lattice
48 * @param vertex_factory used to create the lattice vertices
49 * @param edge_factory used to create the lattice edges
50 * @param latticeSize the number of rows and columns of the lattice
51 * @param isToroidal if true, the created lattice wraps from top to bottom and left to right
53 public Lattice2DGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
54 Factory<E> edge_factory, int latticeSize, boolean isToroidal)
56 this(graph_factory, vertex_factory, edge_factory, latticeSize, latticeSize, isToroidal);
60 * Creates a generator of {@code row_count} x {@code col_count} lattices
61 * with the specified parameters.
63 * @param graph_factory used to create the {@code Graph} for the lattice
64 * @param vertex_factory used to create the lattice vertices
65 * @param edge_factory used to create the lattice edges
66 * @param row_count the number of rows in the lattice
67 * @param col_count the number of columns in the lattice
68 * @param isToroidal if true, the created lattice wraps from top to bottom and left to right
70 public Lattice2DGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
71 Factory<E> edge_factory, int row_count, int col_count, boolean isToroidal)
73 if (row_count < 2 || col_count < 2)
75 throw new IllegalArgumentException("Row and column counts must each be at least 2.");
78 this.row_count = row_count;
79 this.col_count = col_count;
80 this.is_toroidal = isToroidal;
81 this.graph_factory = graph_factory;
82 this.vertex_factory = vertex_factory;
83 this.edge_factory = edge_factory;
84 this.is_directed = (graph_factory.create().getDefaultEdgeType() == EdgeType.DIRECTED);
88 * @see edu.uci.ics.jung.algorithms.generators.GraphGenerator#create()
90 @SuppressWarnings("unchecked")
91 public Graph<V,E> create()
93 int vertex_count = row_count * col_count;
94 Graph<V,E> graph = graph_factory.create();
95 v_array = new ArrayList<V>(vertex_count);
96 for (int i = 0; i < vertex_count; i++)
98 V v = vertex_factory.create();
103 int start = is_toroidal ? 0 : 1;
104 int end_row = is_toroidal ? row_count : row_count - 1;
105 int end_col = is_toroidal ? col_count : col_count - 1;
109 for (int i = 0; i < end_row; i++)
110 for (int j = 0; j < col_count; j++)
111 graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i+1, j));
113 for (int i = 0; i < row_count; i++)
114 for (int j = 0; j < end_col; j++)
115 graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i, j+1));
117 // if the graph is directed, fill in the edges going the other direction...
118 if (graph.getDefaultEdgeType() == EdgeType.DIRECTED)
121 for (int i = start; i < row_count; i++)
122 for (int j = 0; j < col_count; j++)
123 graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i-1, j));
125 for (int i = 0; i < row_count; i++)
126 for (int j = start; j < col_count; j++)
127 graph.addEdge(edge_factory.create(), getVertex(i,j), getVertex(i, j-1));
134 * Returns the number of edges found in a lattice of this generator's specifications.
135 * (This is useful for subclasses that may modify the generated graphs to add more edges.)
137 public int getGridEdgeCount()
139 int boundary_adjustment = (is_toroidal ? 0 : 1);
140 int vertical_edge_count = col_count * (row_count - boundary_adjustment);
141 int horizontal_edge_count = row_count * (col_count - boundary_adjustment);
143 return (vertical_edge_count + horizontal_edge_count) * (is_directed ? 2 : 1);
146 protected int getIndex(int i, int j)
148 return ((mod(i, row_count)) * col_count) + (mod(j, col_count));
151 protected int mod(int i, int modulus)
153 int i_mod = i % modulus;
154 return i_mod >= 0 ? i_mod : i_mod + modulus;
158 * Returns the vertex at position ({@code i mod row_count, j mod col_count}).
160 protected V getVertex(int i, int j)
162 return v_array.get(getIndex(i, j));
166 * Returns the {@code i}th vertex (counting row-wise).
168 protected V getVertex(int i)
170 return v_array.get(i);
174 * Returns the row in which vertex {@code i} is found.
176 protected int getRow(int i)
178 return i / row_count;
182 * Returns the column in which vertex {@code i} is found.
184 protected int getCol(int i)
186 return i % col_count;