Albero casuale con fattore di diramazione specifico in Mathematica

Question

Sai se è possibile generare in qualche modo un grafico ad albero casuale con un fattore di diramazione specifico? Non voglio che sia un albero k-ary.

Sarebbe anche bello se potessi definire sia il fattore di diramazione che la profondità massima. Voglio generare in modo casuale un gruppo di alberi che differirebbero per fattore di ramificazione e profondità.

TreePlot con ingresso intero casuale restituisce qualcosa che è quasi quello che voglio:

TreePlot[RandomInteger[#] -> # + 1 & /@ Range[0, 100]] 

ma non riesco a trovare un modo per ottenere un albero con uno specifico fattore di ramificazione.

Grazie!

Answer 1

Immagino di essere un po 'in ritardo, ma mi piace la domanda. Invece di creare un albero sotto forma

{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4} 

Si utilizzerà la seguente forma di chiamate annidate, dove ogni argomento è un bambino, che rappresenta un altro nodo

0[1[2, 3, 4], 5] 

Entrambe le forme sono equivalenti e possono essere trasformati l'uno nell'altro

Row[{ 
    TreeForm[0[1[2, 3, 4], 5]], 
    TreePlot[{0 -> 1, 0 -> 5, 1 -> 2, 1 -> 3, 1 -> 4}] 
    }] 

Ecco come funziona l'algoritmo: Come argomenti abbiamo bisogno di una funzione di f che fornisce un numero casuale dei bambini e viene chiamato quando si crea un nodo. Inoltre, abbiamo una profondità d che definisce la profondità massima che può avere un (sotto) albero.

1. [Scegliere ramificazione] definire una funzione di ramificazione f che può essere chiamato come f[] e restituisce un numero casuale di bambini. Se si desidera un albero con 2 o 4 figli, è possibile utilizzare ad es. f[] := RandomChoice[{2, 4}]. Questa funzione sarà chiamata per ogni nodo creato nell'albero.

2. [Scegliere la profondità dell'albero] Scegliere una profondità massima d dell'albero. A questo punto, non sono sicuro di cosa vuoi che la casualità sia incorporata nella generazione dell'albero. Quello che faccio qui è che quando viene creato un nuovo nodo, la profondità dell'albero sotto di essa viene scelta casualmente tra la profondità del suo genitore meno uno e zero.

3. [Crea contatore ID] Creare una variabile di contatore univoca count e impostarla su zero. Questo ci darà l'aumento dell'ID del nodo. Quando si crea un nuovo nodo, è aumentato di 1.

4. [Crea un nodo] Aumento count e usarlo come nodo-ID. Se la profondità attuale d è pari a zero, restituire una foglia con il conteggio ID, altrimenti chiamare f per decidere quanti figli il nodo deve ricevere. Per ogni nuovo bambino ha scelto a caso la profondità del suo sotto-albero che può essere 0,...,d-1 e chiamare 4. per ogni nuovo bambino.Quando tutte le chiamate ricorsive sono tornate, l'albero è costruito.

Fortunatamente, in Mathematica -code questa procedura non è così dettagliato e consiste soltanto poche righe. Mi auguro che possiate trovare nel codice quello che ho descritto sopra

With[{counter = Unique[]}, 
generateTree[f_, d_] := (counter = 0; builder[f, d]); 
builder[f_, d_] := Block[ 
    {nodeID = counter++, childs = builder[f, #] & /@ RandomInteger[d - 1, f[]]}, 
    nodeID @@ childs 
]; 
builder[f_, 0] := (counter++); 
] 

Ora è possibile creare un albero casuale come segue

branching[] := RandomChoice[{2, 4}]; 
t = generateTree[branching, 6]; 
TreeForm[t] 

O se vi piace potete utilizzare il prossimo funzione per convertire l'albero in ciò che è accettato da TreePlot

transformTree[tree_] := Module[{transform}, 
    transform[(n_Integer)[childs__]] := (Sow[ 
    n -> # & /@ ({childs} /. h_Integer[__] :> h)]; 
    transform /@ {childs}); 
    Flatten@Last@Reap[transform[tree] 
] 

e utilizzarlo per creare molti alberi casuali

trees = Table[generateTree[branching, depth], {depth, 3, 7}, {5}]; 
GraphicsGrid[Map[TreePlot[transformTree[#]] &, trees, {2}]]