# Arranging “ranked” nodes of a graph symmetrically

I have Markov chains with a pair of absorbing states taken from the $n$-length strings formed from {"H","T"} for n at least 3 (generally 3 or 4), for example

{"HHH", "HHT", "HTH", "HTT", "THH", "THT", "TTH", "TTT"}


and with other states with names "leading up" to those states through the addition of either "H" or "T" to the end of the name of the previous state, from an initial state of "". For example the chain for the pair states "TTH" and "HTT" would have states

{"", "H", "T", "HT", "TT", "HTT", "TTH"}


I would like to represent the Markov chain for the transitions among these states as a graph with the nodes arranged according to their length as, for example in

but Graph does not arrange nodes this way by default,

and I can't figure out how to achieve a finer control over the node arrangement beyond what is offered by GraphLayout (though in some cases, as for this example, choosing "LayeredDrawing" comes close).

Is there a way that I can use the node names to order and align the arrangement of nodes in a Graph so that they appear as they do in the first figure: first "", then 1-length node names, then 2-length node names, etc.?

Ideally the approach should be able to take something like

mp = DiscreteMarkovProcess[1, ( {
{0, .5, 0, 0, .5, 0, 0},
{0, .5, .5, 0, 0, 0, 0},
{0, .5, 0, .5, 0, 0, 0},
{0, 0, 0, 1, 0, 0, 0},
{0, .5, 0, 0, 0, .5, 0},
{0, 0, 0, 0, 0, .5, .5},
{0, 0, 0, 0, 0, 0, 1}
} )];
Graph[mp, VertexLabels -> {1 -> "", 2 -> "H", 3 -> "HT", 4 -> "HTT", 5 -> "T",  6 -> "TT", 7 -> "TTH"}]


and use VertexLables to automatically position the nodes in the Graph (the numbering and ordering of nodes is not guarantee, only the names). This should also work for "degenerate" cases such as

and for longer absorbing states such as

-
Your graph is relatively small and you need fine control over the appearance, possibly create a publication quality figure. What I would do is export the graph to GraphML, import it into yEd, compute an automatic layout, then manually tweak it and manually add styling. The node names are preserved and can be mapped to visual node labels in yEd. –  Szabolcs May 14 at 23:38
@Szabolcs: I'm very much trying to avoid anything along that path. While each graph is small, I'm generating arbitrary graphs on the fly for interactively exploring and comparing them—e.g. with someFuncIDefine["HHH", "TTT"] which currently does all the work for me to build the appropriate Markov chain draw a labeled graph as in the second figure above. I need that function to go the next step and position the nodes as in the other figures. (If I weren't doing this I'd just draw them by hand and then use TikZ.) –  raxacoricofallapatorius May 14 at 23:45
OK, that makes sense. Do the graphs have a special structure that we can exploit to position the nodes "by hand"? Writing a generic layout algorithm that also does what you want sounds hard. Writing one that only works for special cases might be feasible. Your example figures always have a Start node on the left, then precisely two rows of nodes above each other. Are all of them like this? Would it work to position the nodes in a grid (or maybe set of vertically centred columns) where the $n^\text{th}$ column contains length-$n$ nodes? –  Szabolcs May 15 at 0:01
The edge routing would be more difficult, but we could still offload that task to an external but automatic tool (maybe GraphViz? I don't have much experience with it but I know that it's much more flexible at edge routing than Mma). –  Szabolcs May 15 at 0:03
@Szabolcs: Always 1 start node on the left, 2 at the right end (on top of each other), 2 at each each stage to the left of that, until there's just 1 and then 1 the rest of the way leftwards. –  raxacoricofallapatorius May 15 at 0:17

Choosing "MultipartiteEmbedding" with "VertexPartition"->{1,1,2,2,...2} for the GraphLayout option gives the desired layout:
mp = DiscreteMarkovProcess[1, {{1/2, 1/2, 0, 0, 0, 0}, {0, 0, 1/2, 1/2, 0, 0},

That looks promising. For the general case, I'll need to make sure my states are sorted appropriately in constructing the DiscreteMarkovChain, which I think I can figure out how to do. Then I'll need to recognize where I have 2 and where I have one. Let me see if I'm clever enough. –  raxacoricofallapatorius May 15 at 1:00