From da92436b2d8bbb6d3f8ec3555daa762c2221fb5c Mon Sep 17 00:00:00 2001 From: David Mudrak Date: Mon, 4 Jan 2010 17:47:32 +0000 Subject: [PATCH] MDL-19870 Random allocation - work in progress Random allocation implemented. More testing needed. --- mod/workshop/allocation/lib.php | 3 +- mod/workshop/allocation/random/allocator.php | 248 +++++++++++++++++- .../allocation/random/settings_form.php | 19 +- .../random/simpletest/testallocator.php | 106 ++++++++ mod/workshop/lang/en_utf8/workshop.php | 2 +- mod/workshop/locallib.php | 2 +- mod/workshop/renderer.php | 4 + mod/workshop/styles.php | 7 +- 8 files changed, 370 insertions(+), 21 deletions(-) diff --git a/mod/workshop/allocation/lib.php b/mod/workshop/allocation/lib.php index 45a2862cc8..791a9e5b43 100644 --- a/mod/workshop/allocation/lib.php +++ b/mod/workshop/allocation/lib.php @@ -54,7 +54,8 @@ interface workshop_allocator { * * If a form is part of the UI, the caller should have called $PAGE->set_url(...) * The methods must produce output instead of just returning it so mform->display() can - * be used there. + * be used there. This should be changed once we make quickforms deprecated and then, + * this method will just return the required HTML code. * * @param object $wsoutput workshop module renderer can be used * @return void diff --git a/mod/workshop/allocation/random/allocator.php b/mod/workshop/allocation/random/allocator.php index 4591f771b0..1d9209b457 100644 --- a/mod/workshop/allocation/random/allocator.php +++ b/mod/workshop/allocation/random/allocator.php @@ -54,7 +54,7 @@ class workshop_random_allocator implements workshop_allocator { protected $mform; /** - * @param stdClass $workshop Workshop record + * @param workshop $workshop Workshop API object */ public function __construct(workshop $workshop) { $this->workshop = $workshop; @@ -67,7 +67,7 @@ class workshop_random_allocator implements workshop_allocator { global $PAGE; $customdata = array(); - // $customdata['workshop'] = $this->workshop; + $customdata['workshop'] = $this->workshop; $this->mform = new workshop_random_allocator_form($PAGE->url, $customdata); if ($this->mform->is_cancelled()) { redirect($PAGE->url->out(false, array(), false)); @@ -91,7 +91,14 @@ class workshop_random_allocator implements workshop_allocator { $newallocations = array(); // array of (reviewer,reviewee) tuples if ($numofreviews) { - $randomallocations = $this->random_allocation($authors, $reviewers, $assessments, $numofreviews, $numper); + if ($removecurrent) { + // behave as if there were no current assessments + $curassessments = array(); + } else { + $curassessments = $assessments; + } + $randomallocations = $this->random_allocation($authors, $reviewers, $curassessments, $numofreviews, $numper, $o); + $this->filter_current_assessments($randomallocations, $assessments); $newallocations = array_merge($newallocations, $randomallocations); $o[] = 'ok::' . get_string('numofrandomlyallocatedsubmissions', 'workshop', count($randomallocations)); unset($randomallocations); @@ -111,7 +118,7 @@ class workshop_random_allocator implements workshop_allocator { $a = new stdClass(); $a->reviewername = fullname($reviewers[0][$reviewerid]); $a->authorname = fullname($authors[0][$authorid]); - $o[] = 'ok::ident::' . get_string('allocationaddeddetail', 'workshop', $a); + $o[] = 'ok::indent::' . get_string('allocationaddeddetail', 'workshop', $a); } } if ($removecurrent) { @@ -128,10 +135,10 @@ class workshop_random_allocator implements workshop_allocator { 'lastname' => $assessments[$delassessmentid]->reviewerlastname, 'firstname' => $assessments[$delassessmentid]->reviewerfirstname)); if (!is_null($assessments[$delassessmentid]->grade)) { - $o[] = 'error::ident::' . get_string('allocationdeallocategraded', 'workshop', $a); + $o[] = 'error::indent::' . get_string('allocationdeallocategraded', 'workshop', $a); unset($delassessments[$delassessmentkey]); } else { - $o[] = 'info::ident::' . get_string('assessmentdeleteddetail', 'workshop', $a); + $o[] = 'info::indent::' . get_string('assessmentdeleteddetail', 'workshop', $a); } } $this->workshop->delete_assessment($delassessments); @@ -310,16 +317,229 @@ class workshop_random_allocator implements workshop_allocator { } /** - * TODO: short description. + * Allocates submission reviews randomly + * + * The algorithm of this function has been described at http://moodle.org/mod/forum/discuss.php?d=128473 + * Please see the PDF attached to the post before you study the implementation. The goal of the function + * is to connect each "circle" (circles are representing either authors or reviewers) with a required + * number of "squares" (the other type than circles are). * - * @param array $authors - * @param resource $reviewers - * @param array $assessments - * @param mixed $numofreviews - * @param mixed $numper - * @return TODO + * @param array $authors structure of grouped authors + * @param resource $reviewers structure of grouped reviewers + * @param array $assessments currently assigned assessments to be kept + * @param mixed $numofreviews number of reviewes to be allocated to each circle + * @param mixed $numper what user type the circles represent + * @param array $o reference to an array of log messages + * @return array array of (reviewerid => authorid) pairs */ - protected function random_allocation($authors, $reviewers, $assessments, $numofreviews, $numper) { + protected function random_allocation($authors, $reviewers, $assessments, $numofreviews, $numper, &$o) { + if (WORKSHOP_USERTYPE_AUTHOR == $numper) { + // circles are authors, squares are reviewers + $o[] = 'info::Trying to allocate ' . $numofreviews . ' review(s) per author'; // todo translate + $allcircles = $authors; + $allsquares = $reviewers; + // get current workload + list($circlelinks, $squarelinks) = $this->convert_assessments_to_links($assessments); + } elseif (WORKSHOP_USERTYPE_REVIEWER == $numper) { + // circles are reviewers, squares are authors + $o[] = 'info::trying to allocate ' . $numofreviews . ' review(s) per reviewer'; // todo translate + $allcircles = $reviewers; + $allsquares = $authors; + // get current workload + list($squarelinks, $circlelinks) = $this->convert_assessments_to_links($assessments); + } else { + throw new moodle_workshop_exception($this->workshop, 'unknown user type passed'); + } + $o[] = 'debug::circle links = ' . json_encode($circlelinks); + $o[] = 'debug::square links = ' . json_encode($squarelinks); + $squareworkload = array(); // individual workload indexed by squareid + $squaregroupsworkload = array(); // group workload indexed by squaregroupid + foreach ($allsquares as $squaregroupid => $squares) { + $squaregroupsworkload[$squaregroupid] = 0; + foreach ($squares as $squareid => $square) { + if (!isset($squarelinks[$squareid])) { + $squarelinks[$squareid] = array(); + } + $squareworkload[$squareid] = count($squarelinks[$squareid]); + $squaregroupsworkload[$squaregroupid] += $squareworkload[$squareid]; + } + $squaregroupsworkload[$squaregroupid] /= count($squares); + } + unset($squaregroupsworkload[0]); // [0] is not real group, it contains all users + $o[] = 'debug::square workload = ' . json_encode($squareworkload); + $o[] = 'debug::square group workload = ' . json_encode($squaregroupsworkload); + $gmode = groups_get_activity_groupmode($this->workshop->cm); + if (SEPARATEGROUPS == $gmode) { + // shuffle all groups but [0] which means "all users" + $circlegroups = array_keys(array_diff_key($allcircles, array(0 => null))); + shuffle($circlegroups); + } else { + // all users will be processed at once + $circlegroups = array(0); + } + $this->shuffle_assoc($circlegroups); + $o[] = 'debug::circle groups = ' . json_encode($circlegroups); + foreach ($circlegroups as $circlegroupid) { + $o[] = 'debug::processing circle group id ' . $circlegroupid; + $circles = $allcircles[$circlegroupid]; + $this->shuffle_assoc($circles); + foreach ($circles as $circleid => $circle) { + $o[] = 'debug::processing circle id ' . $circleid; + if (!isset($circlelinks[$circleid])) { + $circlelinks[$circleid] = array(); + } + $keeptrying = true; // is there a chance to find a square for this circle? + $failedgroups = array(); // array of groupids where the square should be chosen from (because + // of their group workload) but it was not possible (for example there + // was the only square and it had been already connected + while ($keeptrying && (count($circlelinks[$circleid]) < $numofreviews)) { + // firstly, choose a group to pick the square from + if (NOGROUPS == $gmode) { + if (in_array(0, $failedgroups)) { + $keeptrying = false; + $o[] = 'error::indent::No more peers available'; // todo translate + break; + } + $targetgroup = 0; + } elseif (SEPARATEGROUPS == $gmode) { + if (in_array($circlegroupid, $failedgroups)) { + $keeptrying = false; + $o[] = 'error::indent::No more peers available in this separate group'; // todo translate + break; + } + $targetgroup = $circlegroupid; + } elseif (VISIBLEGROUPS == $gmode) { + $trygroups = array_diff_key($squaregroupsworkload, array(0 => null)); // all but [0] + $trygroups = array_diff_key($trygroups, array_flip($failedgroups)); // withou previous failures + $targetgroup = $this->get_element_with_lowest_workload($trygroups); + } + if ($targetgroup === false) { + $keeptrying = false; + $o[] = 'error::indent::Not enough peers available'; // todo translate + break; + } + $o[] = 'debug::indent::next square should be from group id ' . $targetgroup; + // now, choose a square from the target group + $trysquares = array_intersect_key($squareworkload, $allsquares[$targetgroup]); + $o[] = 'debug::indent::individual workloads in this group are ' . json_encode($trysquares); + unset($trysquares[$circleid]); // can't allocate to self + $trysquares = array_diff_key($trysquares, array_flip($circlelinks[$circleid])); // can't re-allocate the same + $targetsquare = $this->get_element_with_lowest_workload($trysquares); + if (false === $targetsquare) { + $o[] = 'debug::indent::unable to find an available square. trying another group'; + $failedgroups[] = $targetgroup; + continue; + } + $o[] = 'debug::indent::target square = ' . $targetsquare; + // ok - we have found the square + $circlelinks[$circleid][] = $targetsquare; + $squarelinks[$targetsquare][] = $circleid; + $squareworkload[$targetsquare]++; + $o[] = 'debug::indent::increasing square workload to ' . $squareworkload[$targetsquare]; + if ($targetgroup) { + // recalculate the group workload + $squaregroupsworkload[$targetgroup] = 0; + foreach ($allsquares[$targetgroup] as $squareid => $square) { + $squaregroupsworkload[$targetgroup] += $squareworkload[$squareid]; + } + $squaregroupsworkload[$targetgroup] /= count($allsquares[$targetgroup]); + $o[] = 'debug::indent::increasing group workload to ' . $squaregroupsworkload[$targetgroup]; + } + } // end of processing this circle + } // end of processing circles in the group + } // end of processing circle groups + $returned = array(); + if (WORKSHOP_USERTYPE_AUTHOR == $numper) { + // circles are authors, squares are reviewers + foreach ($circlelinks as $circleid => $squares) { + foreach ($squares as $squareid) { + $returned[] = array($squareid => $circleid); + } + } + } + if (WORKSHOP_USERTYPE_REVIEWER == $numper) { + // circles are reviewers, squares are authors + foreach ($circlelinks as $circleid => $squares) { + foreach ($squares as $squareid) { + $returned[] = array($circleid => $squareid); + } + } + } + return $returned; } + /** + * Extracts the information about reviews from the authors' and reviewers' perspectives + * + * @param array $assessments array of assessments as returned by {@link workshop_api::get_assessments()} + * @return array of two arrays + */ + protected function convert_assessments_to_links($assessments) { + $authorlinks = array(); // [authorid] => array(reviewerid, reviewerid, ...) + $reviewerlinks = array(); // [reviewerid] => array(authorid, authorid, ...) + foreach ($assessments as $assessment) { + if (!isset($authorlinks[$assessment->authorid])) { + $authorlinks[$assessment->authorid] = array(); + } + if (!isset($reviewerlinks[$assessment->reviewerid])) { + $reviewerlinks[$assessment->reviewerid] = array(); + } + $authorlinks[$assessment->authorid][] = $assessment->reviewerid; + $reviewerlinks[$assessment->reviewerid][] = $assessment->authorid; + } + return array($authorlinks, $reviewerlinks); + } + + /** + * Selects an element with the lowest workload + * + * If there are more elements with the same workload, choose one of them randomly. This may be + * used to select a group or user. + * + * @param array $workload [groupid] => (int)workload + * @return mixed int|bool id of the selected element or false if it is impossible to choose + */ + protected function get_element_with_lowest_workload($workload) { + if (empty($workload)) { + return false; + } + $minload = min($workload); + $minkeys = array_filter($workload, create_function('$val', 'return $val == ' . $minload . ';')); + return array_rand($minkeys); + } + + /** + * Shuffle the order of array elements preserving the key=>values + * + * @author rich at home dot nl + * @link http://php.net/manual/en/function.shuffle.php#80586 + * @param array $array to be shuffled + * @return true + */ + protected function shuffle_assoc(&$array) { + if (count($array) > 1) { + // $keys needs to be an array, no need to shuffle 1 item or empty arrays, anyway + $keys = array_rand($array, count($array)); + foreach($keys as $key) { + $new[$key] = $array[$key]; + } + $array = $new; + } + return true; // because this behaves like in-built shuffle(), which returns true + } + + /** + * Filter new allocations so that they do not contain an already existing assessment + * + * @param mixed $newallocations array of ('reviewerid' => 'authorid') tuples + * @param array $assessments array of assessment records + * @return void + */ + protected function filter_current_assessments(&$newallocations, $assessments) { + foreach ($assessments as $assessment) { + $allocation = array($assessment->reviewerid => $assessment->authorid); + $foundat = array_keys($newallocations, $allocation); + $newallocations = array_diff_key($newallocations, array_flip($foundat)); + } + } } diff --git a/mod/workshop/allocation/random/settings_form.php b/mod/workshop/allocation/random/settings_form.php index 291c4bda46..2e7930f58d 100644 --- a/mod/workshop/allocation/random/settings_form.php +++ b/mod/workshop/allocation/random/settings_form.php @@ -42,16 +42,29 @@ class workshop_random_allocator_form extends moodleform { */ public function definition() { $mform = $this->_form; - //$workshop = $this->_customdata['workshop']; + $workshop = $this->_customdata['workshop']; $mform->addElement('header', 'settings', get_string('allocationsettings', 'workshop')); - $options_numofreviewes = array(0=>0,1=>1, 2=>2, 3=>2, 4=>4); + switch ($workshop->cm->groupmode) { + case NOGROUPS: + $grouplabel = get_string('groupsnone', 'group'); + break; + case VISIBLEGROUPS: + $grouplabel = get_string('groupsvisible', 'group'); + break; + case SEPARATEGROUPS: + $grouplabel = get_string('groupsseparate', 'group'); + break; + } + $mform->addElement('static', 'groupmode', get_string('groupmode', 'group'), $grouplabel); + + $options_numofreviewes = array(0=>0,1=>1, 2=>2, 3=>3, 4=>4); $options_numper = array(WORKSHOP_USERTYPE_AUTHOR => get_string('numperauthor', 'workshop'), WORKSHOP_USERTYPE_REVIEWER => get_string('numperreviewer', 'workshop')); $grpnumofreviews = array(); $grpnumofreviews[] =& $mform->createElement('select', 'numofreviews', '', $options_numofreviewes); - $mform->setDefault('numofreviews', 0); + $mform->setDefault('numofreviews', 4); $grpnumofreviews[] =& $mform->createElement('select', 'numper', '', $options_numper); $mform->setDefault('numper', WORKSHOP_USERTYPE_AUTHOR); $mform->addGroup($grpnumofreviews, 'grpnumofreviews', get_string('numofreviews', 'workshop'), array(' '), false); diff --git a/mod/workshop/allocation/random/simpletest/testallocator.php b/mod/workshop/allocation/random/simpletest/testallocator.php index 50c1dbcddc..63e6a48e19 100644 --- a/mod/workshop/allocation/random/simpletest/testallocator.php +++ b/mod/workshop/allocation/random/simpletest/testallocator.php @@ -47,6 +47,15 @@ class testable_workshop_random_allocator extends workshop_random_allocator { public function get_unkept_assessments($assessments, $newallocations, $keepselfassessments) { return parent::get_unkept_assessments($assessments, $newallocations, $keepselfassessments); } + public function convert_assessments_to_links($assessments) { + return parent::convert_assessments_to_links($assessments); + } + public function get_element_with_lowest_workload($workload) { + return parent::get_element_with_lowest_workload($workload); + } + public function filter_current_assessments(&$newallocations, $assessments) { + return parent::filter_current_assessments($newallocations, $assessments); + } } class workshop_allocation_random_test extends UnitTestCase { @@ -177,5 +186,102 @@ class workshop_allocation_random_test extends UnitTestCase { $this->assertEqual(array(12), $delassessments); } + /** + * Aggregates assessment info per author and per reviewer + */ + public function test_convert_assessments_to_links() { + // fixture setup + $assessments = array( + 23 => (object)array('authorid' => 3, 'reviewerid' => 3), + 45 => (object)array('authorid' => 5, 'reviewerid' => 11), + 12 => (object)array('authorid' => 5, 'reviewerid' => 3), + ); + // exercise SUT + list($authorlinks, $reviewerlinks) = $this->allocator->convert_assessments_to_links($assessments); + // verify + $this->assertEqual(array(3 => array(3), 5 => array(11, 3)), $authorlinks); + $this->assertEqual(array(3 => array(3, 5), 11 => array(5)), $reviewerlinks); + } + + /** + * Trivial case + */ + public function test_convert_assessments_to_links_empty() { + // fixture setup + $assessments = array(); + // exercise SUT + list($authorlinks, $reviewerlinks) = $this->allocator->convert_assessments_to_links($assessments); + // verify + $this->assertEqual(array(), $authorlinks); + $this->assertEqual(array(), $reviewerlinks); + } + + /** + * If there is a single element with the lowest workload, it should be chosen + */ + public function test_get_element_with_lowest_workload_deterministic() { + // fixture setup + $workload = array(4 => 6, 9 => 1, 10 => 2); + // exercise SUT + $chosen = $this->allocator->get_element_with_lowest_workload($workload); + // verify + $this->assertEqual(9, $chosen); + } + + /** + * If there are no elements available, must return false + */ + public function test_get_element_with_lowest_workload_impossible() { + // fixture setup + $workload = array(); + // exercise SUT + $chosen = $this->allocator->get_element_with_lowest_workload($workload); + // verify + $this->assertTrue($chosen === false); + } + + /** + * If there are several elements with the lowest workload, one of them should be chosen randomly + */ + public function test_get_element_with_lowest_workload_random() { + // fixture setup + $workload = array(4 => 6, 9 => 2, 10 => 2); + // exercise SUT + $elements = $this->allocator->get_element_with_lowest_workload($workload); + // verify + // in theory, this test can fail even if the function works well. However, the probability of getting + // a row of a hundred same ids in this use case is 1/pow(2, 100) + // also, this just tests that each of the two elements has been chosen at least once. this is not to + // measure the quality or randomness of the algorithm + $counts = array(4 => 0, 9 => 0, 10 => 0); + for ($i = 0; $i < 100; $i++) { + $chosen = $this->allocator->get_element_with_lowest_workload($workload); + if (!in_array($chosen, array(4, 9, 10))) { + $this->fail('Invalid element chosen'); + break; + } else { + $counts[$this->allocator->get_element_with_lowest_workload($workload)]++; + } + } + $this->assertTrue(($counts[9] > 0) && ($counts[10] > 0)); + } + + /** + * Filter new assessments so they do not contain existing + */ + public function test_filter_current_assessments() { + // fixture setup + $newallocations = array(array(3 => 5), array(11 => 5), array(2 => 9), array(3 => 5)); + $assessments = array( + 23 => (object)array('authorid' => 3, 'reviewerid' => 3), + 45 => (object)array('authorid' => 5, 'reviewerid' => 11), + 12 => (object)array('authorid' => 5, 'reviewerid' => 3), + ); + // exercise SUT + $this->allocator->filter_current_assessments($newallocations, $assessments); + // verify + $this->assertEqual(array_values($newallocations), array(array(2 => 9))); + } + } diff --git a/mod/workshop/lang/en_utf8/workshop.php b/mod/workshop/lang/en_utf8/workshop.php index aa94d6f9c4..52f18014ae 100644 --- a/mod/workshop/lang/en_utf8/workshop.php +++ b/mod/workshop/lang/en_utf8/workshop.php @@ -25,7 +25,7 @@ defined('MOODLE_INTERNAL') || die(); -$string[''] = ''; +$string['numofrandomlyallocatedsubmissions'] = 'Randomly allocating $a submissions'; $string[''] = ''; $string[''] = ''; $string[''] = ''; diff --git a/mod/workshop/locallib.php b/mod/workshop/locallib.php index 015fb88bc8..bdc3b1e69e 100644 --- a/mod/workshop/locallib.php +++ b/mod/workshop/locallib.php @@ -328,7 +328,7 @@ class workshop_api extends workshop { * mainly they do not contain text fields. * * @param mixed $reviewerid 'all'|int|array User ID of the reviewer - * @return array of objects + * @return array [assessmentid] => assessment object * @see workshop_api::get_assessments_recordset() for the structure of returned objects */ public function get_assessments($reviewerid='all') { diff --git a/mod/workshop/renderer.php b/mod/workshop/renderer.php index 423d8ac983..8795147cbd 100644 --- a/mod/workshop/renderer.php +++ b/mod/workshop/renderer.php @@ -100,6 +100,10 @@ class moodle_mod_workshop_renderer extends moodle_renderer_base { $parts = explode('::', $message); $text = array_pop($parts); $class = implode(' ', $parts); + if (in_array('debug', $parts) && !debugging('', DEBUG_DEVELOPER)) { + // do not display allocation debugging messages + continue; + } $o .= $this->output->output_tag('li', array('class' => $class), $text); } $o .= $this->output->output_end_tag('ul'); diff --git a/mod/workshop/styles.php b/mod/workshop/styles.php index 49eb4ea62d..41dfce2a33 100644 --- a/mod/workshop/styles.php +++ b/mod/workshop/styles.php @@ -41,7 +41,7 @@ font-size: 80%; } -.mod-workshop .allocation-init-results .ident { +.mod-workshop .allocation-init-results .indent { margin-left: 20px; } @@ -60,6 +60,11 @@ background-color: #d2ebff; } +.mod-workshop .allocation-init-results .debug { + color: black; + background-color: #ddd; +} + /** * Manual allocator */ -- 2.39.5