// 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 <stdio.h>
#include<iostream.h>

#include <LINK/graph/nauty.h>	// this is the main include of nauty.h
				// all other compilation units which include
				// it must define EXTDEFS first
#include <LINK/basic/general.h>
#include <LINK/basic/Array.h>
#include <LINK/basic/Matrix.h>
#include <LINK/basic/Set.h>
#include <LINK/graph/Attribute.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/HyperGraph.h>
#include <LINK/graph/DHyperGraph.h>
#include <LINK/graph/UHyperGraph.h>
#include <LINK/graph/BinGraph.h>
#include <LINK/graph/DBinGraph.h>
#include <LINK/graph/UBinGraph.h>

#define UNDIRECTED 0
#define DIRECTED 1

//
// "graph" is defined in nauty.h.  The following is used to change g into
// a format suitable for isomorphism testing with nauty.
//

#define MAXN 30		// MAXN < WORDSIZE causes optimizations in nauty
			// MAXN will have to be redefined for bigger graphs

graph *nautyGraph(const Graph *link_graph)
{
	int order = link_graph->order();
	int m = (order + WORDSIZE - 1) / WORDSIZE;

	AsymMatrix<int> adj_mat = link_graph->adjacencyMatrix();
	graph *g = new graph[MAXN*MAXM];
	
	int i, j;
	set *gv;	//nauty 'set' type
	for (i=0; i<order; i++) {
		gv = GRAPHROW(g,i,m);
		EMPTYSET(gv,m);
		for (j=0; j<order; j++) {
			if (adj_mat(i,j)) 
				ADDELEMENT(gv,j);
		}
	}
	return g;
}

graph *canonicalNautyGraph(const Graph *link_graph, graph *g, 
			   nvector *lab)
{
	int order = link_graph->order();
	int m = (order + WORDSIZE - 1) / WORDSIZE;
	graph *canong = new graph[MAXN*MAXM];
	nvector ptn[MAXN], orbits[MAXN];
	static DEFAULTOPTIONS(options);
	options.getcanon = TRUE;
	if (!link_graph->simpleQ() || link_graph->directedQ())
		options.digraph = TRUE;
	options.writeautoms = FALSE;
	options.writemarkers = FALSE;
	statsblk(stats);
	setword workspace[50*MAXM];
	
	nauty(g, lab, ptn, NILSET, orbits, &options, &stats,
	      workspace, 50*MAXM, m, order, canong);
	return canong;
}

static Graph* newAppropriateGraph(int multi, int bin, 
			   int has_directed, int has_undirected)
{
	Graph *g;
	if (!has_directed) {
		if (multi) {
			if (bin)
				g = new MUBinGraph;
			else
				g = new MUHyperGraph;
		} else {
			if (bin)
				g = new UBinGraph;
			else
				g = new UHyperGraph;
		}
	} else if (!has_undirected) {
		if (multi) {
			if (bin)
				g = new MDBinGraph;
			else
				g = new MDHyperGraph;
		} else {
			if (bin)
				g = new DBinGraph;
			else
				g = new DHyperGraph;
		}
	} else {
		if (multi) {
			if (bin)
				g = new MBinGraph;
			else
				g = new MHyperGraph;
		} else {
			if (bin)
				g = new BinGraph;
			else
				g = new HyperGraph;
		}
	}
	return g;
}

static void determineGraphType(const MSet<Edge*>& eset, int& multi, int& bin,
			int& has_directed_edge, int& has_undirected_edge)
{
	Iterator<Edge*> get_edge(&eset);
	Edge* e;
	bin = TRUE;
	multi = FALSE;
	while (get_edge(e)) {
		Collection<Vertex*>* vertices = e->vertices();
		if (vertices->size() != 2)
			bin = FALSE;
		if (vertices->sortedQ())
			has_undirected_edge = TRUE;
		if (!vertices->sortedQ())
			has_directed_edge = TRUE;
	}
	if (!eset.permutationQ())
		multi = TRUE;
}

static void determineGraphType(const Set<Set<Vertex*> >& eset, 
			int& multi, int& bin,
			int& has_directed_edge, int& has_undirected_edge)
{
	Iterator<Set<Vertex*> > get_edge(&eset);
	Set<Vertex*> e;
	bin = TRUE;
	multi = FALSE;
	has_directed_edge = FALSE;
	has_undirected_edge = TRUE;
	while (get_edge(e)) {
		if (e.size() != 2)
			bin = FALSE;
	}
	if (!eset.permutationQ())
		multi = TRUE;
}

static void determineGraphType(const Set<Sequence<Vertex*> >& eset, 
			int& multi, int& bin,
			int& has_directed_edge, int& has_undirected_edge)
{
	Iterator<Sequence<Vertex*> > get_edge(&eset);
	Sequence<Vertex*> e;
	bin = TRUE;
	multi = FALSE;
	has_directed_edge = TRUE;
	has_undirected_edge = FALSE;
	while (get_edge(e)) {
		if (e.size() != 2)
			bin = FALSE;
	}
	if (!eset.permutationQ())
		multi = TRUE;
}

static void determineGraphType(const MSet<Set<char*> >& eset, int& multi, 
						int& bin)
{
	Iterator<Set<char*> > get_set(&eset);
	Set<char*> s;
	bin = TRUE;
	multi = FALSE;
	while (get_set(s)) {
		if (s.size() != 2)
			bin = FALSE;
	}
	if (!eset.permutationQ())
		multi = TRUE;
}


static void determineGraphType(const MSet<Sequence<char*> >&eseq,int& multi,
						int& bin)
{
	Iterator<Sequence<char*> > get_seq(&eseq);
	Sequence<char*> s;
	bin = TRUE;
	multi = FALSE;
	while (get_seq(s)) {
		if (s.size() != 2)
			bin = FALSE;
	}
	if (!eseq.permutationQ())
		multi = TRUE;
}


static void determineGraphType(const MSet<Set<int*> >& eset, int& multi, 
						int& bin)
{
	Iterator<Set<int*> > get_set(&eset);
	Set<int*> s;
	bin = TRUE;
	multi = FALSE;
	while (get_set(s)) {
		if (s.size() != 2)
			bin = FALSE;
	}
	if (!eset.permutationQ())
		multi = TRUE;
}


/*
static void determineGraphType(const MSet<Sequence<int*> >&eseq,int& multi,
						int& bin)
{
	Iterator<Sequence<int*> > get_seq(&eseq);
	Sequence<int*> s;
	bin = TRUE;
	multi = FALSE;
	while (get_seq(s)) {
		if (s.size() != 2)
			bin = FALSE;
	}
	if (!eseq.permutationQ())
		multi = TRUE;
}
*/

Graph* newEmpty(const Graph *g)
{
	switch (g->type()) {
		case MIXEDHYPERGRAPH: 		return new HyperGraph;	
		case UNDHYPERGRAPH:		return new UHyperGraph;
		case DIRHYPERGRAPH:		return new DHyperGraph;
		case M_MIXEDHYPERGRAPH:		return new MHyperGraph;
		case M_UNDHYPERGRAPH:		return new MUHyperGraph;
		case M_DIRHYPERGRAPH:		return new MDHyperGraph;
		case MIXEDBINARYGRAPH:		return new BinGraph;
		case UNDBINARYGRAPH:		return new UBinGraph;
		case DIRBINARYGRAPH:		return new DBinGraph;
		case M_MIXEDBINARYGRAPH:	return new MBinGraph;
		case M_UNDBINARYGRAPH:		return new MUBinGraph;
		case M_DIRBINARYGRAPH:		return new MDBinGraph;
	}
}

Graph *multiGraph(const Graph* g, Flag clone, Flag reverse)
{
        switch (g->type()) {
             case M_MIXEDHYPERGRAPH:
             case MIXEDHYPERGRAPH:   return new MHyperGraph(*g,clone,reverse);
                                     break;
             case M_UNDHYPERGRAPH:
             case UNDHYPERGRAPH:     return new MUHyperGraph(*g,clone,reverse);
				     break;
             case M_DIRHYPERGRAPH:  
             case DIRHYPERGRAPH:     return new MDHyperGraph(*g,clone,reverse);
				     break;
             case M_MIXEDBINARYGRAPH:
             case MIXEDBINARYGRAPH:  return new MBinGraph(*g,clone,reverse);
				     break;
             case M_UNDBINARYGRAPH:  
             case UNDBINARYGRAPH:    return new MUBinGraph(*g,clone,reverse);
				     break;
             case M_DIRBINARYGRAPH:  
             case DIRBINARYGRAPH:    return new MDBinGraph(*g,clone,reverse);
	}
}

Graph *simpleGraph(const Graph* g, Flag clone, Flag reverse)
{
        switch (g->type()) {
             case M_MIXEDHYPERGRAPH:
             case MIXEDHYPERGRAPH:   return new HyperGraph(*g,clone,reverse);
                                     break;
             case M_UNDHYPERGRAPH:
             case UNDHYPERGRAPH:     return new UHyperGraph(*g,clone,reverse);
				     break;
             case M_DIRHYPERGRAPH:  
             case DIRHYPERGRAPH:     return new DHyperGraph(*g,clone,reverse);
				     break;
             case M_MIXEDBINARYGRAPH:
             case MIXEDBINARYGRAPH:  return new BinGraph(*g,clone,reverse);
				     break;
             case M_UNDBINARYGRAPH:  
             case UNDBINARYGRAPH:    return new UBinGraph(*g,clone,reverse);
				     break;
             case M_DIRBINARYGRAPH:  
             case DIRBINARYGRAPH:    return new DBinGraph(*g,clone,reverse);
	}
}

Graph *directedGraph(const Graph* g, Flag clone, Flag reverse)
{
        switch (g->type()) {
             case M_MIXEDHYPERGRAPH:
             case M_UNDHYPERGRAPH:
             case M_DIRHYPERGRAPH:  return new MDHyperGraph(*g,clone,reverse);
                                    break;
             case M_MIXEDBINARYGRAPH:
             case M_UNDBINARYGRAPH:  
             case M_DIRBINARYGRAPH:  return new MDBinGraph(*g,clone,reverse);
                                     break;
             case MIXEDHYPERGRAPH:   
             case UNDHYPERGRAPH:     
             case DIRHYPERGRAPH:     return new DHyperGraph(*g,clone,reverse);
				     break;
             case MIXEDBINARYGRAPH:  
             case UNDBINARYGRAPH:    
             case DIRBINARYGRAPH:    return new DBinGraph(*g,clone,reverse);
	}
}

Graph *undirectedGraph(const Graph* g, Flag clone, Flag reverse)
{
        switch (g->type()) {
             case M_MIXEDHYPERGRAPH:
             case M_UNDHYPERGRAPH:
             case M_DIRHYPERGRAPH:  return new MUHyperGraph(*g,clone,reverse);
                                    break;
             case M_MIXEDBINARYGRAPH:
             case M_UNDBINARYGRAPH:  
             case M_DIRBINARYGRAPH:  return new MUBinGraph(*g,clone,reverse);
                                     break;
             case MIXEDHYPERGRAPH:   
             case UNDHYPERGRAPH:     
             case DIRHYPERGRAPH:     return new UHyperGraph(*g,clone,reverse);
				     break;
             case MIXEDBINARYGRAPH:  
             case UNDBINARYGRAPH:    
             case DIRBINARYGRAPH:    return new UBinGraph(*g,clone,reverse);
	}
}

Graph* makeGraph(MSet<Vertex*> vset, MSet<Set<Vertex*> > eset)
{
	int bin = TRUE;
	int multi = FALSE;
	int has_directed_edge = FALSE;
	int has_undirected_edge = FALSE;

	determineGraphType(eset, multi, bin, has_directed_edge, 
					     has_undirected_edge);
	Graph *g = newAppropriateGraph(multi, bin, has_directed_edge,
						   has_undirected_edge);

	Iterator<Vertex*> get_vertex(&vset);
	Vertex *v;
	while (get_vertex(v)) {
		g->addVertex(v->name());
	}
	SortedArray<Vertex*> va = g->vertices();

	Iterator<Set<Vertex*> > get_edge(&eset);
	Set<Vertex*> e;
	while (get_edge(e)) {
		Iterator<Vertex*> get_element(&e);
		Vertex *e;
		Set<Vertex*> new_edge;
		while (get_element(e)) {
			new_edge.append(g->findVertexByName(e->name()));
		}
		g->addEdge(new_edge);
	}
	return g;
}


Graph* makeGraph(MSet<Vertex*> vset, MSet<Sequence<Vertex*> > eset)
{
	int bin = TRUE;
	int multi = FALSE;
	int has_directed_edge = FALSE;
	int has_undirected_edge = FALSE;

	determineGraphType(eset, multi, bin, has_directed_edge, 
					     has_undirected_edge);
	Graph *g = newAppropriateGraph(multi, bin, has_directed_edge,
						   has_undirected_edge);

	Iterator<Vertex*> get_vertex(&vset);
	Vertex *v;
	while (get_vertex(v)) {
		g->addVertex(v->name());
	}
	SortedArray<Vertex*> va = g->vertices();

	Iterator<Sequence<Vertex*> > get_edge(&eset);
	Sequence<Vertex*> e;
	while (get_edge(e)) {
		Iterator<Vertex*> get_element(&e);
		Vertex *e;
		Sequence<Vertex*> new_edge;
		while (get_element(e)) {
			new_edge.append(g->findVertexByName(e->name()));
		}
		g->addEdge(new_edge);
	}
	return g;
}

Graph* makeGraph(Set<Vertex*> vset, MSet<Edge*> eset)
{
	int bin = TRUE;
	int multi = FALSE;
	int has_directed_edge = FALSE;
	int has_undirected_edge = FALSE;

	determineGraphType(eset, multi, bin, has_directed_edge, 
					     has_undirected_edge);
	Graph *g = newAppropriateGraph(multi, bin, has_directed_edge,
						   has_undirected_edge);
	Iterator<Vertex*> get_vertex(&vset);
	Vertex *v;
	while (get_vertex(v)) {
		g->addVertex(v->name());
	}
	//SortedArray<Vertex*> va = g->vertices();

	Iterator<Edge*> get_edge(&eset);
	Edge* e;
	while (get_edge(e)) {
		Collection<Vertex*>* vertices = e->vertices();
		Iterator<Vertex*> get_element(vertices);
		Vertex *e;
                Collection<Vertex*>* new_edge = vertices->newEmpty();
		while (get_element(e)) {
			Vertex *nextv = g->findVertexByName(e->name());
			new_edge->append(nextv);
		}
		g->addEdge(*new_edge);
	}
	return g;
}

Graph* makeGraph(MSet<char*> vset, MSet<Set<char*> > eset)
{
	int bin = TRUE;
	int multi = FALSE;

	determineGraphType(eset, multi, bin);
	Graph *g = newAppropriateGraph(multi, bin, FALSE, TRUE);

	Iterator<char*> get_vertex(&vset);
	char *v;
	while (get_vertex(v)) {
		g->addVertex(v);
	}
	SortedArray<Vertex*> va = g->vertices();

	Iterator<Set<char*> > get_set(&eset);
	Set<char*> s;
	while (get_set(s)) {
		Iterator<char*> get_element(&s);
		char *e;
		Set<Vertex*> new_edge;
		while (get_element(e)) {
			new_edge.append(g->findVertexByName(e));
		}
		g->addEdge(new_edge);
	}
	return g;
}


Graph* makeGraph(Set<char*> vseq, MSet<Sequence<char*> > eseq)
{
	int bin = TRUE;
	int multi = FALSE;

	determineGraphType(eseq, multi, bin);
	Graph *g = newAppropriateGraph(multi, bin, TRUE, FALSE);

	Iterator<char*> get_vertex(&vseq);
	char *v;
	while (get_vertex(v)) {
		g->addVertex(v);
	}
	SortedArray<Vertex*> va = g->vertices();

	Iterator<Sequence<char*> > get_seq(&eseq);
	Sequence<char*> s;
	while (get_seq(s)) {
		Iterator<char*> get_element(&s);
		char *e;
		Sequence<Vertex*> new_edge;
		while (get_element(e)) {
			new_edge.append(g->findVertexByName(e));
		}
		g->addEdge(new_edge);
	}
	return g;
}


Graph* makeGraph(Set<int*> vset, MSet<Set<int*> > eset)
{
	char vname[10];
	int bin = TRUE;
	int multi = FALSE;

	determineGraphType(eset, multi, bin);
	Graph *g = newAppropriateGraph(multi, bin, FALSE, TRUE);

	Iterator<int*> get_vertex(&vset);
	int *v;
	while (get_vertex(v)) {
		sprintf(vname, "%d", *v);
		g->addVertex((char*) vname);
	}
	SortedArray<Vertex*> va = g->vertices();

	Iterator<Set<int*> > get_set(&eset);
	Set<int*> s;
	while (get_set(s)) {
		Iterator<int*> get_element(&s);
		int *e;
		Set<Vertex*> new_edge;
		while (get_element(e)) {
			sprintf(vname, "%d", *e);
			new_edge.append(g->findVertexByName(vname));
		}
		g->addEdge(new_edge);
	}
	return g;
}

Graph *bipartiteRepresentation(Graph *h)
{
        UBinGraph *g = new UBinGraph;

	const SortedArray<Vertex*>& vertices = h->vertices();
	MSet<Edge*> edges = h->edges();
        Iterator<Vertex*> get_vert(&vertices);
        Vertex *v;
        while (get_vert(v))
                g->addVertex(v->name());
        Iterator<Edge*> get_edge(&edges);
        Edge *e;
        while (get_edge(e))
                g->addVertex(e->name());
        get_edge.reset();
        while (get_edge(e)) {
                double w;
                getAttribute((GraphObject*) e, "weight", w);
                Vertex *edge_locus = g->findVertexByName(e->name());
                Iterator<Vertex*> edge_vert(e->vertices());
                Vertex *v;
                while (edge_vert(v)) {
                        Vertex *vg = g->findVertexByName(v->name());
			Set<Vertex*> s;
			s.insert(edge_locus); s.insert(vg);
                        Edge *eg = g->addEdge(s);
                        setAttribute((GraphObject*) eg, "weight", w/2);
                }
        }
        return g;
}

/*
Graph* makeGraph(Set<int*> vseq, MSet<Sequence<int*> > eseq)
{
	char vname[10];
	int bin = TRUE;
	int multi = FALSE;

	determineGraphType(eseq, multi, bin);
	Graph *g = newAppropriateGraph(multi, bin, TRUE, FALSE);

	Iterator<int*> get_vertex(&vseq);
	int *v;
	while (get_vertex(v)) {
		sprintf(vname, "%d", *v);
		g->addVertex((char*) vname);
	}
	SortedArray<Vertex*> va = g->vertices();

	Iterator<Sequence<int*> > get_seq(&eseq);
	Sequence<int*> s;
	while (get_seq(s)) {
		Iterator<int*> get_element(&s);
		int *e;
		Sequence<Vertex*> new_edge;
		while (get_element(e)) {
			sprintf(vname, "%d", *e);
			new_edge.append(g->findVertexByName(vname));
		}
		g->addEdge(new_edge);
	}
	return g;
}
*/

int SaveGraph(Graph *g, char *fname)
{
	ofstream ofile;
	ofile.open(fname,ios::out);

  	if(ofile.fail()) {
    		cerr << "Error: could not open file" << endl;
    		return -1;
  	}
	g->saveToFile(&ofile);
	return 0;
}

// see parseGraph.cc for LoadGraph();