Finding paths in a tree

Vincent Tjeng

Oct 8, 2013 01:45

@Rojo - my questions was as follows. I have a nested list in the form {{1}, {2, {3, {4, {5, {6}}, {7}}, {8, {9}}}}, {10, {11, {12}}, {13}}}

this is meant to represent the tree

TreePlot[{0 -> 1, 0 -> 2, 2 -> 3, 3 -> 4, 4 -> 5, 5 -> 6, 4 -> 7,
3 -> 8, 8 -> 9, 0 -> 10, 10 -> 11, 10 -> 13, 11 -> 12}, Top, 0,
VertexLabeling -> True]

I'd like to find all possible paths in the tree.

In a sort of depth-first search

Rojo

@VincentTjeng I have no memories of what I asked you before, but anyway

Heheh

You wish to turn {{1}, {2, {3, {4, {5, {6}}, {7}}, {8, {9}}}}, {10, {11, {12}}, {13}}} into some list of paths of that tree?

Vincent Tjeng

I pinged you on chat asking whether you were around, and you replied some time later that you were

Rojo

Oh yeah

You need that to be efficient or just work?

Will the nodes always be numbers?

Vincent Tjeng

just work would be good i guess

yep, the nodes would always be numbers.

I'm pretty sure there might be a while loop that worked, but I was hoping that there would be a functional way to solve this directly dealing with the lists

although that is not vital

Rojo

Sure

rm -rf

Oct 8, 2013 02:03

list = {0, {{1}, {2, {3, {4, {5, {6}}, {7}}, {8, {9}}}}, {10, {11, {12}}, {13}}}};
Cases[list //. {h__Integer, t__List} :> Map[{h} ~Join~ # &, {t}], {__Integer}, Infinity]

@VincentTjeng ^^

Vincent Tjeng

oh my

rm -rf

(If you have huuge graphs, then a different approach will be needed)

Vincent Tjeng

let me absorb that first

Rojo

Hehe

rm -rf

In any case, your question is answered in this post:

8

Q: Preserve information in flattening a nested list

I have a series of lists in the form below: list={ {1,1} , {2,2}, {3,{3,1},{3,2},{31,{31,1},{32,2}}} } Its a nested list which the dimension is changing case to case. I want to manipulate the list to have an output like this: LIST={{1,1},{2,2},{3,3,1},{3,3,2},{3,31,31,1},{3,31,32,2}} I am t...

list-manipulation

Rojo

Oct 8, 2013 02:07

@VincentTjeng You can also use Position[your list, _?NumericQ] to get the positions (almost) you then want to extract. Or you can do a depth first traversal by defining your own function and keeping track of your stack. Or even use Stack (weird solution)

Or use ReplaceAll to traverse

halirutan

@VincentTjeng @rm-rf hmm... let's make this more compact

t = {{1}, {2, {3, {4, {5, {6}}, {7}}, {8, {9}}}}, {10, {11, {12}}, {13}}};
0 @@ (t //. {r_, c__} :> r[c] /. {n_} :> n)

TreeForm[%]

rm -rf

@halirutan He wanted all the paths...

Vincent Tjeng

@halirutan I feel that I should type this out into a full problem just so I can upvote your solution

(it isn't exactly what I wanted but it was great to learn how to do that too)

@rm-rf gave the output I had in mind. Still working out how it goes, though.

rm -rf

@halirutan but I do like that solution... reminds me of this answer of mine for @Rojo's Q

halirutan

@rm-rf Ah.. I just copied the TreePlot code

Rojo

Oct 8, 2013 02:12

@rm-rf The Composition@@?

Vincent Tjeng

If you guys are interested, the horrible output comes out from this pair of functions, defined to split words

search = Function[{currentString},
valids =
If[DictionaryLookup[StringTake[currentString, #]] == {},
"", #] & /@ Range[StringLength@currentString];
Select[valids, # != "" &]
];

rm -rf

@Rojo Hehe, yes

Vincent Tjeng

recurse = Function[{currentString},
Prepend[recurse[StringDrop[currentString, #]], #] & /@
search[currentString]];

rm -rf

@VincentTjeng split words how?

Vincent Tjeng

then, for example, recurse["partition"] gives the following output

{{2}, {3, {2, {2, {2}}}}, {4, {2, {3}}}, {9}}

corresponding to the function finding the words

"pa", (and the rest not being a valid word)

"par, ti, ti, on"

"part, it, ion"

and "partition"

rm -rf

Oct 8, 2013 02:13

are you building up words successively from a given list?

Vincent Tjeng

I wanted to find all possible ways to split a string completely into dictionary words

so for example the first split would not be accepted, since "rtition" is not a valid word.

rm -rf

@VincentTjeng Hmm... you might want to take a look at my boggle answer. I do something very similar to what you're doing here... (also see Leonid's answer)

34

A: How can I use Mathematica's graph functions to cheat at Boggle?

My solution is a recursive tree traversal algorithm which seeks and searches neighbouring vertices only if it will lead to a word (e.g., Something starting with ZQ is immediately disqualified), but it's faster than yours because I construct the adjacent vertices list from the adjacency matrix rat...

Vincent Tjeng

(with what you guys have given me here, I can definitely write code to get all the possible partitions of a phrase)

(but the perfectionist in me wants a nice solution)

Rojo

@VincentTjeng And what is nice to you?

Because, for example, I believe that @rm's nice is totally different to Mr.Wizard's

Vincent Tjeng

I'm pretty sure that my recursive function can be re-written to immediately output all the possible splits as such

{{0, 2}, {0, 3, 2, 2, 2}, {0, 4, 2, 3}, {0, 9}}

rm -rf

Oct 8, 2013 02:17

@Rojo Hehehehe! YES! :D

Vincent Tjeng

rather than outputting it in the initial form

I'm thinking that this can be done by Mapping my Prepend, but I haven't been able to get it to work for some time

@rm-rf, let me read your boggle solution

rm -rf

@VincentTjeng I'm pretty sure if you start mapping prepends, etc., you'll end up with a version of what I showed :)

(I just use Join to combine them instead of Prepend)

Oh wait... this is for the string thing, not the graph thing. Never mind

Rojo

I may be lazy to read again and think but

What's the desired output of this all? For example, input "partition", what would the output represent?

Vincent Tjeng

okay

input "partition"

output, {{"par","ti","ti","on"},{"part","it","ion"},{"partition"}}

i didn't explain myself well in the first place

Rojo

I see, you want all valid partitions of the word, got it >(

:)

rm -rf

Oct 8, 2013 02:24

@VincentTjeng Why does the algorithm not like "tit"? :/

Vincent Tjeng

i'm not sure!

this needs some investigation

rm -rf

The first should be {"par", "tit", "ion"}

Vincent Tjeng

{"par", "tit", "ion"}, you mean

hmmm....

okay, I really have no idea

"tit" is a word that appears in the dictionary.

Rojo

@rm-rf Good catch

Vincent Tjeng

or not

DictionaryLookup["tit"]

returns {}

Rojo

Oct 8, 2013 02:30

@VincentTjeng Report it to Wolfram

Vincent Tjeng

would you guys mind trying just for verification

rm -rf

That's stupid... it has "titties" and "titty", but not "tit" and "tits". I'm sure some censoring algorithm must've removed it before shipping.

Vincent Tjeng

what's more, it's actually a bird too

wolfram would be extremely amused about how we found this

rm -rf

Of course, "wolfram" is a word... ffs

lol

Rojo

Dear god, that guy

Vincent Tjeng

Oct 8, 2013 02:39

anw guys, thanks for the very interesting conversation today :) I'll continue working on the problem, and perhaps post it as in full q&a format (if a similar question doesn't already exist on the site ... my search skills are terrible)

Rojo

Oh, it's an alternate name for tungsten

rm -rf

@Rojo Sure, but I checked and they don't have "aurum" (gold) or "argentum" (silver)...

Rojo

@VincentTjeng I was hoping some variant of StringReplaceList would do it all in a one liner but I failed so far

Vincent Tjeng

(if you have a nice solution feel free to ping me, I'll write up the question properly so the community can see the solution)

@rm-rf I can already begin to imagine the email that wolfram's tech support receives. "To whom it may concern ... I was very disappointed to find that Mathematica's dictionary contains 'wolfram' as a word but not 'tit' ... "

Rojo

If you are sticking to English there's also WordData

Wolfram Mathematica

Participants