#  Copyright (c) 1997-2006
#  Ewgenij Gawrilow, Michael Joswig (Technische Universitaet Berlin, Germany)
#  http://www.math.tu-berlin.de/polymake,  mailto:polymake@math.tu-berlin.de
#
#  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, or (at your option) any
#  later version: http://www.gnu.org/licenses/gpl.txt.
#
#  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.
#-----------------------------------------------------------------------------
#  $Project: polymake $$Id: morse_matching.rules 7044 2006-02-21 19:34:28Z gawrilow $

INCLUDE
   complex_properties.rules

object SimplicialComplex;

# Category: Topology
# to compute a Morse matching by the greedy algorithm
label greedy

# Category: Topology
# to compute a Morse matching by Forman's canceling algorithm
label cancel


# category: Topology
# A Morse matching is a reorientation of the arcs in the Hasse diagram of a simplicial complex
# such that at most one arc incident to each face is reoriented (matching condition) and the
# resulting orientation is acyclic (acyclicity condition). Morse matchings capture the main
# structure of discrete Morse functions, see
#
#      Robin Forman: Morse Theory for Cell-Complexes,
#      Advances in Math., 134 (1998), pp. 90-145.
#
# This property is computed by one of two heuristics. The default heuristic is
# a simple greedy algorithm (@see greedy). The alternative is to use a canceling algorithm
# due to Forman (@see cancel). Note that the computation of a Morse matching of largest
# size is NP-hard. See
#
#      Michael Joswig, Marc E. Pfetsch: Computing Optimal Morse Matchings
#      SIAM J. Discrete Math., 2006, to appear
#
property MORSE_MATCHING
$type="graph";
$diff=sub { undef };


# category: Topology
# Size of the computed Morse matching.
property MORSE_MATCHING_SIZE
$type="cardinal";
$temporary=1;
$diff=sub { undef };

MORSE_MATCHING_SIZE : MORSE_MATCHING
  client("morse_matching_size", $this);


# category: Topology
# The critical faces of the computed Morse matching, i.e., the faces not
# incident to any reoriented arc (not matched).
property MORSE_MATCHING_CRITICAL_FACES
$type="array<set>";
$temporary=1;
$diff=sub { undef };


# category: Topology
# The vector of critical faces in each dimension.
property MORSE_MATCHING_CRITICAL_FACE_VECTOR
$type="array<cardinal>";
$temporary=1;
$diff=sub { undef };

MORSE_MATCHING_CRITICAL_FACES, MORSE_MATCHING_CRITICAL_FACE_VECTOR : MORSE_MATCHING
  client("morse_matching_critical_faces", $this);


# category: Topology
# Number of critical faces of the computed Morse matching.
property MORSE_MATCHING_N_CRITICAL_FACES
$type="cardinal";
$temporary=1;
$diff=sub { undef };

MORSE_MATCHING_N_CRITICAL_FACES: MORSE_MATCHING
  client("morse_matching_n_critical_faces", $this);



# clients to compute Morse matching:
MORSE_MATCHING, MORSE_MATCHING_SIZE, MORSE_MATCHING_CRITICAL_FACES, MORSE_MATCHING_N_CRITICAL_FACES, MORSE_MATCHING_CRITICAL_FACE_VECTOR : HASSE_DIAGRAM
WEIGHT 2.10
  client("morse_matching", $this, "-both");

greedy.morse_matching: MORSE_MATCHING, MORSE_MATCHING_SIZE, MORSE_MATCHING_CRITICAL_FACES, MORSE_MATCHING_N_CRITICAL_FACES, MORSE_MATCHING_CRITICAL_FACE_VECTOR : HASSE_DIAGRAM
WEIGHT 1.10
  client("morse_matching", $this, "-greedy");

cancel.morse_matching: MORSE_MATCHING, MORSE_MATCHING_SIZE, MORSE_MATCHING_CRITICAL_FACES, MORSE_MATCHING_N_CRITICAL_FACES, MORSE_MATCHING_CRITICAL_FACE_VECTOR : HASSE_DIAGRAM
WEIGHT 2.10
  client("morse_matching", $this, "-cancel");

# Local Variables:
# mode: perl
# c-basic-offset:3
# End:
