// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Patricia K. Fasel (Los Alamos Nat. Lab.), 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 <strstream.h>
#include <LINK/basic/SetFuncs.h>
#include <LINK/graph/Attribute.h>
#include <LINK/graph/BinGraph.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Vertex.h>


//
// delete the passed vertex from the graph
//
void
MBinGraph::deleteVertex(Vertex* passed_vertex)
{
    MSet<Edge*> inc_edges = passed_vertex->incidentEdges();
    Iterator<Edge*> get_edge(&inc_edges);
    Edge* edge;
    while (get_edge(edge))
	deleteEdge(edge);
    _vertices.remove(passed_vertex);
    delete passed_vertex;
}


//
// construct a new undirected edge from the set of vertices
// add to the graph
//
Edge*
MBinGraph::addEdge(Edge* e)
{
	return MHyperGraph::addEdge(e);
}

ostream& operator<<(ostream&, const Collection<Vertex*>&);

Edge*
MBinGraph::addEdge(Collection<Vertex*>& passed_vertices, String e_name)
{
    if (passed_vertices.size() != 2) {
	error("Binary edge may only contain two vertices");
	return 0;
    }
    Iterator<Vertex*> get_vertex(&passed_vertices);
    Vertex *vertex1, *vertex2;

    get_vertex(vertex1);
    get_vertex(vertex2);
    if (!vertex1 || !vertex2 ||
        (vertex1->owner() != this) || (vertex2->owner() != this)) {
	ostrstream sos;
	sos << "edge " << passed_vertices 
	  	<< "contains vertices not in V(G). Edge not inserted" ;
	char *s = sos.str();
	warning(s);
	delete s;
	return (Edge*) 0;
    }

    Set<Vertex*>* edge_vertices = new Set<Vertex*>;
    Edge* edge = new Edge(this, edge_vertices);

    edge_vertices->insert(vertex1);
    edge_vertices->insert(vertex2);

    vertex1->addEdge(edge);
    vertex2->addEdge(edge);

    _edges.append(edge);

    if (e_name == 0) {
	e_name = makeEdgeName();
    }
    e_name = strcpy(new char[strlen(e_name)+1], e_name);
    setAttribute((GraphObject*) edge, "name", e_name);

    return edge;
}


//
// construct a new directed edge from sequence of vertices
// add to the graph
//
Edge*
MBinGraph::addEdge(Sequence<Vertex*> passed_vertices, String e_name)
{
    if (passed_vertices.size() != 2) {
	error("Binary edge may only contain two vertices");
	return 0;
    }
    Iterator<Vertex*> get_vertex(&passed_vertices);
    Vertex *vertex1, *vertex2;

    get_vertex(vertex1);
    get_vertex(vertex2);

    if (!vertex1 || !vertex2 ||
        (vertex1->owner() != this) || (vertex2->owner() != this)) {
	ostrstream sos;
	sos << "edge " << passed_vertices 
	   	<< "contains vertices not in V(G). Edge not inserted" ;
	char *s = sos.str();
	warning(s);
	delete s;
	return (Edge*) 0;
    }

    Sequence<Vertex*>* edge_vertices = new Sequence<Vertex*>;
    Edge* edge = new Edge(this, edge_vertices);

    edge_vertices->append(vertex1);
    edge_vertices->append(vertex2);

    vertex1->addEdge(edge);
    vertex2->addEdge(edge);

    _edges.append(edge);

    if (e_name == 0)
	e_name = makeEdgeName();
    String new_name = strcpy(new char[strlen(e_name)+1], e_name);
    setAttribute((GraphObject*) edge, "name", new_name);

    return edge;
}

MBinGraph MBinGraph::lineGraph() const
//
// Originally coded by Michael Murphy murphy@c3.lanl.gov
//
{
    AsymMatrix<int> incidence_matrix = IncidenceMatrix(this, 0);

    // compute the product of Transpose(incidenceMatrx) and incidenceMatrix 
    SymMatrix<int> line_graph_mat = LaplacianMatrix(incidence_matrix);

    // subtract 2 from the diagonal
    int num_edges = line_graph_mat.numCols();
    for (int i=0; i < num_edges; i++)
        line_graph_mat(i,i) -=2; 

    // create the new graph 
    MBinGraph g = AdjacencyMatrix2Graph(line_graph_mat);

    return g;
}


MBinGraph MBinGraph::intersection(const Graph& g) const
{
        MBinGraph result;
	warning("intersection(): not implemented yet");
	return result;
}

MBinGraph MBinGraph::lexicographicProduct(const Graph& g) const
{
        MBinGraph result;
	warning("lexicographicProduct: not implemented yet");
	return result;
}

MBinGraph MBinGraph::product(const Graph& g) const
{
        MBinGraph result;
        if (!binaryQ() || !g.binaryQ())
                return result;
        Set<Vertex*> vset = _vertices;
        Set<Vertex*> g_vset = g.vertices();

        Set<Sequence<Vertex*> > pairs =
                        SetFuncs<Vertex*>::cartesianProduct(vset, g_vset);
        Iterator<Sequence<Vertex*> > get_pair1(&pairs), get_pair2(&pairs);
        Sequence<Vertex*> pair1, pair2;
        MSet<Vertex*> new_edge;
        Vertex *u1, *u2, *v1, *v2;
	int ctr=0, gord = g.order();
	Set<Vertex*> component;
	Set<Set<Vertex*> > components;
        while (get_pair1(pair1)) {
                ostrstream oss;
                oss << pair1 << ends;
                char *str = oss.str();
                Vertex *v =result.addVertex(str);
                delete str;
		component.append(v);
		if ((ctr++ % gord) == (gord-1)) {
			components.insert(component);
			component.clear();
		}
        }
        get_pair1.reset();
        while (get_pair1(pair1)) {
                while (get_pair2(pair2)) {
                        if (pair1 != pair2) {
                                u1 = pair1.ref(0);
                                u2 = pair2.ref(0);
                                v1 = pair1.ref(1);
                                v2 = pair2.ref(1);
                                if  (((u1 == u2) && g.adjacentQ(v1, v2)) ||
                                     ((v1 == v2) && adjacentQ(u1, u2))) {
                                        ostrstream oss;
                                        oss << pair1 << ends;
                                        char *s = oss.str();
                                        ostrstream oss2;
                                        oss2 << pair2 << ends;
                                        char *s2 = oss2.str();
                                        Vertex*rv1=result.findVertexByName(s);
                                        Vertex*rv2=result.findVertexByName(s2);
                                        delete s;
                                        delete s2;
                                        new_edge.insert(rv1);
                                        new_edge.insert(rv2);
                                        if (!result.isEdge(new_edge))
                                                result.addEdge(new_edge);
                                        new_edge.clear();
                                }
                        }
                }
                get_pair2.reset();
        }
	//ComponentLayout(&result, components, CIRCULAR, CIRCULAR);
        return result;
}

MBinGraph MBinGraph::sum(const Graph& g) const
{
	MBinGraph result;
	if (!binaryQ())
		return result;
	int i, j, ord1 = order(), ord2 = g.order();
	const SortedArray<Vertex*>& gverts = g.vertices();
	for (i=0; i<ord1; i++) {
		Vertex *v = new Vertex(*_vertices[i], CLONE);
		v->_owner = &result;	// this is ok since the Graph
		result.addVertex(v);	// copy constructor will be 
	}				// invoke upon return
	for (i=0; i<ord2; i++) {
		Vertex *v = new Vertex(*gverts[i], CLONE);
		v->_owner = &result;
		result.addVertex(v);	
	}
	const SortedArray<Vertex*>& rverts = result.vertices();
	MSet<Edge*> gedges = g.edges();
	Iterator<Edge*> get_edge(&_edges), get_g_edge(&gedges);
	Edge *e;
	Collection<Vertex*>* everts;
	while (get_edge(e)) {
		everts = e->vertices();
		Iterator<Vertex*> get_vert(everts);
		Vertex *v;
		if (everts->sortedQ()) {
			MSet<Vertex*> result_everts;
			while (get_vert(v))
				result_everts.insert(
					result.findVertexByName(v->name()));
			result.addEdge(result_everts);
		} else {
			Sequence<Vertex*> result_everts;
			while (get_vert(v))
				result_everts.append(
					result.findVertexByName(v->name()));
			result.addEdge(result_everts);
		}
	}
	while (get_g_edge(e)) {
		everts = e->vertices();
		Iterator<Vertex*> get_vert(everts);
		Vertex *v;
		if (everts->sortedQ()) {
			MSet<Vertex*> result_everts;
			while (get_vert(v))
				result_everts.insert(
					result.findVertexByName(v->name()));
			result.addEdge(result_everts);
		} else {
			Sequence<Vertex*> result_everts;
			while (get_vert(v))
				result_everts.append(
					result.findVertexByName(v->name()));
			result.addEdge(result_everts);
		}
	}
	return result;
}

MBinGraph MBinGraph::complement() const
{
	MBinGraph result;
	if (!binaryQ())
		return result;	// might change 
	Set<Vertex*> vs;
	Sequence<Vertex*> vsq;
	int i, j, init, ord = order();
	double weight;
	for (i=0; i<ord; i++) {
		Vertex *v = new Vertex(*_vertices[i], CLONE);
		v->_owner = (Graph *) &result;
		result.addVertex(v);
    	}
	const SortedArray<Vertex*>& rverts = result.vertices();
	for (i=0; i<ord; i++) {
		for (j=i+1; j<ord; j++) {
			vsq.append(_vertices[i]);
			vsq.append(_vertices[j]);
			if (i!=j && !isEdge(vsq)) {
				vs.clear();
				vs.insert(rverts[i]);
				vs.append(rverts[j]);
				result.addEdge(vs);
			}
			vsq.clear();
		}
	}
	return result;
}

MBinGraph MBinGraph::operator+(const Graph &g) const
{
	return sum(g);
}


MBinGraph MBinGraph::operator*(const Graph &g) const
{
	return product(g);
}