Graph Drawing Toolkit
#include <rm3_upwa_plan_undi_graph.h>
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 gdtedge:
Definition at line 98 of file rm3_upwa_plan_undi_graph.h.
| upwa_plan_undi_graph::upwa_plan_undi_graph | ( | ) |
Empty constructor.
| upwa_plan_undi_graph::~upwa_plan_undi_graph | ( | ) |
Destructor.
| upwa_plan_undi_graph::upwa_plan_undi_graph | ( | const undi_graph & | ug, | |
| algorithm_type | alg = PLAN_UPWARD_OPTIMAL, |
|||
| bool | err_mess = true | |||
| ) |
Constructor from undi_graph class, applying algorithm type. If err_mess = true an error message is produced when a layout is not possible.
PRECONDITIONS: graph must be directed and candidate
| upwa_plan_undi_graph::upwa_plan_undi_graph | ( | const plan_undi_graph & | pug, | |
| algorithm_type | alg = PLAN_UPWARD_OPTIMAL, |
|||
| bool | err_mess = true | |||
| ) |
Constructor from plan_undi_graph class, applying algorithm type. If err_mess = true an error message is produced when a layout is not possible.
PRECONDITIONS: graph must be directed and candidate
| upwa_plan_undi_graph::upwa_plan_undi_graph | ( | const plan_undi_graph & | pug, | |
| face | ef, | |||
| algorithm_type | alg = PLAN_UPWARD_OPTIMAL, |
|||
| bool | err_mess = true | |||
| ) |
Constructor from plan_undi_graph class, applying algorithm_type, with face as external face. If err_mess = true an error message is produced when a layout is not possible.
PRECONDITIONS: graph must be directed and candidate
| upwa_plan_undi_graph::upwa_plan_undi_graph | ( | const plan_undi_graph & | pug, | |
| gdt::gdtnode_array< gdtedge > & | first_edge | |||
| ) |
Constructor from plan_undi_graph class, applying a predefined shape. Shape is specified by using the gdt::gdtnode_array 'first_edge'. Namely, first_edge[v] (where v is a gdtnode of pug) indicate the left-most gdtedge incident v in the upward representation (candidate lists). Obiouvsly, this gdtedge is considered for source and sink nodes only.
| upwa_plan_undi_graph::upwa_plan_undi_graph | ( | const upwa_plan_undi_graph & | upug | ) |
Copy constructor.
| upwa_plan_undi_graph& upwa_plan_undi_graph::operator= | ( | const undi_graph & | ug | ) |
Equality operator from undi_graph class.
PRECONDITIONS: graph must be directed and candidate
Reimplemented from plan_undi_graph.
| upwa_plan_undi_graph& upwa_plan_undi_graph::operator= | ( | const plan_undi_graph & | pug | ) |
Equality operator from plan_undi_graph_class.
PRECONDITIONS: graph must be directed and candidate
Reimplemented from plan_undi_graph.
| upwa_plan_undi_graph& upwa_plan_undi_graph::operator= | ( | const upwa_plan_undi_graph & | upug | ) |
Copy equality operator.
| void upwa_plan_undi_graph::local_get | ( | face & | p1, | |
| algorithm_type & | p2, | |||
| gdt::gdtedge_map< bend_constraint > & | p3, | |||
| gdt::gdtnode_map< struct_upwa_node_info > *& | p4, | |||
| int & | p5 | |||
| ) |
Get all local variables.
| bool upwa_plan_undi_graph::get_in_cand_edges_are_ordered | ( | gdtnode | ) | const |
| bool upwa_plan_undi_graph::get_out_cand_edges_are_ordered | ( | gdtnode | ) | const |
Return the first in-gdtedge (left->right) of the gdtnode v.
Return the first out_edge (left->right) of the gdtnode v.
Return the successive adjacent gdtedge of e in v (left->right).
Return the previous adjacent gdtedge of e in v (left-right).
| face upwa_plan_undi_graph::external_face | ( | ) | const |
Return the current external face of the graph.
| algorithm_type upwa_plan_undi_graph::get_layout_algorithm | ( | ) | const |
Return the current layout algorithm.
| bend_constraint upwa_plan_undi_graph::get_constraint_on_bends_of_edge | ( | gdtedge | e | ) | const |
Return the current bend constraint on the gdtedge e.
| bool upwa_plan_undi_graph::is_source | ( | gdtnode | v | ) | const |
Return true if v is a source.
Reimplemented from undi_graph.
| bool upwa_plan_undi_graph::is_target | ( | gdtnode | v | ) | const |
Return true if v is a target.
Reimplemented from undi_graph.
| bool upwa_plan_undi_graph::is_extremal | ( | gdtnode | v | ) | const |
Return true if v is either a source or a target.
Reimplemented from undi_graph.
| bool upwa_plan_undi_graph::is_internal | ( | gdtnode | v | ) | const |
return true if v is neither a source nor a target
Reimplemented from undi_graph.
Return true if the gdtedge e and adj_cyclic_succ(e,v) have the same direction.
PRECONDITIONS: e must be adjacent to v.
Reimplemented from undi_graph.
Return true if the gdtedge e and adj_cyclic_succ(e,v) have opposite direction.
PRECONDITIONS: e must be adjacent to v.
Reimplemented from undi_graph.
Return true if the gdtnode v is source into the face f.
Return true if the gdtnode v is target into the face f.
Return true if the gdtnode v is either source or target (extremal) into the face f (only for biconnected).
Return true if the gdtnode v is neither source nor target (internal) into the face f (only for biconnected).
Return true if there is a big angle (>180 deg) on v into f (only for biconnected graph).
Return true if there is a big angle (>180 deg) on v between e and the succ_adj_edge (e,v).
| gdt::gdtlist<gdtedge> upwa_plan_undi_graph::in_cand_edges | ( | gdtnode | v | ) |
Return the left->right list of the edges entering gdtnode (in-edges candidate list).
| gdt::gdtlist<gdtedge> upwa_plan_undi_graph::out_cand_edges | ( | gdtnode | v | ) |
Return the left->right list of the edges leaving gdtnode (out-edges candidate list).
| int upwa_plan_undi_graph::number_of_extremals | ( | ) | const |
Return the total number of extremal nodes.
Reimplemented from undi_graph.
Return the number of extremal nodes into the face f. Observe that if the graph is not biconnected a gdtnode might be counted more than one time as extremal in f.
| int upwa_plan_undi_graph::number_of_bends | ( | ) | const |
Return the total number of dummy nodes added.
| int upwa_plan_undi_graph::max_bends_on_edge | ( | ) | const |
Return the maximum number of dummy nodes added on a single gdtedge.
Return the capacity of the face, defined as follow: capacity(f) = number_of_extremals(f)/2 - 1 if f is an internal face; capacity(f) = number_of_extremals(f)/2 + 1 if f is the external face.
| int upwa_plan_undi_graph::cost_of_last_algorithm | ( | ) | const |
Return the flow cost in the last computation apply_layout_algorithm. (INFINITE when no solution is found)
| gdt::gdtlist<gdtnode> upwa_plan_undi_graph::extremals | ( | face | f | ) | const |
Return all the extremal nodes for the face f. Observe that if the graph is not biconnected a gdtnode is might be counted more than one time as extremal in f.
| void upwa_plan_undi_graph::extremals | ( | face | f, | |
| gdt::gdtlist< gdtnode > & | ext, | |||
| gdt::gdtmap< gdt::list_item, bool > & | is_big | |||
| ) |
Return all the extremals nodes for the face f and the associated mapping of big (true) or small (false) angles in f.
| gdt::gdtlist<gdtnode> upwa_plan_undi_graph::big_angles | ( | face | f | ) |
Return the list of the nodes having a big angle into the face f.
| bool upwa_plan_undi_graph::face_is_regular | ( | face | f, | |
| border_step & | r1, | |||
| border_step & | r2 | |||
| ) |
Return true when the face is regular, that is when the face has not a pair of kitty corners (see definition of switch-regularity). If the face f is not regular a pair of border steps r1 and r2 is returned, such that their stop nodes are a pair of kitty corners.
| angle_type upwa_plan_undi_graph::angle_of_border_step | ( | border_step | bs | ) |
Return the angle formed by border step bs with the successive border step, according to the following correspondence:
_090: denote a small angle (less than 90 degrees) _180: denote a flat angle (in the range (90,180) degrees) _270: denote a big (large) angle when the stop of bs is not a vertex of degree one (in the range (180,60) degrees) _360: denote a big (large) angle when the stop of bs is a vertex of degree one (exactly 360 degrees)
| face upwa_plan_undi_graph::find_external_face | ( | ) |
Scan all faces and return the one that has two big angles more than the number of small angles; Return NULL_FACE is such a face is not found
| void upwa_plan_undi_graph::clear | ( | ) |
Delete all nodes and edges.
Reimplemented from plan_undi_graph.
| void upwa_plan_undi_graph::steal_from | ( | undi_graph & | ug, | |
| algorithm_type | alg = PLAN_UPWARD_OPTIMAL, |
|||
| bool | err_mess = true | |||
| ) |
Make *this with the undi_graph ug internal variables and cut these variables from ug. This method is used to make an undi_graph as an upwa_plan_undi_graph, manteining the same internal variables. If err_mess = true return an error message when a layout is not possible WARNING: ug has an empty body after this method is applied.
PRECONDITIONS: ug must be connected and with at least one gdtnode.
| void upwa_plan_undi_graph::steal_from | ( | plan_undi_graph & | pug, | |
| algorithm_type | alg = PLAN_ORTH_OPTIMAL, |
|||
| bool | err_mess = true | |||
| ) |
Make *this with the plan_undi_graph pug internal variables and cut these variables from pug. This method is used to make a plan_undi_graph as an upwa_plan_undi_graph, manteining the same internal variables. If err_mess = true return an error message when a layout is not possible.
WARNING: pug has an empty body after this method is applied
| void upwa_plan_undi_graph::steal_from | ( | plan_undi_graph & | pug, | |
| face | ef, | |||
| algorithm_type | alg = PLAN_ORTH_OPTIMAL, |
|||
| bool | err_mess = true | |||
| ) |
Make *this with the plan_undi_graph pug internal variables and setting external face before applying the selected layout algorithm, and cut these variables from pug. This method is used to make a plan_undi_graph as an upwa_plan_undi_graph, manteining the same internal variables. If err_mess = true return an error message when a layout is not possible.
WARNING: pug has an empty body after this method is applied
| void upwa_plan_undi_graph::mirror | ( | upwa_plan_undi_graph & | upug | ) |
Copy all private variables of upwa_plan_undi_graph in *this.
| void upwa_plan_undi_graph::forget | ( | ) |
Cut all private variables in *this.
Reimplemented from plan_undi_graph.
| void upwa_plan_undi_graph::set_external_face | ( | face | ef | ) |
Set face as external face.
| void upwa_plan_undi_graph::set_layout_algorithm | ( | algorithm_type | alg | ) |
Set algorithm_type as the layout algorithm.
| gdt::gdtlist<gdtedge> upwa_plan_undi_graph::make_st | ( | gdtnode & | s, | |
| gdtnode & | t | |||
| ) |
Add dummy edges and nodes (s and t) to make the graph as an st-graph. The augmentation performed is a standard technique. Return the list of dummy edges and the dummy source s and target t.
| gdt::gdtlist<gdtedge> upwa_plan_undi_graph::make_st_with_regularity | ( | gdtnode & | s, | |
| gdtnode & | t | |||
| ) |
Add dummy edges and nodes (s and t) to make the graph as an st-graph. The augmentation performed uses a switch-regularity technique. Return the list of dummy edges and the dummy source s and target t.
| int upwa_plan_undi_graph::apply_layout_algorithm | ( | bool | err_mess = true |
) |
Compute a quasi-upward representation, by applying the current layout algorithm. If err_mess = true return an error message if a layout is true.
| bool upwa_plan_undi_graph::regularize_face | ( | face | f, | |
| gdt::gdtlist< gdtedge > & | dummy_edges | |||
| ) |
Add a number of dummy edges to f in order to make the face regular; return true if the face was not regular. Store in dummy_edges the edges added
| int upwa_plan_undi_graph::regularize_all_faces | ( | gdt::gdtlist< gdtedge > & | dummy_edges | ) |
Apply the method regularize_face to all faces of the graph Store in dummy_edges the edges added. Return the number of irregular faces found
| void upwa_plan_undi_graph::print | ( | print_mode | mode = BY_FACES, |
|
| bool | candidate = false, |
|||
| std::ostream & | os = std::cout | |||
| ) |
Print the graph on ostream os; print_mode can be BY_NODES, BY_EDGE, BY_FACES, COMPLETE. if candidate is true print the two linear candidate lists for each gdtnode
| void upwa_plan_undi_graph::print | ( | gdtnode | v, | |
| bool | candidate = false, |
|||
| std::ostream & | os = std::cout | |||
| ) |
Print gdtnode on ostream os if candidate is true print the two linear candidate lists of gdtnode.
| void upwa_plan_undi_graph::print | ( | gdtedge | e, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print gdtedge on ostream os.
Reimplemented from plan_undi_graph.
| void upwa_plan_undi_graph::print | ( | face | f, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print face on ostream os.
Reimplemented from plan_undi_graph.
| void upwa_plan_undi_graph::print | ( | separation_pair | sp, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print separation_pair on ostream os.
Reimplemented from plan_undi_graph.
| void upwa_plan_undi_graph::print | ( | constraint | c, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print constraint on ostream os.
Reimplemented from plan_undi_graph.
1.5.3