-- 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 only supports TSP/TSPLIB and SAT/SATLIB, however it is
--   hoped that the loading routines can be expanded and the range of
--   problems expanded to cover problems like scheduling and 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.3


-- | 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 ()