// 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
// 

///////////////////////////////////////////////////////////////////////////
// LINK: Generic Graph Tool and Class Library                               
//
//      Function name:  LaplacianMatrix
//                                                                            
//      Synopsis: Constructs the Laplacian Matrix given a matrix.
//                
//                                                                            
//      Description: The Laplacian Matrix is simply the transpose of a 
//                   matrix multiplied by the matrix itself.  A symmetric
//                   matrix is returned.
//                                                                           
//      Creation: 1993 July 2, James T. Klosowski, jklosow@mathlab.sunysb.edu  
//                                                                            
//      Routines used:                                                       
//                                                                            
//      Related files: Matrix.cc, Matrix.h
//                                                                            
//      Test suite: 
//                                                                            
//      User documentation:                                                   
//                                                                            
//      Development History:                                                  
//           1993 July 2  Lifted code from lineGraph.cc to write function
//           Author of lineGraph.cc : murphy@c3serve.c3.lanl.gov
//
//      Testing History:                                                      
//           date  - full@email.address.xxx  description of tests done
//                                                                           
//      Code Review:                                                          
//           date  - full@email.address.xxx  any notes you may have 
//
//      Bugs and Deficiencies:                          
//
//
//	Copyright (c) 1993 - State University of New York, Stony Brook
//////////////////////////////////////////////////////////////////////////////

#include <iostream.h>
#include <LINK/basic/Matrix.h>

SymMatrix<int> LaplacianMatrix(Matrix<int>& M)
{
    SymMatrix<int> result(M.numCols());
    for (int i=0; i < M.numCols(); i++) 
        for (int j=0; j <= i; j++)
            for (int k=0; k < M.numRows(); k++)
                result(i,j) += M(k,i) * M(k,j);
    return result;
}