GDToolkit GAPI Documentation

undi_graph::undi_graph ( )

Empty constructor. Creates an undi_graph object without nodes and edges.

See also:: undi_graph(const undi_graph& ug)

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.

Parameters:

&ug

an undi_graph object

See also:: undi_graph()

bool undi_graph::make_embedding_planar_boyer ( )

void undi_graph::set_source	(	gdtedge	,
		gdtnode
	)			`[protected]`

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.

Returns:: a non-negative integer that is a valid gdtnode identifier

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.

Returns:: a non-negative integer that is a valid gdtedge identifier

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 non-negative integer that is a valid constraint identifier

int undi_graph::id ( gdtnode v ) const

Returns a gdtnode identifier.

Parameters:

v

a gdtnode of this graph.

Returns:: the identifier of v.

Reimplemented in plan_undi_graph.

Referenced by gdt::PQ_tree< T >::PQ_tree_into_undi_graph().

Here is the caller graph for this function:

int undi_graph::id ( gdtedge e ) const

Returns a gdtedge identifier.

Parameters:

e

a gdtedge of this graph.

Returns:: the identifier of e.

Reimplemented in plan_undi_graph.

int undi_graph::id ( constraint c ) const

Returns a constraint identifier.

Parameters:

c

a constraint of this graph.

Returns:: the identifier of c.

int undi_graph::get_max_node_id ( ) const

Returns the maximum value of a gdtnode identifier in this graph.

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.

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.

Returns:: the maximum value of a constraint identifier in this graph.

int undi_graph::degree ( gdtnode v ) const

Counts the number of edges incident on a gdtnode.

Parameters:

v

a gdtnode of this graph

Returns:: the number of edges incident on v

Reimplemented in plan_undi_graph.

int undi_graph::degree_in ( gdtnode v ) const

Counts the number of incoming edges incident on a gdtnode.

Parameters:

v

a gdtnode of this graph

Returns:: the number of incoming edges incident on v

int undi_graph::degree_out ( gdtnode v ) const

Counts the number of outgoing edges incident on a gdtnode.

Parameters:

v

a gdtnode of this graph

Returns:: the number of outgoing edges incident on v

int undi_graph::number_of_nodes ( ) const

Counts the number of nodes of the graph.

Returns:: the number of nodes of the graph.

int undi_graph::number_of_edges ( ) const

Counts the number of edges of the graph.

Returns:: the number of edges of the graph.

int undi_graph::number_of_constraints ( ) const

Counts the number of constraints on the graph.

Returns:: the number of constraints on the graph.

constraint_type undi_graph::type_of_constraint ( constraint c ) const

Reads the type of a constraint.

Parameters:

c

a constraint on this graph

Returns:: the constraint_type of c

int undi_graph::max_degree ( ) const

Counts the maximum number of edges incident on a node of this graph.

Returns:: 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.

Returns:: 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.

Returns:: the total number of extremal nodes of the graph.

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.

Parameters:

component

a gdtnode_array of integer numbers

Returns:: the total number of connected components, that is, |C|.

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.

Parameters:

	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.

Returns:: the number of biconnected components.

bool undi_graph::node_belongs_to_edge	(	gdtnode	v,
		gdtedge	e
	)			const

Informs if a node is an end-node of an edge.

Parameters:

	v	a gdtnode
	e	a gdtedge

Returns:: true if v is an end-node of e, and false otherwise.

bool undi_graph::edge_is_directed ( gdtedge e ) const

Informs if an edge is directed.

Parameters:

e

a gdtedge

Returns:: true if e is directed, and false otherwise.

bool undi_graph::all_edges_are_directed ( ) const

Informs if all edges of the graph are directed.

Returns:: true if all edges are directed, and false otherwise.

bool undi_graph::is_st_digraph	(	gdtnode &	s,
		gdtnode &	t
	)

Checks if the graph is an st-digraph. An st-digraph is an acyclic directed graph with a single source and a single sink.

Parameters:

	&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

Returns:: true if the graph is an st-digraph.

bool undi_graph::is_connected ( ) const

Checks if the graph is connected.

Returns:: true if the graph is connected, and false otherwise.

bool undi_graph::is_biconnected ( ) const

Checks if the graph is biconnected.

Returns:: true if the graph is biconnected, and false otherwise..

bool undi_graph::is_acyclic ( ) const

Checks if the (undirected) graph is acyclic, i.e., if it is a forest.

Returns:: true if the graph is acyclic, and false otherwise.

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.

Parameters:

v

a gdtnode

Returns:: true if node v is bimodal, and else otherwise.

bool undi_graph::is_candidate ( ) const

Checks if all nodes are candidate (bimodal).

Returns:: true if each node is bimodal.

See also:: is_candidate(gdtnode v)

bool undi_graph::is_source ( gdtnode v ) const

Checks if a node is a source node (without incoming edges)

Parameters:

v

a gdtnode

Returns:: true if v is a source node, and false otherwise.

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)

Parameters:

v

a gdtnode

Returns:: true if v is a target node, and false otherwise.

Reimplemented in upwa_plan_undi_graph.

bool undi_graph::is_extremal ( gdtnode v ) const

Reimplemented in upwa_plan_undi_graph.

bool undi_graph::is_extremal	(	gdtnode	v,
		gdtedge	e
	)			const

Checks if edge e and its successive edge in the counterclocwise incident list of node v are both incoming or both outgoing.

Parameters:

	v	a gdtnode
	e	a gdtedge incident on v

Returns:: true if e and its successor are both incoming or both outgoing, and false otherwise.

PRECONDITIONS: v is an end-node of e.

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.

Parameters:

v

a gdtnode

Returns:: true if v is internal, and false otherwise.

Reimplemented in upwa_plan_undi_graph.

bool undi_graph::is_internal	(	gdtnode	v,
		gdtedge	e
	)			const

Checks if edge e and its successive edge in the counterclocwise incident list of node v have opposite orientation.

Parameters:

	v	a gdtnode
	e	a gdtedge incident on v

Returns:: true if e and its successor have opposite orientation, and false otherwise.

PRECONDITIONS: v is an end-node of e.

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.

Parameters:

e

a gdtedge

Returns:: true if there are other edges with the same end-nodes as e, and false otherwise.

bool undi_graph::is_marked	(	gdtnode	v,
		marker_type	m
	)			const

Checks if node v has a marker of type m.

Parameters:

	v	a gdtnode
	m	a valid marker_type

Returns:: true if v has a marker of type m, and false otherwise.

bool undi_graph::is_marked	(	gdtedge	e,
		marker_type	m
	)			const

Checks if edge e has a marker of type m.

Parameters:

	e	a gdtedge
	m	a valid marker_type

Returns:: true if e has a marker of type m, and false otherwise.

gdtnode undi_graph::find_first_node_marked_as ( marker_type m ) const

Finds the first node with the specified marker type m.

Parameters:

m

a marker type.

Returns:: the first gdtnode in the gdtnode-list of the graph that is marked m.

gdtedge undi_graph::find_first_edge_marked_as ( marker_type m ) const

Finds the first edge with the specified marker type m.

Parameters:

m

a marker type.

Returns:: the first gdtedge in the gdtedge-list of the graph that is marked m.

gdt::gdtlist<gdtnode> undi_graph::find_nodes_marked_as ( marker_type m ) const

Finds all nodes having the specified marker type m.

Parameters:

m

a marker type.

Returns:: the list of gdtnodes marked m.

gdt::gdtlist<gdtedge> undi_graph::find_edges_marked_as ( marker_type m ) const

Finds all edges having the specified marker type m.

Parameters:

m

a marker type.

Returns:: the list of gdtedges marked m.

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.

Parameters:

	v	a gdtnode.
	m	a marker type.

Returns:: the list of gdtedges marked m and incident on v.

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.

Parameters:

	v	a gdtnode
	m	a marker type

Returns:: the list of gdtedges not marked m and incident on v.

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.

Parameters:

	v	a gdtnode.
	m	a marker type.

Returns:: the list of gdtedges marked m and incoming on v.

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.

Parameters:

	v	a gdtnode.
	m	a marker type.

Returns:: the list of gdtedges marked m and outgoing from v.

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.

Parameters:

	v1	a gdtnode.
	v2	a gdtnode.

Returns:: the list of the edges with end-nodes v1 and v2.

gdtnode undi_graph::node_between_adj_edges	(	gdtedge	e1,
		gdtedge	e2
	)			const

Finds, if it exists, a node shared by the two edges e1 and e2.

Parameters:

	e1	a gdtedge.
	e2	a gdtedge.

Returns:: the common end-node of e1 and e2, if it exists, otherwise NULL_NODE is returned.

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.

Parameters:

	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.

Returns:: false if the underlying undirected graph is acyclic.

See also:: complex_DFS

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.

Parameters:

	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.

Returns:: false if the underlying undirected graph is acyclic.

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.

Parameters:

	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.

Returns:: false if the underlying undirected graph is acyclic.

See also:: simple_DFS.

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).

Parameters:

	spanned_edges	the computed list of spanned edges
	unspanned_edges	the computed list of unspanned edges

Returns:: false if the graph has no vertices.

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.

Parameters:

	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

Returns:: the length (number of edges) of the shortest 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.

Parameters:

	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.

Parameters:

	v	a gdtnode
	w	a gdtnode
	f	a gdtnode_array<int> function
	co	an enumerate value in {MIN,MAX}

gdtnode undi_graph::find_node ( int id ) const

Finds the gdtnode with the specified identifier.

Parameters:

id

an integer number

Returns:: the gdtnode with identifier id if it exists, otherwise NULL_NODE is returned.

Reimplemented in draw_undi_graph.

Referenced by gdt::PQ_tree< T >::PQ_tree_into_undi_graph().

Here is the caller graph for this function:

gdtnode undi_graph::first_node ( ) const

Returns:: the first gdtnode in the gdtnode-list of the graph.

gdtnode undi_graph::last_node ( ) const

Returns:: the last gdtnode in the gdtnode-list of the graph.

gdtnode undi_graph::succ_node ( gdtnode v ) const

Parameters:

v

a gdtnode

Returns:: the gdtnode that follows v in the gdtnode-list of the graph.

gdtnode undi_graph::pred_node ( gdtnode v ) const

Parameters:

v

a gdtnode

Returns:: the gdtnode that precedes v in the gdtnode-list of the graph.

gdtnode undi_graph::source ( gdtedge e ) const [inline]

Parameters:

e

a gdtedge

Returns:: the source node of edge e.

Definition at line 2091 of file rm3_undi_graph.h.

gdtnode undi_graph::target ( gdtedge e ) const [inline]

Parameters:

e

a gdtedge

Returns:: the target node of edge e.

Definition at line 2108 of file rm3_undi_graph.h.

gdtnode undi_graph::opposite	(	gdtnode	v,
		gdtedge	e
	)			const `[inline]`

Parameters:

	v	a gdtnode
	e	a gdtedge

Returns:: the gdtnode opposite to v on edge e.

PRECONDITIONS: v is an end-node of e.

Definition at line 2127 of file rm3_undi_graph.h.

gdtnode undi_graph::start ( gdtedge e ) const [inline]

Parameters:

e

a gdtedge

Returns:: the start node of edge e if e is directed, otherwise NULL_NODE is returned.

Definition at line 2153 of file rm3_undi_graph.h.

gdtnode undi_graph::stop ( gdtedge e ) const

Parameters:

e

a gdtedge

Returns:: the stop node of edge e if e is directed, otherwise NULL_NODE is returned.

gdt::gdtlist<gdtnode> undi_graph::adj_nodes ( gdtnode v ) const

Parameters:

v

a gdtnode

Returns:: the list of all nodes that are adjacent to v.

const gdt::gdtlist<gdtnode>& undi_graph::all_nodes ( ) const

Returns:: a constant reference to the gdtnode-list of the graph.

gdtedge undi_graph::find_edge ( int id ) const

Finds the edge with the specified identifier.

Parameters:

id

an integer number

Returns:: the gdtedge with identifier id if it exists, otherwise NULL_EDGE is returned.

Reimplemented in draw_undi_graph.

gdtedge undi_graph::find_edge	(	gdtnode	v1,
		gdtnode	v2
	)			const

Finds an edge having the specified end-nodes.

Parameters:

	v1	a gdtnode
	v2	a gdtnode

Returns:: a gdtedge with end-nodes v1 and v2 if there exists one, otherwise NULL_EDGE is returned.

gdtedge undi_graph::first_edge ( ) const

Returns:: the first gdtedge of the gdtedge-list of the graph.

gdtedge undi_graph::last_edge ( ) const

Returns:: the last gdtedge of the gdtedge-list of the graph.

gdtedge undi_graph::succ_edge ( gdtedge e ) const

Parameters:

e

a gdtedge

Returns:: the edge that follows e in the gdtedge-list of the graph.

gdtedge undi_graph::pred_edge ( gdtedge e ) const

Parameters:

e

a gdtedge

Returns:: the edge that precedes e in the gdtedge-list of the graph.

gdtedge undi_graph::first_in_edge ( gdtnode v )

Parameters:

v

a gdtnode

Returns:: the first edge in the list of the incoming edges of v.

gdtedge undi_graph::first_out_edge ( gdtnode v )

Parameters:

v

a gdtnode

Returns:: the first edge in the list of the outgoing edges of v.

gdtedge undi_graph::first_adj_edge ( gdtnode v ) const

Parameters:

v

a gdtnode

Returns:: the first edge in the list of incident edges of v.

Reimplemented in plan_undi_graph.

gdtedge undi_graph::last_in_edge ( gdtnode v )

Parameters:

v

a gdtnode

Returns:: the last edge in the list of incident edges of v.

gdtedge undi_graph::last_out_edge ( gdtnode v )

Parameters:

v

a gdtnode

Returns:: the last edge in the list of the outgoing edges of v.

gdtedge undi_graph::last_adj_edge ( gdtnode v ) const

Parameters:

v

a gdtnode

Returns:: the last edge in the list of the incident edges of v.

Reimplemented in plan_undi_graph.

gdtedge undi_graph::in_succ	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that follows e in the list of incoming edges of v.

PRECONDITIONS: e is incoming v.

gdtedge undi_graph::out_succ	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that follows e in the list of outgoing edges of v.

PRECONDITIONS: e is outgoing v.

gdtedge undi_graph::adj_succ	(	gdtedge	e,
		gdtnode	v
	)			const

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that follows e in the list of incident edges of v.

PRECONDITIONS: e is incident on v.

Reimplemented in plan_undi_graph.

gdtedge undi_graph::in_pred	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that precedes e in the list of incoming edges of v.

PRECONDITIONS: e is incoming v.

gdtedge undi_graph::out_pred	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that precedes e in the list of outgoing edges of v.

PRECONDITIONS: e is outgoing v.

gdtedge undi_graph::adj_pred	(	gdtedge	e,
		gdtnode	v
	)			const

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that precedes e in the list of incident edges of v.

PRECONDITIONS: e is incident on v.

Reimplemented in plan_undi_graph.

gdtedge undi_graph::cyclic_in_succ	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that cyclically follows e in the circular list of incoming edges of v.

PRECONDITIONS: e is incoming v.

gdtedge undi_graph::cyclic_out_succ	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that cyclically follows e in the circular list of outgping edges of v.

PRECONDITIONS: e is outgoing v.

gdtedge undi_graph::cyclic_adj_succ	(	gdtedge	e,
		gdtnode	v
	)			const

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that cyclically follows e in the circular list of incident edges of v.

PRECONDITIONS: e is incident on v.

Reimplemented in plan_undi_graph.

gdtedge undi_graph::cyclic_in_pred	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that cyclically precedes e in the circular list of incoming edges of v.

PRECONDITIONS: e is incoming v.

gdtedge undi_graph::cyclic_out_pred	(	gdtedge	e,
		gdtnode	v
	)

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that cyclically precedes e in the circular list of outgoing edges of v.

PRECONDITIONS: e is outgoing v.

gdtedge undi_graph::cyclic_adj_pred	(	gdtedge	e,
		gdtnode	v
	)			const

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the edge that cyclically precedes e in the circular list of incident edges of v.

PRECONDITIONS: e is incident on v.

Reimplemented in plan_undi_graph.

gdtedge undi_graph::find_directed_edge	(	gdtnode	v1,
		gdtnode	v2
	)

Finds an edge having the start and the stop end-nodes specified.

Parameters:

	v1	a gdtnode
	v2	a gdtnode

Returns:: a directed gdtedge having v1 as start end-node and v2 as stop end-node if there exists any, otherwise NULL_EDGE is returned.

gdtedge undi_graph::reverse_of_edge ( gdtedge e )

Finds an edge having the reverse orientation of the specified edge

Parameters:

e

a gdtedge

Returns:: a gdtedge having the reverse orientation of e if there exists one, otherwise NULL_EDGE is returned.

NOTICE: the method returns NULL_EDGE even if e is undirected.

gdt::gdtlist<gdtedge> undi_graph::in_edges ( gdtnode v )

Parameters:

v

a gdtnode

Returns:: the list of incoming edges of v.

gdt::gdtlist<gdtedge> undi_graph::out_edges ( gdtnode v )

Parameters:

v

a gdtnode

Returns:: the list of outgoing edges of v.

gdt::gdtlist<gdtedge> undi_graph::adj_edges ( gdtnode v ) const

Parameters:

v

a gdtnode

Returns:: the list of indicent edges of v.

Reimplemented in plan_undi_graph.

const gdt::gdtlist<gdtedge>& undi_graph::all_edges ( ) const

Returns:: a constant reference to the gdtedge-list of the graph.

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.

Parameters:

	e	a gdtedge
	v	a gdtnode

Returns:: the position of e in the list of incident edges of gdtnode v.

PRECONDITIONS: e is incident on v.

constraint undi_graph::find_constraint ( int id ) const

Finds the constraint with the specified identifier.

Parameters:

id

an integer number

Returns:: the constraint with identifier id if it exists, otherwise NULL_CONSTRAINT is returned.

constraint undi_graph::first_constraint ( ) const

Returns:: the first constraint in the constraint-list of the graph.

constraint undi_graph::last_constraint ( ) const

Returns:: the last constraint in the constraint-list of the graph.

constraint undi_graph::succ_constraint ( constraint c ) const

Parameters:

c

a constraint

Returns:: the constraint that follows c in the constraint-list of the graph.

constraint undi_graph::pred_constraint ( constraint c ) const

Parameters:

c

a constraint

Returns:: the constraint that precedes c in the constraint-list of the graph.

const gdt::gdtlist<constraint>& undi_graph::all_constraints ( ) const

Returns:: a constant reference to the constraint-list of the graph.

gdt::gdtlist<constraint> undi_graph::constraints_on_edge ( gdtedge e )

Parameters:

e

a gdtedge

Returns:: the list of constraints involving e.

gdt::gdtlist<constraint> undi_graph::constraints_on_node ( gdtnode v )

Parameters:

v

a gdtnode

Returns:: a list of all constraints involving gdtnode v.

gdt::gdtlist<marker_type> undi_graph::markers ( gdtnode v ) const

Parameters:

v

a gdtnode

Returns:: the list of all markers of gdtnode v.

gdt::gdtlist<marker_type> undi_graph::markers ( gdtedge e ) const

Parameters:

e

a gdtedge

Returns:: the list of all markers of gdtnode v.

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.

Parameters:

	v	a gdtnode
	ug	an undi_graph

Returns:: a gdtnode of this graph with the same identifier as v if it exists, otherwise NULL_NODE is returned.

PRECONDITIONS: v is a node of ug.

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.

Parameters:

	e	a gdtedge
	ug	an undi_graph

Returns:: a gdtedge of this graph with the same identifier as e if it exists, otherwise NULL_EDGE is returned.

PRECONDITIONS: e is an edge of ug.

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.

Parameters:

	c	a constraint
	ug	an undi_graph

Returns:: a constraint of this graph with the same identifier as c if it exists, otherwise NULL_CONSTRAINT is returned.

PRECONDITIONS: c is a constraint of ug.

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

Parameters:

	ug	an undi_graph
	node_corr_in_ug	the gdtnode_map<gdtnode> constructed as output

NOTES: node_corr_in_ug is initialized on the nodes of this graph.

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

Parameters:

	ug	an undi_graph
	edge_corr_in_ug	the gdtedge_map<gdtedge> constructed as output

NOTES: edge_corr_in_ug is initialized on the nodes of this graph.

gdtnode undi_graph::new_node ( 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.

Parameters:

new_id

an integer number

Returns:: the gdtnode created.

PRECONDITIONS: if specified, new_id is non-negative and unique.

Referenced by rel_coord_orth::new_node(), and gdt::PQ_tree< T >::PQ_tree_into_undi_graph().

Here is the caller graph for this function:

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.

Parameters:

	L,a	list of nodes
	new_id	an integer number

Returns:: the gdtnode created.

PRECONDITIONS: if specified, new_id is non-negative and unique. The nodes in L belongs to this graph.

gdtedge undi_graph::new_edge	(	gdtnode	v1,
		gdtnode	v2,
		int	new_id = `AUTO_ID`
	)

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.

Parameters:

	v1	a gdtnode
	v2	a gdtnode
	new_id	an integer number

Returns:: the gdtedge created.

PRECONDITIONS: if specified, new_id is non-negative and is unique.

Reimplemented in dire_graph.

Referenced by rel_coord_orth::new_edge(), and gdt::PQ_tree< T >::PQ_tree_into_undi_graph().

Here is the caller graph for this function:

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.

Parameters:

	v1	a gdtnode
	e1	a gdtedge
	v2	a gdtnode
	new_id	an integer number
	dir	a value between {after (default), before}

Returns:: the gdtedge created.

PRECONDITIONS: if specified, new_id is non-negative and is unique. Edge e1 is an incident edge of v1.

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.

Parameters:

	v1	a gdtnode
	e1	a gdtedge
	v2	a gdtnode
	e2	a gdtedge
	new_id	an integer number
	dir	a value between {after (default), before}

Returns:: the gdtedge created.

PRECONDITIONS: if specified, new_id is non-negative and is unique. Edge e1 is an incident edge of v1 and edge e2 is an incident edge of v2.

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).

Parameters:

c

a constraint

Returns:: the new constraint

PRECONDITIONS: c is consistent with the graph topology and belongs to another graph.

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.

Parameters:

	e	a gdtedge
	new_id	an integer number

Returns:: the new constraint.

PRECONDITIONS: if specified, new_id is non-negative and is unique.

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.

Parameters:

	e	a gdtedge
	b	a bend_constraint; possible value for b are: NONE: no bend on gdtedge (straight gdtedge) ANY : any number of bends on gdtedge (zero cost bend on gdtedge). new_id an integer number

Returns:: the new constraint.

PRECONDITIONS: if specified, new_id is non-negative and is unique.

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.

Parameters:

	e	a gdtedge
	v	a gdtnode
	new_id	an integer number

Returns:: the new constraint.

PRECONDITIONS: if specified, new_id is non-negative and is unique. Edge e is incident on v.

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.

Parameters:

	v	a gdtnode
	face_label	an integer label
	new_id	an integer number

Returns:: the new constraint.

PRECONDITIONS: if specified, new_id is non-negative and is unique.

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.

Parameters:

	Ln	a gdtlist of gdtnodes
	face_label	an integer number

Returns:: the list of new constraints.

See also:: new_constraint_same_face_node (gdtnode, int, int)

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.

Parameters:

	Ln	a gdtlist of gdtnodes
	face_label	an integer number

Returns:: the list of new constraints.

PRECONDITIONS: if specified, new_id is non-negative and is unique.

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.

Parameters:

	n	a gdtnode
	x	a real number
	new_id	an integer number

Returns:: the new constraint.

PRECONDITIONS: if specified, new_id is non-negative and is unique.

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.

Parameters:

	n	a gdtnode
	x	a real number
	new_id	an integer number

Returns:: the new constraint.

PRECONDITIONS: if specified, new_id is non-negative and is unique.

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.

Parameters:

	rn	a gdtnode
	re	a gdtedge
	value	an integer number
	new_id	an integer number

Returns:: PRECONDITIONS: if specified, new_id is non-negative and is unique. e is incident on v.

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.

Parameters:

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.

Parameters:

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.

Parameters:

c

a constraint

void undi_graph::del_constraints_type ( constraint_type ct )

Removes all constraints with ct type from this graph.

Parameters:

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".

Parameters:

e

a gdtedge

void undi_graph::del_all_constraints_involving_node ( gdtnode v )

Removes from this graph all constraints involving the node v".

Parameters:

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.

Parameters:

	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.

Parameters:

	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.

void undi_graph::assign_id	(	gdtnode	v,
		int	new_id = `AUTO_ID`
	)

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.

void undi_graph::assign_id	(	gdtedge	e,
		int	new_id = `AUTO_ID`
	)

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.

Returns:: the list of the added edges

int undi_graph::make_max_degree ( int d )

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.

void undi_graph::make_directed	(	gdtedge	e,
		gdtnode	v
	)

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.

void undi_graph::make_directed	(	gdtnode	s,
		gdtnode	t
	)

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

gdtedge undi_graph::weld_edges_at_node ( gdtnode v )

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.

gdtedge undi_graph::expand	(	gdtnode	v,
		gdtedge	e_init,
		gdtedge	e_end
	)

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.

gdtnode undi_graph::contract ( gdtedge e )

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:

DO_NOT_PRESERVE_EMBEDDING
PRESERVE_EMBEDDING

In the first case the ordering of the edges around vertices could be changed by the algorithm. In the second case, the algorithm does not change this ordering.

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:

start from a triangle graph;
at each step is randomly chosen either the operation "insert vertex" (split gdtedge) or the operation "insert gdtedge";
the "insert vertex" operation is chosen with probability "prob_iv", and the "insert gdtedge" operation is selected with probability 1 - "prob_iv", where 0 < "prob_iv" < 1.

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:

NODELIST>

NODE>

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:

BY_NODES: print each gdtnode and the ordered list of its incident edges;
BY_EDGE: print each gdtedge and its extremal nodes;
COMPLETE: print all the information, combining all the previous modalities.

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.

node_vector: stores informations collected about nodes <L i>=""> node_vector: stores informations collected about edges

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.

node_vector: information about nodes collected by bm_spanning_tree

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.

node_vector: information about nodes collected by bm_spanning_tree

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

node_vector: stores informations collected about nodes:
node_vector: stores informations collected about edges:
root: node used as root of the spanning tree.

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.

node_vector: informations about nodes collected by bm_preprocessing:
node_vector: informations about edges collected by bm_preprocessing:
root: root of the spanning tree.

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

node_vector: informations about nodes collected by bm_preprocessing
edge_vector: informations about edges collected by bm_preprocessing
IMM: for each node give the corresponding bic_obj
root: root node of the spanning tree
edges_inserted: for each edge, true if it was added to the embedding

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.

bic: list of the planar biconnected componets

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.

root: root node of the spanning tree

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.

IMM: for each nodes gives the corresponding bic_obj

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.

Returns:: the number of edge swapping that must be applied to ug to obtain the same embedding ad this graph.

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.

int undi_graph::kplanarity ( gdtnode n )

Compute the maximum distance k from node n from which the visible subgraph from n at distance k is planar

int undi_graph::extended_kplanarity ( gdtnode n )

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]

Reimplemented in skeleton.

Definition at line 795 of file rm3_undi_graph.h.

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.

Graph Drawing Toolkit

undi_graph Class Reference

Public Member Functions

Protected Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation


Public Member Functions
bool	make_embedding_planar_boyer ()
	undi_graph ()
	~undi_graph ()
	undi_graph (const undi_graph &ug)
undi_graph &	operator= (const undi_graph &ug)
void	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 &	nodes_and_edges () const
int	generate_node_id ()
int	generate_edge_id ()
int	generate_constraint_id ()
int	id (gdtnode v) const
int	id (gdtedge e) const
int	id (constraint c) const
int	get_max_node_id () const
int	get_max_edge_id () const
int	get_max_constraint_id () const
int	degree (gdtnode v) const
int	degree_in (gdtnode v) const
int	degree_out (gdtnode v) const
int	number_of_nodes () const
int	number_of_edges () const
int	number_of_constraints () const
constraint_type	type_of_constraint (constraint c) const
int	max_degree () const
int	min_degree () const
int	number_of_extremals () const
int	connected_components (gdt::gdtnode_array< int > &component) const
int	biconnected_components (gdtnode v, gdt::gdtnode_map< dfs_node_info * > &vettore_nodi, gdt::gdtlist< undi_graph * > &bic) const
bool	node_belongs_to_edge (gdtnode v, gdtedge e) const
bool	edge_is_directed (gdtedge e) const
bool	all_edges_are_directed () const
bool	is_st_digraph (gdtnode &s, gdtnode &t)
bool	is_connected () const
bool	is_biconnected () const
bool	is_acyclic () const
bool	is_candidate (gdtnode v) const
bool	is_candidate () const
bool	is_source (gdtnode v) const
bool	is_target (gdtnode v) const
bool	is_extremal (gdtnode v) const
bool	is_extremal (gdtnode v, gdtedge e) const
bool	is_internal (gdtnode v) const
bool	is_internal (gdtnode v, gdtedge e) const
bool	is_multiple (gdtedge e) const
bool	is_marked (gdtnode v, marker_type m) const
bool	is_marked (gdtedge e, marker_type m) const
gdtnode	find_first_node_marked_as (marker_type m) const
gdtedge	find_first_edge_marked_as (marker_type m) const
gdt::gdtlist< gdtnode >	find_nodes_marked_as (marker_type m) const
gdt::gdtlist< gdtedge >	find_edges_marked_as (marker_type m) const
gdt::gdtlist< gdtedge >	find_adj_edges_marked_as (gdtnode v, marker_type m) const
gdt::gdtlist< gdtedge >	find_adj_edges_not_marked_as (gdtnode v, marker_type m) const
gdt::gdtlist< gdtedge >	find_in_edges_marked_as (gdtnode v, marker_type m) const
gdt::gdtlist< gdtedge >	find_out_edges_marked_as (gdtnode v, marker_type m) const
gdt::gdtlist< gdtedge >	edges_with_extremal_nodes (gdtnode v1, gdtnode v2) const
gdtnode	node_between_adj_edges (gdtedge e1, gdtedge e2) const
bool	simple_DFS (gdtnode v, gdt::gdtnode_array< bool > &reached, gdt::gdtnode_array< gdtedge > &father, gdt::gdtlist< gdtnode > &order) const
bool	simple_BFS (gdtnode v, gdt::gdtnode_array< bool > &reached, gdt::gdtnode_array< gdtedge > &father, gdt::gdtnode_array< int > &dist, gdt::gdtlist< gdtnode > &order) const
bool	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
bool	spanning_tree (gdt::gdtlist< gdtedge > &spanned_edges, gdt::gdtlist< gdtedge > &unspanned_edges, gdtnode start_node=NULL_NODE) const
int	unweighted_unoriented_shortest_path (gdtnode start_node, gdtnode end_node, gdt::gdtlist< gdtnode > &nodes, gdt::gdtlist< gdtedge > &edges) const
void	visit_from_node_through_not_marked_nodes (gdtnode v, gdt::gdtnode_array< bool > &marked_node, gdt::gdtlist< gdtedge > &visited_edges) const
gdtnode	compare (gdtnode v, gdtnode w, gdt::gdtnode_array< int > &f, compare_option co=MIN) const
gdtnode	find_node (int id) const
gdtnode	first_node () const
gdtnode	last_node () const
gdtnode	succ_node (gdtnode v) const
gdtnode	pred_node (gdtnode v) const
gdtnode	source (gdtedge e) const
gdtnode	target (gdtedge e) const
gdtnode	opposite (gdtnode v, gdtedge e) const
gdtnode	start (gdtedge e) const
gdtnode	stop (gdtedge e) const
gdt::gdtlist< gdtnode >	adj_nodes (gdtnode v) const
const gdt::gdtlist < gdtnode > &	all_nodes () const
gdtedge	find_edge (int id) const
gdtedge	find_edge (gdtnode v1, gdtnode v2) const
gdtedge	first_edge () const
gdtedge	last_edge () const
gdtedge	succ_edge (gdtedge e) const
gdtedge	pred_edge (gdtedge e) const
gdtedge	first_in_edge (gdtnode v)
gdtedge	first_out_edge (gdtnode v)
gdtedge	first_adj_edge (gdtnode v) const
gdtedge	last_in_edge (gdtnode v)
gdtedge	last_out_edge (gdtnode v)
gdtedge	last_adj_edge (gdtnode v) const
gdtedge	in_succ (gdtedge e, gdtnode v)
gdtedge	out_succ (gdtedge e, gdtnode v)
gdtedge	adj_succ (gdtedge e, gdtnode v) const
gdtedge	in_pred (gdtedge e, gdtnode v)
gdtedge	out_pred (gdtedge e, gdtnode v)
gdtedge	adj_pred (gdtedge e, gdtnode v) const
gdtedge	cyclic_in_succ (gdtedge e, gdtnode v)
gdtedge	cyclic_out_succ (gdtedge e, gdtnode v)
gdtedge	cyclic_adj_succ (gdtedge e, gdtnode v) const
gdtedge	cyclic_in_pred (gdtedge e, gdtnode v)
gdtedge	cyclic_out_pred (gdtedge e, gdtnode v)
gdtedge	cyclic_adj_pred (gdtedge e, gdtnode v) const
gdtedge	find_directed_edge (gdtnode v1, gdtnode v2)
gdtedge	reverse_of_edge (gdtedge e)
gdt::gdtlist< gdtedge >	in_edges (gdtnode v)
gdt::gdtlist< gdtedge >	out_edges (gdtnode v)
gdt::gdtlist< gdtedge >	adj_edges (gdtnode v) const
const gdt::gdtlist < gdtedge > &	all_edges () const
gdt::list_item	pos_of_edge_in_adj_edges_of_node (gdtedge e, gdtnode v) const
constraint	find_constraint (int id) const
constraint	first_constraint () const
constraint	last_constraint () const
constraint	succ_constraint (constraint c) const
constraint	pred_constraint (constraint c) const
const gdt::gdtlist < constraint > &	all_constraints () const
gdt::gdtlist < constraint >	constraints_on_edge (gdtedge e)
gdt::gdtlist < constraint >	constraints_on_node (gdtnode v)
gdt::gdtlist < marker_type >	markers (gdtnode v) const
gdt::gdtlist < marker_type >	markers (gdtedge e) const
gdtnode	corresponding_node (gdtnode v, const undi_graph &ug) const
gdtedge	corresponding_edge (gdtedge e, const undi_graph &ug) const
constraint	corresponding_constraint (constraint c, const undi_graph &ug) const
void	build_mapping_node_to_node_with_undi_graph (const undi_graph &ug, gdt::gdtnode_map< gdtnode > &node_corr_in_ug) const
void	build_mapping_edge_to_edge_with_undi_graph (const undi_graph &ug, gdt::gdtedge_map< gdtedge > &edge_corr_in_ug) const
gdtnode	new_node (int new_id=AUTO_ID)
gdtnode	new_node (gdt::gdtlist< gdtnode > L, int new_id=AUTO_ID)
gdtedge	new_edge (gdtnode v1, gdtnode v2, int new_id=AUTO_ID)
gdtedge	new_edge (gdtnode v1, gdtedge e1, gdtnode v2, int new_id=AUTO_ID, int dir=gdt::after)
gdtedge	new_edge (gdtnode v1, gdtedge e1, gdtnode v2, gdtedge e2, int new_id=AUTO_ID, int dir=gdt::after)
constraint	new_constraint (constraint c)
constraint	new_constraint_uncrossable_edge (gdtedge e, int new_id=AUTO_ID)
constraint	new_constraint_number_of_bends_on_edge (gdtedge e, bend_constraint b, int new_id=AUTO_ID)
constraint	new_constraint_bend_direction_on_edge (gdtedge e, gdtnode v, int new_id=AUTO_ID)
constraint	new_constraint_same_face_node (gdtnode v, int face_label, int new_id=AUTO_ID)
gdt::gdtlist < constraint >	new_constraint_same_face_node (gdt::gdtlist< gdtnode > Ln, int face_label)
constraint	new_constraint_same_face_ordered_nodes (gdt::gdtlist< gdtnode > Ln, int new_id=AUTO_ID)
constraint	new_constraint_node_width (gdtnode n, double x, int new_id=AUTO_ID)
constraint	new_constraint_node_height (gdtnode n, double x, int new_id=AUTO_ID)
constraint	new_constraint_angle_sweep (gdtnode rn, gdtedge re, angle_type alpha, int new_id=AUTO_ID)
constraint	new_constraint_edge_attachment_wrt_previous_corner (gdtnode rn, gdtedge re, int value, int new_id=AUTO_ID)
constraint	new_constraint_min_tieing (int value, int new_id=AUTO_ID)
void	del_node (gdtnode v)
void	del_edge (gdtedge e)
void	del_constraint (constraint c)
void	del_constraints_type (constraint_type ct)
void	del_all_constraints ()
void	del_all_constraints_involving_edge (gdtedge e)
void	del_all_constraints_involving_node (gdtnode v)
void	del_constraints_type_involving_edge (constraint_type ct, gdtedge e)
void	del_constraints_type_involving_node (constraint_type ct, gdtnode v)
void	clear ()
void	mirror (undi_graph &ug)
void	forget ()
void	assign_id (gdtnode v, int new_id=AUTO_ID)
void	assign_id (gdtedge e, int new_id=AUTO_ID)
void	assign_id (constraint c, int new_id=AUTO_ID)
void	mark (gdtnode v, marker_type m)
void	mark (gdtedge e, marker_type m)
void	mark (gdtnode v, gdt::gdtlist< marker_type > ml)
void	mark (gdtedge e, gdt::gdtlist< marker_type > ml)
void	unmark (gdtnode v, marker_type m)
void	unmark (gdtedge e, marker_type m)
void	unmark_all (gdtnode v)
void	unmark_all (gdtedge e)
void	make_embedding_as (const undi_graph &ug)
void	make_embedding_cand (gdtnode v)
void	make_embedding_cand ()
bool	make_embedding_planar ()
bool	make_embedding_cand_planar ()
gdt::gdtlist< gdtedge >	make_embedding_cand_expanded ()
gdt::gdtlist< gdtnode >	make_simple ()
gdt::gdtlist< gdtedge >	make_connected ()
gdt::gdtlist< gdtedge >	make_biconnected ()
int	make_max_degree (int d)
void	make_directed (gdtedge e, gdtnode v)
void	make_directed (bool randomly=false)
void	make_directed (gdtnode s, gdtnode t)
void	make_undirected (gdtedge e)
void	make_undirected ()
void	make_source (gdtnode v)
void	make_sink (gdtnode v)
void	reverse (gdtedge e)
void	st_number (gdtedge e_st, gdtnode s, gdt::gdtnode_array< int > &st_num)
int	calculate_level_of_node (gdtnode v, gdt::gdtnode_array< int > &levels_buffer)
void	calculate_level_of_all_nodes (gdt::gdtnode_array< int > &levels_buffer)
gdtedge	weld_edges_at_node (gdtnode v)
gdtedge	expand (gdtnode v, gdtedge e_init, gdtedge e_end)
gdtnode	contract (gdtedge e)
gdt::gdtlist< gdtnode >	contract ()
void	update_max_node_id ()
void	update_max_edge_id ()
void	update_max_constraint_id ()
void	rise_max_node_id (int new_max_node_id)
void	rise_max_edge_id (int new_max_edge_id)
void	rise_max_constraint_id (int new_max_constraint_id)
int	planarize (planarize_options po=DO_NOT_PRESERVE_EMBEDDING)
gdt::gdtlist< gdtedge >	replace_edge_with_path (gdtedge e, gdt::gdtlist< int > &node_id_path, gdt::gdtlist< int > &edge_id_path)
gdt::gdtlist< gdtedge >	replace_edge_with_path_of_graph (gdtedge e, gdt::gdtlist< gdtedge > &edge_path, undi_graph &ug)
void	generate_plan_biconnected (int n, double prob_iv, int k=INFINITE, bool multiple=true)
void	disable_keep_ordering_of_directed_edges ()
void	enable_keep_ordering_of_directed_edges ()
bool	write (std::string file_name)
bool	read (std::string file_name)
void	append_section_to_fstream (std::ofstream &out)
void	read_section_from_fstream (std::ifstream &in)
void	print (print_mode mode=BY_NODES, std::ostream &os=std::cout) const
void	print (gdtnode v, std::ostream &os=std::cout) const
void	print (gdtedge e, std::ostream &os=std::cout) const
void	print (constraint c, std::ostream &os=std::cout) const
void	print_constraints_on_node (gdtnode v, std::ostream &os=std::cout)
void	print_constraints_on_edge (gdtedge e, std::ostream &os=std::cout)
void	print_constraints (std::ostream &os=std::cout) const
bool	internal_consistency_check () const
bool	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)
void	create_children_ordered (bm_node_info node_vector[], gdtnode graph_nodes[], int nodes_in_component)
void	create_out_back_edges_ordered (bm_node_info node_vector[])
bool	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)
int	create_bicomp (gdtnode root, bm_node_info node_vector[], gdt::gdtnode_map< bic_obj_node * > &IMM)
bool	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)
bool	merge_biconnected (gdt::gdtlist< undi_graph * > &bic)
bool	boyer (gdtnode root)
bool	is_planar ()
void	destroy_bicomp (gdt::gdtlist< bic_obj * > &bic_obj_created)
int	compare_embedding (undi_graph &ug)
void	visible_subgraph (gdtnode n, int k, undi_graph &vg)
int	kplanarity (gdtnode n)
int	extended_kplanarity (gdtnode n)
void	kplanarity (gdt::gdtnode_map< int > &kplan)
void	extended_kplanarity (gdt::gdtnode_map< int > &kplan)
bool	quick_minimum_spanning_tree (gdt::gdtedge_map< int > weights, gdt::gdtlist< gdtedge > &span_edges)
Protected Member Functions
void	set_source (gdtedge, gdtnode)
void	update_constraints_after_del_edge (gdtedge e)
void	update_constraints_after_del_node (gdtnode v)
void	update_constraints_after_split_edge (gdtedge e, gdtedge e1, gdtedge e2)
void	update_constraints_after_split_node (gdtnode v, gdtnode v1, gdtnode v2)
void	update_constraints_after_merge_edges (gdtedge e1, gdtedge e2, gdtedge e)
void	update_constraints_after_merge_nodes (gdtnode v1, gdtnode v2, gdtnode v)
void	update_constraints_after_edge_translation (gdtedge e, gdtnode ve1, gdtnode ve2, gdtedge d, gdtnode vd1, gdtnode vd2)
void	update_constraints_on_path_replacing_edge (gdtedge e, undi_graph &ug, gdt::gdtlist< gdtedge > path)
void	copy_constraints_from_subgraph_of_undi_graph (gdt::gdtlist< gdtedge > &sub, undi_graph &ug)
gdt::gdtlist< gdtedge >	path_corresponding_to_edge (gdtedge, undi_graph &) const
int	count_not_dummy_nodes () const
Friends
class	SPQR_tree
class	struct_constraint
class	bic_obj
class	bic_obj_node