An 'upwa_plan_undi_graph' represents a plan_undi_graph with all directed edges
and an associated upward representation. Such a representation is given by using two
linear (left->right) lists of in/out-edges around each node.
A necessary condition to make an upwa_plan_undi_graph object is that the graph used
to initialize it has a candidate planar embedding (that is all in/out-edges around
each node are consecutive).
When this condition is verified an upwa_plan_undi_graph upug is built, possibly adding
a minimum number of switches (sources and sinks) on some edges. In this case, these
dummy nodes (that we call "bends") are atumatically removed when passing upug to a
draw_undi_graph object; drawings so obtained are called "quasi-upward drawings".
An upward drawing is a quasi-upward drawing without bends.
Observe that this class is very similar to the orth_plan_undi one.
Three different kinds of 'bend_constraint' are possible for an edge:
Two different algorithms for producing a quasi-upward drawing upug:
- ANY = any number of bends on edge;
- NONE = no bends on edge;
- MINIMAL = a 'minimal' number of bends on edge (default).
Both algorithms handle the bend constraints on edges.
- PLAN_UPWARD_OPTIMAL: finds an upug with the minimum number of bends,
preserving the embedding. (Polynomial)
- PLAN_UPWARD_SLOW : finds an upug with the minimum number of bends,
searching over all possible planar embeddings of
the graphs. It is an exponential-time algorithm based
on branch and bound techniques, and currently works
for biconnected graphs only.
Page generated from source code by SCP Source Code Publisher.
SCP © INTEGRA Sistemi, www.IntegraSistemi.com