Say we have a group of N person, and each person might want to sell or buy one of the M items, how to find a closed path among them for an exchange?

Question

Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,

• person 1 has item A, C, D, and wants item F

• person 2 has item B, C, and wants E

• person 3 has item E, and wants G

  ...

You get the idea. So it's basically a supply/demand matching problem, and if we represent this as a person-item matrix, it's gonna be a very sparse one.

So my question would be:

1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
2. How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I've figured how by using some matrix operations)?
3. What would be the complexity for finding longest/shortest paths?

Any advice would be appreciated.

Answer 1

Instead of a sparse matrix I'd go with a Directed Graph, where each node is a person and each link is a potential transaction.

Each cycle in the graph is a potential trade. See Best algorithm for detecting cycles in a directed graph for more information.

Answer 2

I think a good way to represent the problem is as a bipartite, directed graph.

To create the graph, do this:

• Draw a node for each person.
• Also draw a node for each item.
• Whenever a person has an item, draw an arrow from that person to that item. (The idea is: if the person is happy, then we can obtain the item.)
• Whenever a person wants an item, draw an arrow from that item to that person. (The idea is: if we have the item, then we can make the person happy.)

Your goal is simply to find a circuit in this graph.

This means that your question can be rephrased as, "How can I find circuits in a bipartite directed graph?" The algorithms described in these questions and answers may be helpful:

• https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph
• https://cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph

(The difference between a circuit and a cycle is that a circuit can visit the same node multiple times (although it can't use the same arrow multiple times), while a cycle can only visit each node once. In the context of your problem, a cycle would mean that each person only participates in one trade, and each item only participates in one trade.)

Answer 3

Edit: My other answer is better than this one; look at that one instead.

The problem can be represented by making a grid filled with dots. The grid has:

• N rows, one for each person.
• M columns, one for each item.
• One green dot whenever a person is willing to give an item (because "give" starts with "G" for "green"). For example, if Bob is willing to trade up to three apples, then put 3 green dots in the grid cell which is in the row representing Bob and the column representing apples.
• One red dot whenever a person wants to receive an item.

(In mathematical terms, this would be two N × M matrices, called G and R.)

Here's one algorithm for solving your problem. It's probably not the best algorithm, but it's an algorithm.

First, transform the grid into a directed graph by taking these two steps:

• Draw an arrow from every green dot to every red dot in the same column (indicating that one person can give an item and another person can receive it).
• Draw an arrow from every red dot to every green dot in the same row (indicating that a person can receive one item and give another item).

Second, find a directed cycle in the graph. This cycle provides the answer.

As an example, suppose that Bob has an apple and wants an orange, and Sarah has an orange and wants an apple. The grid would contain

• a green dot for (Bob, apple),
• a green dot for (Sarah, orange),
• a red dot for (Bob, orange), and
• a red dot for (Sarah, apple).

The cycle that we find

• starts at the green dot (Bob, apple) and goes to the red dot (Sarah, apple) (Bob gives an apple and Sarah receives it);
• goes from the red dot (Sarah, apple) to the green dot (Sarah, orange) (since Sarah received an apple, she's willing to give an orange);
• goes from the green dot (Sarah, orange) to the red dot (Bob, orange) (Sarah gives an orange to Bob); and
• returns from the red dot (Bob, orange) back to the green dot (Bob, apple) (Bob received an orange and so he's willing to give up an apple).