Debian Bug report logs - #482825
problem resolution doesn't display solutions ordered by score

version graph

Package: aptitude; Maintainer for aptitude is Aptitude Development Team <aptitude-devel@lists.alioth.debian.org>; Source for aptitude is src:aptitude.

Reported by: Jonas K�r <jonaskoelker@gnu.org>

Date: Sun, 25 May 2008 10:51:01 UTC

Severity: normal

Found in version aptitude/0.4.11.2-1

Fixed in version aptitude/0.5.2-1

Done: Daniel Burrows <dburrows@debian.org>

Bug is archived. No further changes may be made.

Toggle useless messages

View this report as an mbox folder, status mbox, maintainer mbox


Report forwarded to debian-bugs-dist@lists.debian.org, Daniel Burrows <dburrows@debian.org>:
Bug#482825; Package aptitude. Full text and rfc822 format available.

Acknowledgement sent to Jonas K�r <jonaskoelker@gnu.org>:
New Bug report received and forwarded. Copy sent to Daniel Burrows <dburrows@debian.org>. Full text and rfc822 format available.

Message #5 received at submit@bugs.debian.org (full text, mbox):

From: Jonas K�r <jonaskoelker@gnu.org>
To: Debian Bug Tracking System <submit@bugs.debian.org>
Subject: problem resolution doesn't display solutions ordered by score
Date: Sun, 25 May 2008 12:45:22 +0200
[Message part 1 (text/plain, inline)]
Package: aptitude
Version: 0.4.11.2-1
Severity: normal

When aptitude runs into a problem (packages conflict?) and needs to resolve
it, it displays a bunch of suggestions;  I've noted that they aren't sorted by
score.

I think the scoring algorithm works reasonably well, so it would make a lot of
sense to try to display the best scored alternative first.  If that's
infeasible (potentially there are many alternatives and they take a while to
compute), approximate it.

For instance, stick the first five suggestions in a maxheap; when the user
refuses the top one, add two and repeat.  If you want extra brownie points,
compute the next two while waiting for user input; this decreases my wait time
and makes me a happy man ;)

Possibly a faster growing look-ahead buffer would be useful; you could either
use a bigger constant or go superlinear; say, n^{3/2} or n^{4/2}.

-- Package-specific info:
aptitude 0.4.11.2 compiled at Apr 12 2008 04:21:26
Compiler: g++ 4.2.3 (Debian 4.2.3-3)
Compiled against:
  apt version 4.6.0
  NCurses version 5.6
  libsigc++ version: 2.0.18
  Ept support enabled.

Current library versions:
  NCurses version: ncurses 5.6.20080203
  cwidget version: 0.5.11
  Apt version: 4.6.0
	linux-gate.so.1 =>  (0xffffe000)
	libapt-pkg-libc6.7-6.so.4.6 => /usr/lib/libapt-pkg-libc6.7-6.so.4.6 (0xb7ed6000)
	libncursesw.so.5 => /lib/libncursesw.so.5 (0xb7e9a000)
	libsigc-2.0.so.0 => /usr/lib/libsigc-2.0.so.0 (0xb7e93000)
	libcwidget.so.3 => /usr/lib/libcwidget.so.3 (0xb7da3000)
	libept.so.0 => /usr/lib/libept.so.0 (0xb7d2b000)
	libxapian.so.15 => /usr/lib/libxapian.so.15 (0xb7bb8000)
	libz.so.1 => /usr/lib/libz.so.1 (0xb7ba3000)
	libpthread.so.0 => /lib/i686/cmov/libpthread.so.0 (0xb7b8b000)
	libstdc++.so.6 => /usr/lib/libstdc++.so.6 (0xb7a9d000)
	libm.so.6 => /lib/i686/cmov/libm.so.6 (0xb7a78000)
	libgcc_s.so.1 => /lib/libgcc_s.so.1 (0xb7a6b000)
	libc.so.6 => /lib/i686/cmov/libc.so.6 (0xb791e000)
	libutil.so.1 => /lib/i686/cmov/libutil.so.1 (0xb791a000)
	libdl.so.2 => /lib/i686/cmov/libdl.so.2 (0xb7915000)
	/lib/ld-linux.so.2 (0xb7fbb000)
Terminal: screen
$DISPLAY is set.
`which aptitude`: /usr/bin/aptitude
aptitude version information:

aptitude linkage:

-- System Information:
Debian Release: lenny/sid
  APT prefers testing
  APT policy: (650, 'testing'), (600, 'stable'), (550, 'unstable')
Architecture: i386 (i686)

Kernel: Linux 2.6.24-1-686 (SMP w/2 CPU cores)
Locale: LANG=en_US.UTF-8, LC_CTYPE=en_US.UTF-8 (charmap=UTF-8)
Shell: /bin/sh linked to /bin/dash

Versions of packages aptitude depends on:
ii  apt [libapt-pkg-libc6. 0.7.11            Advanced front-end for dpkg
ii  libc6                  2.7-6             GNU C Library: Shared libraries
ii  libcwidget3            0.5.11-1          high-level terminal interface libr
ii  libept0                0.5.17            High-level library for managing De
ii  libgcc1                1:4.3.0-1         GCC support library
ii  libncursesw5           5.6+20080203-1    Shared libraries for terminal hand
ii  libsigc++-2.0-0c2a     2.0.18-2          type-safe Signal Framework for C++
ii  libstdc++6             4.3.0-1           The GNU Standard C++ Library v3
ii  libxapian15            1.0.5-1           Search engine library
ii  zlib1g                 1:1.2.3.3.dfsg-11 compression library - runtime

Versions of packages aptitude recommends:
ii  aptitude-doc-en [aptitude-doc 0.4.11.2-1 English manual for aptitude, a ter
pn  libparse-debianchangelog-perl <none>     (no description available)

-- no debconf information

-- 
Jonas Kölker <jonaskoelker@gnu.org> <URL:http://jonaskoelker.ignorelist.com>
[signature.asc (application/pgp-signature, inline)]

Information forwarded to debian-bugs-dist@lists.debian.org:
Bug#482825; Package aptitude. Full text and rfc822 format available.

Acknowledgement sent to Daniel Burrows <dburrows@debian.org>:
Extra info received and forwarded to list. Full text and rfc822 format available.

Message #10 received at 482825@bugs.debian.org (full text, mbox):

From: Daniel Burrows <dburrows@debian.org>
To: Jonas K�r <jonaskoelker@gnu.org>, 482825@bugs.debian.org
Subject: Re: Bug#482825: problem resolution doesn't display solutions ordered by score
Date: Mon, 26 May 2008 12:57:44 -0700
On Sun, May 25, 2008 at 12:45:22PM +0200, Jonas K�r <jonaskoelker@gnu.org> was heard to say:
> When aptitude runs into a problem (packages conflict?) and needs to resolve
> it, it displays a bunch of suggestions;  I've noted that they aren't sorted by
> score.

  Unfortunately, there is no algorithm I know of that will always produce
solutions sorted by score in a reasonable amount of time and space.  You
can't predict whether a given step will ultimately lead to a higher or
lower score actually calculating all the potential solutions that
include it (because, essentially, a step that scores badly might open
possibilities down the line that score well), and the number of
potential solutions is exponential.

  The idea of doing a finite lookahead is interesting, since it doesn't
require any serious algorithmic changes.  There's a risk of falling off
the edge of a combinatorial explosion [0], but with suitable step-limits
that can be avoided.  (e.g.: instead of saying "show me the first
solution you calculate within 5,000 steps", as I do now, I can say "show
me all the solutions you calculate up to 5,000 steps" and then pick the
best one; if there is a blowup, I can just take the first solution that
the resolver manages to converge on, as I do now).

  Another question is whether a better UI for this exists; e.g., maybe
display a list of solution summaries ordered by score.  I think this
would actually be worse, but maybe there are other options that are an
improvement.

  Daniel

  [0] the resolver is tuned so that it usually converges to *a* solution
      in a reasonable amount of time, but solutions beyond the first are
      sometimes hard to calculate.  This usually happens if you have
      more than 2 repositories in sources.list and a large suite of
      packages with complex interdependencies that are all at different
      versions in each repository; aptitude can end up searching a large
      proportion of the set of possible combinations of packages trying
      to find a solution.




Tags added: pending Request was from Daniel Burrows <dburrows@debian.org> to control@bugs.debian.org. (Fri, 24 Apr 2009 02:06:12 GMT) Full text and rfc822 format available.

Reply sent to Daniel Burrows <dburrows@debian.org>:
You have taken responsibility. (Fri, 24 Apr 2009 15:25:09 GMT) Full text and rfc822 format available.

Notification sent to Jonas K�r <jonaskoelker@gnu.org>:
Bug acknowledged by developer. (Fri, 24 Apr 2009 15:25:28 GMT) Full text and rfc822 format available.

Message #17 received at 482825-close@bugs.debian.org (full text, mbox):

From: Daniel Burrows <dburrows@debian.org>
To: 482825-close@bugs.debian.org
Subject: Bug#482825: fixed in aptitude 0.5.2-1
Date: Fri, 24 Apr 2009 15:02:15 +0000
Source: aptitude
Source-Version: 0.5.2-1

We believe that the bug you reported is fixed in the latest version of
aptitude, which is due to be installed in the Debian FTP archive:

aptitude-dbg_0.5.2-1_i386.deb
  to pool/main/a/aptitude/aptitude-dbg_0.5.2-1_i386.deb
aptitude-doc-cs_0.5.2-1_all.deb
  to pool/main/a/aptitude/aptitude-doc-cs_0.5.2-1_all.deb
aptitude-doc-en_0.5.2-1_all.deb
  to pool/main/a/aptitude/aptitude-doc-en_0.5.2-1_all.deb
aptitude-doc-fi_0.5.2-1_all.deb
  to pool/main/a/aptitude/aptitude-doc-fi_0.5.2-1_all.deb
aptitude-doc-fr_0.5.2-1_all.deb
  to pool/main/a/aptitude/aptitude-doc-fr_0.5.2-1_all.deb
aptitude-doc-ja_0.5.2-1_all.deb
  to pool/main/a/aptitude/aptitude-doc-ja_0.5.2-1_all.deb
aptitude-gtk_0.5.2-1_i386.deb
  to pool/main/a/aptitude/aptitude-gtk_0.5.2-1_i386.deb
aptitude_0.5.2-1.diff.gz
  to pool/main/a/aptitude/aptitude_0.5.2-1.diff.gz
aptitude_0.5.2-1.dsc
  to pool/main/a/aptitude/aptitude_0.5.2-1.dsc
aptitude_0.5.2-1_i386.deb
  to pool/main/a/aptitude/aptitude_0.5.2-1_i386.deb
aptitude_0.5.2.orig.tar.gz
  to pool/main/a/aptitude/aptitude_0.5.2.orig.tar.gz



A summary of the changes between this version and the previous one is
attached.

Thank you for reporting the bug, which will now be closed.  If you
have further comments please address them to 482825@bugs.debian.org,
and the maintainer will reopen the bug report if appropriate.

Debian distribution maintenance software
pp.
Daniel Burrows <dburrows@debian.org> (supplier of updated aptitude package)

(This message was generated automatically at their request; if you
believe that there is a problem with it please contact the archive
administrators by mailing ftpmaster@debian.org)


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Format: 1.8
Date: Thu, 23 Apr 2009 09:08:27 -0700
Source: aptitude
Binary: aptitude aptitude-gtk aptitude-dbg aptitude-doc-cs aptitude-doc-en aptitude-doc-fi aptitude-doc-fr aptitude-doc-ja
Architecture: source i386 all
Version: 0.5.2-1
Distribution: experimental
Urgency: low
Maintainer: Daniel Burrows <dburrows@debian.org>
Changed-By: Daniel Burrows <dburrows@debian.org>
Description: 
 aptitude   - terminal-based package manager (terminal interface only)
 aptitude-dbg - Debug symbols for the aptitude package manager
 aptitude-doc-cs - Czech manual for aptitude, a terminal-based package manager
 aptitude-doc-en - English manual for aptitude, a terminal-based package manager
 aptitude-doc-fi - Finnish manual for aptitude, a terminal-based package manager
 aptitude-doc-fr - French manual for aptitude, a terminal-based package manager
 aptitude-doc-ja - Japanese manual for aptitude, a terminal-based package manager
 aptitude-gtk - terminal-based package manager (GUI and terminal interfaces)
Closes: 473296 482825 510977 511238 512384 513472 514011 514545 514676 514714 514820 514930 516296 516296 516389 516527 517272 518981 519693 521152 521255 522881 524221 524667
Changes: 
 aptitude (0.5.2-1) experimental; urgency=low
 .
   * New upstream release.
 .
     - Support for guaranteed ordering of solutions produced by the
     dependency resolver. (Closes: #514820, #514930, #524221, #473296)
 .
     - The dependency resolver will continue searching for a short time
       after finding a solution, in case a better solution turns up.
       (Closes: #482825)
 .
     - The GTK+ interface should no longer crash while trying to find
       dependency chains. (Closes: #514714)
 .
     - aptitude is now more careful about automatically canceling the
       removal of an unused package, to avoid triggering a conflict with
       other packages (for instance, packages included in a dependency
       solution). (Closes: #522881, #524667)
 .
     - The curses interface no longer warns users when they purge an
       already-removed Essental package. (Closes: #513472)
 .
     - The curses interface no longer computes an excessive amount of
       dependency information every time a package is highlighted.
       (Closes: #516296)
 .
     - Fixed incorrect formatting in some command-line error messages.
       (Closes: #516296, #514676)
 .
     - Fix really stupid column wrapping in "aptitude why".
       (Closes: #516389)
 .
     - Translation updates:
 .
       + Asturian (Closes: #518981, #519693)
       + Danish (Closes: #512384)
       + German
       + Italian
       + Norwegian Bokmål (Closes: #510977)
       + Spanish (Closes: #517272)
       + Swedish (Closes: #511238, #514011)
 .
   * Change the reportbug script to run in the C locale, so program output
     that's inserted doesn't get translated.
 .
   * Change the description of aptitude-gtk to say that it has a GUI
     interface. (Closes: #514545, #521152)
 .
   * Give aptitude-gtk a versioned dependency on aptitude. (Closes: #516527)
 .
   * Include .desktop file contributed by Fabit Greffrath.  I know that
     using su-to-root is not ideal, but since aptitude-gtk can't be used to
     install / remove packages unless it's run as root, this is probably a
     good interim approach.  Eventually we'll hook up the code so that the
     GTK+ frontend can do what the curses frontend does (automagically
     become root and preserve selections). (Closes: #521255)
 .
   * New build-deps: liblog4cxx10-dev, inkscape.
Checksums-Sha1: 
 14f15b10147b5b9572c6937fa6b5949d377b8a94 1470 aptitude_0.5.2-1.dsc
 b138312be6fcc90c81dc4c005717d512f57ea750 7133402 aptitude_0.5.2.orig.tar.gz
 ec7e4ac6bb16106322a92a6f4227bbba6c81ef96 35501 aptitude_0.5.2-1.diff.gz
 6113b0b646e805bd4f3682c345c44fe77025db5d 3330290 aptitude_0.5.2-1_i386.deb
 61d8aba41318a80441fda0fb6e43a443a01c558d 1487680 aptitude-gtk_0.5.2-1_i386.deb
 554f45fe2c4a28ca0496e07326a672dd1b9ca499 16278950 aptitude-dbg_0.5.2-1_i386.deb
 53b100d1d1ea89a350d30365ef7b1a00848bff8f 379860 aptitude-doc-cs_0.5.2-1_all.deb
 6b7d2da18ab7034cdc53fd752ae8d1be794bafb3 377440 aptitude-doc-en_0.5.2-1_all.deb
 b54e2c2bddef79b78295c653459ddf6266728003 271822 aptitude-doc-fi_0.5.2-1_all.deb
 8d5811fd20a918d3a2235e22cb461417e4c26f36 325090 aptitude-doc-fr_0.5.2-1_all.deb
 7a3a746145011cf43915be822b34b0bf83786579 388792 aptitude-doc-ja_0.5.2-1_all.deb
Checksums-Sha256: 
 3fd4c2436207d4e547ef1b834e56f3ed53d064a24086883a355946cb9669a9af 1470 aptitude_0.5.2-1.dsc
 491c7471219addaa7769655837c81206da80cc2f0ef7c510707d1499073715be 7133402 aptitude_0.5.2.orig.tar.gz
 3f8c3535a5903ae2596ec74b5253daaf20d026db4e8e2b78c8bddf832d4a9bc9 35501 aptitude_0.5.2-1.diff.gz
 73d04bfe1a88352a15ed41002d2aea6fd07291e5698c5b885c53648f4597d40e 3330290 aptitude_0.5.2-1_i386.deb
 6207d9746703f729a61d5c8b5a1f58b28c79f656f9fa0520c73a4d41e4b6a15a 1487680 aptitude-gtk_0.5.2-1_i386.deb
 6e0fbc933f99f7360b9d898e03df259bef433510724f67bea28241f4b23eac4d 16278950 aptitude-dbg_0.5.2-1_i386.deb
 acb2168e036b4966eb0bf4957cf5a12281e58350cbaa782efcb0821641bdbc24 379860 aptitude-doc-cs_0.5.2-1_all.deb
 d88bf0bc1c1aa78f1559d1d0752926a3ac5dae8b8eb0e0d1a5744c9b5f965356 377440 aptitude-doc-en_0.5.2-1_all.deb
 cf5a2c2335d7aa390fa024b0746431cafc873b3e1e38f4f8891b82b94056efcc 271822 aptitude-doc-fi_0.5.2-1_all.deb
 efacac86bb4ddf5d883d28449f30cf9f9992ed8f3f4a38e178d3a92753ef40eb 325090 aptitude-doc-fr_0.5.2-1_all.deb
 93b03cd14daa3b1f439e075e56a82ff7dd9d4eec798ba0c9d6abe8b4b55361c2 388792 aptitude-doc-ja_0.5.2-1_all.deb
Files: 
 bcfeb8ecb6ed184a74bd5eaa47b09bf7 1470 admin - aptitude_0.5.2-1.dsc
 074aeb68c570003a58f42d1e6031fa25 7133402 admin - aptitude_0.5.2.orig.tar.gz
 1e5c119f64d2ba7af4ea9c2fa71bf0d3 35501 admin - aptitude_0.5.2-1.diff.gz
 84265fa156faaaeb731a57acab855f9c 3330290 admin important aptitude_0.5.2-1_i386.deb
 f2ecb4df9b8d592c9b690c99ca37c86e 1487680 admin important aptitude-gtk_0.5.2-1_i386.deb
 ec67d6e719d9d3dc79495c62578764be 16278950 devel extra aptitude-dbg_0.5.2-1_i386.deb
 13c8fd668a55fe601d727def826f1167 379860 doc optional aptitude-doc-cs_0.5.2-1_all.deb
 620760f6d415a6c4f6994281e0c98089 377440 doc optional aptitude-doc-en_0.5.2-1_all.deb
 63de5659873f329ec0eb9183fd7c9c11 271822 doc optional aptitude-doc-fi_0.5.2-1_all.deb
 e44fe09a6758a787f5f50074b8056391 325090 doc optional aptitude-doc-fr_0.5.2-1_all.deb
 19d76cd2ebe35d7b5a7490cd9d820c16 388792 doc optional aptitude-doc-ja_0.5.2-1_all.deb

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)

iEYEARECAAYFAknxxhMACgkQch6xsM7kSXiFZACgw5tIvOzMjJ+ooOw4sFQttOfI
BAsAoNjJ2rMrw78+q65/SaTeXZvl4xEX
=NIZF
-----END PGP SIGNATURE-----





Bug archived. Request was from Debbugs Internal Request <owner@bugs.debian.org> to internal_control@bugs.debian.org. (Tue, 23 Mar 2010 07:33:16 GMT) Full text and rfc822 format available.

Send a report that this bug log contains spam.


Debian bug tracking system administrator <owner@bugs.debian.org>. Last modified: Sun Apr 20 08:34:27 2014; Machine Name: beach.debian.org

Debian Bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.