org.cpsolver.exam.heuristics

## Class ExamColoringConstruction

- java.lang.Object
- - org.cpsolver.exam.heuristics.ExamColoringConstruction

- All Implemented Interfaces:
    NeighbourSelection<Exam,ExamPlacement>

      public class ExamColoringConstruction
      extends Object
      implements NeighbourSelection<Exam,ExamPlacement>

  Examination timetabling construction heuristics based on graph vertex coloring. This approach is trying to find a (direct) conflict-free examination schedule using a depth-first search, assigning periods to exams in a way that there is not student or instructor direct conflict.
  This heuristics works in following modes (defined by Exam.ColoringConstructionMode).
  - Greedy .. all exams are greedily assigned with periods (and best available rooms); Exams with smallest number of available periods (or highest number of connected exams if multiple) are assigned first.
  - ColorOnly .. all exams are assigned with periods using a depth-first search (ignoring all other constraints), this coloring is then extended to exam placements as much as possible
  - Irredundant .. other constraints (distributions, rooms) are considered, however, to speedup the search redundant colorings are avoided -- this may not find a complete solution, especially when some periods are not swap-able
  - Full .. all constraints are considered, a complete solution is guaranteed to be found, if it exists (and enough time is given)
  Time to run can be limited using Exam.ColoringConstructionTimeLimit parameter (double precision, limit is in seconds, defaults to 5 minutes)
  Version:
    ExamTT 1.3 (Examination Timetabling)
    Copyright (C) 2008 - 2014 Tomáš Müller
    muller@unitime.org
    http://muller.unitime.org
    This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.
    This library 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 Lesser General Public License for more details.
    You should have received a copy of the GNU Lesser General Public License along with this library; if not see http://www.gnu.org/licenses/.
  Author:
    Tomáš Müller

- - ### Constructor Summary

    Constructors
    Constructor and Description
    `ExamColoringConstruction(DataProperties config)`

  - ### Method Summary

    All Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `Set<ExamRoomPlacement>` | `findRooms(Assignment<Exam,ExamPlacement> assignment, Exam exam, ExamPeriodPlacement period)`
    `void` | `init(Solver<Exam,ExamPlacement> solver)` Criterion initialization
    `Neighbour<Exam,ExamPlacement>` | `selectNeighbour(Solution<Exam,ExamPlacement> solution)` select a neighbour of a given solution

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Constructor Detail

    - #### ExamColoringConstruction

          public ExamColoringConstruction(DataProperties config)

  - ### Method Detail

    - #### init

          public void init(Solver<Exam,ExamPlacement> solver)

      Description copied from interface: `NeighbourSelection`
      Criterion initialization
      Specified by:
        `init` in interface `NeighbourSelection<Exam,ExamPlacement>`
      Parameters:
        `solver` - current solver

    - #### findRooms

          public Set<ExamRoomPlacement> findRooms(Assignment<Exam,ExamPlacement> assignment,
                                                  Exam exam,
                                                  ExamPeriodPlacement period)

    - #### selectNeighbour

          public Neighbour<Exam,ExamPlacement> selectNeighbour(Solution<Exam,ExamPlacement> solution)

      Description copied from interface: `NeighbourSelection`
      select a neighbour of a given solution
      Specified by:
        `selectNeighbour` in interface `NeighbourSelection<Exam,ExamPlacement>`
      Parameters:
        `solution` - given solution
      Returns:
        a neighbour assignment