#
# spec file for package perl-Algorithm-Munkres
#
# Copyright (c) 2024 SUSE LLC
#
# All modifications and additions to the file contributed by third parties
# remain the property of their copyright owners, unless otherwise agreed
# upon. The license for this file, and modifications and additions to the
# file, is the same license as for the pristine package itself (unless the
# license for the pristine package is not an Open Source License, in which
# case the license is the MIT License). An "Open Source License" is a
# license that conforms to the Open Source Definition (Version 1.9)
# published by the Open Source Initiative.

# Please submit bugfixes or comments via https://bugs.opensuse.org/
#


%define cpan_name Algorithm-Munkres
Name:           perl-Algorithm-Munkres
Version:        0.80.0
Release:        0
# 0.08 -> normalize -> 0.80.0
%define cpan_version 0.08
#Upstream:  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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
License:        GPL-2.0-or-later
Summary:        Munkres.pm
URL:            https://metacpan.org/release/%{cpan_name}
Source0:        https://cpan.metacpan.org/authors/id/T/TP/TPEDERSE/%{cpan_name}-%{cpan_version}.tar.gz
Source1:        cpanspec.yml
Source100:      README.md
BuildArch:      noarch
BuildRequires:  perl
BuildRequires:  perl-macros
Provides:       perl(Algorithm::Munkres) = %{version}
%undefine       __perllib_provides
%{perl_requires}

%description
    Assignment Problem: Given N jobs, N workers and the time taken by
    each worker to complete a job then how should the assignment of a
    Worker to a Job be done, so as to minimize the time taken.

	Thus if we have 3 jobs p,q,r and 3 workers x,y,z such that:
	    x  y  z
	 p  2  4  7
	 q  3  9  5
	 r  8  2  9

        where the cell values of the above matrix give the time required
        for the worker(given by column name) to complete the job(given by
        the row name)

	then possible solutions are:
		 	 Total
	 1. 2, 9, 9       20
	 2. 2, 2, 5        9
	 3. 3, 4, 9       16
	 4. 3, 2, 7       12
	 5. 8, 9, 7       24
	 6. 8, 4, 5       17

    Thus (2) is the optimal solution for the above problem.
    This kind of brute-force approach of solving Assignment problem
    quickly becomes slow and bulky as N grows, because the number of
    possible solution are N! and thus the task is to evaluate each
    and then find the optimal solution.(If N=10, number of possible
    solutions: 3628800 !)
    Munkres' gives us a solution to this problem, which is implemented
    in this module.

    This module also solves Assignment problem for rectangular matrices
    (M x N) by converting them to square matrices by padding zeros. ex:
    If input matrix is:
	 [2, 4, 7, 9],
	 [3, 9, 5, 1],
	 [8, 2, 9, 7]
    i.e 3 x 4 then we will convert it to 4 x 4 and the modified input
    matrix will be:
	 [2, 4, 7, 9],
	 [3, 9, 5, 1],
	 [8, 2, 9, 7],
 	 [0, 0, 0, 0]

%prep
%autosetup  -n %{cpan_name}-%{cpan_version}

%build
perl Makefile.PL INSTALLDIRS=vendor
%make_build

%check
make test

%install
%perl_make_install
%perl_process_packlist
%perl_gen_filelist

%files -f %{name}.files
%doc Changes README

%changelog