Layout produces overlapping nodes

[cpettitt]

The input below renders with {08,09} overlapping and {15,16} overlapping.

digraph {
"B"->"A"
"C"->"B"
"D"->"B"
"E"->"B"
"F"->"B"
"G"->"C"
"H"->"C"
"C"->"I"
"J"->"D"
"D"->"I"
"K"->"D"
"L"->"E"
"E"->"I"
"M"->"E"
"N"->"F"
"O"->"G"
"P"->"G"
"Q"->"G"
"R"->"G"
"S"->"G"
"T"->"G"
"U"->"G"
"V"->"G"
"W"->"G"  
"X"->"H"
"Y"->"H"
"O"->"H"
"T"->"H"
"Z"->"H"
"M"->"H"
"I"->"01"
"I"->"02"
"I"->"03"
"I"->"04"
"Q"->"J"
"05"->"J"
"06"->"K"
"Y"->"K"
"07"->"L"
"S"->"L"
"08"->"L"
"09"->"L"
"R"->"L"
"Q"->"L"
"10"->"L"
"P"->"L"
"X"->"M"
"Y"->"M"
"06"->"M"
"W"->"N"
"11"->"Q"
"12"->"W"
"13"->"W"
"14"->"W"
"15"->"Z"
"Y"->"Z"
"16"->"Z"
"17"->"Z"
"18"->"03"
"19"->"03"
"20"->"11"
"R"->"11"
"21"->"12"
"08"->"18"
"22"->"18"
"10"->"18"
"L"->"18"
"Y"->"19"
"X"->"19"
"23"->"19"
"25"->"23"
"05"->"25"
"26"->"25"
"A"->"27"
"A"->"28"
"24"->"21"
}

[cpettitt]

Heres a smaller instance which also violates separation rules. In this case there is no obvious overlap, but the separation between nodes B and R is too small for the down-right alignment:

Position phase: sep violation. Align: dr. Layer 10. U: B V: R. Actual sep: 63 Expected sep: 81 

digraph {
"F"->"B"
"J"->"D"
"D"->"I"
"E"->"I"
"Q"->"G"
"V"->"G"
"W"->"G"  
"Q"->"J"
"R"->"L"
"11"->"Q"
"12"->"W"
"15"->"Z"
"18"->"03"
"19"->"03"
"R"->"11"
"21"->"12"
"L"->"18"
"X"->"19"
"24"->"21"
}

[cpettitt]

It appears that there are at least a couple of problems with the "fast and simple" coordinate algorithm we're using. One which I had already seen and addressed was the possibility of applying shift too many times to nodes in a class. The second appears to be that shift cannot always be applied correctly with the original algorithm. Shift should be relative to some other shifted class (except for the top-most class), but the algorithm doesn't provide a way to track the possibilities. Will look into how to get this into the algorithm. Longer term I may switch this out with something that doesn't cause as much difficulty!