// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): James T. Klosowski (SUNY Stony Brook)

// 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 <LINK/graph/Graph.h>
#include <LINK/graph/UBinGraph.h>
#include <LINK/graph/UHyperGraph.h>
#include <LINK/graph/DBinGraph.h>
#include <LINK/graph/DHyperGraph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <LINK/basic/Matrix.h>
#include <LINK/basic/general.h>

//
// constructs the incidence matrix of a graph 
//
AsymMatrix<int> IncidenceMatrix(const Graph* graph, int direction)
{ 
    // associate each edge with a unique integer so we can index the matrices
    // we reuse the general purpose "mark" attribute

    int order=graph->order(), size=graph->size();
    const MSet<Edge*>& edges = graph->edges();
    Iterator<Edge*> get_edge(&edges);
    Edge *edge;
    
    int i=0;
    while (get_edge(edge))
	setAttribute((GraphObject*) edge, "mark", i++);

    // associate each vertex with a unique integer so we can index the matrices
    Array<Vertex*> vertices = graph->vertices();
    int num_vertices = vertices.size();
    for (i=0; i < num_vertices; i++)
	setAttribute((GraphObject*) vertices[i], "mark", i);
    
    AsymMatrix<int> incidenceMatrix(num_vertices, size);

    if ((direction==0) || (graph->type()==UNDBINARYGRAPH)) {
	get_edge.reset();
	while (get_edge(edge)) {
	    int j;
	    getAttribute((GraphObject*) edge, "mark", j);
	    Iterator<Vertex*> get_vertex(edge->vertices());
	    Vertex* vertex;
    	    while (get_vertex(vertex)) {
		int i;
		getAttribute((GraphObject*) vertex, "mark", i);
	        incidenceMatrix((num_vertices-1-i),j) = 1; 
	    }
        }
    }
    else {   //graph is directed or mixed or the user wishes a directed I.M. 
             //We cannot presently distinguish between directed and undirected
             //edges, therefore, we can only mark the source and sink nodes
             //for these edges.
        get_edge.reset();
	while (get_edge(edge)) {
	    int j;
	    getAttribute((GraphObject*) edge, "mark", j);

	    int i;
	    getAttribute((GraphObject*) edge->sourceVertex(), "mark", i);
	    incidenceMatrix((num_vertices-1-i),j) = 1;

	    getAttribute((GraphObject*) edge->sinkVertex(), "mark", i);
	    incidenceMatrix((num_vertices-1-i),j) = -1;
        }
    }
    return incidenceMatrix;  
}


UHyperGraph IncidenceMatrix2Graph(const AsymMatrix<int>& A)
{
	UHyperGraph result;
	warning("IncidenceMatrix2Graph() not implemented yet");
	return result;
}