// 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 <iostream.h>
#include <stdlib.h>
#include <LINK/basic/Set.h>
#include <LINK/basic/SetFuncs.h>
#include <LINK/basic/Array.h>
#include <LINK/graph/Attribute.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/algorithm/Algorithms.h>

// findEdge - not general (doesn't work on hypergraphs, multigraphs,
//			   which is why it's defined here & not in graph lib.)
//	      direction doesn't matter - return e where v1 and v2 are in e.
static Edge *findEdge(Vertex *v1, Vertex *v2)
{
	MSet<Edge*> v1_edges = v1->incidentEdges();
	Iterator<Edge*> get_edge(&v1_edges);
	Edge *e;
	while (get_edge(e)) 
		if (e->vertices()->memberQ(v2))
			return e;
	return 0;
}

static char *colors [] = { BLACK, BLUE, GREEN, PURPLE, BROWN, ORANGE, 
		    RED, GRAY, YELLOW, WHITE };

typedef Vertex * VertexPtr;
int my_compare(const VertexPtr& v1, const VertexPtr& v2)
{
	double w1, w2;
	getAttribute((GraphObject*)v1, "weight", w1);
	getAttribute((GraphObject*)v2, "weight", w2);
	cout << "worked" << endl;
	if (w1 > w2)
		return 1;
	else if (w1 < w2)
		return -1;
	return 0;
}
	

//
// Exhaustive - Only Useful for very small graphs
//
void HamiltonianCycles(Graph *g, char *graph_view)
{
	ResetAttributes(g);
	SortedArray<Vertex*> vertices = g->vertices();
	Set<Sequence<Vertex*> > result;
	int i=0;

	setAttribute((GraphObject*) vertices[0], "pred", vertices[0]);
	setAttribute((GraphObject*) vertices[0], "weight", (double)10.0);
	List<Vertex*> l = vertices;
	l.sort(my_compare);
	cout << l << endl;
	SaveGraph(g, "test.g");
	Graph *h = LoadGraph("test.g");
	SortedArray<Vertex*> hvertices = h->vertices();
	Vertex *v;
	getAttribute((GraphObject*) hvertices[0], "pred", v);
	cout << *v << endl;
	SaveGraph(h, "htest.g");
	

	Permutation p(g->order());
        Permutation last = p.last();
        p.first();
        while (p != last) {
		Sequence<Vertex*> potential_cycle = 
				SetFuncs<Vertex*>::permutation(vertices, p);
		Iterator<Vertex*> next_vertex(&potential_cycle);
		Vertex *source;
		Vertex *sink;
		Set<Vertex*> otn;
		Edge *e;
		next_vertex(source);
		int cycle = TRUE, m=0;
		while (next_vertex(sink)) {
			otn = source->outNeighbors();
			e = findEdge(source, sink);
			getAttribute((GraphObject*)e, "mark", m);
			if (!otn.memberQ(sink) || m) {
				cycle = FALSE;
				break;
			}
			source = sink;
		}
		source = potential_cycle.last();
		sink   = potential_cycle.first();
		e = findEdge(source, sink);
		getAttribute((GraphObject*)e, "mark", m);
		if (!otn.memberQ(sink) || m) 
				cycle = FALSE;
		if (cycle) {
			next_vertex.reset();
			next_vertex(source);
			while (next_vertex(sink)) {
				e = findEdge(source, sink);
				setAttribute((GraphObject*)e, "mark", 1);
				animateEdge(e, graph_view, 
					"color", "color", ALG_STEP,
					(char*) colors[i]);
				source = sink;
			}
			source = potential_cycle.last();
			sink   = potential_cycle.first();
			e = findEdge(source, sink);
			setAttribute((GraphObject*)e, "mark", 1);
			animateEdge(e, graph_view, "color", "color", ALG_STEP,
					(char*) colors[i]);
			i++;
		}
		p.next();
	}
}