Avoidance of edge crossing in easy cases

[hyanwong]

This might be too tricky, but for the following tree sequence:

def whatis_example():
    demes_yml = """\
        description:
          Asymmetric migration between two extant demes.
        time_units: generations
        defaults:
          epoch:
            start_size: 5000
        demes:
          - name: Ancestral_population
            epochs:
              - end_time: 1000
          - name: A
            ancestors: [Ancestral_population]
          - name: B
            ancestors: [Ancestral_population]
            epochs:
              - start_size: 2000
                end_time: 500
              - start_size: 400
                end_size: 10000
        migrations:
          - source: A
            dest: B
            rate: 1e-4
        """
    graph = demes.loads(demes_yml)
    demography = msprime.Demography.from_demes(graph)
    # Choose seed so num_trees=3, tips are in same order,
    # first 2 trees are topologically different, and all trees have the same root
    seed = 12581
    return msprime.sim_ancestry(
        samples={"A": 2, "B": 3},
        demography=demography,
        recombination_rate=1e-8,
        sequence_length=1000,
        random_seed=seed)

ts = whatis_example()
d3arg = visualizer.D3ARG(ts=ts)
d3arg.draw(
  width=500,
  height=300,
  y_axis_labels=True,
  y_axis_scale="rank",
  tree_highlighting=True,
  edge_type="line",
);

The default layout means the nodes on the far left have overlapping edges (which is a bit misleading in the case of 14->6, I think):

If node 14 is dragged to the right, a more sensible edge arrangement is displayed:

It may be that this doesn't generalise easily, though, and an algorithm to get it to work in the general case is tricky or impossible. If so, just close this issue, I reckon.

[kitchensjn]

The positioning rules would probably be hard to generalize across many ARGs as the force layout isn't recognizing the presence of edge crossovers so doesn't know how to avoid them. If you were to play with the repelling and attracting forces, you could probably find a balance for this specific ARG, but I think that would be a pretty unique combination of forces.

Also for reference, here are the starting and ending positions if you use graphviz to set initial node positions:

Not fully equivalent, but a more approachable solution could be stylizing edge overlaps in a way that makes them more clear to users. With edge_type="ortho", edges have a thicker white line beneath them to give the appearance that they are crossing overtop one another but not connected (see connection from Node 26 to Node 22 or Node 18/19 from this other tree sequence).

This is not implemented in edge_type="line" because of some ugliness near node connections, but something similar might help with your tree sequence... thoughts?

[kitchensjn]

Closing this for now and will open different issue specifically about stylizing edge crosses.