#include <rm3_undi_graph.h>
Nodes and edges of an undi_graph object have non-negative integer identifiers. Two distinct nodes (resp. edges) can not have the same identifier. Identifiers are preserved during each copy of the graph.
In addition to nodes and edges, an undi_graph object can have a list of constraints. A constraint can be a topological or a drawing constraint. For example, a topological constraint may require that a specified edge is not allowed to cross in the current graph embedding; a drawing constraint may require that a specified node has a given size. Constraint can be created and added to an undi_graph with public methods. As for nodes and edges, each constraint has a non-negative integer identifier. Constraints and their identifiers are preserved during copy operations.
NOTICE: selfloops are not handled.
Definition at line 792 of file rm3_undi_graph.h.
undi_graph::undi_graph | ( | ) |
Empty constructor. Creates an undi_graph object without nodes and edges.
undi_graph::~undi_graph | ( | ) |
Destructor. Deallocates the memory required by the undi_graph object.
undi_graph::undi_graph | ( | const undi_graph & | ug | ) |
Copy constructor. Creates an undi_graph object, and initializes it with the same topology and embedding as ug.
&ug | an undi_graph object |
bool undi_graph::make_embedding_planar_boyer | ( | ) |
Reimplemented in plan_undi_graph.
void undi_graph::update_constraints_after_del_edge | ( | gdtedge | e | ) | [protected] |
void undi_graph::update_constraints_after_del_node | ( | gdtnode | v | ) | [protected] |
void undi_graph::update_constraints_after_split_edge | ( | gdtedge | e, | |
gdtedge | e1, | |||
gdtedge | e2 | |||
) | [protected] |
void undi_graph::update_constraints_after_split_node | ( | gdtnode | v, | |
gdtnode | v1, | |||
gdtnode | v2 | |||
) | [protected] |
void undi_graph::update_constraints_after_merge_edges | ( | gdtedge | e1, | |
gdtedge | e2, | |||
gdtedge | e | |||
) | [protected] |
void undi_graph::update_constraints_after_merge_nodes | ( | gdtnode | v1, | |
gdtnode | v2, | |||
gdtnode | v | |||
) | [protected] |
void undi_graph::update_constraints_after_edge_translation | ( | gdtedge | e, | |
gdtnode | ve1, | |||
gdtnode | ve2, | |||
gdtedge | d, | |||
gdtnode | vd1, | |||
gdtnode | vd2 | |||
) | [protected] |
void undi_graph::update_constraints_on_path_replacing_edge | ( | gdtedge | e, | |
undi_graph & | ug, | |||
gdt::gdtlist< gdtedge > | path | |||
) | [protected] |
void undi_graph::copy_constraints_from_subgraph_of_undi_graph | ( | gdt::gdtlist< gdtedge > & | sub, | |
undi_graph & | ug | |||
) | [protected] |
gdt::gdtlist<gdtedge> undi_graph::path_corresponding_to_edge | ( | gdtedge | , | |
undi_graph & | ||||
) | const [protected] |
int undi_graph::count_not_dummy_nodes | ( | ) | const [protected] |
undi_graph& undi_graph::operator= | ( | const undi_graph & | ug | ) |
Copy operator. Deletes all nodes and edges of the undi_graph object, and makes it as a copy of the undi_graph ug.
Reimplemented in dime_orth_plan_undi_graph, dire_graph, draw_undi_graph, flow_dire_graph, orth_plan_undi_graph, plan_undi_graph, tree, and upwa_plan_undi_graph.
void undi_graph::local_get | ( | gdt::gdtlist< gdtnode > *& | p, | |
gdt::gdtlist< gdtedge > *& | p0, | |||
gdt::gdtnode_map< struct_undi_node_info > *& | p2, | |||
gdt::gdtedge_map< struct_undi_edge_info > *& | p3, | |||
gdt::gdtlist< constraint > *& | p4, | |||
gdt::gdtmap< int, gdtnode > *& | p5, | |||
gdt::gdtmap< int, gdtedge > *& | p6, | |||
gdt::gdtmap< int, constraint > *& | p7, | |||
int & | p8, | |||
int & | p9, | |||
int & | p10, | |||
bool & | p11 | |||
) |
const undi_graph& undi_graph::nodes_and_edges | ( | ) | const |
int undi_graph::generate_node_id | ( | ) |
Automatically generates a new valid gdtnode identifier for this graph. A gdtnode identifier is valid when it is distinct from any other gdtnode identifier in the graph.
int undi_graph::generate_edge_id | ( | ) |
Automatically generates a new valid gdtedge identifier for this graph. A gdtedge identifier is valid when it is distinct from any other gdtedge identifier in the graph.
int undi_graph::generate_constraint_id | ( | ) |
Automatically generates a new valid constraint identifier for this graph. A constraint identifier is valid when it is distinct from any other constraint identifier in the graph.
Returns a gdtnode identifier.
v | a gdtnode of this graph. |
Reimplemented in plan_undi_graph.
Referenced by gdt::PQ_tree< T >::PQ_tree_into_undi_graph().
Returns a gdtedge identifier.
e | a gdtedge of this graph. |
Reimplemented in plan_undi_graph.
int undi_graph::id | ( | constraint | c | ) | const |
Returns a constraint identifier.
c | a constraint of this graph. |
int undi_graph::get_max_node_id | ( | ) | const |
Returns the maximum value of a gdtnode identifier in this graph.
int undi_graph::get_max_edge_id | ( | ) | const |
Returns the maximum value of a gdtedge identifier in this graph.
int undi_graph::get_max_constraint_id | ( | ) | const |
the maximum value of a constraint identifier in this graph.
Counts the number of edges incident on a gdtnode.
v | a gdtnode of this graph |
Reimplemented in plan_undi_graph.
Counts the number of incoming edges incident on a gdtnode.
v | a gdtnode of this graph |
Counts the number of outgoing edges incident on a gdtnode.
v | a gdtnode of this graph |
int undi_graph::number_of_nodes | ( | ) | const |
Counts the number of nodes of the graph.
int undi_graph::number_of_edges | ( | ) | const |
Counts the number of edges of the graph.
int undi_graph::number_of_constraints | ( | ) | const |
Counts the number of constraints on the graph.
constraint_type undi_graph::type_of_constraint | ( | constraint | c | ) | const |
Reads the type of a constraint.
c | a constraint on this graph |
int undi_graph::max_degree | ( | ) | const |
Counts the maximum number of edges incident on a node of this graph.
int undi_graph::min_degree | ( | ) | const |
Counts the minimum number of edges incident on a node of this graph.
int undi_graph::number_of_extremals | ( | ) | const |
Returns the total number of extremal nodes of the graph. A node is extremal if it is a source node (node with only outgoing edges) or if it is a sink node (node with only incoming edges).
NOTICE: An undirected edge is considered both incoming and outgoing.
Reimplemented in upwa_plan_undi_graph.
int undi_graph::connected_components | ( | gdt::gdtnode_array< int > & | component | ) | const |
Computes the set C of all connected components of the graph. Each connected component is identified by an integer number in the range [1, ..., |C|]. The array component[v] stores the number of the component containing the gdtnode v.
component | a gdtnode_array of integer numbers |
int undi_graph::biconnected_components | ( | gdtnode | v, | |
gdt::gdtnode_map< dfs_node_info * > & | vettore_nodi, | |||
gdt::gdtlist< undi_graph * > & | bic | |||
) | const |
Computes the set of all biconnected components of the graph. The graph is visited starting by a specified node. The biconnected components are represented as undi_graph objects. Each biconnected component preserves the node and edge identifiers of the original graph.
PRECONDITIONS: the graph must be connected.
v | the gdtnode used as the starting point for visiting the graph | |
node_information[u] | stores the dfs_node_info of each node list of the biconnected components. |
Informs if a node is an end-node of an edge.
v | a gdtnode | |
e | a gdtedge |
bool undi_graph::edge_is_directed | ( | gdtedge | e | ) | const |
Informs if an edge is directed.
e | a gdtedge |
bool undi_graph::all_edges_are_directed | ( | ) | const |
Informs if all edges of the graph are directed.
Checks if the graph is an st-digraph. An st-digraph is an acyclic directed graph with a single source and a single sink.
&s | a gdtnode in which the source node is stored in positive case | |
&t | a gdtnode in which the sink node is stored in positive case |
bool undi_graph::is_connected | ( | ) | const |
Checks if the graph is connected.
bool undi_graph::is_biconnected | ( | ) | const |
Checks if the graph is biconnected.
bool undi_graph::is_acyclic | ( | ) | const |
Checks if the (undirected) graph is acyclic, i.e., if it is a forest.
bool undi_graph::is_candidate | ( | gdtnode | v | ) | const |
Checks if a gdtnode is candidate (bimodal), that is, if both its incoming edges and its outgoing edges appear consecutive in a circular order.
v | a gdtnode |
bool undi_graph::is_candidate | ( | ) | const |
Checks if all nodes are candidate (bimodal).
bool undi_graph::is_source | ( | gdtnode | v | ) | const |
Checks if a node is a source node (without incoming edges)
v | a gdtnode |
Reimplemented in upwa_plan_undi_graph.
bool undi_graph::is_target | ( | gdtnode | v | ) | const |
Checks if a node is a target (sink) node (without outgoing edges)
v | a gdtnode |
Reimplemented in upwa_plan_undi_graph.
bool undi_graph::is_extremal | ( | gdtnode | v | ) | const |
Reimplemented in upwa_plan_undi_graph.
Checks if edge e and its successive edge in the counterclocwise incident list of node v are both incoming or both outgoing.
v | a gdtnode | |
e | a gdtedge incident on v |
Reimplemented in upwa_plan_undi_graph.
bool undi_graph::is_internal | ( | gdtnode | v | ) | const |
Checks if node v is an internal vertex, that is, if it is neither a source nor a sink.
v | a gdtnode |
Reimplemented in upwa_plan_undi_graph.
Checks if edge e and its successive edge in the counterclocwise incident list of node v have opposite orientation.
v | a gdtnode | |
e | a gdtedge incident on v |
Reimplemented in upwa_plan_undi_graph.
bool undi_graph::is_multiple | ( | gdtedge | e | ) | const |
Checks if there are some other edges with the same end-node as edge e.
e | a gdtedge |
bool undi_graph::is_marked | ( | gdtnode | v, | |
marker_type | m | |||
) | const |
Checks if node v has a marker of type m.
v | a gdtnode | |
m | a valid marker_type |
bool undi_graph::is_marked | ( | gdtedge | e, | |
marker_type | m | |||
) | const |
Checks if edge e has a marker of type m.
e | a gdtedge | |
m | a valid marker_type |
gdtnode undi_graph::find_first_node_marked_as | ( | marker_type | m | ) | const |
Finds the first node with the specified marker type m.
m | a marker type. |
gdtedge undi_graph::find_first_edge_marked_as | ( | marker_type | m | ) | const |
Finds the first edge with the specified marker type m.
m | a marker type. |
gdt::gdtlist<gdtnode> undi_graph::find_nodes_marked_as | ( | marker_type | m | ) | const |
Finds all nodes having the specified marker type m.
m | a marker type. |
gdt::gdtlist<gdtedge> undi_graph::find_edges_marked_as | ( | marker_type | m | ) | const |
Finds all edges having the specified marker type m.
m | a marker type. |
gdt::gdtlist<gdtedge> undi_graph::find_adj_edges_marked_as | ( | gdtnode | v, | |
marker_type | m | |||
) | const |
Finds all edges incident on node v that have the specified marker type m.
v | a gdtnode. | |
m | a marker type. |
gdt::gdtlist<gdtedge> undi_graph::find_adj_edges_not_marked_as | ( | gdtnode | v, | |
marker_type | m | |||
) | const |
Finds all edges incident on node v that do not have the specified marker type m.
v | a gdtnode | |
m | a marker type |
gdt::gdtlist<gdtedge> undi_graph::find_in_edges_marked_as | ( | gdtnode | v, | |
marker_type | m | |||
) | const |
Finds all edges incoming on node v that have the specified marker type m.
v | a gdtnode. | |
m | a marker type. |
gdt::gdtlist<gdtedge> undi_graph::find_out_edges_marked_as | ( | gdtnode | v, | |
marker_type | m | |||
) | const |
Finds all edges outgoing from node v that have the specified marker type m.
v | a gdtnode. | |
m | a marker type. |
gdt::gdtlist<gdtedge> undi_graph::edges_with_extremal_nodes | ( | gdtnode | v1, | |
gdtnode | v2 | |||
) | const |
Finds the list of the edges with end-nodes v1 and v2. If the graph has not multiple edges, such a list contains at most one element.
v1 | a gdtnode. | |
v2 | a gdtnode. |
Finds, if it exists, a node shared by the two edges e1 and e2.
e1 | a gdtedge. | |
e2 | a gdtedge. |
bool undi_graph::simple_DFS | ( | gdtnode | v, | |
gdt::gdtnode_array< bool > & | reached, | |||
gdt::gdtnode_array< gdtedge > & | father, | |||
gdt::gdtlist< gdtnode > & | order | |||
) | const |
Performs a depth first search (DFS) of the underlying undirected graph, starting from the specified node v. Information about the DFS tree are returned in the parameters. NOTICE: you should initialize all array and list parameters before calling the method.
v | a gdtnode representing the starting node | |
reached | [w] = true if the gdtnode w is visited. | |
father | [w] = father gdtedge of w in the DFS tree. | |
order | = ordered list of the visited nodes. |
bool undi_graph::simple_BFS | ( | gdtnode | v, | |
gdt::gdtnode_array< bool > & | reached, | |||
gdt::gdtnode_array< gdtedge > & | father, | |||
gdt::gdtnode_array< int > & | dist, | |||
gdt::gdtlist< gdtnode > & | order | |||
) | const |
Performs a breadth first search (BFS) of the underlying undirected graph, starting from the specified node v. Information about the BFS tree are returned in the parameters. NOTICE: you should initialize all array and list parameters before calling the method.
v | a gdtnode representing the starting node | |
reached[w] | = true if the gdtnode w is visited. | |
father[w] | = father gdtedge of w in the BFS tree. | |
dist[w] | = minimum distance of w from v | |
order | = ordered list of the visited nodes. |
bool undi_graph::complex_DFS | ( | gdtnode | v, | |
gdtedge | e, | |||
gdt::gdtnode_array< bool > & | reached, | |||
gdt::gdtnode_array< gdtedge > & | father, | |||
gdt::gdtlist< gdtnode > & | order, | |||
gdt::gdtnode_array< gdtnode > & | lowpt1, | |||
gdt::gdtnode_array< gdtnode > & | lowpt2, | |||
gdt::gdtnode_array< int > & | num_succ, | |||
bool & | root_is_articulated | |||
) | const |
Performs a depth first search (DFS) of the underlying undirected graph, starting from the specified node v. With respect to method simple_DFS, more information about the DFS tree are returned in the parameters. NOTICE: you should initialize all array and list parameters before calling the method.
reached[w] | = true if gdtnode w is visited. | |
reached[w] | = true if the gdtnode w is visited. | |
father[w] | = father gdtedge of w in the DFS tree. | |
lowpt1[w] | = the highest ancestor of w, reacheable from w or from a descendant of w with a backward edge. | |
lowpt2[w] | = the second highest ancestor of w, reacheable from w or from a descendant of w with a backward edge. | |
num_succ[w] | = number of descendants of w. | |
root_is_articulated | = true if v is a cut-node of the graph. |
bool undi_graph::spanning_tree | ( | gdt::gdtlist< gdtedge > & | spanned_edges, | |
gdt::gdtlist< gdtedge > & | unspanned_edges, | |||
gdtnode | start_node = NULL_NODE | |||
) | const |
Computes the list spanned_edges of the edges in a spanning tree of the graph. The visit starts from the gdtnode start_node (if given). The list "unspanned_edges" is the list of the edges that do not belong to the spanning tree.
PRECONDITIONS: lists spanned_edges and unspanned_edges must be empty (checked).
spanned_edges | the computed list of spanned edges | |
unspanned_edges | the computed list of unspanned edges |
int undi_graph::unweighted_unoriented_shortest_path | ( | gdtnode | start_node, | |
gdtnode | end_node, | |||
gdt::gdtlist< gdtnode > & | nodes, | |||
gdt::gdtlist< gdtedge > & | edges | |||
) | const |
Computes an unoriented shortest path from node start and node end. The lists edges and nodes represent the ordered sequence of all edges and nodes (including nodes start and end) in the path.
start | the starting gdtnode | |
end | the ending gdtnode | |
nodes | the ordered list of gdtnodes in the path | |
edges | the ordered list of gdtedges in the path |
void undi_graph::visit_from_node_through_not_marked_nodes | ( | gdtnode | v, | |
gdt::gdtnode_array< bool > & | marked_node, | |||
gdt::gdtlist< gdtedge > & | visited_edges | |||
) | const |
Executes an unoriented BFS-visit starting from node v and traversing only nodes that are not in the list marked_nodes. The list visited_edges is the list of the visited edges.
v | the starting gdtnode | |
marked_nodes | the list of nodes that cannot be traversed | |
visited_edges | the list of edges visited in the BFS. |
gdtnode undi_graph::compare | ( | gdtnode | v, | |
gdtnode | w, | |||
gdt::gdtnode_array< int > & | f, | |||
compare_option | co = MIN | |||
) | const |
Computes the minimum (if co == MIN) or the maximum (if co == MAX) between f[v] and f[w], where v and w are two nodes of the graph, and f is an integer function on the nodes of the graph.
v | a gdtnode | |
w | a gdtnode | |
f | a gdtnode_array<int> function | |
co | an enumerate value in {MIN,MAX} |
Finds the gdtnode with the specified identifier.
id | an integer number |
Reimplemented in draw_undi_graph.
Referenced by gdt::PQ_tree< T >::PQ_tree_into_undi_graph().
gdtnode undi_graph::first_node | ( | ) | const |
gdtnode undi_graph::last_node | ( | ) | const |
v | a gdtnode |
v | a gdtnode |
e | a gdtedge |
Definition at line 2091 of file rm3_undi_graph.h.
e | a gdtedge |
Definition at line 2108 of file rm3_undi_graph.h.
v | a gdtnode | |
e | a gdtedge |
Definition at line 2127 of file rm3_undi_graph.h.
e | a gdtedge |
Definition at line 2153 of file rm3_undi_graph.h.
e | a gdtedge |
gdt::gdtlist<gdtnode> undi_graph::adj_nodes | ( | gdtnode | v | ) | const |
v | a gdtnode |
const gdt::gdtlist<gdtnode>& undi_graph::all_nodes | ( | ) | const |
Finds the edge with the specified identifier.
id | an integer number |
Reimplemented in draw_undi_graph.
Finds an edge having the specified end-nodes.
v1 | a gdtnode | |
v2 | a gdtnode |
gdtedge undi_graph::first_edge | ( | ) | const |
gdtedge undi_graph::last_edge | ( | ) | const |
e | a gdtedge |
e | a gdtedge |
v | a gdtnode |
v | a gdtnode |
v | a gdtnode |
Reimplemented in plan_undi_graph.
v | a gdtnode |
v | a gdtnode |
v | a gdtnode |
Reimplemented in plan_undi_graph.
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
Reimplemented in plan_undi_graph.
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
Reimplemented in plan_undi_graph.
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
Reimplemented in plan_undi_graph.
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
e | a gdtedge | |
v | a gdtnode |
Reimplemented in plan_undi_graph.
Finds an edge having the start and the stop end-nodes specified.
v1 | a gdtnode | |
v2 | a gdtnode |
Finds an edge having the reverse orientation of the specified edge
e | a gdtedge |
gdt::gdtlist<gdtedge> undi_graph::in_edges | ( | gdtnode | v | ) |
v | a gdtnode |
gdt::gdtlist<gdtedge> undi_graph::out_edges | ( | gdtnode | v | ) |
v | a gdtnode |
gdt::gdtlist<gdtedge> undi_graph::adj_edges | ( | gdtnode | v | ) | const |
const gdt::gdtlist<gdtedge>& undi_graph::all_edges | ( | ) | const |
gdt::list_item undi_graph::pos_of_edge_in_adj_edges_of_node | ( | gdtedge | e, | |
gdtnode | v | |||
) | const |
Finds the position of an edge in the list of incident edges of a node.
e | a gdtedge | |
v | a gdtnode |
constraint undi_graph::find_constraint | ( | int | id | ) | const |
Finds the constraint with the specified identifier.
id | an integer number |
constraint undi_graph::first_constraint | ( | ) | const |
constraint undi_graph::last_constraint | ( | ) | const |
constraint undi_graph::succ_constraint | ( | constraint | c | ) | const |
c | a constraint |
constraint undi_graph::pred_constraint | ( | constraint | c | ) | const |
c | a constraint |
const gdt::gdtlist<constraint>& undi_graph::all_constraints | ( | ) | const |
gdt::gdtlist<constraint> undi_graph::constraints_on_edge | ( | gdtedge | e | ) |
e | a gdtedge |
gdt::gdtlist<constraint> undi_graph::constraints_on_node | ( | gdtnode | v | ) |
v | a gdtnode |
gdt::gdtlist<marker_type> undi_graph::markers | ( | gdtnode | v | ) | const |
v | a gdtnode |
gdt::gdtlist<marker_type> undi_graph::markers | ( | gdtedge | e | ) | const |
e | a gdtedge |
gdtnode undi_graph::corresponding_node | ( | gdtnode | v, | |
const undi_graph & | ug | |||
) | const |
Searches in this graph a node with the same identifier as as node v of graph ug.
v | a gdtnode | |
ug | an undi_graph |
gdtedge undi_graph::corresponding_edge | ( | gdtedge | e, | |
const undi_graph & | ug | |||
) | const |
Searches in this graph an edge with the same identifier as as edge e of graph ug.
e | a gdtedge | |
ug | an undi_graph |
constraint undi_graph::corresponding_constraint | ( | constraint | c, | |
const undi_graph & | ug | |||
) | const |
Searches in this graph a constraint with the same identifier as as constraint c of graph ug.
c | a constraint | |
ug | an undi_graph |
void undi_graph::build_mapping_node_to_node_with_undi_graph | ( | const undi_graph & | ug, | |
gdt::gdtnode_map< gdtnode > & | node_corr_in_ug | |||
) | const |
Builds in linear time a mapping node_corr_in_ug between the nodes of this graph and the nodes of graph ug based on node identifiers
ug | an undi_graph | |
node_corr_in_ug | the gdtnode_map<gdtnode> constructed as output |
void undi_graph::build_mapping_edge_to_edge_with_undi_graph | ( | const undi_graph & | ug, | |
gdt::gdtedge_map< gdtedge > & | edge_corr_in_ug | |||
) | const |
Builds in linear time a mapping edge_corr_in_ug between the edges of this graph and the edges of graph ug based on edge identifiers
ug | an undi_graph | |
edge_corr_in_ug | the gdtedge_map<gdtedge> constructed as output |
Adds to this graph a new node with identifier new_id. If not specified, new_id is automatically assigned as the integer that immediately follows the maximum node identifier in the graph.
new_id | an integer number |
Referenced by rel_coord_orth::new_node(), and gdt::PQ_tree< T >::PQ_tree_into_undi_graph().
gdtnode undi_graph::new_node | ( | gdt::gdtlist< gdtnode > | L, | |
int | new_id = AUTO_ID | |||
) |
Adds to this graph a new node with identifier new_id. If not specified, new_id is automatically assigned as the integer that immediately follows the maximum node identifier in the graph. Also, the new node is attached to all nodes in the list L, in the same ordering they occur.
L,a | list of nodes | |
new_id | an integer number |
Adds to this graph a new undirected edge connecting v1 (the source node) and v2 (the target node). If not specified, new_id is automatically assigned as the integer that immediately follows the maximum edge identifier in the graph.
v1 | a gdtnode | |
v2 | a gdtnode | |
new_id | an integer number |
Reimplemented in dire_graph.
Referenced by rel_coord_orth::new_edge(), and gdt::PQ_tree< T >::PQ_tree_into_undi_graph().
gdtedge undi_graph::new_edge | ( | gdtnode | v1, | |
gdtedge | e1, | |||
gdtnode | v2, | |||
int | new_id = AUTO_ID , |
|||
int | dir = gdt::after | |||
) |
Adds to this graph a new undirected edge connecting v1 (the source node) and v2 (the target node). If not specified, new_id is automatically assigned as the integer that immediately follows the maximum edge identifier in the graph. The new edge is inserted after(before) gdtedge e1 around v1.
v1 | a gdtnode | |
e1 | a gdtedge | |
v2 | a gdtnode | |
new_id | an integer number | |
dir | a value between {after (default), before} |
Reimplemented in dire_graph.
gdtedge undi_graph::new_edge | ( | gdtnode | v1, | |
gdtedge | e1, | |||
gdtnode | v2, | |||
gdtedge | e2, | |||
int | new_id = AUTO_ID , |
|||
int | dir = gdt::after | |||
) |
Adds to this graph a new undirected edge connecting v1 (the source node) and v2 (the target node). If not specified, new_id is automatically assigned as the integer that immediately follows the maximum edge identifier in the graph. The new edge is inserted after(before) gdtedge e1 around v1 and after(before) gdtedge e2 around v2.
v1 | a gdtnode | |
e1 | a gdtedge | |
v2 | a gdtnode | |
e2 | a gdtedge | |
new_id | an integer number | |
dir | a value between {after (default), before} |
Reimplemented in dire_graph.
constraint undi_graph::new_constraint | ( | constraint | c | ) |
Adds to this graph a new constraint that is a perfect copy of the given constraint c (the identifier is also preserved).
c | a constraint |
constraint undi_graph::new_constraint_uncrossable_edge | ( | gdtedge | e, | |
int | new_id = AUTO_ID | |||
) |
Adds to this graph a new constraint imposing that edge e can not be crossed in the planarization procedure. The new constraint will have identifier new_id; if not specified, new_id will be assigned as the integer number that immediately follows the maximum constraint identifier in the graph.
e | a gdtedge | |
new_id | an integer number |
constraint undi_graph::new_constraint_number_of_bends_on_edge | ( | gdtedge | e, | |
bend_constraint | b, | |||
int | new_id = AUTO_ID | |||
) |
Adds to this graph a new constraint on the number of bends that edge e can have in a drawing. The new constraint will have identifier new_id; if not specified, new_id will be assigned as the integer number that immediately follows the maximum constraint identifier in the graph.
e | a gdtedge | |
b | a bend_constraint; possible value for b are:
|
constraint undi_graph::new_constraint_bend_direction_on_edge | ( | gdtedge | e, | |
gdtnode | v, | |||
int | new_id = AUTO_ID | |||
) |
Adds a new constraint on the bend direction of edge e. More precisely, the constraint means that e can bend only to the right while moving from v. The new constraint will have identifier new_id; if not specified, new_id will be assigned as the integer number that immediately follows the maximum constraint identifier in the graph.
e | a gdtedge | |
v | a gdtnode | |
new_id | an integer number |
constraint undi_graph::new_constraint_same_face_node | ( | gdtnode | v, | |
int | face_label, | |||
int | new_id = AUTO_ID | |||
) |
Adds a new planarization constraint imposing that node v belong to the same face as all other nodes having the same type of constraint with the same face_label.
v | a gdtnode | |
face_label | an integer label | |
new_id | an integer number |
gdt::gdtlist<constraint> undi_graph::new_constraint_same_face_node | ( | gdt::gdtlist< gdtnode > | Ln, | |
int | face_label | |||
) |
Adds a new contraint same_face_node for each node in the list Ln.
Ln | a gdtlist of gdtnodes | |
face_label | an integer number |
constraint undi_graph::new_constraint_same_face_ordered_nodes | ( | gdt::gdtlist< gdtnode > | Ln, | |
int | new_id = AUTO_ID | |||
) |
Adds a new planarization constraint imposing that all the nodes in the given list Ln will belong to the same face in the order they are given while walking on the border of the face.
Ln | a gdtlist of gdtnodes | |
face_label | an integer number |
constraint undi_graph::new_constraint_node_width | ( | gdtnode | n, | |
double | x, | |||
int | new_id = AUTO_ID | |||
) |
Adds a new constraint on the width of a node. This means that the node should have the specified width (in terms of grid units) in a drawing of the graph.
n | a gdtnode | |
x | a real number | |
new_id | an integer number |
constraint undi_graph::new_constraint_node_height | ( | gdtnode | n, | |
double | x, | |||
int | new_id = AUTO_ID | |||
) |
Adds a new constraint on the height of a node. This means that the node should have the specified height (in terms of grid units) in a drawing of the graph.
n | a gdtnode | |
x | a real number | |
new_id | an integer number |
constraint undi_graph::new_constraint_angle_sweep | ( | gdtnode | rn, | |
gdtedge | re, | |||
angle_type | alpha, | |||
int | new_id = AUTO_ID | |||
) |
constraint undi_graph::new_constraint_edge_attachment_wrt_previous_corner | ( | gdtnode | rn, | |
gdtedge | re, | |||
int | value, | |||
int | new_id = AUTO_ID | |||
) |
Adds a new constraint imposing that edge e attaches to vertex v with a distance value from the previous corner of the vertex, in a drawing of a graph. The previous corner is the corner preceding the side which the edge is incident to.
rn | a gdtnode | |
re | a gdtedge | |
value | an integer number | |
new_id | an integer number |
constraint undi_graph::new_constraint_min_tieing | ( | int | value, | |
int | new_id = AUTO_ID | |||
) |
void undi_graph::del_node | ( | gdtnode | v | ) |
Delete the node v from this graph.
v | a gdtnode |
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, plan_undi_graph, and split_component.
void undi_graph::del_edge | ( | gdtedge | e | ) |
Removes the edge e from this graph.
e | a gdtedge |
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, plan_undi_graph, and split_component.
void undi_graph::del_constraint | ( | constraint | c | ) |
Removes the constraint c from this graph.
c | a constraint |
void undi_graph::del_constraints_type | ( | constraint_type | ct | ) |
Removes all constraints with ct type from this graph.
ct | a constraint type |
void undi_graph::del_all_constraints | ( | ) |
Removes all constraints from the graph.
void undi_graph::del_all_constraints_involving_edge | ( | gdtedge | e | ) |
Removes from this graph all constraints involving the edge e".
e | a gdtedge |
void undi_graph::del_all_constraints_involving_node | ( | gdtnode | v | ) |
Removes from this graph all constraints involving the node v".
v | a gdtnode |
void undi_graph::del_constraints_type_involving_edge | ( | constraint_type | ct, | |
gdtedge | e | |||
) |
Removes all constraints with ct type involving the edge e.
ct | a constraint type | |
e | a gtdtedge |
void undi_graph::del_constraints_type_involving_node | ( | constraint_type | ct, | |
gdtnode | v | |||
) |
Removes all constraints with ct type involving the node v.
ct | a constraint type | |
v | a gtdtnode |
void undi_graph::clear | ( | ) |
Removes all nodes and edges of the graph.
Reimplemented in dime_orth_plan_undi_graph, dire_graph, draw_undi_graph, flow_dire_graph, orth_plan_undi_graph, plan_undi_graph, split_component, skeleton, SPQR_tree, tree, and upwa_plan_undi_graph.
void undi_graph::mirror | ( | undi_graph & | ug | ) |
Copies all private variables (pointers to internal data strauctures) of undi_graph in this graph.
NOTICE: the owner graph of constraints of undi_graph is replaced with this graph.
NOTICE: a method on undi_graph should follow this method to avoid collisions.
void undi_graph::forget | ( | ) |
Cut all private variables (pointers to internal data structures) from this graph.
Reimplemented in dime_orth_plan_undi_graph, flow_dire_graph, orth_plan_undi_graph, plan_undi_graph, split_component, tree, and upwa_plan_undi_graph.
METHOD assign_id Assign identifier "new_id" to gdtnode "v".
PRECONDITIONS: there is not already a gdtnode with such identifier.
Reimplemented in plan_undi_graph.
Assign identifier "new_id" to gdtedge "e".
PRECONDITIONS: there is not already any gdtedge with such identifier.
Reimplemented in plan_undi_graph.
void undi_graph::assign_id | ( | constraint | c, | |
int | new_id = AUTO_ID | |||
) |
Assign identifier "new_id" to constraint "c".
PRECONDITIONS: there is not already any constraint with such identifier.
void undi_graph::mark | ( | gdtnode | v, | |
marker_type | m | |||
) |
Mark gdtnode "v" with marker "m".
void undi_graph::mark | ( | gdtedge | e, | |
marker_type | m | |||
) |
Mark gdtedge "e" with marker "m".
void undi_graph::mark | ( | gdtnode | v, | |
gdt::gdtlist< marker_type > | ml | |||
) |
Mark gdtnode "v" with all markers in the list "ml".
void undi_graph::mark | ( | gdtedge | e, | |
gdt::gdtlist< marker_type > | ml | |||
) |
Mark gdtedge "e" with all markers in the list "ml".
void undi_graph::unmark | ( | gdtnode | v, | |
marker_type | m | |||
) |
y marker "m" from the marker-list of gdtnode "v".
void undi_graph::unmark | ( | gdtedge | e, | |
marker_type | m | |||
) |
Remove marker "m" from the marker-list of gdtnode "v".
void undi_graph::unmark_all | ( | gdtnode | v | ) |
Remove all markers from the marker-list of gdtnode "v".
void undi_graph::unmark_all | ( | gdtedge | e | ) |
Remove all markers from the marker-list of gdtedge "e".
void undi_graph::make_embedding_as | ( | const undi_graph & | ug | ) |
Make the ordering of the edges around each vertex equal to the ordering in graph "ug".
NOTICE: this graph and "ug" must have the same number of nodes and edges, with the same identifiers.
void undi_graph::make_embedding_cand | ( | gdtnode | v | ) |
Make the ordering of the edges around vertex "v" as candidate, that is both the incoming and outgoing edges will be consecutive around "v".
void undi_graph::make_embedding_cand | ( | ) |
Make the ordering of the edges around each vertex as candidate, that is both the incoming and outgoing edges will be consecutive around each vertex.
bool undi_graph::make_embedding_planar | ( | ) |
Make the ordering of the edges around vertices as planar (planar embedding), if there exists any. This means that a planar drawing exists within such an ordering. Return false when no planar embeddings exist.
bool undi_graph::make_embedding_cand_planar | ( | ) |
Make the embedding of the graph both candidate and planar (see above), if there exists any. Return false when no candidate planar embeddings exist.
gdt::gdtlist<gdtedge> undi_graph::make_embedding_cand_expanded | ( | ) |
Make the embedding of the graph as candidate and expand each vertex 'v' having at least 2 incoming edges and 2 outgoing edges. The expansion consists in splitting such a vertex 'v' into two vertices 'v1' and 'v2', the first keeping only the incoming edges of 'v' and the second keeping only the outgoing edges of 'v'; also, a directed gdtedge (v1,v2) is added, and marked RM3_ADDED_BY_EXPAND. Return the list of dummy edges introduced.
gdt::gdtlist<gdtnode> undi_graph::make_simple | ( | ) |
Make the graph simple, that is add a minimum number of dummy nodes in order to remove multiple edges. Each dummy gdtnode is marked RM3_ADDED_BY_MAKE_SIMPLE. Return the list of dummy nodes.
Reimplemented in plan_undi_graph.
gdt::gdtlist<gdtedge> undi_graph::make_connected | ( | ) |
Make the graph connected, that is add a minimum number of edges in order to attach all connected components. Each dummy gdtedge is marked RM3_ADDED_BY_MAKE_CONNECTED. Return the list of dummy edges inserted.
gdt::gdtlist<gdtedge> undi_graph::make_biconnected | ( | ) |
Make the graph biconnected, that is add a set of edges between the connected components of the graph. This method preserves the planarity of the graph. If the original graph is planar, then also the augmented graph will be planar.
Delete a minimal set of edges in order to have each gdtnode with degree at most "d" (that is with at most d incident edges). Return the number of deleted edges.
NOTICE: the graph could be not connected after this method is applied.
Make gdtedge "e" directed from gdtnode "v", that is "v" will be the start gdtnode of "e".
PRECONDITIONS: "e" is incident "v".
void undi_graph::make_directed | ( | bool | randomly = false |
) |
Make directed all edges of the graph. Each gdtedge is oriented randomly if "random" is true, and from its source if "random" is false.
Make an st-orientation of the edges with source "s" and sink "t" (see "is_st_digraph()" method).
PRECONDITIONS: the graph plus an gdtedge (s,t) is biconnected and "s", "t" are distinct.
void undi_graph::make_undirected | ( | gdtedge | e | ) |
Make gdtedge "e" undirected.
void undi_graph::make_undirected | ( | ) |
Make all edges of the graph undirected.
void undi_graph::make_source | ( | gdtnode | v | ) |
Make gdtnode "v" as a source-gdtnode, that is all the edges incident "v" will be made as outgoing edges of "v".
void undi_graph::make_sink | ( | gdtnode | v | ) |
Make gdtnode "v" as a sink-gdtnode, that is all the edges incident "v" will be made as incoming edges of "v".
void undi_graph::reverse | ( | gdtedge | e | ) |
Reverse the direction of gdtedge "e".
void undi_graph::st_number | ( | gdtedge | e_st, | |
gdtnode | s, | |||
gdt::gdtnode_array< int > & | st_num | |||
) |
Computes an st_numbering of the graph, with source gdtnode "s" and sink gdtnode the opposite of "s" in gdtedge "e_st".
PRECONDITIONS: graph is biconnected and "e_st" is incident "s".
int undi_graph::calculate_level_of_node | ( | gdtnode | v, | |
gdt::gdtnode_array< int > & | levels_buffer | |||
) |
Return the topological level of gdtnode "v" in an ordering induced by an st-numbering (recursive function).
PRECONDITIONS: graph is st-oriented
void undi_graph::calculate_level_of_all_nodes | ( | gdt::gdtnode_array< int > & | levels_buffer | ) |
Return the level of all nodes in an ordering induced by an st-numbering.
PRECONDITIONS: graph is st-oriented
Make one only gdtedge by merging the two edges incident gdtnode "v" and delete gdtnode. PRECONDITIONS: gdtnode "v" has degree 2.
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and plan_undi_graph.
Split 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. The dummy gdtedge is marked RM3_ADDED_BY_EXPAND. Return the dummy gdtedge.
Reimplemented in plan_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)}. Return gdtnode 'v'.
Reimplemented in plan_undi_graph.
gdt::gdtlist<gdtnode> undi_graph::contract | ( | ) |
Apply a contract(v) operation for each gdtnode 'v'. (see above for more details). Return the list of nodes derived by all contractions.
Reimplemented in plan_undi_graph.
void undi_graph::update_max_node_id | ( | ) |
Update the 'max_node_id' value to the current maximum gdtnode-identifier.
void undi_graph::update_max_edge_id | ( | ) |
Update the 'max_edge_id' value to the current maximum gdtedge-identifier.
void undi_graph::update_max_constraint_id | ( | ) |
Update the 'max_constraint_id' value to the current maximum constraint-identifier.
void undi_graph::rise_max_node_id | ( | int | new_max_node_id | ) |
Update 'max_node_id' (gdtnode identifier) value with "new_max_node_id".
PRECONDITIONS: "new_max_node_id" is greater than 'max_node_id'.
void undi_graph::rise_max_edge_id | ( | int | new_max_edge_id | ) |
Update "max_edge_id" (gdtedge identifier) value with "new_max_edge_id".
PRECONDITIONS: "new_max_edge_id" is greater than 'max_edge_id'.
void undi_graph::rise_max_constraint_id | ( | int | new_max_constraint_id | ) |
Update max_constraint_id (constraint identifier) value with "new_max_constraint_id".
PRECONDITIONS: "new_max_constraint_id" is greater than 'max_edge_id'.
int undi_graph::planarize | ( | planarize_options | po = DO_NOT_PRESERVE_EMBEDDING |
) |
Perform a planarization of the graph, introducing dummy nodes in order to make the embedding planar if they are needed.
Nothing assures that the number of dummy nodes introduced is minimum (the problem of finding the minimum number of crossing is NP-complete). All dummy nodes are marked RM3_CROSSES_ON_REAL_EDGES. Parameter 'planarize_options po' specifies the type of planarization, chosen in the following list:
Return the number of dummy nodes added (INFINITE when no embedding is found due to infeasible constraints).
gdt::gdtlist<gdtedge> undi_graph::replace_edge_with_path | ( | gdtedge | e, | |
gdt::gdtlist< int > & | node_id_path, | |||
gdt::gdtlist< int > & | edge_id_path | |||
) |
Replace gdtedge "e" with an ordered path of nodes and edges with identifiers given in the "node_id_path" and in the "edges_id_path" lists, respectively. Return the list of the new edges added.
PRECONDITIONS: the extremal nodes of gdtedge "e" have the same identifier as the first and the last gdtnode in the "node_id_path" list.
gdt::gdtlist<gdtedge> undi_graph::replace_edge_with_path_of_graph | ( | gdtedge | e, | |
gdt::gdtlist< gdtedge > & | edge_path, | |||
undi_graph & | ug | |||
) |
Replace gdtedge "e" with an ordered path of nodes and edges that is a copy of "edge_path" in the graph "ug". Return the list of new edges added.
PRECONDITIONS: the extremal nodes of gdtedge "e" have the same identifier as two nodes in the first and the last edges in the "edge_path" list.
void undi_graph::generate_plan_biconnected | ( | int | n, | |
double | prob_iv, | |||
int | k = INFINITE , |
|||
bool | multiple = true | |||
) |
Make the graph as a randomly generated planar biconnected graph with "n" nodes and keeping it "k"-planar (that is each vertex has degree at most k). Also, if "multiple" is false, no multiple edges are generated.
The basic technique used to generate graphs is the following:
void undi_graph::disable_keep_ordering_of_directed_edges | ( | ) |
Disable the maintenance of directed edges, that is the lists of in- and out-edges are not updated consistently with the embedding of all underlying edges ADVICE: useful to save computation-time if you are not interested in the embedding of directed edges.
void undi_graph::enable_keep_ordering_of_directed_edges | ( | ) |
Enable the maintenance of the ordering of directed edges, that is the lists of in- and out-edges are always updated consistently with the embedding of all underlying edges NOTICE: an immediate update is done
bool undi_graph::write | ( | std::string | file_name | ) |
Write the graph in a file with name "file_name". A GDToolkit file is organized in sections, each one independent from each other, and without a specific ordering to keep. Each class in the GDToolkit library has a dedicated section, and it is possible to omit some of these sections in order to store only the information that are needed (for example only the topology and not drawing information). The file format restricted to the undi_graph section information is organized as follows. There are two tags <UNDISECTION>, </UNDISECTION> at the beginning and at the end of the section, respectively. The topology of the graph is described by the ordered list of the edges around each gdtnode. Namely, you have to specify the gdtnode-identifier and the ordered list of the gdtedge-identifiers for this gdtnode. The two tags <NODELIST>, </NODELIST> indicate the beginning and the end of the nodes list, respectively. Before putting a new gdtnode-identifier a tag <NODE> is needed, then you have to put a tag <EDGE> before each gdtedge-identifier that describes an gdtedge incident the gdtnode. Finally, a tag </NODE> indicates the end of the edges incident the gdtnode. An example of an undi_graph section is shown:
<UNDISECTION>
Return true if no file error occurs during the operations.
Reimplemented in draw_undi_graph.
bool undi_graph::read | ( | std::string | file_name | ) |
Read the graph from a file with name "file_name" and return true if no file error occurs during the operations.
Reimplemented in draw_undi_graph.
void undi_graph::append_section_to_fstream | ( | std::ofstream & | out | ) |
Append the undi_graph section to the ofstream "out" (See write method for the file format).
Reimplemented in draw_undi_graph.
void undi_graph::read_section_from_fstream | ( | std::ifstream & | in | ) |
Read the undi_graph section from the ifstream "in".
Reimplemented in draw_undi_graph.
void undi_graph::print | ( | print_mode | mode = BY_NODES , |
|
std::ostream & | os = std::cout | |||
) | const |
Print the undi_graph information in the ostream "os"; print_mode can be:
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and plan_undi_graph.
void undi_graph::print | ( | gdtnode | v, | |
std::ostream & | os = std::cout | |||
) | const |
Print the identifier of gdtnode v in the ostream "os".
Reimplemented in dime_orth_plan_undi_graph, orth_plan_undi_graph, and plan_undi_graph.
void undi_graph::print | ( | gdtedge | e, | |
std::ostream & | os = std::cout | |||
) | const |
Print the identifier of gdtedge e in the ostream "os".
Reimplemented in orth_plan_undi_graph, plan_undi_graph, and upwa_plan_undi_graph.
void undi_graph::print | ( | constraint | c, | |
std::ostream & | os = std::cout | |||
) | const |
Print constraint "c" in the ostream "os". The printing features depend on the constraint type (See documentation on constraints for more details).
Reimplemented in orth_plan_undi_graph, plan_undi_graph, and upwa_plan_undi_graph.
void undi_graph::print_constraints_on_node | ( | gdtnode | v, | |
std::ostream & | os = std::cout | |||
) |
Print all constraints involving gdtnode "v" in the ostream "os".
void undi_graph::print_constraints_on_edge | ( | gdtedge | e, | |
std::ostream & | os = std::cout | |||
) |
Print all constraints involving gdtedge "e" in the ostream "os".
void undi_graph::print_constraints | ( | std::ostream & | os = std::cout |
) | const |
Print all constraints of the graph in the ostream "os".
bool undi_graph::internal_consistency_check | ( | ) | const |
Check consistency of the gdtnode/gdtedge internal structures.
Reimplemented in plan_undi_graph.
bool undi_graph::bm_spanning_tree | ( | bm_node_info | node_vector[], | |
gdt::gdtlist< gdtedge > & | added_edges, | |||
bic_obj_node * | IMM[], | |||
gdtnode | v, | |||
bool | reached[], | |||
bool | e_reached[], | |||
gdtedge | iterator[], | |||
gdtnode | graph_nodes[], | |||
int & | nodes_in_component, | |||
bic_obj *& | bic_obj_actual_pointer, | |||
bic_obj_node *& | bic_obj_node_actual_pointer | |||
) |
Compute a spanning tree of the graph and collects informations about nodes and edges. Information are stored in node_vector and edge_vector. Return false if the graph is not biconnected. This method is required by the Boyer and Myrvold planarity testing algorithm.
PRECONDITIONS: graph must be biconnected.
void undi_graph::create_children_ordered | ( | bm_node_info | node_vector[], | |
gdtnode | graph_nodes[], | |||
int | nodes_in_component | |||
) |
Create for each node an ordered list of its children in the spanning tree. Children are ordered by increasing lowpoint value. This method is required by the Boyer and Myrvold planarity testing algorithm.
PRECONDITIONS: Function bm_spannig_tree must be applied.
void undi_graph::create_out_back_edges_ordered | ( | bm_node_info | node_vector[] | ) |
Create for each node an ordered list of its back-edges in the spanning tree. Back-edges are ordered by increasing DFI value. This method is required by the Boyer and Myrvold planarity testing algorithm.
PRECONDITIONS: Function bm_spannig_tree must be applied.
bool undi_graph::bm_preprocessing | ( | bm_node_info | node_vector[], | |
gdt::gdtlist< gdtedge > & | added_edges, | |||
gdtnode | root, | |||
bic_obj_node * | IMM[], | |||
bool | reached[], | |||
bool | e_reached[], | |||
gdtedge | iterator[], | |||
int & | nodes_in_component, | |||
gdtnode | graph_nodes[], | |||
bic_obj *& | bic_obj_actual_pointer, | |||
bic_obj_node *& | bic_obj_node_actual_pointer | |||
) |
All the pre-processing operation required to execute the algorithm. This function compute a spanning tree of the graph, and then applies create_children_ordered and create_out_back_edges_ordered. This method is required by the Boyer and Myrvold planarity testing algorithm.
Return false if the graph is not biconnected.
PRECONDITIONS: Graph must be biconnected
int undi_graph::create_bicomp | ( | gdtnode | root, | |
bm_node_info | node_vector[], | |||
gdt::gdtnode_map< bic_obj_node * > & | IMM | |||
) |
This method is required by the Boyer and Myrvold planarity testing algorithm.
Create the data structure of the elementary bicomps described in the algorithm. Return the number of the elementary bicomp created. PRECONDITIONS: Graph must be biconnected. Function bm_preprocessing must be executed.
bool undi_graph::make_planar_embedding | ( | bm_node_info | node_vector[], | |
bic_obj_node * | IMM[], | |||
gdtnode | root, | |||
bool | edge_to_be_inserted[], | |||
int | flip[], | |||
bic_obj *& | bic_obj_actual_pointer | |||
) |
Apply the planarity test to a biconnected graph. Call the bm_preprocessing, create the initial bicomp structure. Then make a post-order visit of the spanning tree, and for each node with entry back edges, try to insert them using pre_walk_up, walk_up and walk_down operations (see class bic_obj). If the graph is planar return true, and modify the embedding. NOTE: edges_inserted must be initialized with false
bool undi_graph::merge_biconnected | ( | gdt::gdtlist< undi_graph * > & | bic | ) |
Read a list of biconnected planar graph, which are the biconnected components of this graph. Each node of this graph must have one and only one corresponding node in one biconnected component. This method copy the embedding of the biconnected components into the original graph, and return true if the operation ends successfully. This method is necessary to apply the algorithm to graphs which are not biconnected.
bool undi_graph::boyer | ( | gdtnode | root | ) |
Apply the Boyer and Myrvold planarity testing algorithm to connected graphs.
Split the graph in biconnected components, and apply make_planar_embedding to all them. If all the components are planar, modify the embedding of the original graph with merge_biconnected If graph is planar return true, otherwhise return false.
bool undi_graph::is_planar | ( | ) |
void undi_graph::destroy_bicomp | ( | gdt::gdtlist< bic_obj * > & | bic_obj_created | ) |
Destroy the bicomp structure created by make_planar_embedding.
int undi_graph::compare_embedding | ( | undi_graph & | ug | ) |
Compare the embeddings of this graph and the undi_graph ug. PRECONDITION: the two graphs must be equal.
void undi_graph::visible_subgraph | ( | gdtnode | n, | |
int | k, | |||
undi_graph & | vg | |||
) |
Extract the induced subgraph of the nodes at distance at most k from node n. The subgraph is stored in vg.
Compute the maximum distance k from node n from which the visible subgraph from n at distance k is planar
void undi_graph::kplanarity | ( | gdt::gdtnode_map< int > & | kplan | ) |
Compute the k-planarity of each node
void undi_graph::extended_kplanarity | ( | gdt::gdtnode_map< int > & | kplan | ) |
bool undi_graph::quick_minimum_spanning_tree | ( | gdt::gdtedge_map< int > | weights, | |
gdt::gdtlist< gdtedge > & | span_edges | |||
) |
If the graph is planar, compute a minimum spanning tree
friend class SPQR_tree [friend] |
friend class struct_constraint [friend] |
Definition at line 796 of file rm3_undi_graph.h.
friend class bic_obj [friend] |
Definition at line 797 of file rm3_undi_graph.h.
friend class bic_obj_node [friend] |
Definition at line 798 of file rm3_undi_graph.h.