-- Returns a list of reviews as ordered pairs (reviewer#, proposal#).
doMatching :: Instance -> [(Int, Int)]
doMatching inst@(Instance numRvrs numProps _ _) =
- -- Copied from doReduction. There should be a better way to get these here.
- let
- source = 0
- sink = 1
- rvrNode i boringness = 2 + 3*i + boringness
- propNode j expertness = 2 + 3*numRvrs + 3*j + expertness
- firstPropNode = propNode 0 0
- idPropNode n = (n - (2 + 3*numRvrs)) `div` 3
- numNodes = 2 + 3*numRvrs + 3*numProps
- in
let ReductionResult graph source sink idxBounds edIdx = doReduction inst in
let flowArray = minCostFlow idxBounds reIdx reCap reCost graph (source, sink) in
let pairs = do
import Data.Graph.Inductive.Tree
import ArrayStuff
+-- A fixed-seeded random number generator for reproducible experimentation.
+myGen = read "314159265 1" :: StdGen
+
+-- TESTING GRAPH ALGORITHMS
myGraph = mkGraph [(0, ()), (1, ()), (2, ())]
[(0, 1, (0, 2)), (0, 2, (1, 3)), (2, 1, (2, -2))] :: Gr () (Int, Int)
myNCGraph = mkGraph [(0, ())] [(0, 0, -1)] :: Gr () Int
bfNCResult = bellmanFord id 0 myNCGraph
+-- VISUALIZATION STUFF
data REdgeF = REdgeF Int Int Int Wt
instance Show REdgeF where
show (REdgeF idx cap flow cost) = "#" ++ (show idx) ++ ": "
mkGraph (labNodes g) (map (\(n1, n2, REdge i ca co) ->
(n1, n2, REdgeF i ca (fa ! i) co)) $ labEdges g) :: Gr () REdgeF
+showInstanceAsGraph :: Instance -> [(Int, Int)] -> Gr String String
+showInstanceAsGraph (Instance numRvrs numProps rloadA prefA) matchedPairs =
+ let
+ rvrNode i = i
+ propNode j = numRvrs + j
+ numNodes = numRvrs + numProps
+ theNodes = map (\i -> (rvrNode i, "R#" ++ show i ++
+ " (RLoad " ++ show (rloadA ! i) ++ ")")) [0..numRvrs-1] ++
+ map (\j -> (propNode j, "P#" ++ show j)) [0..numProps-1]
+ parenthesizeIf False s = s
+ parenthesizeIf True s = "(" ++ s ++ ")"
+ theEdges = do
+ i <- [0..numRvrs-1]
+ j <- [0..numProps-1]
+ return (rvrNode i, propNode j,
+ parenthesizeIf (elem (i, j) matchedPairs) $ show (prefA ! (i, j)))
+ in mkGraph theNodes theEdges
+
+-- PROPOSAL-MATCHING EXAMPLES
-- Example from idea book p. 425
{-
(myNumRvrs, myNumProps) = (4, 3)
rdnFlowArray = minCostFlow rreib reIdx reCap reCost rrg (rrso, rrsi)
rrg2 = flowAnnotate rrg rdnFlowArray
myMatching = doMatching myInst
+
+iGraph = showInstanceAsGraph myInst myMatching -- Visualize me!