{"type":"rich","version":"1.0","author_name":"npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","author_url":"https://nostr.ae/npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3l","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2021-08-23\n📝 Original message:\nGood morning Stefan,\n\n\u003e Hi Zmn! That is some amazing lateral thinking you have been applying there. I'm quite certain I haven't understood everything fully, but it has been highly entertaining to read. Will have to give it a closer read when I get some time.\n\u003e\n\u003e As a first impression, here are some preliminary observations: While I highly like the Haskell-style datatype, and the algorithm we use does mostly use Dijkstra pathfinding, I think what is really important in your definition is the computeCost definition. This is what we would call the cost function IIUC, and in order to be able to solve min-cost flow problems it generally has to be separable and convex. I believe your datatype merely hides the fact that it is neither. \n\nWell, it really depends on what min flow cost algorithms actually assume of the \"numbers\" being used.\n\nFor instance, it is well known that the Dijkstra-A\\*-Greedy family of algorithms do not handle \"negative costs\".\nWhat it really means is that the algorithms assume:\n\n    a + b \u003e= a\n    a + b \u003e= b\n\nThis holds if `a` and `b` are naturals (0 or positive), but not if they are integers.\n1 + -1 = 0, and 0 \u003e= 1 is not true, thus the type for costs in those algorithms cannot be integer types, they have to be naturals.\nHowever if you restrict the type to naturals,  `a + b \u003e= a` holds, and thus Dijkstra and its family of algorithms work.\n\nThus, if you are going to use Dijkstra-A\\*-Greedy, you \"only\" need to have the following \"operations\":\n\n    `+` :: Cost -\u003e Cost -\u003e Cost\n    `\u003c` :: Cost -\u003e Cost -\u003e Bool\n    zero :: Cost\n\nWith the following derived operations:\n\n    a \u003e b = b \u003c a\n    a \u003e= b = not (a \u003c b)\n    a \u003c= b = not (b \u003c a)\n    a == b = (a \u003e= b) \u0026\u0026 (a \u003c= b)\n    a /= b = (a \u003c b) || (a \u003e b)\n\nAnd following the laws:\n\n    forall (a :: Cost) =\u003e a + zero == a\n    forall (a :: Cost) =\u003e zero + a == a\n    forall (a :: Cost, b :: Cost) =\u003e a + b == b + a\n    forall (a :: Cost, b :: Cost, c :: Cost) =\u003e (a + b) + c == a + (b + c)\n    forall (a :: Cost, b :: Cost) =\u003e a + b \u003e= a\n    forall (a :: Cost, b :: Cost) =\u003e a + b \u003e= b\n\nAs a non-mathist I have no idea what \"separable\" and \"convex\" actually mean.\nBasic search for \"convex\" and \"concave\" tends to show up information in geometry, which I think is not related (though it is possible there is some extension of the geometric concept to pure number theory?).\nAnd definitions on \"separable\" are not understandable by me, either.\n\nWhat exactly are the operations involved, and what are the laws those operations must follow, for the data type to be \"separable\" and \"convex\" (vs.\"concave\")?\n\nI guess my problem as well is that I cannot find easy-to-understand algorithms for min cost flow --- I can find discussions on the min cost flow \"problem\", and some allusions to solutions to that problem, but once I try looking into algorithms it gets quite a bit more complicated.\n\nBasically: do I need these operations?\n\n    `*` :: Cost -\u003e Cost -\u003e Cost\n    `/` :: Cost -\u003e Cost -\u003e Cost --- or Maybe Cost\n\nIf not, then why cannot `type Cost = UnifiedCost`?\n\n\nFor example, this page: https://www.topcoder.com/thrive/articles/Minimum%20Cost%20Flow%20Part%20Two:%20Algorithms\n\nIncludes this pseudocode:\n\n    Transform network G by adding source and sink\n    Initial flow x is zero\n    while ( Gx contains a path from s to t ) do\n        Find any shortest path P from s to t\n        Augment current flow x along P\n        update Gx\n\nIf \"find any shortest path\" is implemented using Dijkstra-A\\*-Greedy, then that does not require `Cost` to be an actual numeric type, they just require a type that provides `+`, `\u003c`, and `zero`, all of which follow the laws I pointed out, *and no more than those*.\n`UnifiedCost` follows those laws (tough note that my definition of `zero` has a bug, `successProbability` should be `1.0` not `0`).\n\nIn short --- the output of the cost function is a `UnifiedCost` structure and ***not*** a number (in the traditional sense).\n\nBasically, I am deconstructing numbers here and trying to figure out what makes them tick, and seeing if I can use a different type to provide the \"tick\".\n\n\nRegards,\nZmnSCPxj"}