CODEWITHSUNDEEP
algorithmpathtreecombinations
fa323
fa323

Reputation: 13

All combination tree algorithm

I have a question related to trees. I have about 100 sentences on a topic like "car." Those sentences basically talk about a car. If a user submits a query: "Find all combinations of word links between words "engine" and "oil"." I want to find all the word links possible so that "engine" and "oil" connects by any number of similar words in a sentence.

For instance.

  1. Engine is hot when it runs.
  2. Car has an engine.
  3. Car use an oil.

In this case the answer will be: engine->car->oil (three word combination). And I want to find all the combinations possible so that in the end "engine" and "oil" connects with each other. It is not the shortest path, or the longest path, but all possible paths running in all directions and words. It is even possible to have 1,000 word combinations to reach "engine" and "oil" as long as the paths are not similar of course.

Is there a way to do this. I tried using bread-first, but it is little tricky. For instance combinations could be.

  1. engine->car->run->stop->oil
  2. engine->car->oil
  3. engine->fast->brake->oil

Can anyone please help me with this. What is the logic and idea here. I can't ignore a word I already visited because that will stop the algorithm right there and not give me all the links.

Please help and insights.

Thanks.

fa323

Upvotes: 1

Views: 1431

Answers (1)

Chris Hopman
Chris Hopman

Reputation: 2102

Your question is so underspecified... that is, even in your example, it is unclear why the answer doesn't include engine->an->oil.

Also, it doesn't actually have anything to do with trees, rather it deals with graphs.

The first thing you need to do is determine how to build your graph. A reasonable way of doing this would be to have an edge between two words if they both appear in a particular sentence.

Then you have to decide what you want outputted. I highly doubt that you want all paths. Why? Well, if you build the graph I described, then even using just your first sentence, there are 24 paths from engine to oil not counting paths with cycles. However, if that is what you want anyway, you can find all non-cyclic paths in a graph via depth-first search, where you mark a node visited when you push it on the stack, and unmark it when you take it off.

Upvotes: 2

Related Questions