// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

///////////////////////////////////////////////////////////////////////////
//      Creation: 1993 June 14, John MacCuish, jmaccuis@lanl.gov
//////////////////////////////////////////////////////////////////////////////

#include <stdlib.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/UBinGraph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/basic/Set.h>

    
//
// Generate a grid graph, given an n x m grid, and layout the
// vertices and edges on that grid.  m rows and n columns.
//
UBinGraph*
GenGridGraph(int m, int n)
{
    UBinGraph*  graph = new UBinGraph(); 	// Undirected binary graph

    // Create and label vertices
    graph->addVertices(n*m);

    const SortedArray<Vertex*>& vertices = graph->vertices();

    // For each vertex, but the n*m-th one (last one), create horizontal // (to the right) and/or vertical edges (below), if they exist.
    int i, j;
    for (i=0; i < m-1; i++) {
        for (j=0; j < n-1; j++) {
		Set<Vertex*> s;  
		s.insert(vertices[i*m+j]);
		s.insert(vertices[i*m+j+1]);
                graph->addEdge(s);
		Set<Vertex*> s2;  
		s2.insert(vertices[i*m+j]);
		s2.insert(vertices[(i+1)*m+j]);
                graph->addEdge(s2);
	}
    }	    
    // bottom row, edges to the right
    for (j=0; j < n-1; j++) {
	Set<Vertex*> s;  
	s.insert(vertices[j+m*(n-1)]);
	s.insert(vertices[j+1+m*(n-1)]);
        graph->addEdge(s);
    }

    // rightmost column, edges down the column
    for (i=0; i < m-1; i++) {
	Set<Vertex*> s;  
	s.insert(vertices[(n-1)+m*i]);
	s.insert(vertices[(n-1)+m*(i+1)]);
        Edge* edge1 = graph->addEdge(s);
    }
    return graph;	
}