#include <rm3_orth_plan_undi_graph.h>
Three different kinds of 'bend_constraint' are possible for an gdtedge:
Definition at line 157 of file rm3_orth_plan_undi_graph.h.
orth_plan_undi_graph::orth_plan_undi_graph | ( | ) |
Empty constructor.
orth_plan_undi_graph::~orth_plan_undi_graph | ( | ) |
Destructor.
orth_plan_undi_graph::orth_plan_undi_graph | ( | const undi_graph & | ug, | |
algorithm_type | alg = PLAN_ORTH_OPTIMAL , |
|||
bool | err_mess = true | |||
) |
Constructor from undi_graph applying algorithm_type. If err_mess = true an error message is produced when a layout is not possible
orth_plan_undi_graph::orth_plan_undi_graph | ( | const plan_undi_graph & | pug, | |
algorithm_type | alg = PLAN_ORTH_OPTIMAL , |
|||
bool | err_mess = true | |||
) |
Constructor from plan_undi_graph applying algorithm_type. If err_mess = true an error message is produced when a layout is not possible
orth_plan_undi_graph::orth_plan_undi_graph | ( | const plan_undi_graph & | pug, | |
face | ef, | |||
algorithm_type | alg = PLAN_ORTH_OPTIMAL , |
|||
bool | err_mess = true | |||
) |
Constructor from plan_undi_graph, applying algorithm_type, with face as external face. If err_mess = true an error message is produced when a layout is not possible
orth_plan_undi_graph::orth_plan_undi_graph | ( | const upwa_plan_undi_graph & | upug, | |
algorithm_type | alg = PLAN_ORTH_UPWA_STRAIGHT_MIDDLE | |||
) |
Constructor from upwa_plan_undi_graph. WARNING: constraints are not handled
orth_plan_undi_graph::orth_plan_undi_graph | ( | const orth_plan_undi_graph & | opug | ) |
Copy constructor.
gdtedge orth_plan_undi_graph::split_face_with_shaped_edge | ( | gdtnode | v, | |
gdtedge | ev, | |||
angle_type | av, | |||
gdtnode | w, | |||
gdtedge | ew, | |||
angle_type | aw, | |||
std::string | bends_sequence, | |||
int | new_id = AUTO_ID | |||
) | [protected] |
void orth_plan_undi_graph::split_list_of_edges_on_side | ( | gdt::gdtlist< gdtedge > & | L, | |
gdtnode | v, | |||
gdt::gdtlist< gdtedge > & | L_left, | |||
gdtedge & | ec, | |||
gdt::gdtlist< gdtedge > & | L_right | |||
) | [protected] |
void orth_plan_undi_graph::merge_edges_on_same_side | ( | gdtnode | v | ) | [protected] |
orth_plan_undi_graph& orth_plan_undi_graph::operator= | ( | const undi_graph & | ug | ) |
Equality operator from the undi_graph class.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
orth_plan_undi_graph& orth_plan_undi_graph::operator= | ( | const plan_undi_graph & | pug | ) |
Equality operator from the plan_undi_graph class.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
orth_plan_undi_graph& orth_plan_undi_graph::operator= | ( | const upwa_plan_undi_graph & | upug | ) |
Equality operator from the upwa_plan_undi_graph class.
orth_plan_undi_graph& orth_plan_undi_graph::operator= | ( | const orth_plan_undi_graph & | opug | ) |
Copy equality operator.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::local_get | ( | face & | p1, | |
algorithm_type & | p2, | |||
gdt::gdtedge_map< bend_constraint > & | p3, | |||
gdt::gdtmap< border_step, struct_orth_border_step_info > *& | p4, | |||
bool & | p5, | |||
bool & | p6, | |||
border_step & | p7, | |||
int | p8 | |||
) |
Get all private variables.
border_step orth_plan_undi_graph::get_ref_border_step | ( | ) | const |
Return the reference_border_step. orth_plan_undi_graphs do not have a preferred upward direction to see them straight up. You can rotate them as you like. dime_orth_plan_undi_graphs, instead, do handle a preferred direction: this information in the dime_orth_plan_undi_graph is represented by means of a pair of values: a reference_border_step, and a heading (north, south, east, or west). The reference_border_step, though, is a member of the orth_plan_undi_graph for updating reasons.
gdt::gdtlist<bend_type> orth_plan_undi_graph::bends_of_border_step | ( | border_step | s | ) | const |
Return the sequence of bends of border_step.
angle_type orth_plan_undi_graph::angle_of_border_step | ( | border_step | s | ) | const |
Return the angle formed between the border_step and its successive. (Remember that border_steps are in clockwise order inside the face).
int orth_plan_undi_graph::thickness_of_border_step | ( | border_step | s | ) | const |
Return the thickness of the border_step s, that is the number of border_steps compressed in s. To represent overlapped edges, some information is needed to know
int orth_plan_undi_graph::pin_number_of_border_step | ( | border_step | s | ) | const |
Return the pin_numbero of the border_step s.
The meaning of the pin_number varies depending on the value of the thickness of the border_step:
Return the sum of the thickness of the two border steps of e minus 1.
Return the thickness of border_step of gdtedge e with start gdtnode v.
Return the thickness of border_step of gdtedge e with start gdtnode the opposite(v,e).
int orth_plan_undi_graph::number_of_bends | ( | ) | const |
Return the total number of bends of the orthogonal representation.
Return the number of bends on gdtedge.
int orth_plan_undi_graph::number_of_bends | ( | gdt::gdtlist< gdtedge > | ls_edge | ) | const |
Return the number of bends on a list of edges.
int orth_plan_undi_graph::number_of_bends | ( | border_step | s | ) | const |
Return the number of border_step.
int orth_plan_undi_graph::number_of_left_bends | ( | border_step | s | ) | const |
Return the number of left-turns of border_step.
int orth_plan_undi_graph::number_of_right_bends | ( | border_step | s | ) | const |
Return the number of right-turns of border_step.
int orth_plan_undi_graph::max_number_of_bends_on_edge | ( | ) | const |
Return the maximum number of bends on an gdtedge.
Return the number of left-turns wolking on border of face.
Return the number of right-turns wolking on border of face.
int orth_plan_undi_graph::number_of_left_turns_along_border | ( | border_step | sv, | |
border_step | sw | |||
) | const |
Return the number of left-turns wolking from a border_step to another of the same face.
int orth_plan_undi_graph::number_of_right_turns_along_border | ( | border_step | sv, | |
border_step | sw | |||
) | const |
Return the number of right-turns wolking from a border_step to another of the same face.
double orth_plan_undi_graph::mean_number_of_bends_on_edge | ( | ) | const |
Return the mean number of bends for gdtedge.
double orth_plan_undi_graph::bend_standard_deviation | ( | ) | const |
Return the bends standard deviation.
face orth_plan_undi_graph::external_face | ( | ) | const |
Return the external face.
bend_constraint orth_plan_undi_graph::get_constraint_on_bends_of_edge | ( | gdtedge | e | ) | const |
Return the bend-constraint type on gdtedge.
algorithm_type orth_plan_undi_graph::get_layout_algorithm | ( | ) | const |
Return the current layout algorithm.
bool orth_plan_undi_graph::get_local_consistency_is_suspended | ( | ) | const |
Return true if the checking on local consistency is suspended.
bool orth_plan_undi_graph::get_diagnostic_printouts_are_enabled | ( | ) | const |
Return true if the diagnostic_printouts flag is enabled.
bool orth_plan_undi_graph::border_is_closed | ( | face | f | ) | const |
Return true if the border of face is really closed.
bool orth_plan_undi_graph::border_step_turns_left | ( | border_step | s | ) | const |
Return true if border_step turns left with respect its previous border_step.
bool orth_plan_undi_graph::border_step_turns_right | ( | border_step | s | ) | const |
Return true if border_step turns right with respect its previous border_step.
bool orth_plan_undi_graph::border_step_turns_back | ( | border_step | s | ) | const |
Return true if border_step turns back with respect its previous border_step.
bool orth_plan_undi_graph::border_step_goes_straight | ( | border_step | s | ) | const |
Return true if border_step goes straight with respect its previous border_step.
gdt::list_item orth_plan_undi_graph::find_border_step_turning_left | ( | gdt::gdtlist< border_step > & | bsl, | |
gdt::list_item | start_pos = NULL | |||
) | const |
Find a border_step turning left in gdt::gdtlist<border_step>, starting from position start_pos.
gdt::list_item orth_plan_undi_graph::find_border_step_turning_right | ( | gdt::gdtlist< border_step > & | bs, | |
gdt::list_item | start_pos = NULL | |||
) | const |
Find a border_step turning right in gdt::gdtlist<border_step>, starting from position start_pos.
gdt::list_item orth_plan_undi_graph::find_border_step_turning_left_or_turning_back | ( | gdt::gdtlist< border_step > & | bs, | |
gdt::list_item | start_pos = NULL | |||
) | const |
Find a border_step turning right or left in gdt::gdtlist<border_step>, starting from position start_pos.
int orth_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<border_step> orth_plan_undi_graph::turning_border_steps_of_face | ( | face | f | ) | const |
Return the list of border_steps that do not go straight on border of face.
void orth_plan_undi_graph::edges_on_each_side_of_node | ( | gdtnode | v, | |
gdt::gdtlist< gdtedge > & | L1, | |||
gdt::gdtlist< gdtedge > & | L2, | |||
gdt::gdtlist< gdtedge > & | L3, | |||
gdt::gdtlist< gdtedge > & | L4 | |||
) | const |
Return all edges on each side of the gdtnode v in counterclockwise order.
bool orth_plan_undi_graph::face_is_regular | ( | face | f, | |
border_step & | r1, | |||
border_step & | r2 | |||
) | const |
Return true when the face is regular, that is when the face has not a pair of kitty corners (see definition of turn-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. PRECONDITIONS: face must be linearized, that is it has not bends.
bool orth_plan_undi_graph::is_orthogonal | ( | ) |
Return true if the graph is really orthogonal This method can be used to check the consistency of the data structures
bool orth_plan_undi_graph::node_is_flat | ( | gdtnode | v | ) | const |
return true if the gdtnode has degree two and two angles of 180 degree
Split gdtedge by creating a new gdtnode on it, and returning it. PRECONDITIONS: gdtedge must have no bends. NOTICE : this method is implemented to correctly work for 4-planar graphs only.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
Split gdtedge e by creating a new gdtnode on it, and returning it. The new gdtnode is added on segment number seg_num starting from gdtnode v. PRECONDITIONS: seg_num must be not greater than the number of segments of gdtedge e; also, the segment must have sufficient space to host a new gdtnode;
Reimplemented in dime_orth_plan_undi_graph.
gdtnode orth_plan_undi_graph::new_node | ( | gdtnode | v, | |
gdtedge | e, | |||
angle_type | alpha, | |||
int | new_node_id = AUTO_ID , |
|||
int | new_edge_id = AUTO_ID | |||
) |
Create and return a new gdtnode, by attaching it to the gdtnode "v". A new straight gdtedge is created to connect the new gdtnode and "v". Such gdtedge is inserted after the gdtedge "e" in counterclockwise order around "v", with an angle equal to "alpha". "new_node_id" and "new_edge_id" specify the identifiers of the new gdtnode and the new gdtedge, respectively. PRECONDITIONS: "alpha" should be in {_090, _180, _270, _360}, and it should be possible to add the new gdtnode without generating _000 angle.
Split face f by adding a new gdtedge between v and w. The new gdtedge is returned. PRECONDITIONS: v and w are vertices of the border of f and v != w NOTICE : When v (or w) is the start-gdtnode of a bridge, the new gdtedge is inserted on the right of that bridge, moving on the bridge from v (w) to its opposite. This method is implemented to correctly wotk for 4-planar graphs only.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
gdtedge orth_plan_undi_graph::new_edge | ( | gdtnode | v, | |
gdtedge | ev, | |||
gdtnode | w, | |||
gdtedge | ew, | |||
int | new_id = AUTO_ID | |||
) |
Split a face by adding a new gdtedge between v and w, and put it after ev around v and after ew around w. The new gdtedge is returned. PRECONDITIONS: v and w are vertices of the border of a same face and operation can be executed preserving the planarity NOTICE : this method is implemented to correctly wotk for 4-planar graphs only.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
Delete the edges incident on "v" and merge them in a single gdtedge, which is returned. PRECONDITIONS: "v" has degree two.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
Replace gdtnode v with bend. PRECONDITIONS: v has degree 2
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::replace_bend_with_node | ( | gdtedge | e, | |
gdtnode | v, | |||
int | pos, | |||
gdt::gdtlist< gdtnode > & | N, | |||
gdt::gdtlist< gdtedge > & | E | |||
) |
Replace the bend at position pos along gdtedge e, starting from v, with a dummy gdtnode. Dummy gdtnode is stored in N, and the two dummy edges derived by splitting are stored in E.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::replace_bends_with_nodes | ( | gdtedge | e, | |
gdt::gdtlist< gdtnode > & | N, | |||
gdt::gdtlist< gdtedge > & | E | |||
) |
Replace all bends of gdtedge e with dummy nodes. Dummy nodes are stored in N and dummy edges are stored in E.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::replace_bends_with_nodes | ( | face | f, | |
gdt::gdtlist< gdtnode > & | N, | |||
gdt::gdtlist< gdtedge > & | E | |||
) |
Replace all bends of edges of face f with dummy nodes. Dummy nodes are stored in N and dummy edges are stored in E.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::replace_bends_with_nodes | ( | gdt::gdtlist< gdtnode > & | N, | |
gdt::gdtlist< gdtedge > & | E | |||
) |
Replace all bends of graph with dummy nodes. Dummy nodes are stored in N and dummy edges are stored in E.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::decompose_all_faces_into_smaller_rectangular_faces | ( | gdt::gdtlist< gdtnode > & | N, | |
gdt::gdtlist< gdtedge > & | E | |||
) |
Execute a rectangularization of graph and store all dummy nodes in N and all dummy edges in E. Preconditions : the graph must be 4-planar
int orth_plan_undi_graph::regularize_all_faces | ( | gdt::gdtlist< gdtnode > & | N, | |
gdt::gdtlist< gdtedge > & | E, | |||
algorithm_type | alg | |||
) |
Execute a regularization heuristic of graph and store all dummy nodes in N and all dummy edges in E. The heuristic is chosen according to the given alg. Return the number of irregular faces. Preconditions : the graph must be 4-planar.
void orth_plan_undi_graph::clear | ( | ) |
Delete all nodes and edges.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::steal_from | ( | undi_graph & | ug, | |
algorithm_type | alg = PLAN_ORTH_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 orth_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 orth_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 orth_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 orth_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 orth_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 orth_plan_undi_graph::mirror | ( | orth_plan_undi_graph & | opug | ) |
Copy all private variables of orth_plan_undi_graph in *this.
void orth_plan_undi_graph::forget | ( | ) |
Cut all private variables in *this.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::set_external_face | ( | face | ef | ) |
Set the external face with face. NOTICE: if local consistency is not suspended, the current layout algorithm is executed automatically
void orth_plan_undi_graph::set_reference_border_step | ( | border_step | s | ) |
Make "s" as the new reference border step
Make the border step of gdtedge "e" with start gdtnode "v" as the new reference border step
void orth_plan_undi_graph::set_layout_algorithm | ( | algorithm_type | la | ) |
Set the layout algorithm with algorithm_type. NOTICE: if local consistency is not suspended, the set layout algorithm is automatically applied
int orth_plan_undi_graph::apply_layout_algorithm | ( | bool | err_mess = true |
) |
Apply the current layout algorithm, and return the flow-cost if the algorithm applied is PLAN_ORTH_OPTIMAL or PLAN_ORTH_SLOW, and zero otherwise. If err_mess = true return an error message when a layout is not possible
void orth_plan_undi_graph::suspend_local_consistency | ( | ) |
Suspend local consistency on data structure.
void orth_plan_undi_graph::restore_local_consistency | ( | ) |
Restore local consistency on data structure.
void orth_plan_undi_graph::enable_diagnostic_printouts | ( | ) |
Enable diagnostic printouts.
void orth_plan_undi_graph::disable_diagnostic_printouts | ( | ) |
Disable diagnostic printouts.
void orth_plan_undi_graph::print | ( | print_mode | mode = BY_FACES , |
|
std::ostream & | os = std::cout | |||
) | const |
Print the graph on ostream os; print_mode can be BY_NODES, BY_EDGE, BY_FACES, COMPLETE.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::print | ( | gdtnode | v, | |
std::ostream & | os = std::cout | |||
) | const |
Print gdtnode on ostream os.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::print | ( | gdtedge | e, | |
std::ostream & | os = std::cout | |||
) | const |
Print gdtedge on ostream os.
Reimplemented from plan_undi_graph.
void orth_plan_undi_graph::print | ( | face | f, | |
std::ostream & | os = std::cout | |||
) | const |
Print face on ostream os.
Reimplemented from plan_undi_graph.
Reimplemented in dime_orth_plan_undi_graph.
void orth_plan_undi_graph::print | ( | constraint | c, | |
std::ostream & | os = std::cout | |||
) | const |
Print constraint on ostream os.
Reimplemented from plan_undi_graph.
void orth_plan_undi_graph::print | ( | separation_pair | sp, | |
std::ostream & | os = std::cout | |||
) | const |
Print the separation pair on ostream os.
Reimplemented from plan_undi_graph.
friend class dime_orth_plan_undi_graph [friend] |
Definition at line 161 of file rm3_orth_plan_undi_graph.h.