// 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
// 

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Attribute.h>
#include <LINK/basic/Array.h>
#include <LINK/layout/Layouts.h>

#define min(x, y) ( ((x) < (y)) ? (x) : (y))

void applyLayout(Graph *g, int layout_type)
{
	int rows;
	switch (layout_type) {
		case BIPARTITE:	HyperBipartiteLayout(g);
				break;
		case CIRCULAR:	CircleLayout(g);
				break;
		case GRID:	rows = (int) sqrt(g->order()) + 1;
				GridLayout(g, rows, rows);
				break;
		case RANDOM:	RandomLayout(g);
				break;
		case SPRING:	SpringLayout(g);
				break;
	}
}

void 
ComponentLayout(Graph* graph, Set<Set<Vertex*> > pieces, int layout_type1,
							 int layout_type2)
{
	int graph_order = graph->order();
	graph->collapseComponents(pieces); 
	applyLayout(graph, layout_type1);
	SortedArray<Vertex*> gc_v = graph->vertices(); // need the copy here
	int i, gc_order = graph->order();	    // since subgraph operations
	Array<double> xcrds, ycrds;
	for (i=0; i<gc_order; i++) {
		getAttribute((GraphObject*)gc_v[i], "x", xcrds[i]);
		getAttribute((GraphObject*)gc_v[i], "y", ycrds[i]);
	}
	for (i=0; i<gc_order; i++) {		    // are going on.
		double x, y, gc_vx, gc_vy;
		Set<Vertex*> sv = graph->dissolveSubgraph(gc_v[i]);
		Graph *sg = graph->inducedSubgraph(sv, 1);
		applyLayout(sg, layout_type2);
		Vertex **vertices = sg->vertexStart();
		int j, ord = sg->order();

		// scale each component according to:
		// min ( |V(c)| / |V(G)|, (min(dist(sv, boundary))/0.5))
		double sx = ord / (double) graph_order, sy;
		double min_dist_to_boundary = min(min(1.0-xcrds[i], xcrds[i]),
						  min(1.0-ycrds[i],ycrds[i]));
		sx = sy = min(sx, min_dist_to_boundary/0.5);

		for (j=0; j<ord; j++) {
			getAttribute((GraphObject*) vertices[j], "x", gc_vx);
			getAttribute((GraphObject*) vertices[j], "y", gc_vy);
			Vertex *v=graph->findVertexByName(vertices[j]->name());
			double sgx = (sx * (gc_vx - 0.5));
			double sgy = (sy * (gc_vy - 0.5));
			setAttribute((GraphObject*) v, "x", xcrds[i]+sgx);
			setAttribute((GraphObject*) v, "y", ycrds[i]+sgy);
		}
	}
}