<p>This is technically not in scope for this site, but we're friendly people here :), and your question is relatively well-formed. </p>

<p>It sounds like what you have is a <a href="http://en.wikipedia.org/wiki/Directed_graph">directed graph</a> where the strings are your vertices, and your two tables are storing the "forward edges" (a -> b) and the backward edges (a &lt;- b). The question you're asking is whether there's a way to go from one vertex in this graph to another. </p>

<p>The answer is to do a <a href="http://en.wikipedia.org/wiki/Graph_traversal">graph traversal</a> (breadth-first or depth-first) on this graph. Any basic textbook on algorithms (<a href="http://en.wikipedia.org/wiki/Introduction_to_Algorithms">like this one</a>) should help. </p>

CC BY-SA 3.0
2012-07-19T18:34:15.963Z
Thanks for pointing me in the right direction :) I'll check out the resources you mentioned.
amba88
CC BY-SA 3.0
2012-07-19T17:48:42.743Z
2012-07-19T17:48:42.743Z
Suresh Venkat
<p>I don't know if CS theory is the best place for this, sorry if it's not.</p>

<p>I'm not a computer scientist so I don't know complex maths, but I have a theoretical problem in an application I'm working on that I can't wrap my head around. I would appreciate any help.</p>

<p>I need to find the best or correct string to fit between two other strings.</p>

<p>Given the strings <code>strA</code> and <code>strB</code> the function should analyse a database and return a string that looks like:</p>

<p><code>strA strC strD strE strB</code> The number of strings in between can vary in number.</p>

<p>I have a database in place that looks something like this:</p>

<pre><code>strA strC
strA strD
strA strB

strB strA
strB strC

strC strA
</code></pre>

<p>This basically says that in the final string <code>strC</code> can come after <code>strB</code> but <code>strD</code> cannot come after <code>strB</code>.</p>

<p>I also have a secondary database which describes which strings can come before which strings. So for example...</p>

<pre><code>strA strC
strA strD
strA strB

strB strA
strB strC

strC strA
</code></pre>

<p>But this database states that <code>strC</code> can come before <code>strB</code>, but not <code>strD</code>.</p>

<p>I have a function which, only given the beginning string can find all the strings which would fit after it in the correct order. But I need to also include an ending string and have it find the correct path between the start and finish.</p>

<p>I've thought about it over and over again and I don't even know where to start with this. I hope my explanation is not too convoluted. I would greatly appreciate any ideas.</p>

<ds.algorithms><graph-theory><application-of-theory>
Find the best path between two strings
amba88
# Find the best path between two strings

(Asked by: username_0 on 2012-07-19)

I don't know if CS theory is the best place for this, sorry if it's not.

I'm not a computer scientist so I don't know complex maths, but I have a theoretical problem in an application I'm working on that I can't wrap my head around. I would appreciate any help.

I need to find the best or correct string to fit between two other strings.

Given the strings `strA` and `strB` the function should analyse a database and return a string that looks like:

`strA strC strD strE strB` The number of strings in between can vary in number.

I have a database in place that looks something like this:

```
strA strC
strA strD
strA strB

strB strA
strB strC

strC strA

```

This basically says that in the final string `strC` can come after `strB` but `strD` cannot come after `strB`.

I also have a secondary database which describes which strings can come before which strings. So for example...

```
strA strC
strA strD
strA strB

strB strA
strB strC

strC strA

```

But this database states that `strC` can come before `strB`, but not `strD`.

I have a function which, only given the beginning string can find all the strings which would fit after it in the correct order. But I need to also include an ending string and have it find the correct path between the start and finish.

I've thought about it over and over again and I don't even know where to start with this. I hope my explanation is not too convoluted. I would greatly appreciate any ideas.

**Tags:** ds.algorithms, graph-theory, application-of-theory


---

## 1 answers

### Answer by username_1 on 2012-07-19. Score: 5 | Accepted answer

This is technically not in scope for this site, but we're friendly people here :), and your question is relatively well-formed.

It sounds like what you have is a [directed graph](http://en.wikipedia.org/wiki/Directed_graph) where the strings are your vertices, and your two tables are storing the "forward edges" (a -> b) and the backward edges (a <- b). The question you're asking is whether there's a way to go from one vertex in this graph to another.

The answer is to do a [graph traversal](http://en.wikipedia.org/wiki/Graph_traversal) (breadth-first or depth-first) on this graph. Any basic textbook on algorithms ([like this one](http://en.wikipedia.org/wiki/Introduction_to_Algorithms)) should help.

> **Comments:**
> **username_0**: Thanks for pointing me in the right direction :) I'll check out the resources you mentioned.  

---

