// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Michael Murphy (Los Alamos National Laboratory)

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

AsymMatrix<int>
AdjacencyMatrix(const Graph *g)
{
	int i, neigh_rank, order = g->order();
	AsymMatrix<int> adj_matrix(order,order);  
	const SortedArray<Vertex*>& vertices = g->vertices();

	for (i=0; i<order; i++) {
		Set<Vertex*> neighs = vertices[i]->neighbors();                
		Iterator<Vertex*> get_neigh(&neighs);
		Vertex *n;
		while (get_neigh(n)) {
			neigh_rank = g->rank(n); 
			adj_matrix(i, neigh_rank) = 1;
		}
	}
	adj_matrix.display(cout);
	return adj_matrix;
}

// saves space if we are dealing with huge graphs
SymMatrix<int> 
UndirectedGraph2AdjacencyMatrix(const Graph* graph)
{
// might want to write, might want to delete
}

//
// constructs a graph given an adjacency matrix
//
MBinGraph
AdjacencyMatrix2Graph(const Matrix<int>& passed_matrix)
{
    int i, numVertices = passed_matrix.numRows();

    UBinGraph resultGraph;

    char s[10];  // temporary label string;

    // Create Vertices in the graph
    for (int j=0; j< numVertices; j++) {
        sprintf(s,"%d",j);
        resultGraph.addVertex(s);
    }

    // go through each element in the adjacency matrix, and add an edge if
    // something is there.

    Array<Vertex*> vertices = resultGraph.vertices();
    for (i=0; i < numVertices; i++) {
        for (int j=0; j<= i; j++) {

            if (passed_matrix(i,j)) {   // add the edge 
		Set<Vertex*> s;
		s.insert(vertices[i]);
		s.insert(vertices[j]);
                resultGraph.addEdge(s);
	    }
        }
    }
    MBinGraph resultGraph2 = resultGraph;
    return(resultGraph2);
}

MBinGraph
AdjacencyMatrix2Digraph(const Matrix<int>& passed_matrix)
{
    int i, numVertices = passed_matrix.numRows();

    DBinGraph resultGraph;

    char s[10];  // temporary label string;

    // Create Vertices in the graph
    for (int j=0; j< numVertices; j++) {
        sprintf(s,"%d",j);
        resultGraph.addVertex(s);
    }

    // go through each element in the adjacency matrix, and add an edge if
    // something is there.

    Array<Vertex*> vertices = resultGraph.vertices();
    for (i=0; i < numVertices; i++) {
        for (int j=0; j< numVertices; j++) {

            if (passed_matrix(i,j)) {  // add the edge 
		Sequence<Vertex*> s;
		s.append(vertices[i]);
		s.append(vertices[j]);
                resultGraph.addEdge(s);
	    }
        }
    }
    MBinGraph resultGraph2 = resultGraph;
    return(resultGraph);
}