CODEWITHSUNDEEP
algorithmmathgraph-theory
Karibiusk
Karibiusk

Reputation: 107

Matching items 1-1 with partial information in rust

I have encountered the following situation when writing my program and I am not sure what is the best way to go about solving it, there is probably some algorithm that would be best for it, but I am not sure on what would be the correct terms for it.

I have 3 lists:

  1. An unordered list of detailed information about individual users.
  2. An unordered list of users
  3. An list of "hints" for matching the users to their information, varying in correctness

I know that every single information item belongs to one user that is in my list, and the number of users and information items is equal.

The "hints" that I have can be described in the style of "User B has a number that is >= 8 at index 52 of their information item", or "User C has a number that is equal to 6 at index 12 of their information item".

The point is that for any given information item, I can check if it either satisfies the hint for that user, or it doesn't satisfy the hint of a user. Of course, a hint can be true for multiple items and an item cannot belong to more than one user.

It is important to note that the amount of hints I have will not necessarily be enough to match every user to an item, but I want to nevertheless narrow it down as much as possible with the information that I have, and maybe get results that would describe, for example, that item 5 belongs to A, item 6 belongs to either B, C, item 5 belongs to e or f, but item 6 certainly belongs to c if item 5 belongs to f.

I also do not trust all my hints equally. I have some hints that are almost certainly true, and I want these to be assumed to not be able to contradict themselves, and if they do contradict or create an impossible situation with the provided info item list, that it is found out about the error. And I also have hints that I don't trust as much, and these might contradict themselves, and if so the trusted ones are given priority, and these less trusted ones are only used as a last resort to suggest ways to narrow down the possibilities even further only at the very end.

I am using rust and petgraph for my program until I am at this point, I would think that there is a way that you are supposed to create a graph for this and use some algorithm on it to solve this problem.

Upvotes: 1

Views: 83

Answers (1)

Dave
Dave

Reputation: 9085

You can set this up as a bipartite graph, use edge weights to reflect your information, and then find the maximum matching.

You have two sets of nodes: one for users, and another for information. There are weighted edges between users and information nodes, with the edge weight representing our confidence in the connection.

I'm assuming for every hint you have a confidence score between 0 and 1 representing how likely you think the hint is to be true.

Here's how to convert hints to edge weights: Say we have 3 hints for a (user, info) pair: h1, h2, h3, with confidence scores c1, c2, c3. Then the edge between user and info gets the score 1 - ((1 - c1) * (1 - c2) * (1 - c3)).

E.g., say our confidence scores are 0.9, 0.3, 0.2. Then the edge weight becomes 1 - ((1 - 0.9) * (1 - 0.3) * (1 - 0.2)) = 1 - 0.1 * 0.7 * 0.8 = 0.944.

Leave any (user, info) pairs with no hints as having no edge.

Then, find the maximum weight matching in a bipartite graph. (e.g. https://www.geeksforgeeks.org/maximum-bipartite-matching/). This will maximize your confidence per the scores above.

Finally we're left with (user, info) pairs with no hints, which you can pair up however you like.

Upvotes: 3

Related Questions