The module "graph_reduce" of the Mastrave modelling library

Copyright and license notice of the function graph_reduce

Copyright © 2008,2009,2010,2011,2012 Daniele de Rigo

The file graph_reduce.m is part of Mastrave.

Mastrave 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 3 of the License, or (at your option) any later version.

Mastrave 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 Mastrave. If not, see http://www.gnu.org/licenses/.

Function declaration

 [reduced_val, edge_vals, norm_vals] = ...
    graph_reduce( node_weights        , 
                  edge_weights        , 
                  edge_func           , 
                  norm_func    = @()1 , 
                  reduce_func  = @sum , 
                  use_autoinfo = true )

Description

Utility for applying a reduce operator (in the sense of APL array operators) to a graph.

A graph here is considered as an array-based semantic structure which extends the semantics of a vector by also associating to it a matrix describing the intensity (the weight) of the mutual relationship between each element of the vector (edge weight matrix). The utility allows concisely expressing a generic data-transformation from a graph to a statistics reduced_val which summarizes the graph characteristics following user-provided data-transformation functions.

The graph to be processed is described by passing the weights associated to each node (the vector node_weights ) and the weights associated to each edge (the matrix edge_weights ). Passing a (full or sparse) matrix as edge_weights imposes all edges to be considered. Instead, passing a vector as edge_weights constrains the reduction to only consider the edges whose weights would correspond to the diagonal elements of the edge weight matrix. In this case, only autocycles (i.e. edges whose endpoints are the same node) are considered.

The reduced_val statistics is computed in three steps, by:

1. computing the values edge_vals assigned to each edge of the graph
by means of the passed data-transformation function edge_func ;

2. computing optional normalization factors norm_vals (using the
function norm_func ) with which edge_vals have to be scaled
(by default, normalization is omitted);

3. aggregating the normalized edge_vals with the reduce operator
reduce_func (by default, the reduce fucntion is @sum ).

Input arguments

 node_weights      ::numeric::
                   Vector of the weights associated to each node
                   of the graph.

 edge_weights      ::numeric,matrix::
                   Matrix of the weights associated to each edge
                   of the graph or vector of the weights associated
                   to autocycles of the graph.

 edge_func         ::function_handle::
                   Data-transformation function for computing  edge_vals .
                   The function is expected to receive up to three input
                   arguments of the same size, each element of them
                   respectively is the weight of the  i-th  and  j-th  
                   node and the weight of the edge connecting the  i-th
                   and  j-th  nodes.

 norm_func         ::function_handle::
                   Data-transformation function for computing  norm_vals .
                   The function is expected to receive up to three input
                   arguments of the same size, each element of them
                   respectively is the weight of the  i-th  and  j-th  
                   node and the weight of the edge connecting the  i-th
                   and  j-th  nodes.
                   If omitted, its default value is the constant unit
                   function: 
                      @()1
                   so that the values computed with  edge_func  are not
                   normalized. 
                   If an empty array is passed, the default value is used. 

 reduce_func       ::function_handle::
                   Data-transformation function for computing  reduce_val .
                   The function is expected to receive as input argument
                   a vector containing the ratio:
                       edge_vals  ./  norm_vals  .
                   If omitted, its default values is:  @sum  so that all
                   normalized  edge_vals  are summed together.
                   If an empty array is passed, the default value is used.

 use_autoinfo      ::logical::
                   Flag for controlling whether the information associated
                   with autocycles is to be used or not.
                   If omitted, its default value is:  true  so information
                   referring to autocycles is considered. 
                   If an empty array is passed, the default value is used.

                  

Example of usage

   nodes = [10 1 1 6 2]
   edges = [ 1 1 0 1 0; 0 2 3 1 1; 0 2 1 1 1; 20 0 0 1 1; 0 1 1 1 1]

   % Basic statistics:
   % Number of edges with nonzero weights
   sum( edges ~= 0 )
   graph_reduce( nodes, edges, @(x,y,e)e~=0 )

   % Maximum aggregated weight of the nodes connected by nonzero weights
   % (aggregation: sum; edge weights: unused; autocycles: included)
   graph_reduce( nodes, edges, @(x,y,e)(x+y).*(e~=0), [], @max )
   % (aggregation: sum; edge weights: unused; autocycles: excluded)
   graph_reduce( nodes, edges, @(x,y,e)(x+y).*(e~=0), [], @max, false )
   % (aggregation: product; edge weights: unused; autocycles: excluded)
   graph_reduce( nodes, edges, @(x,y,e)(x.*y).*(e~=0), [], @max, false )

   % Maximum aggregated weight of the nodes connected by nonzero weights
   % (aggregation: sum; edge weights: used; autocycles: included)
   graph_reduce( nodes, edges, @(x,y,e)(x+y).*e, [], @max )
   % (aggregation: sum; edge weights: used; autocycles: excluded)
   graph_reduce( nodes, edges, @(x,y,e)(x+y).*e, [], @max, false )
   % (aggregation: product; edge weights: used; autocycles: excluded)
   graph_reduce( nodes, edges, @(x,y,e)(x.*y).*e, [], @max, false )

See also:
   graph_scan



Keywords:
   graph, data-transformation, reduce



Version: 0.4.1

Support

The Mastrave modelling library is committed to provide reusable and general - but also robust and scalable - modules for research modellers dealing with computational science.  You can help the Mastrave project by providing feedbacks on unexpected behaviours of this module.  Despite all efforts, all of us - either developers or users - (should) know that errors are unavoidable.  However, the free software paradigm successfully highlights that scientific knowledge freedom also implies an impressive opportunity for collectively evolve the tools and ideas upon which our daily work is based.  Reporting a problem that you found using Mastrave may help the developer team to find a possible bug.  Please, be aware that Mastrave is entirely based on voluntary efforts: in order for your help to be as effective as possible, please read carefully the section on reporting problems.  Thank you for your collaboration.