Graph Drawing Toolkit
#include <rm3_plan_undi_graph.h>
Definition at line 287 of file rm3_plan_undi_graph.h.
| plan_undi_graph::plan_undi_graph | ( | ) |
Empty constructor.
| plan_undi_graph::~plan_undi_graph | ( | ) |
Destructor.
| plan_undi_graph::plan_undi_graph | ( | const undi_graph & | ug, | |
| planarize_options | po = DO_NOT_PRESERVE_EMBEDDING, |
|||
| bool | err_mess = true | |||
| ) |
Constructor from the undi_graph class. If the embedding of the undi_graph is not planar a planarization step is executed in which dummy nodes may be added to replace crosses. Cross nodes are marked RM3_CROSS_ON_REAL_EDGE. Also, two possible planarization option can be specified: PRESERVE_EMBEDDING and DO_NOT_PRESERVE_EMBEDDING, in order to preserve (not preserve) the original embedding. Note that if DO_NOT_PRESERVE_EMBEDDING is specified, no dummy nodes are added when the graph is planar (that is it admits a planar embedding). If err_mess == true, an error message is returned when the embedding is not found.
PRECONDITIONS: undi_graph must be connected and with at least an gdtedge
| plan_undi_graph::plan_undi_graph | ( | const plan_undi_graph & | pug | ) |
Copy constructor.
Reimplemented from undi_graph.
| void plan_undi_graph::set_faces_shared_by_separation_pair | ( | const gdt::gdtlist< face > & | , | |
| separation_pair | ||||
| ) | [protected] |
| void plan_undi_graph::set_separation_pair_pole1 | ( | gdtnode | , | |
| separation_pair | ||||
| ) | [protected] |
| void plan_undi_graph::set_separation_pair_pole2 | ( | gdtnode | , | |
| separation_pair | ||||
| ) | [protected] |
| gdtnode plan_undi_graph::first_node_visited_while_moving_on_edge_around_face | ( | gdtedge | , | |
| face | ||||
| ) | const [protected] |
| gdtnode plan_undi_graph::second_node_visited_while_moving_on_edge_around_face | ( | gdtedge | , | |
| face | ||||
| ) | const [protected] |
| void plan_undi_graph::calculate_dual | ( | plan_undi_graph & | , | |
| gdt::gdtmap< face, gdtnode > & | ||||
| ) | [protected] |
| void plan_undi_graph::calculate_dual | ( | plan_undi_graph & | , | |
| gdtedge | , | |||
| gdt::gdtmap< face, gdtnode > & | ||||
| ) | [protected] |
| plan_undi_graph& plan_undi_graph::operator= | ( | const undi_graph & | ug | ) |
Equality operator from the undi_graph class. If the embedding of the undi_graph is not planar a planarization step is executed in which dummy nodes may be added to replace crosses. Cross nodes are marked RM3_CROSS_ON_REAL_EDGE. If the graph is planar (that is it admits a planar embedding) no dummy nodes are added.
PRECONDITIONS: undi_graph must be connected and with at least an gdtedge
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and upwa_plan_undi_graph.
| plan_undi_graph& plan_undi_graph::operator= | ( | const plan_undi_graph & | pug | ) |
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and upwa_plan_undi_graph.
| void plan_undi_graph::local_get | ( | gdt::gdtlist< face > *& | p1, | |
| gdt::gdtedge_map< struct_plan_edge_info > *& | p2, | |||
| gdt::gdtmap< int, face > *& | p3, | |||
| int & | p4, | |||
| int & | p5 | |||
| ) |
CATEGORY access Access operations. Get all private variables.
| int plan_undi_graph::generate_face_id | ( | ) |
Automatically generate a new compatible face identifier.
Return the idendifier of gdtnode.
Reimplemented from undi_graph.
Return the identifier of gdtedge.
Reimplemented from undi_graph.
| int plan_undi_graph::get_max_face_id | ( | ) | const [inline] |
Return the maximum value for a face-identifier.
Return the number of edges incident gdtnode.
Reimplemented from undi_graph.
Return either the number of edges or border_steps in face according to bool is false or true.
| int plan_undi_graph::number_of_faces | ( | ) | const |
Return the number of faces of the graph.
| int plan_undi_graph::number_of_cross_nodes | ( | ) | const |
Return the number of dummy nodes added as crosses. Return INFINITE, if the last planarization step failed
Return true if gdtnode belongs to face.
Return true if gdtedge belongs to gdtedge.
| gdtnode plan_undi_graph::separation_pair_pole1 | ( | separation_pair | sp | ) | const |
Return the pole1 of separation_pair.
| gdtnode plan_undi_graph::separation_pair_pole2 | ( | separation_pair | sp | ) | const |
Return the pole2 of separation_pair.
Return the face with identifier id if there exists, else return NULL_FACE.
| face plan_undi_graph::first_face | ( | ) | const |
Return the first face in the face-list of the graph.
| face plan_undi_graph::last_face | ( | ) | const |
Return the last face in the face-list of the graph.
Return the successive of face in the face-list of the graph.
Return the previous of face in the face-list of the graph.
Return the face adjacent to face by gdtedge.
Return the right face moving along gdtedge starting from gdtnode.
Return the left face moving along gdtedge starting from gdtnode.
| face plan_undi_graph::face_of_border_step | ( | border_step | s | ) | const |
Return the face of border_step.
| const gdt::gdtlist<face>& plan_undi_graph::all_faces | ( | ) | const |
Return a constant reference to the face-list of the graph.
Return the first gdtedge of the adj-edges list of gdtnode.
Reimplemented from undi_graph.
Return the first gdtedge of the adj-edges list of face.
Return the last gdtedge of the adj-edges list of gdtnode.
Reimplemented from undi_graph.
Return the last gdtedge of the adj-edges list of face.
Return the previous of gdtedge in the adj-edges list of gdtnode.
Reimplemented from undi_graph.
Return the previous of gdtedge in the adj-edges list of face.
Return the successive of gdtedge in the adj-edges list of gdtnode.
Reimplemented from undi_graph.
Return the successive of gdtedge in the adj-edges list of face.
Return the cyclic previous of gdtedge in the adj-edges list of gdtnode.
Reimplemented from undi_graph.
Return the cyclic previous of gdtedge in the adj-edges list of face.
Return the cyclic successive of gdtedge in the adj-edges list of gdtnode.
Reimplemented from undi_graph.
Return the cyclic successive of gdtedge in the adj-edges list of face.
| gdtedge plan_undi_graph::edge_of_border_step | ( | border_step | s | ) | const |
Return the gdtedge of border_step.
| gdt::gdtlist<gdtnode> plan_undi_graph::nodes_shared_by_faces | ( | face | f1, | |
| face | f2 | |||
| ) | const |
Return the list of nodes shared by the two faces.
| gdt::gdtlist<gdtnode> plan_undi_graph::adj_nodes | ( | face | f | ) | const |
Return the circular clockwise list of gdtnode belonging to face.
NOTE: a gdtnode might appear more than one time, walking on the face border
| gdt::gdtlist<gdtedge> plan_undi_graph::adj_edges | ( | gdtnode | v | ) | const |
Return the adj-edges list of gdtnode.
Reimplemented from undi_graph.
| gdt::gdtlist<gdtedge> plan_undi_graph::adj_edges | ( | face | f, | |
| gdtnode | v = NULL_NODE | |||
| ) | const |
Return the list of gdtedge of face if v == NULL_NODE, else return the edges adjacent to v on face.
PRECONDITIONS: if v!=NULL_NODE it must belong to face
| gdt::gdtlist<face> plan_undi_graph::adj_faces | ( | gdtnode | v | ) | const |
Return a list of all faces adjancet gdtnode.
| gdt::gdtlist<gdtedge> plan_undi_graph::edges_shared_by_faces | ( | face | f1, | |
| face | f2 | |||
| ) | const |
Return the list of edges shared by the two faces.
| gdt::gdtlist<gdtedge> plan_undi_graph::edges_entering_node_while_moving_around_face | ( | gdtnode | v, | |
| face | f | |||
| ) | const |
Return the list of edges entering gdtnode while moving around face.
| gdt::gdtlist<face> plan_undi_graph::faces_shared_by_separation_pair | ( | separation_pair | sp | ) | const |
Return the list of faces shared by separation_pair.
| gdt::list_item plan_undi_graph::pos_in_border | ( | gdtedge | e, | |
| face | f | |||
| ) | const |
Return the position-item of gdtedge into the gdtedge-list of face.
| gdt::list_item plan_undi_graph::pos_in_border | ( | border_step | s | ) | const |
Return the position-item of border_step into the border_step-list of face.
| gdtnode plan_undi_graph::start_of_border_step | ( | border_step | s | ) | const |
Return the start gdtnode of border_step.
| gdtnode plan_undi_graph::stop_of_border_step | ( | border_step | s | ) | const |
Return the stop gdtnode of border_step.
| border_step plan_undi_graph::first_border_step | ( | face | f | ) | const |
Return the first border_step of the border_step-list of face.
| border_step plan_undi_graph::last_border_step | ( | face | f | ) | const |
Return the last border_step of the border_step-list of face.
| border_step plan_undi_graph::succ_border_step | ( | border_step | s | ) | const |
Return the successive of border_step in the border_step-list of face of border_step.
| border_step plan_undi_graph::pred_border_step | ( | border_step | s | ) | const |
Return the previous of border_step in the border_step-list of face of border_step.
| border_step plan_undi_graph::cyclic_succ_border_step | ( | border_step | s | ) | const |
Return the cyclic successive of border_step in the border_step-list of face of border_step.
| border_step plan_undi_graph::cyclic_pred_border_step | ( | border_step | s | ) | const |
Return the cyclic previous of border_step in the border_step-list of face of border_step.
| border_step plan_undi_graph::opposite_border_step | ( | border_step | s | ) | const |
Return the opposite of border_step.
| border_step plan_undi_graph::border_step_moving_along_edge | ( | gdtedge | e, | |
| gdtnode | v | |||
| ) | const |
Return the border_step of gdtedge and having gdtnode as start_node.
| gdt::gdtlist<border_step> plan_undi_graph::adj_border_steps | ( | face | f | ) | const |
Return the border_step-list of face.
| gdt::gdtlist<border_step> plan_undi_graph::border_steps_starting_at_node | ( | gdtnode | v | ) | const |
Return the list of border_steps having gdtnode as start_node.
| gdt::gdtlist<border_step> plan_undi_graph::border_step_sequence | ( | border_step | s1, | |
| border_step | s2 | |||
| ) | const |
Return the border_step sequence between two border_steps.
| void plan_undi_graph::border_step_sequence | ( | border_step | s1, | |
| border_step | s2, | |||
| gdt::gdtlist< border_step > & | L | |||
| ) | const |
Put (appending) in L the border step sequence between two border_steps.
| gdt::gdtlist<border_step> plan_undi_graph::border_step_sequence | ( | gdtnode | v1, | |
| gdtnode | v2, | |||
| face | f | |||
| ) | const |
Return the shortest sequence of border_steps from v1 to v2 walking on border of face f.
| void plan_undi_graph::border_step_sequence | ( | gdtnode | v1, | |
| gdtnode | v2, | |||
| face | f, | |||
| gdt::gdtlist< border_step > & | L | |||
| ) | const |
Put (appending) in L the shortest sequence of border_steps from v1 to v2 walking on border of face f.
| separation_pair plan_undi_graph::find_separation_pair | ( | int | idv1, | |
| int | idv2, | |||
| const gdt::gdtlist< separation_pair > & | sp_list | |||
| ) | const |
Return the separation_pair sp in sp_list such that its poles have identifier idv1 and idv2 (or vice-versa), respectively. If it does not exist return NULL.
| gdt::gdtlist<separation_pair> plan_undi_graph::find_separation_pairs | ( | ) | const |
Return the list of all separation_pairs of the graph.
| void plan_undi_graph::make_dual | ( | plan_undi_graph & | dual_pug, | |
| gdt::gdtmap< face, gdtnode > & | primal_face_2_dual_node, | |||
| gdt::gdtmap< gdtnode, face > & | dual_node_2_primal_face, | |||
| gdt::gdtmap< gdtedge, gdtedge > & | primal_edge_2_dual_edge, | |||
| gdt::gdtmap< gdtedge, gdtedge > & | dual_edge_2_primal_edge | |||
| ) | const |
Make a dual plan_undi_graph 'dual_pug' and all mapping between face/gdtnode of primal and dual graphs.
NOTE: bridges in the primal graph should cause loops in the dual graph, but loops are not allowed for plan_undi_graphs. So, bridges don't have a corresponding gdtedge in the dual graph => several primal nodes may fall in the same dual face => the 'dual_face_2_primal_node' map could not be defined.
| void plan_undi_graph::compute_visibility_representation | ( | gdt::gdtnode_array< horizontal_segment > & | seg_node, | |
| gdt::gdtedge_array< vertical_segment > & | seg_edge, | |||
| face | ext_face, | |||
| bool | compacted = false, |
|||
| gdt::gdtedge_array< int > * | cp = NULL | |||
| ) |
Compute a visibility representation of the planar graph, having ext_face as external face. If compacted == true a min_cost_flow technique is used to reduce the total gdtedge length with respect to the gdtedge-cost array (*cp). If cp==NULL, all edges are considered with same cost. Visibility is returned as an array of horizontal_segment structures (for nodes), and an array of vertical_segment structures (for edges). These structures are defined as follows:
struct vertical_segment { int y_min; int y_max; int x; };
struct horizontal_segment { int x_min; int x_max; int y; };
PRECONDITIONS: graph must be biconnected.
| void plan_undi_graph::compute_visibility_representation | ( | gdt::gdtnode_array< horizontal_segment > & | seg_node, | |
| gdt::gdtedge_array< vertical_segment > & | seg_edge, | |||
| gdtedge | e_st, | |||
| bool | compacted = false, |
|||
| gdt::gdtedge_array< int > * | cp = NULL | |||
| ) |
Compute a visibility representation of the planar st-digraph, having gdtedge e_st=(s,t) on the external face. If compacted == true a min_cost_flow technique is used to reduce the total gdtedge length with respect to the gdtedge-cost array (*cp). If cp==NULL, all edges are considered with same cost. Visibility is returned as an array of horizontal_segment structures (for nodes), and an array of vertical_segment structures (for edges). These structures are defined as follows:
struct vertical_segment { int y_min; int y_max; int x; };
struct horizontal_segment { int x_min; int x_max; int y; };
PRECONDITION: graph must be biconnected and an e_st-digraph).
| face plan_undi_graph::corresponding_face | ( | face | f, | |
| const plan_undi_graph & | pug | |||
| ) |
Return the face with the same identifier as face in plan_undi_graph if there exists, else return NULL_NODE.
| border_step plan_undi_graph::corresponding_border_step | ( | border_step | s, | |
| const plan_undi_graph & | pug | |||
| ) |
Return the border_step such that gdtedge of border_step and start of border_step are corrispondent in plan_undi_graph.
Split gdtedge with a new gdtnode with identifier new_id, and return such gdtnode.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and split_component.
| gdtnode plan_undi_graph::new_node | ( | gdtnode | n, | |
| gdtedge | e, | |||
| int | node_id = AUTO_ID, |
|||
| int | edge_id = AUTO_ID | |||
| ) |
Attach a new gdtnode to gdtnode after gdtedge (in counterclocwise circular order) and return it. The new gdtnode and new gdtedge have identifier node_id and edge_id, respectively
Insert a gdtnode inside face and link it with all nodes of face.
Insert a new undirected gdtedge with source v1 and terget v2, and id new_id, by splitting face f, and return it. PRECONDITIONS: both v1 and v2 belongs to f.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and split_component.
| gdtedge plan_undi_graph::new_edge | ( | gdtnode | v1, | |
| gdtedge | e1, | |||
| gdtnode | v2, | |||
| gdtedge | e2, | |||
| int | new_id = AUTO_ID | |||
| ) |
Insert a new undirected gdtedge with source v1 and target v2, and identifier new_id, and return it. Also the gdtedge is inserted after e1 around v1 anf after e2 around v2.
PRECONDITIONS: v1 and v2 belongs to a same face and the operation can be executed preserving the planarity
Reimplemented in dime_orth_plan_undi_graph, and orth_plan_undi_graph.
Delete gdtedge and return the face obtained by merging the two previous faces of the deleted gdtedge.
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and split_component.
Delete gdtnode and return the face obtained by recursively merging the faces of the deleted edges.
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and split_component.
Delete the edges incident on "v" and merge them in a single gdtedge, which is returned.
PRECONDITIONS: "v" has degree two.
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, and orth_plan_undi_graph.
| void plan_undi_graph::clear | ( | ) |
Delete all nodes and edges.
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, split_component, skeleton, and upwa_plan_undi_graph.
| void plan_undi_graph::steal_from | ( | undi_graph & | ug, | |
| planarize_options | po = DO_NOT_PRESERVE_EMBEDDING, |
|||
| 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 a plan_undi_graph, manteining the same internal variables. If err_mess == true an error message is returned when the embedding is not found.
WARNING: ug has an empty body after this method is applied.
PRECONDITIONS: ug must be connected and with at least one gdtnode.
| void plan_undi_graph::mirror | ( | plan_undi_graph & | pug | ) |
Copy all private variables of plan_undi_graph in *this.
| void plan_undi_graph::forget | ( | ) |
Cut all private variables in *this.
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, split_component, and upwa_plan_undi_graph.
Assign identifier new_id to gdtnode.
PRECONDITIONS: there is not any gdtnode with new_id
Reimplemented from undi_graph.
Assign identifier new_id to gdtedge.
PRECONDITIONS: there is not any gdtedge with new_id
Reimplemented from undi_graph.
Assign identifier new_id to face.
PRECONDITIONS: there is not any face with new_id
| void plan_undi_graph::update_max_face_id | ( | ) |
Update the max_facee_id value to the current maximum face-identifier.
| face plan_undi_graph::plan_with_fixed_face_of_undi_graph | ( | undi_graph & | ug, | |
| gdtedge | start_edge, | |||
| gdtnode | start_node | |||
| ) |
Make the undi_graph part of the graph with ug and return the face that is the right face moving along gdtedge start_edge (i.e. the corresponding gdtedge in *this), starting from gdtnode start_node (i.e. the corresponding gdtnode in *this).
NOTE: start_edge and start_node are edges and nodes of ug, respectively; also, this method does not modify ug.
| void plan_undi_graph::make_embedding_as | ( | const plan_undi_graph & | pug | ) |
Make the current planar embedding equal to the planar embedding of pug.
Split the gdtnode v into two nodes with gdtedge lists. L1=(e_init,e_end) and L2=(cyclic_adj_succ(e_end,v), cyclic_adj_pred(e_init,v)), respectively, by inserting a new dummy gdtedge. Also, return the added gdtedge and mark it as RM3_ADDED_BY_EXPAND.
Reimplemented from undi_graph.
Merge the extremal nodes v1, v2 of gdtedge e into a gdtnode v and make adj-edges(v) = adj-edges(v1) U adj-edges(v2) \ {e: e=(v1,v2)}, then return v.
Reimplemented from undi_graph.
| gdt::gdtlist<gdtnode> plan_undi_graph::contract | ( | ) |
Contract all the edges marked by the expand method.
Reimplemented from undi_graph.
| gdt::gdtlist<gdtnode> plan_undi_graph::make_simple | ( | ) |
Make the graph simple, that is add a minimum number of dummy nodes to remove multiple edges. Return the list of dummy nodes. These nodes are also marked RM3_ADDED_BY_MAKE_SIMPLE
Reimplemented from undi_graph.
| void plan_undi_graph::make_upward_embedding | ( | face | ext_face, | |
| gdt::gdtnode_array< gdtedge > & | fe, | |||
| int | minimum_switches = 0 | |||
| ) |
Make an upward embedding of the graph. This is done by two steps:
| void plan_undi_graph::generate_biconnected | ( | int | n, | |
| double | prob_iv, | |||
| int | k = INFINITE, |
|||
| bool | multiple = true | |||
| ) |
Make the graph as a randomly generated biconnected graph with n nodes and manteining it k-planar. Also, if multiple = false, no multiple edges are generated. The basic technique used to generate graphs is the following:
| void 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, COMPLET.
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, and orth_plan_undi_graph.
| void plan_undi_graph::print | ( | gdtnode | v, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print gdtnode on ostream os.
Reimplemented from undi_graph.
Reimplemented in dime_orth_plan_undi_graph, and orth_plan_undi_graph.
| void plan_undi_graph::print | ( | gdtedge | e, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print gdtedge on ostream os.
Reimplemented from undi_graph.
Reimplemented in orth_plan_undi_graph, and upwa_plan_undi_graph.
| void plan_undi_graph::print | ( | face | f, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print face on ostream os.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and upwa_plan_undi_graph.
| void plan_undi_graph::print | ( | constraint | c, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print constraint on ostream os.
Reimplemented from undi_graph.
Reimplemented in orth_plan_undi_graph, and upwa_plan_undi_graph.
| void plan_undi_graph::print | ( | separation_pair | sp, | |
| std::ostream & | os = std::cout | |||
| ) | const |
Print separation_pair on ostream os.
Reimplemented in orth_plan_undi_graph, and upwa_plan_undi_graph.
| bool plan_undi_graph::internal_consistency_check | ( | ) | const |
Check consistency of the face/border_step internal structure.
NOTE: It assume that the underlaying undi_graph is consistent.
Reimplemented from undi_graph.
friend class undi_graph [friend] |
Definition at line 291 of file rm3_plan_undi_graph.h.
1.5.3