Skip to content

Instantly share code, notes, and snippets.

@realazthat
Created January 26, 2015 18:20
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save realazthat/9299877a83cba4720aec to your computer and use it in GitHub Desktop.
dot graphs for "Maintaining an efficient ordering where you can insert elements “in between” any two other elements in the ordering?" at http://cs.stackexchange.com/a/14710/2755
#step 1
digraph list{
{rank=same;
D1[style=invis,shape=point];
D1[style=invis];
}
{rank=same;
D[dir=back];
}
D1 -> D;
}
#step 2
digraph list{
{rank=same;
C1[style=invis,shape=point];
D1[style=invis,shape=point];
C1 -> D1[style=invis];
}
{rank=same;
C -> D[dir=back];
}
C1 -> C;
}
#step 3
digraph list{
{rank=same;
A1[style=invis,shape=point];
C1[style=invis,shape=point];
D1[style=invis,shape=point];
A1 -> C1 -> D1[style=invis];
}
{rank=same;
A -> C[dir=back];
C -> D[dir=back];
}
A1 -> A;
}
#step 4
digraph list{
{rank=same;
A1[style=invis,shape=point];
B1[style=invis,shape=point];
C1[style=invis,shape=point];
D1[style=invis,shape=point];
A1 -> B1 -> C1 -> D1[style=invis];
}
{rank=same;
A -> B[dir=back];
B -> C[dir=back];
C -> D[dir=back];
}
B1 -> B;
}
#step 5
digraph list{
{rank=same;
A1[style=invis,shape=point];
B1[style=invis,shape=point];
C1[style=invis,shape=point];
D1[style=invis,shape=point];
E1[style=invis,shape=point];
A1 -> B1 -> C1 -> D1 -> E1[style=invis];
}
{rank=same;
A -> B[dir=back];
B -> C[dir=back];
C -> D[dir=back];
D -> E[dir=back];
}
E1 -> E;
}
#step 6
digraph list{
{rank=same;
A1[style=invis,shape=point];
B1[style=invis,shape=point];
C1[style=invis,shape=point];
F1[style=invis,shape=point];
D1[style=invis,shape=point];
E1[style=invis,shape=point];
A1 -> B1 -> C1 -> F1 -> D1 -> E1[style=invis];
}
{rank=same;
A -> B[dir=back];
B -> F[dir=back];
F -> C[dir=back];
C -> D[dir=back];
D -> E[dir=back];
}
F1 -> F;
}
#step 1
digraph tree{
D;
}
#step 2
digraph tree{
D -> C;
D -> D1[style=invis]; D1[style=invis];
}
#step 3
digraph tree{
D -> C;
D -> D1[style=invis]; D1[style=invis];
C -> A;
C -> C1[style=invis]; C1[style=invis];
}
#step 3, rotation
digraph tree{
C -> A;
C -> D;
}
#step 4
digraph tree{
C -> A;
C -> D;
A -> A0[style=invis]; A0[style=invis];
A -> B;
}
#step 5
digraph tree{
C -> A;
C -> CAD0[style=invis]; CAD0[style=invis];
C -> D;
A -> A0[style=invis]; A0[style=invis];
A -> B;
D -> D0[style=invis]; D0[style=invis];
D -> E;
}
#step 6
digraph tree{
C -> A;
C -> CAD0[style=invis]; CAD0[style=invis];
C -> D;
A -> A0[style=invis]; A0[style=invis];
A -> B;
D -> D0[style=invis]; D0[style=invis];
D -> E;
B -> B0[style=invis]; B0[style=invis];
B -> F;
}
#step 6, rotation
digraph tree{
C -> B;
C -> CAD0[style=invis]; CAD0[style=invis];
C -> D;
B -> A;
D -> D0[style=invis]; D0[style=invis];
D -> E;
B -> F;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment