CODEWITHSUNDEEP
graph-theory
Chris
Chris

Reputation: 8656

Calculating and identifying "desirable" routes through directed graph

Forgive the vague title, it's been a few years since I've done any Mathematics related to this area and my terminology is fairly lacking (part of why I'm asking this question). I'm sure there's a well defined algorithm/theory that already deals with what I'm trying to achieve, but I can't quite pin down the words to find it.

I'll try and describe the situation I'm modelling:

Given a group of items [a,b,c,d,e,f], a person may be offering to trade certain items, e.g. I may swap you "a" for "b", and you may be offering "2xc" for an "e". I can scoop up all these trades and create a graph outlining the options on offer. I'm interested in looking for particular trade paths, and as an aside, trade paths that would give me surplus items - I assume this sort of thing must already exist in the financial sector (again, I'm missing the names/experience of the mathematics).

so if I had "a" and wanted "f", and I had the following paths available:

a -> b, b -> f, c -> b, a-> 2(c), b -> a

I'd end up with

a -> b -> f

a -> (2)c -> b -> f    
      |
      c             (An additional c)

There may places where I could cycle repeatedly, so if I used the b -> a relation above, I could continually extract c because of the surplus c item.

I'm reasonably sure I can write a program to do this, but I'm a big fan of understanding the correct terminology and methodology behind problems like this one. If anyone can point me in the right direction for a particular topic to read about, or a if there's a obvious name for what it is I'm trying to achieve, I'd be very grateful.

Apologies again for the vague-ness.

Upvotes: 0

Views: 113

Answers (1)

Fred Foo
Fred Foo

Reputation: 363627

Sounds like a typical state space search problem. Algorithms like BFS or iterative deepening can find the shortest series of trades, or even generate all possibilities.

To apply these algorithms, you'll have to redefine your graph. Instead of using nodes like a and b with an edge a -> b, define a state space where a state consists of a finite number of each of the elements {a, b, c, f} (in this case, a four-tuple of integers would suffice) and a successor function S that applies all possible trades given a state and constructs a set of successors states. E.g., in pseudo-Python notation,

S({a: 1, b: 2, c: 0, f: 0}) = [{a: 0, b: 3, c: 0, f: 0},   # trade a for b
                               {a: 1, b: 1, c: 0, f: 1},   # trade b for f
                               {a: 1, b: 2, c: 2, f: 0},   # trade a for 2c
                               {a: 2, b: 1, c: 0, f: 0}]   # trade b for a

Since state-space search is a classical paradigm in AI, most AI textbooks cover it. In particular, I can recommend AIMA by Russell and Norvig, which spends its first few chapters discussing state space search in quite some detail.

Upvotes: 1

Related Questions