Given a set of buyers, houses, agents with the following constraints:
- Agents only know a subset of buyers
- Agents only know a subset of houses
- Agents can only do some amount of transactions
Construct a flow network to model the problem. Disclaimer this is homework
I have put together some thoughts on a solution to this problem. First I realized that agents should be right before the sink node with a max flow equal to the number of possible transactions. This would then limit the number of transactions that can flow through an agent since the max flow can't be exceeded.
I was then thinking that it would be possible to put an edge between each person and house that an agent knows (example if agent knows person A, B and house 1, 2 there are edges (A,1), (A,2), (B,1), (B,2)). Finally, connect each house that an agent knows to an agent with max flow of 1. Then by running a Ford-Fulkerson algorithm across it the inflow of the sink node would indicate max number of transactions.
However, I am concerned that there is no limit of stopping a house from being purchased more than once. I have tried building the network with various configurations (swapping houses and clients, building nodes of client/house pairs) and nothing seems to solve this specific problem.
I am mostly looking for hints to solve this problem.
