Algorithm to match / link complementary pairs

Question

I'm working on a problem where I have a large number of pairs

e.g

1 -> 2

4 -> 3

2 -> 8

..

And a "match" would be considered 1 -> 2 and 2 -> 8 to make 1 -> 2 -> 8, as "1 -> 2" ends with 2 and "2 -> 8" starts with 2.

Given a large set of pairs, i'd like to create the longest possible chain. I know I could brute force it, but I'm wondering if there is a better way

Edit - I can give more precise context for the problem (Sorry, i'm a student currently in data structures who has not taken an algorithms course)

The datapoints in the pairs would be song names which well flow together. There is a subreddit called "/r/ocrableach" which posts pairs of songs where the ending of one song blends well with the beginning of another song.

An item can appear multiple times in the data set, but i will be discarding repeats as i build my chain.

I'd like to pull posts from /r/ocrableach and try to build the longest continuous playlist based on the song pairs.

If I have the pairs

"Okra -> Bleach"
"Bleach -> I THINK"
"On God" -> "Okra"

I'd like to start constructing a linked list like this:

"Okra -> Bleach" and "Bleach -> "I THINK" match
= "Okra -> Bleach -> I THINK"

"Okra -> Bleach -> I THINK" and "On God -> Okra" match
= "On God -> Okra -> Bleach -> I THINK"

I'm essentially checking if the tail of one pair matches with the head of the "chain" to see if it can be added.

Answer 1

Assuming you don't want to repeat a song, this is the problem of finding a longest path in a directed graph. Here the graph has one vertex per song, and an edge $s \to t$ if the ending of song $s$ blends well with the beginning of song $t$.

Unfortunately, the longest-path problem is NP-hard. (See, e.g., Is finding the longest path of a graph NP-complete?, How to prove NP-hardness of a longest-path problem?.) This means that you should not expect to find an efficient algorithm for your problem that works on all graphs and that is always correct. Instead,if you want to solve it in practice, your best will be to look for approximation algorithms or heuristics.

Unfortunately, it is also known that there are no approximation algorithms with guaranteed performance, i.e., that are guaranteed to find a path that is close to the longest, for all graphs. (See https://en.wikipedia.org/wiki/Longest_path_problem#Approximation.) So your best bet is to look for heuristics... or hope your graph has some special structure.

If you are willing to allow repeated songs, then the problem becomes tractable in theory, but the resulting algorithms are probably going to provide poor-quality results in practice. In particular, if you find any cycle in the graph, then it is possible to traverse the cycle an unbounded number of times, achieving an arbitrarily long path. Unfortunately these algorithms have a decent chance of producing a cycle of short length, which means that your playlist will just repeat the same few songs over and over... which is probably not what you'd hope for.

One simple heuristic might be to pick a starting vertex randomly, do depth-first search starting from that vertex, find the leaf in the tree with largest depth, and use the path from the root to that leaf as your playlist. You could repeat a few times from a few different random starting points and take the best playlist found. There are no guarantees for how well this will perform; you'd have to try it out to see.