/* -*- mode: C -*- */
/*
IGraph library.
Copyright (C) 2006 Gabor Csardi
MTA RMKI, Konkoly-Thege Miklos st. 29-33, Budapest 1121, Hungary
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA
*/
#include
int igraph_laplacian(const igraph_t *graph, igraph_matrix_t *res);
/**
* \ingroup conversion
* \function igraph_laplacian
* \brief Returns the Laplacian matrix of a graph
*
*
* The result for edge i--j is -1 if i!=j and is
* equal to the degree of vertex i if i==j
* igraph_laplacian will work on a directed graph but won't consider loops
* \param graph Pointer to the graph to convert
* \param res Pointer to an initialized matrix object, it will be
* resized if needed.
* \return Error code:
* \c IGRAPH_EINVAL invalid type argument.
*
* Time complexity: O(|V||V|),
* |V| is the
* number of vertices in the graph.
*/
int igraph_laplacian(const igraph_t *graph, igraph_matrix_t *res) {
igraph_eit_t edgeit;
long int no_of_nodes=igraph_vcount(graph);
igraph_bool_t directed=igraph_is_directed(graph);
long int from, to;
igraph_integer_t ffrom, fto;
igraph_vector_t degree;
int i;
IGRAPH_CHECK(igraph_matrix_resize(res, no_of_nodes, no_of_nodes));
igraph_matrix_null(res);
IGRAPH_CHECK(igraph_eit_create(graph, igraph_ess_all(0), &edgeit));
IGRAPH_FINALLY(igraph_eit_destroy, &edgeit);
IGRAPH_VECTOR_INIT_FINALLY(°ree, no_of_nodes);
if(directed){
IGRAPH_WARNING("Computing Laplacian of a directed graph");
IGRAPH_CHECK(igraph_degree(graph, °ree, igraph_vss_all(),
IGRAPH_OUT, IGRAPH_NO_LOOPS));
for(i=0;i