-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | A number of data structures to represent and allow the manipulation of standard combinatorial problems, used as test problems in computer science.
--   
--   In computer science there are a number of standard test problems that
--   are used for testing algorithms, especially those related to
--   Artificial Intelligence and Operations Research. Online there are a
--   number of repositories for collections of known interesting problems,
--   for example the TSPLIB at
--   <a>http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/</a> and the
--   SATLIB at <a>http://www.satlib.org/</a>.
--   
--   This library seeks to provide implementations of data structures to
--   store these problems, along with functions for manipulating the
--   problems and routines to load problem files from various sources.
--   
--   At present it supports TSP/TSPLIB, SAT/SATLIB and TIM (format used by
--   the International Timetabling Competition, which has been run twice at
--   current date), however it is hoped that the loading routines can be
--   expanded and the range of problems expanded to cover problems like
--   scheduling and more general timetabling. The internal data structures
--   make heavy use of the <tt>Data.Map</tt> library and
--   <tt>Data.Array</tt>. It is not currently using unboxed values. The
--   library does not use the <tt>bytestring</tt> library for loading and
--   saving data either, which will probably need to be changed later.
@package combinatorial-problems
@version 0.0.4


-- | A library for the representation and manipulation of Time Tabling
--   Problems. Still experimental and not particularly general. The
--   underlying problem description is that used by the International
--   Timetabling Competition, and the code is rather specialised towards
--   that, with the aim of being used for meta-heuristics.
module CombinatorialOptimisation.TIM

-- | Core concepts, location, timeslot, person, two events cannot happen in
--   the same place at the same time. This version expects a constrained
--   data set, so that the roomEvent lookup for example only yields events
--   that can reasonably be scheduled in that room.
--   
--   Originally I intended the objectives (low over scheduling of people)
--   and the soft objectives to be handled somewhere else. At this time, I
--   am unsure how to abstract this, and I want a system that works now, so
--   I will over specialise to the time tabling competition specifications.
--   Hopefully this can be rectified in a later version.
data TimeTable
TimeTable :: Int -> Int -> Int -> Int -> (PersonNumber -> [EventNumber]) -> (EventNumber -> [PersonNumber]) -> (EventNumber -> [RoomNumber]) -> (RoomNumber -> [EventNumber]) -> Map EventNumber (TimeSlot, RoomNumber) -> Map (TimeSlot, RoomNumber) EventNumber -> Map (TimeSlot, PersonNumber) Counter -> [EventNumber] -> Int -> Int -> Counter -> (TimeSlot -> DayNumber) -> (TimeSlot -> DaySlot) -> Map (DayNumber, PersonNumber) Counter -> Counter -> Counter -> Counter -> TimeTable
numberOfEvents :: TimeTable -> Int
numberOfRooms :: TimeTable -> Int
numberOfPeople :: TimeTable -> Int
numberOfTimeSlots :: TimeTable -> Int
personEventLookup :: TimeTable -> PersonNumber -> [EventNumber]
eventPersonLookup :: TimeTable -> EventNumber -> [PersonNumber]
eventRoomLookup :: TimeTable -> EventNumber -> [RoomNumber]
roomEventLookup :: TimeTable -> RoomNumber -> [EventNumber]
eventLocation :: TimeTable -> Map EventNumber (TimeSlot, RoomNumber)
locationEvent :: TimeTable -> Map (TimeSlot, RoomNumber) EventNumber
personUsage :: TimeTable -> Map (TimeSlot, PersonNumber) Counter
unscheduledEvents :: TimeTable -> [EventNumber]
lastDay :: TimeTable -> Int
lastSlotOfDay :: TimeTable -> Int
overSchedule :: TimeTable -> Counter
daynumberDecode :: TimeTable -> TimeSlot -> DayNumber
dayslotDecode :: TimeTable -> TimeSlot -> DaySlot
eventsInDay :: TimeTable -> Map (DayNumber, PersonNumber) Counter
singleEventInDayCounter :: TimeTable -> Counter
lastSlotOfDayCounter :: TimeTable -> Counter
moreThanTwoEventsCounter :: TimeTable -> Counter

-- | Splitting off the two parts of show, so we have a simple show for the
--   state of the solution, a more complex solution description and the
--   constant constrained problem.
viewConstrainedProblem :: TimeTable -> String

-- | Fails silently if the event is not currently scheduled.
descheduleEvent :: EventNumber -> TimeTable -> TimeTable

-- | Fails silently if the time slot and room number are not booked.
descheduleSlot :: TimeSlot -> RoomNumber -> TimeTable -> TimeTable

-- | Fails silently and does no update the schedule if the very hard
--   constraints fail.
schedule :: TimeSlot -> RoomNumber -> EventNumber -> TimeTable -> TimeTable

-- | The other part of the time table data type. See the current status of
--   the solution.
viewTimeTableDetails :: TimeTable -> String

-- | The validity function as specific by the 2002 competition rules.
--   Basically no clashes at this point.
ittcValidity :: TimeTable -> Bool

-- | The objective function as specific by the 2002 competition rules.
ittcObjectiveValue :: TimeTable -> Int

-- | A simple spread sheet display seems like a good idea.
timeTableDetailsAsCSV :: TimeTable -> String

-- | Maybe a helper, making it public anyway.
timeTableForRoomAsCSV :: TimeTable -> RoomNumber -> String

-- | Just a combination of existing useful functions.
currentlyScheduledEvents :: TimeTable -> [EventNumber]
type TimeSlot = Int
type DayNumber = Int
type DaySlot = Int
type RoomNumber = Int
type EventNumber = Int
type PersonNumber = Int
type FeatureNumber = Int
type Counter = Int
instance Show TimeTable


-- | The loading routines for the TIM file format. I am not sure what (if
--   anything) TIM stands for. The format has been used by the
--   |International Timetabling Competition| which has been run twice so
--   far (2002,2007). Problems in this format can be found on their
--   websites.
module FileFormat.TIM

-- | This is intended to be an internal format only, though I will provide
--   access and visibility to it so that it can be inspected by other
--   programs. In practice I do not expect users to operate upon the raw
--   problem, but instead upon TimeTable.
data RawTimeTableProblem
RawTimeTableProblem :: Int -> Int -> Int -> Int -> Int -> Int -> (RoomNumber -> Int) -> (PersonNumber -> [EventNumber]) -> (RoomNumber -> [FeatureNumber]) -> (EventNumber -> [FeatureNumber]) -> RawTimeTableProblem
rawNumberOfEvents :: RawTimeTableProblem -> Int
rawNumberOfRooms :: RawTimeTableProblem -> Int
rawNumberOfPeople :: RawTimeTableProblem -> Int
rawNumberOfFeatures :: RawTimeTableProblem -> Int
rawNumberOfSlotsPerDay :: RawTimeTableProblem -> Int
rawNumberOfDays :: RawTimeTableProblem -> Int
rawRoomSizes :: RawTimeTableProblem -> RoomNumber -> Int
rawPersonEventLookup :: RawTimeTableProblem -> PersonNumber -> [EventNumber]
rawRoomFeatureLookup :: RawTimeTableProblem -> RoomNumber -> [FeatureNumber]
rawEventFeatureLookup :: RawTimeTableProblem -> EventNumber -> [FeatureNumber]

-- | parseFile is a file parser for the <i>tim</i> format. For the output
--   format, the FullyDescriptiveTimeTableProblem data type, I have
--   included a number of slots per day and number of days. These are
--   constants in this loading routine.
parseFile :: Parser RawTimeTableProblem

-- | Load in a TIM file, but keep the data in the original form, as a large
--   number of grids of bits.
loadTIMFileRaw :: String -> IO RawTimeTableProblem

-- | Load a TIM file, and transform it into the constrained data format so
--   that the look up tables no longer give back just ones and zeros, but
--   lists of valid options. This should be easier to work with.
loadTIMFile :: String -> IO TimeTable

-- | Use the raw data to constrain problem. Only rooms that can reasonably
--   be chosen (feature and size constraints) should be available for
--   specific events and so on. In short I am doing my own constraint (hard
--   coded urg) processing here.
convertToConstrainedProblem :: RawTimeTableProblem -> TimeTable

-- | This is for human readability. It will take a raw format and return a
--   comma and new line separated format as a String. Dump the string to a
--   file and it should now be easy to load into a spread sheet and
--   inspect. I was not comfortable incoding this as a |show| function, it
--   seems to me that there is far too much information here to easily
--   display it to a user, at least in a terminal window.
rawToCSV :: RawTimeTableProblem -> String


-- | Simple library for fixed point arithmetic. Pure Haskell style,
--   unlikely to be efficient. Really this has been added as a bit of a
--   hack at the present time to remove rounding errors in the TSP
--   implementation (which was having them from the use of Float and
--   Double). Not intended to be a full library on it's own, but I guess I
--   see what happens.
--   
--   Internally uses Int64 as the data type and this is then divided to 32
--   bits below the point, 31 above and the sign is still in place. Basic
--   arithmetic becomes simple integer arithmetic (what I really really
--   want), multiplication and division has to make use of conversion to
--   Integer type and shifting, probably not that fast.
module CombinatorialOptimisation.TSP.FixedPoint
newtype FP
FP :: Int64 -> FP
instance Eq FP
instance Ord FP
instance Real FP
instance Fractional FP
instance Num FP
instance Show FP


-- | A library for the representation and manipulation of travelling
--   salesperson problems. The approach taken is the creation of a complex
--   data structure called TSPProblem which contains both the problem, the
--   current solution and the current value of the route. The route is
--   stored as a dictionary (<tt>Data.Map</tt>) of vertex indexes to a pair
--   of values, the previous vertex and the next vertex in the sequence.
--   This is to facilitate changing the route quickly, and avoid searching
--   for data in lists.
--   
--   The data structure also contains two additional fields, the
--   <tt>routeElementToIndex</tt> and <tt>indexToRouteElement</tt>
--   components. These exist to allow manipulation either by the vertex
--   number or the position in the current solution. Solutions are
--   hamiltonian cycles. For ease of reasoning it is recommended that users
--   do not attempt to move vertex 0, or index 0, so that solutions are
--   cycles from 0 to 0. I may change this in the future to lock this down
--   a bit. In the meantime, there is no actual problem with making these
--   changes, however later manipulations may not match up clearly with the
--   way the show routines work.
--   
--   Currently only two functions are provided for manipulating routes,
--   either by position in the sequence (<tt>exchangeCitiesOnIndex</tt>) or
--   by vertex name (<tt>exchangeCities</tt>).
--   
--   I am not sure how this will clearly support meta-heuristics that work
--   by deleting edges and recombining subsequences. However since I am
--   storing association lists I think it should be possible to make this
--   work, I will worry about it later.
module CombinatorialOptimisation.TSP

-- | The data type for carrying the combination problem and solution to the
--   TSP. The route is stored as a dictionary of associations from vertex
--   name to a pair of values, the name of the preceding vertex and the
--   next vertex. This forms an infinite loop, so use carefully.
--   
--   The <tt>routeElementToIndex</tt>/<tt>indexToRouteElement</tt> pair
--   store fixed indexes to the cities. This is intended to allow a dumb
--   heuristic to decide to switch elements 0 and 2, knowing they must be
--   separated by 1 element, rather than vertices 0 and 2, which may be
--   next to each other, or very different parts of the cycle.
data TSPProblem
TSPProblem :: FP -> Map Int (Int, Int) -> (Int -> Int -> FP) -> Int -> Map Int Int -> Map Int Int -> TSPProblem

-- | Internally all edge costs are stored as a fixed point values. For
--   external visibility however this function is provided, converting the
--   values into floating point numbers.
edgeCost :: Floating a => TSPProblem -> Int -> Int -> a

-- | Internally the value of the solution is stored as a fixed point value,
--   stored in an Int64 data type. For external visibility however this
--   function is provided, converting the value into a floating point
--   numbers.
solutionValue :: Floating a => TSPProblem -> a
getTSPPathAsList :: TSPProblem -> [Int]

-- | There are three possible internal storage forms. A full explicit
--   matrix, an upper triangular matrix or recomputation from data points.
--   The advantage of full explicit is speed, but it takes more memory. It
--   is also the only option for asymmetric TSP problems. The triangular
--   matrix is also fast, but can only be used in symmetric problems, and
--   also still requires quite a bit of memory. Recomputation is the last
--   option, it is slow because it is no longer a lookup table, but will
--   take much less room. Can only be used with problems where the distance
--   between two points can be calculated. Currently I am only supporting
--   symmetric TSPs for this.
data InternalStorage
ExplicitMatrix :: InternalStorage
TriangularMatrix :: InternalStorage
Recomputation :: InternalStorage

-- | Converts the lookup table of a problem into a comma and newline
--   delimited string. This should facilitate copying into spreadsheets for
--   checking the problem being used and validating solutions by hand.
showEdgeWeights :: TSPProblem -> String

-- | Will perform a switch of 2 cities in the path. This is by city name,
--   not current index in the path. It looks up the current indexes by city
--   name and passes the work off to <tt>exchangeCitiesOnIndex</tt>.
exchangeCities :: Int -> Int -> TSPProblem -> TSPProblem

-- | Performs the bulk of the work for exchanging elements of the cycle.
--   This version no longer assumes the indices are ordered due to
--   confusion this caused in my own code. In addition there was an
--   oversight, when exchanging indices 0 and last. This is now fixed.
exchangeCitiesOnIndex :: Int -> Int -> TSPProblem -> TSPProblem

-- | A brute force recalculation of the current length of the path. Use
--   sparingly.
evaluateRouteNaive :: TSPProblem -> TSPProblem

-- | Shuffles a simple list of cities and then passes off the work to
--   setRoute.
randomiseRoute :: RandomGen g => g -> TSPProblem -> TSPProblem

-- | Take a path through the system and a problem, insert the path into the
--   system, calculating distances and setting up appropriate look up
--   tables. It does not validate the list in terms of going through all
--   the cities, or going through a city more than once (though this is
--   likely to break other parts of the system very very fast). It does
--   organise the list so that the starting node is vertex 0.
--   
--   Uses the <tt>evaluateRouteNaive</tt> to calculate the length of the
--   path via a brute force method. This is not expected to be used
--   frequently.
setRoute :: [Int] -> TSPProblem -> TSPProblem

-- | Construct a TSPProblem instance for an Asymmetric TSP. That is, the
--   distance from A-B is the not necessarily the same as B-A. The actual
--   route will not be set up initially, the dictionaries will be empty.
--   This could be used directly for a global search system (branch and
--   bound), or use in conjunction with <tt>setRoute</tt> or
--   <tt>randomiseRoute</tt> to initialise for local search. Internal data
--   structure is always fully explicit matrix.
makeASymmetricTSPMap :: RandomGen g => (Double, Double) -> Int -> g -> TSPProblem

-- | Construct a TSPProblem instance for a Symmetric TSP. That is, the
--   distance from A-B is the same as B-A. The actual route will not be set
--   up initially, the dictionaries will be empty. This could be used
--   directly for a global search system (branch and bound), or use in
--   conjunction with <tt>setRoute</tt> or <tt>randomiseRoute</tt> to
--   initialise for local search. Should be noted that this does not create
--   locations and calculate distances, but rather randomly assigns
--   distances to each edge, making them symmetric.
makeSymmetricTSPMap :: RandomGen g => InternalStorage -> (Double, Double) -> Int -> g -> TSPProblem

-- | Construct a TSPProblem instance for a Symmetric TSP. The route will
--   not be initially set up, the dictionaries will be empty. This does
--   create the vertices of the graph as points in a 2d space, and the
--   lengths of edges are calculated, so this supports all internal storage
--   types.
makeEuclideanTSPMap :: RandomGen g => InternalStorage -> (Double, Double) -> (Double, Double) -> Int -> g -> TSPProblem
instance Show InternalStorage
instance Eq InternalStorage
instance Show TSPProblem


-- | Partial loading routines for the TSPLIB file format. The format itself
--   has a large number of variations, and this has only been designed to
--   load the <tt>tsp</tt> and <tt>atsp</tt> variants. It has been tried on
--   all the files from the repository in these classes and it parses them
--   at least.
--   
--   Relies upon the <tt>CombinatorialOptimisation.TSP</tt> library.
--   
--   Currently this does not use the Haskell parsing libraries, nor
--   ByteString, just some custom built routines.
module FileFormat.TSPLIB

-- | Loads a TSPLIB style file. The first parameter is the internal storage
--   type from <tt>CombinatorialProblems.TSP</tt>. It allows for full
--   matrix, triangular matrix and full recalculation. If the requested
--   internal storage cannot be used with the file, this will throw an
--   error (e.g. recomputation where you are given a full matrix in the
--   file).
--   
--   The second parameter is the file path.
loadTSPFile :: InternalStorage -> FilePath -> IO TSPProblem
instance Show Specification


-- | A library for the representation and manipulation of satisfiability
--   problems. Currently this is expected to only be 3-SAT however I do not
--   think the code is particularly limited to 3-SAT. The approach taken is
--   that there is a complex data structure called SATProblem, which
--   contains both the problem and the solution (settings of variables). In
--   addition it contains a number additional fields that allow for making
--   changes quickly, such as a table of clause positions. This is a Map
--   from clause index to the number of variable terms that are currently
--   set to true.
--   
--   Currently the only function for quickly changing a problem is the
--   flipping of a single variable. I think some other low level operations
--   for finding clauses not currently evaluating to true and so on would
--   be useful.
module CombinatorialOptimisation.SAT
data SATProblem
SATProblem :: Int -> Int -> Int -> (Int -> ([Int], [Int])) -> (Int -> ([Int], [Int])) -> Map Int Bool -> Map Int Int -> SATProblem
numClauses :: SATProblem -> Int
numSATEDClauses :: SATProblem -> Int
numVariables :: SATProblem -> Int
variableLookUp :: SATProblem -> Int -> ([Int], [Int])
clauseLookUp :: SATProblem -> Int -> ([Int], [Int])
variablePosition :: SATProblem -> Map Int Bool
clausePosition :: SATProblem -> Map Int Int

-- | The number of unsatisfied clauses in the problem, the inverse of
--   <tt>numSATEDClauses</tt>
numUnSATEDClauses :: SATProblem -> Int

-- | For the purposes of getting a general impression of the state of the
--   system, it returns the number of variables in the True, and False
--   positions.
getTrueFalseCount :: SATProblem -> (Int, Int)

-- | Partial display function, for usage in show, displays some general
--   statistics about the solution status.
summariseSAT :: SATProblem -> String

-- | I am not sure how often this will be used in practice, as randomly
--   created problems often seem to be quite easy to solve. Requires a
--   source of random numbers, the number of variables and the number of
--   clauses to create, in that order. It is assumed that 3-SAT problems
--   are the type wanted.
makeRandomSATProblem :: RandomGen g => g -> Int -> Int -> SATProblem

-- | The first low level operation. Takes a problem and changes the setting
--   of the indexed variable from true to false. This is expected to be
--   used in conjunction with other program logic to select which index to
--   flip.
flipVariable :: Int -> SATProblem -> (SATProblem, Int)

-- | Alternative constructor for the data structure. Takes only those
--   elements that can not be derived and correctly initialises the other
--   components, such as calculating how many clauses are currently
--   evaluating to true. Requires the number of clauses, the number of
--   variables, the lookup function for variables (variable index returning
--   two lists, the first is the indexes of clauses in which this variable
--   is present, the second list the indexes of clauses in which the
--   inverse of this variable is present), the lookup table for clauses
--   (clause index to lists of variable indexes) and the current settings
--   of each variable.
satproblem :: Int -> Int -> (Int -> ([Int], [Int])) -> (Int -> ([Int], [Int])) -> Map Int Bool -> SATProblem

-- | For rapid initialisation of problem instances. This fixes the setting
--   of all variables to either true or false. The effect this has on the
--   number of clauses that evaluate to true is unknown until it is carried
--   out.
setAllVars :: Bool -> SATProblem -> SATProblem

-- | For rapid initialisation of problem instances for usage in stochastic
--   algorithms. Specifically expected to be used for genetic algorithms
--   and other forms of stochastic meta-heuristic.
randomiseVariables :: RandomGen g => g -> SATProblem -> SATProblem
instance Show SATProblem
instance Ord SATProblem
instance Eq SATProblem


-- | The loading routines for the Conjunctive Normal Form (cnf) styled
--   files that can be found on the SATLIB website. Relies upon the
--   <tt>CombinatorialOptimisation.SAT</tt> library for the data
--   structures.
module FileFormat.SATLIB

-- | Loading routine that takes the file path and returns a SATProblem. All
--   variables will be set to false in the initial setup, and the truth
--   values of all clauses set appropriately.
loadCNFFile :: FilePath -> IO (SATProblem)

-- | Save routine for SATProblem, outputs back into SATLIB cnf format. The
--   code <tt>(loadCNFFile f) &gt;&gt;= (saveAsCNF f)</tt> should have no
--   effect upon the file. All information such as variable settings and
--   the truth values of clauses is lost. To save extra information use
--   standard prelude write file function with show. I will try to improve
--   on that at some point.
saveAsCNF :: FilePath -> SATProblem -> IO ()