[Aptitude-devel] r3181 - in branches/aptitude-0.3/aptitude: . src/generic/problemresolver

[Daniel Burrows]

Author: dburrows
Date: Thu Apr 28 17:24:09 2005
New Revision: 3181

Modified:
   branches/aptitude-0.3/aptitude/ChangeLog
   branches/aptitude-0.3/aptitude/src/generic/problemresolver/problemresolver.h
Log:
Discard obviously redundant solutions.

Modified: branches/aptitude-0.3/aptitude/ChangeLog
==============================================================================
--- branches/aptitude-0.3/aptitude/ChangeLog	(original)
+++ branches/aptitude-0.3/aptitude/ChangeLog	Thu Apr 28 17:24:09 2005
@@ -2,6 +2,10 @@
 
 	* src/generic/problemresolver/problemresolver.h:
 
+	  Ignore any solution that's a subset of another solution.
+
+	* src/generic/problemresolver/problemresolver.h:
+
 	  Write in a definition of operator!= for solutions -- I don't
 	  know where the default was coming from, but it's wrong, wrong,
 	  WRONG.

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	Thu Apr 28 17:24:09 2005
@@ -530,6 +530,9 @@
   /** Stores already-seen solutions: */
   std::set<solution, solution_contents_compare> closed;
 
+  /** Stores generated solutions: */
+  std::vector<solution> generated_solutions;
+
   /** Represents a possible successor to the given solution, created
    *  by installing a single 'new' version.
    */
@@ -564,6 +567,27 @@
     }
   };
 
+  /** \return \b true if the given solution is "irrelevant": that is,
+   *  either it was already generated and placed in the closed queue,
+   *  or it includes an already-generated solution as a proper subset.
+   */
+  bool irrelevant(const solution &s)
+  {
+    if(closed.find(s) != closed.end())
+      return true;
+
+    // The efficiency of this step hinges on the *assumption* that the
+    // number of solutions that will be generated is small relative to
+    // the number of potential solutions.
+    for(typename std::vector<solution>::const_iterator i=generated_solutions.begin();
+	i!=generated_solutions.end(); ++i)
+      if(includes(i->get_actions().begin(), i->get_actions().end(),
+		  s.get_actions().begin(), s.get_actions().end()))
+	return true;
+
+    return false;
+  }
+
   /** Enqueues a single successor node to the given solution by
    *  installing the given package version.
    *
@@ -651,7 +675,7 @@
 			 new_score,
 			 new_action_score);
 
-    if(closed.find(s2) == closed.end())
+    if(!irrelevant(s2))
       {
 	if(debug)
 	  {
@@ -668,7 +692,7 @@
       {
 	if(debug)
 	  {
-	    std::cout << "Dropping closed solution ";
+	    std::cout << "Dropping irrelevant solution ";
 	    s2.dump(std::cout);
 	    std::cout << std::endl;
 	  }
@@ -909,11 +933,11 @@
 	solution s=open.top();
 	open.pop();
 
-	if(closed.find(s) != closed.end())
+	if(irrelevant(s))
 	  {
 	    if(debug)
 	      {
-		std::cout << "Dropping closed solution ";
+		std::cout << "Dropping irrelevant solution ";
 		s.dump(std::cout);
 		std::cout << std::endl;
 	      }
@@ -944,6 +968,8 @@
 	    if(open.empty())
 	      finished=true;
 
+	    generated_solutions.push_back(s);
+
 	    return s;
 	  }
 	// Nope, let's go enqueue successor nodes.