[Aptitude-devel] r3151 - in branches/aptitude-0.3/aptitude: . src/generic src/generic/problemresolver
Daniel Burrows
dburrows@costa.debian.org
Wed, 27 Apr 2005 15:56:27 +0000
Author: dburrows
Date: Wed Apr 27 15:56:24 2005
New Revision: 3151
Modified:
branches/aptitude-0.3/aptitude/ChangeLog
branches/aptitude-0.3/aptitude/src/generic/aptcache.cc
branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.cc
branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h
branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Penalize brokenness less, and avoid generating too many successors.
Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog (original)
+++ branches/aptitude-0.3/aptitude/ChangeLog Wed Apr 27 15:56:24 2005
@@ -1,5 +1,18 @@
2005-04-27 Daniel Burrows <dburrows@debian.org>
+ * src/generic/aptcache.cc, src/generic/aptitude_resolver.cc, src/generic/aptitude_resolver.h, src/generic/problemresolver/problemresolver.h:
+
+ Put a cap on how many successors will be generated for any given
+ dep. This is sufficient to generate all solutions (albiet
+ possibly in a bad order); for simple problems (where everything
+ worked already) it has no effect if the cap is large enough; and
+ it should produce reasonable results for complicated programs.
+
+ * src/generic/aptcache.cc:
+
+ Penalize brokenness less again; placing too high a bounty on
+ fixing broken deps makes solutions turn up in the wrong order.
+
* src/generic/aptcache.cc:
Make infinity smaller and penalize brokenness more. Now if
Modified: branches/aptitude-0.3/aptitude/src/generic/aptcache.cc
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/aptcache.cc (original)
+++ branches/aptitude-0.3/aptitude/src/generic/aptcache.cc Wed Apr 27 15:56:24 2005
@@ -1350,8 +1350,9 @@
assert(resolver==NULL);
resolver=new aptitude_resolver(aptcfg->FindI(PACKAGE "::ProblemResolver::StepScore", -10),
- aptcfg->FindI(PACKAGE "::ProblemResolver::BrokenScore", -200),
+ aptcfg->FindI(PACKAGE "::ProblemResolver::BrokenScore", -50),
aptcfg->FindI(PACKAGE "::ProblemResolver::Infinity", 50000),
+ aptcfg->FindI(PACKAGE "::ProblemResolver::Max-Successors", 50),
aptcfg->FindI(PACKAGE "::ProblemResolver::ResolutionScore", 50));
resolver->add_action_scores(aptcfg->FindI(PACKAGE "::ProblemResolver::PreserveManualScore", 40),
Modified: branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.cc
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.cc (original)
+++ branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.cc Wed Apr 27 15:56:24 2005
@@ -22,8 +22,9 @@
aptitude_resolver::aptitude_resolver(int step_penalty,
int broken_penalty,
int infinity,
+ int max_successors,
int resolution_score)
- :generic_problem_resolver<aptitude_universe>(step_penalty, broken_penalty, infinity, resolution_score, universe),
+ :generic_problem_resolver<aptitude_universe>(step_penalty, broken_penalty, infinity, max_successors, resolution_score, universe),
universe()
{
}
Modified: branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h (original)
+++ branches/aptitude-0.3/aptitude/src/generic/aptitude_resolver.h Wed Apr 27 15:56:24 2005
@@ -1168,7 +1168,8 @@
const aptitude_universe universe;
public:
aptitude_resolver(int step_score, int broken_score,
- int infinity, int resolution_score);
+ int infinity, int max_successors,
+ int resolution_score);
/** Assign scores to all packages and all package versions according
* to its arguments. All scores are assigned with add_score, so
Modified: branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
==============================================================================
--- branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h (original)
+++ branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h Wed Apr 27 15:56:24 2005
@@ -468,6 +468,31 @@
*/
int minimum_score;
+ /** The "maximum" number of successors to generate for any given
+ * node. Note, however, that a full set of successors will always
+ * be generated for each broken dependency, so this is not exact.
+ *
+ * The theoretical justification is that in order to cover all
+ * solutions, it's sufficient to generate all successors for a
+ * single broken dependency. This avoids the problem that when a
+ * large number of packages are broken, or when a single package
+ * version with a large number of reverse dependencies is broken,
+ * you can end up searching way too many successor nodes, even if
+ * all the successors are discarded outright.
+ *
+ * Unfortunately, only generating one successor has its own
+ * problem: solutions might be generated out-of-order (i.e., worse
+ * solutions before better). This variable allows you to seek a
+ * "happy medium" by generating a reasonable number of successors,
+ * but not too many. If a single package breaks a large number of
+ * other packages, then any attempt to fix those packages should
+ * generate the correct successor (which will then pop to the top
+ * of the queue and likely stay there), while if a large number of
+ * unrelated packages are broken, it doesn't matter which successor
+ * goes first.
+ */
+ unsigned int max_successors;
+
/** How much to reward real solutions -- solutions that fix all
* dependencies. Make this big to immediately pick them up, or
* small to ignore "bad" solutions (at the risk of running out of
@@ -530,8 +555,10 @@
/** Enqueues a single successor node to the given solution by
* installing the given package version.
+ *
+ * \return \b true if the new solution was not in the closed set.
*/
- void try_install(const solution &s,
+ bool try_install(const solution &s,
const version &v)
{
version old_version=s.version_of(v.get_package());
@@ -605,7 +632,7 @@
{
if(debug)
std::cout << "Not generating solution (infinite badness " << new_score << "<" << minimum_score << ")" << std::endl;
- return;
+ return true;
}
solution s2=solution(action(v), s,
@@ -623,6 +650,8 @@
}
open.push(s2);
+
+ return true;
}
else
{
@@ -632,14 +661,23 @@
s2.dump(std::cout);
std::cout << std::endl;
}
+
+ return false;
}
}
/** Generates (and enqueues) successor nodes for the given broken
* dependency of the given solution.
+ *
+ * \param s the solution to generate successors for
+ * \param d the dependency to fix
+ * \param count a value to increment for every successor that
+ * is enqueued or discarded (as long as it's discarded
+ * for being too bad, and not for being in closed).
*/
void generate_successors(const solution &s,
- const dep &d)
+ const dep &d,
+ unsigned int &count)
{
version source_version=d.get_source();
package source_package=source_version.get_package();
@@ -678,7 +716,8 @@
{
if(debug)
std::cout << " Trying to resolve " << d << " by installing " << (*vi).get_package().get_name() << " version " << (*vi).get_name() << std::endl;
- try_install(s, *vi);
+ if(try_install(s, *vi))
+ ++count;
}
}
@@ -698,7 +737,8 @@
{
if(debug)
std::cout << " Trying to resolve " << d << " by installing " << (*si).get_package().get_name() << " version " << (*si).get_name() << std::endl;
- try_install(s, *si);
+ if(try_install(s, *si))
+ ++count;
}
}
}
@@ -708,9 +748,12 @@
*/
void process_solution(const solution &s)
{
+ // How many solutions have been generated?
+ unsigned int sols=0;
+
for(typename std::set<dep>::const_iterator bi=s.get_broken().begin();
- bi!=s.get_broken().end(); ++bi)
- generate_successors(s, *bi);
+ bi!=s.get_broken().end() && (sols==0 || sols<max_successors); ++bi)
+ generate_successors(s, *bi, sols);
}
public:
@@ -725,11 +768,11 @@
* \param _universe the universe in which we are working.
*/
generic_problem_resolver(int _step_score, int _broken_score,
- int infinity,
+ int infinity, unsigned int _max_successors,
int _full_solution_score,
const PackageUniverse &_universe)
:step_score(_step_score), broken_score(_broken_score),
- minimum_score(-infinity),
+ minimum_score(-infinity), max_successors(_max_successors),
full_solution_score(_full_solution_score),
universe(_universe), finished(false), debug(false)
{