cpettitt / dig.js

Graph algorithms for JavaScript
MIT License
20 stars 4 forks source link

Unnecessary type-2 conflicts with example graph #49

Open cpettitt opened 12 years ago

cpettitt commented 12 years ago

Numerous crossings in this graph, some of which are unnecessary. Note the type-2 conflict between 2 -> 8 and 15 -> 27.

digraph {
    0 -> 4;
    0 -> 5;
    0 -> 6;
    0 -> 29;
    17 -> 3;
    5 -> 3;
    5 -> 4;
    5 -> 26;
    5 -> 14;
    5 -> 10;
    5 -> 2;
    3 -> 4;
    26 -> 18;
    14 -> 10;
    2 -> 8;
    2 -> 23;
    23 -> 24;
    24 -> 15;
    24 -> 12;
    24 -> 28;
    1 -> 12;
    12 -> 6;
    12 -> 19;
    12 -> 9;
    6 -> 13;
    6 -> 29;
    6 -> 25;
    6 -> 21;
    29 -> 25;
    21 -> 22;
    25 -> 11;
    22 -> 8;
    22 -> 9;
    15 -> 27;
    15 -> 16;
    8 -> 16;
    8 -> 20;
    11 -> 16;
    11 -> 9;
    16 -> 27;
    27 -> 13;
    27 -> 19;
    13 -> 20;
    19 -> 9;
    20 -> 4;
    9 -> 4;
    9 -> 28;
    28 -> 7;
}
cpettitt commented 12 years ago

Ordering dump:

Row 7:

0: "_d-24-28-1"
1: "_d-12-9-0"
2: "_d-12-19-0"
3: "_d-0-29-5"
4: "_d-15-16-0"
5: "6"
6: "_d-15-27-0"
7: "_d-2-8-3"
8: "_d-5-4-4"
9: "_d-3-4-3"
10: "_d-0-4-5"

Row 8:

0: "_d-24-28-2"
1: "_d-12-9-1"
2: "_d-12-19-1"
3: "29"
4: "_d-6-25-0"
5: "_d-15-16-1"
6: "21"
7: "_d-15-27-1"
8: "_d-2-8-4"
9: "_d-6-13-0"
10: "_d-5-4-5"
11: "_d-3-4-4"
12: "_d-0-4-6"

Note that 15-27 is to the left of 2-8 in both rows, so the ordering phase is behaving correctly. It appears that this is an issue with the x-position phase.