How to model the finding of linked-list or graph solutions?

51 views
Skip to first unread message

meta_leap

unread,
Nov 22, 2023, 1:07:40 PM11/22/23
to MiniZinc
Having finished the Handbook (and thus in theory absorbed all the language's expressible constructs), I still can't quite reason this out. Certainly there's no notion of recursive record types. Let's say you want to find a path. Like the person-to-person-message-passing problem, with data-defined sender, recipient, and DB of all people and who they meet (to potentially pass on the message from sender to recipient).

For just one path, I could have a None enumerant in the Person enum and a hardbounded array-of-var-Person that's full of Nones at the end (or the start).

But the problem wants all possible paths that could have reached recipient from sender.

I could cheat and snatch this right from hakank's solution, but I actually wanted to come with something "native in MiniZinc terms" by myself. Yet here I am asking.

How just how does a general-purpose-PL-conditioned programmer reshape one's formulations/thinkings to all this...

Update: took a sneak peek at the first few lines of hakank's solution (only had the top part with the problem-description visible before), and immediately I see:

int: num_edges = 13;
I guess that way, a result linked-list can be array-modeled. I suppose there is no sort of "dynamic allocation" aka "solver, YOU find out how long this list gets"? Aka lists-not-arrays in most-PL's-parlance?

meta_leap

unread,
Nov 22, 2023, 2:53:44 PM11/22/23
to MiniZinc
Well I made it work from scratch for one-possible-path (via arr-of-vars), the result being correct but definitely not the shortest-path.

Or indeed all-possible-paths... (via some unknown-to-me `var array of`-alternative, such construct being non-existant — and perhaps also even non-sensical to the seasoned logician/constraint-programmer).

So how to find those, typically? Does the minizinc-caller solve the model repeatedly and upon every solution, exclude it from a next solve run via appended constraint, until "Unsatisfiable" results? And gather, afterwards rank, all those solutions "manually", so to speak?

boris...@gmail.com

unread,
Nov 22, 2023, 6:14:30 PM11/22/23
to MiniZinc
> Well I made it work from scratch for one-possible-path 

MiniZinc gives you as many solutions as you ask for (unless it can't) :-)
Hit "Show configuration editor" (top-right of IDE) -> "User defined behavior". Then you could choose the number of solutions in the menu below.

Looking at your model, this is probably not a good idea:
array[Person,Person] of var bool: meets; 

'meets' is not a decision variable, but rather an array of constant values. If you look at the first couple of solutions the model gives, you will see what the problem is.

meta_leap

unread,
Nov 23, 2023, 4:15:21 AM11/23/23
to MiniZinc
Thanks Boris, I was too much in non-CP/SAT/logic programmer-thinking territory yesterday to remember that even one array-of-var represents potentially numerous solutions. Being typical-type-system-conditioned, I keep up the "there's var int, var bool, var SomeEnum etc so then for solved-for arrays it'll be var-array-of" shortcut jump, albeit mistaken.

Well I fixed the program to find the shortest correct path. Is this the only way to count the number of value-foo-in-array-bar? Somehow I keep missing first-class-functions / functions-as-values. So I could make a constructor function to fill any (param not var) `array[Enum1,Enum2]of bool` from a (param not var) `array[_]of tuple(MyEnum1: MyEnum2)` for example. Generally the likes of map, indexOf(value), indexOf(pred) etc...

Probably just not applicable to this paradigm? It's gotta be utterly never-in-demand given that the very extensive and rich stdlib has no such built-ins.

boris...@gmail.com

unread,
Nov 23, 2023, 10:13:03 AM11/23/23
to MiniZinc
Yes, the paradigms are very different. In conventional programming (except maybe logical programming), the computation of output is done through the transformation of input.  In CP,  it's done through satisfying constraints, which are relations between different parts of the input. 
So the notion of function is different between these two. For the former, functions are used for data transformation. For CP, functions are compositions of constraints and are constraints themselves. 

> So I could make a constructor function to fill any (param not var) `array[Enum1,Enum2]of bool` from a (param not var) `array[_]of tuple(MyEnum1: MyEnum2)` for example.

For transformations of par data, MiniZinc is somewhat limited. You could use a host language to preprocess the input of the model, using "to-MiniZinc" interface libraries, if they are available. There are libs for Python, Java, R, Elixir, and maybe more.
Reply all
Reply to author
Forward
0 new messages