third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/Lattice2DGenerator.java

   1 /*
   2  * Copyright (c) 2009, 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 package edu.uci.ics.jung.algorithms.generators;
  12
  13 import java.util.ArrayList;
  14 import java.util.List;
  15
  16 import org.apache.commons.collections15.Factory;
  17
  18 import edu.uci.ics.jung.graph.Graph;
  19 import edu.uci.ics.jung.graph.util.EdgeType;
  20
  21 /**
  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.
  26  *
  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.
  29  *
  30  * @author Joshua O'Madadhain
  31  */
  32 public class Lattice2DGenerator<V,E> implements GraphGenerator<V,E>
  33 {
  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;
  42
  43     /**
  44      * Constructs a generator of square lattices of size {@code latticeSize}
  45      * with the specified parameters.
  46      *
  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
  52      */
  53     public Lattice2DGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
  54             Factory<E> edge_factory, int latticeSize, boolean isToroidal)
  55     {
  56         this(graph_factory, vertex_factory, edge_factory, latticeSize, latticeSize, isToroidal);
  57     }
  58
  59     /**
  60      * Creates a generator of {@code row_count} x {@code col_count} lattices
  61      * with the specified parameters.
  62      *
  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
  69      */
  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)
  72     {
  73         if (row_count < 2 || col_count < 2)
  74         {
  75             throw new IllegalArgumentException("Row and column counts must each be at least 2.");
  76         }
  77
  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);
  85     }
  86
  87     /**
  88      * @see edu.uci.ics.jung.algorithms.generators.GraphGenerator#create()
  89      */
  90     @SuppressWarnings("unchecked")
  91     public Graph<V,E> create()
  92     {
  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++)
  97         {
  98             V v = vertex_factory.create();
  99             graph.addVertex(v);
 100             v_array.add(i, v);
 101         }
 102
 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;
 106
 107         // fill in edges
 108         // down
 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));
 112         // right
 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));
 116
 117         // if the graph is directed, fill in the edges going the other direction...
 118         if (graph.getDefaultEdgeType() == EdgeType.DIRECTED)
 119         {
 120             // up
 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));
 124             // left
 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));
 128         }
 129
 130         return graph;
 131     }
 132
 133     /**
 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.)
 136      */
 137     public int getGridEdgeCount()
 138     {
 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);
 142
 143         return (vertical_edge_count + horizontal_edge_count) * (is_directed ? 2 : 1);
 144     }
 145
 146     protected int getIndex(int i, int j)
 147     {
 148         return ((mod(i, row_count)) * col_count) + (mod(j, col_count));
 149     }
 150
 151     protected int mod(int i, int modulus)
 152     {
 153         int i_mod = i % modulus;
 154         return i_mod >= 0 ? i_mod : i_mod + modulus;
 155     }
 156
 157     /**
 158      * Returns the vertex at position ({@code i mod row_count, j mod col_count}).
 159      */
 160     protected V getVertex(int i, int j)
 161     {
 162         return v_array.get(getIndex(i, j));
 163     }
 164
 165     /**
 166      * Returns the {@code i}th vertex (counting row-wise).
 167      */
 168     protected V getVertex(int i)
 169     {
 170         return v_array.get(i);
 171     }
 172
 173     /**
 174      * Returns the row in which vertex {@code i} is found.
 175      */
 176     protected int getRow(int i)
 177     {
 178         return i / row_count;
 179     }
 180
 181     /**
 182      * Returns the column in which vertex {@code i} is found.
 183      */
 184     protected int getCol(int i)
 185     {
 186         return i % col_count;
 187     }
 188 }