DDG::LOOP

LOOP Class Reference

Inheritance diagram for LOOP:

DAG

Detailed Description

This class represent cyclic data dependence graphs of simple loops (without branches).

Author:
Sid Touati
It inherits from the LEDA class GRAPH<INFO_NODE, INFO_EDGE>. The attributes of the nodes are of type INFO_NODE, and the attributes of edges are of type INFO_EDGE. It models cyclic data dependence graphs. The implemented LOOP model is described in Loop Model.

All LEDA access, creation and update methods can be used on a LOOP object.

Examples:

dag_example.cpp, gl2vcg.cpp, and loop_example.cpp.

Definition at line 71 of file loop.h.


Public Member Functions

Creation


 LOOP ()
 Default constructor.
void clear ()
 Empty the DAG.
 LOOP (ARCHITECTURE isa)
 Constructs an empty LOOP object encapsulating a user-defined generic description of the architecture (ISA).
 ~LOOP ()
Access Operations


int MaxLambda () const
 Returns the maximal iteration edge distance in the loop. Formally equal to $ \max_{e \in E} \lambda(e)$.
int MinLambda () const
 Returns the minimal iteration edge distance in the loop. Formally equal to $ \min_{e \in E} \lambda(e)$.
LEDA::set< edge > flow_from_to (node u, node v) const
 Returns the set of all flow edges (not necessarily through registers) from the source node $ u $ to the destination node $ v $. Formally equal to $ \{ e=(u,v)\in E | e \textrm {is a flow edge} \} $.
LEDA::set< edge > flow_from_to (int id_u, int id_v) const
 Returns the set of all flow edges (not necessarily through registers) from the source node to the destination node. Formally equal to $ \{ e=(u,v)\in E | e \textrm {is a flow edge} \} $.
LEDA::set< edge > flow_reg_from_to (node u, node v) const
 Returns the set of all flow edges through registers from the source node $ u $ to the destination node $ v $. Formally equal to $ \{ e=(u,v)\in E_R \} $.
LEDA::set< edge > flow_reg_from_to (int id_u, int id_v) const
 Returns the set of all flow edges through registers from the source node to the destination node. Formally equal to $ \{ e=(u,v)\in E_R \} $.
LEDA::set< edge > flow_reg_from_to (node u, node v, int t) const
 Returns the set of all flow edges of type $ t $ from the source node $ u $ to the destination node $ v $. Formally equal to $ \{ e=(u,v)\in E_{R,t} \} $.
LEDA::set< edge > flow_reg_from_to (int id_u, int id_v, int t) const
 Returns the set of all flow edges through registers from the source node to the destination node. Formally equal to $ \{ e=(u,v)\in E_R \} $.
int max_dist (node u, node v) const
 Returns the maximal distance between two nodes (in terms of number of iterations). Formally equal to $ \max_{e=(u,v)\in E} \lambda(e)$.
int max_dist (int id_u, int id_v) const
 Returns the maximal iteration distance between two nodes. Formally equal to $ \max_{e=(u,v)\in E} \lambda(e)$.
int max_flow_dist (node u, node v) const
 Returns the maximal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \max_{\textrm{a flow edge } e=(u,v)\in E} \lambda(e)$.
int max_flow_dist (int id_u, int id_v) const
 Returns the maximal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \max_{\textrm{a flow edge } e=(u,v)\in E} \lambda(e)$.
int max_flow_reg_dist (node u, node v) const
 Returns the maximal iteration flow distance through registers between two nodes. Formally equal to $ \max_{e=(u,v)\in E_R} \lambda(e)$.
int max_flow_reg_dist (int id_u, int id_v) const
 Returns the maximal iteration flow distance through registers between two nodes. Formally equal to $ \max_{e=(u,v)\in E_R} \lambda(e)$.
int max_flow_reg_dist (node u, node v, int t) const
 Returns the maximal iteration flow distance through registers of type t between two nodes. Formally equal to $ \max_{e=(u,v)\in E_{R,t}} \lambda(e)$.
int max_flow_reg_dist (int id_u, int id_v, int t) const
 Returns the maximal iteration flow distance through registers between two nodes. Formally equal to $ \max_{e=(u,v)\in E_{R,t}} \lambda(e)$.
int min_dist (node u, node v) const
 Returns the minimal iteration distance between two nodes. Formally equal to $ \min_{e=(u,v)\in E} \lambda(e)$.
int min_dist (int id_u, int id_v) const
 Returns the minimal iteration distance between two nodes. Formally equal to $ \max_{e=(u,v)\in E} \lambda(e)$.
int min_flow_dist (node u, node v) const
 Returns the minimal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \min_{{\textrm a flow edge }e=(u,v)\in E} \lambda(e)$.
int min_flow_dist (int id_u, int id_v) const
 Returns the minimal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \max_{\textrm{a flow edge } e=(u,v)\in E} \lambda(e)$.
int min_flow_reg_dist (node u, node v) const
 Returns the minimial iteration flow distance through registers between two nodes. Formally equal to $ \min_{e=(u,v)\in E_R} \lambda(e)$.
int min_flow_reg_dist (int id_u, int id_v) const
 Returns the minimal iteration flow distance through registers between two nodes. Formally equal to $ \min_{e=(u,v)\in E_R} \lambda(e)$.
int min_flow_reg_dist (node u, node v, int t) const
 Returns the minimial iteration flow distance through registers of type t between two nodes. Formally equal to $ \min_{e=(u,v)\in E_{R,t}} \lambda(e)$.
int min_flow_reg_dist (int id_u, int id_v, int t) const
 Returns the minimal iteration flow distance through registers of type t between two nodes. Formally equal to $ \min_{e=(u,v)\in E_{R,t}} \lambda(e)$.
LEDA::rational CRITICAL_CYCLE () const
 Returns the ratio of the critical cycle of the loop.
LEDA::rational CRITICAL_CYCLE (LEDA::list< edge > &el) const
int lambda (edge e) const
 Returns the distance $ \lambda(e) $ of the edge $ e $ (in terms of number of iterations).
Update Operations


void copy (const LOOP &G2)
 Duplicates a LOOP.
void copy (const LOOP &G2, node_map< node > &mn, edge_map< edge > &me)
 Duplicates a LOOP.
void build_internal_structures ()
 Build internal data structures for the LOOP object.
void set_lambda (edge e, int l)
 Sets a distance $ \lambda(e) \ge 0 $ (in terms of number of iterations) to the edge $ e $ .
void write_to_vcg (const char *filename) const
 Exports the LOOP DDG to a vcg file in order to be visualized with the xvcg tool. For more information about xvcg, see http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html The user can navigate using vcg on all DDG attrbutes (types of edges, opcodes, etc.).
void write_to_vcg (const char *filename, int t) const
 Exports the LOOP DDG to a vcg file in order to be visualized with the xvcg tool. This function considers one register type.
void write_to_gl (const char *filename) const
 Exports the LOOP to a gl file. If multiple registers types exist, they are all considered as the same type.
void write_to_gl (const char *filename, int regtype_id) const
 Exports the LOOP to a gl file considering one register type.
bool read_from_gl (const char *filename, int regtype_id)
 Imports a DDG loop from a gl file. In case of multiple registers types, this function allows to considere one of them.
bool read_from_gl (const char *filename)
 Imports a DDG loop from a gl file.
void write_to_xml (const char *filename) const
 Exports the LOOP to a leda XML format. .
bool read_from_xml (const char *filename)
 Imports the LOOP from an XML file.
bool check ()
 A simple check method that returns true if the DAG object seems ok. False otherwise.
bool check (int regtype_id)
 A simple check method that returns true if the DAG object seems ok for the specified register type. False otherwise.
Access Operations


LEDA::set< edge > edges_from_to (node u, node v) const
 Returns the set of all edges from the source node $ u $ to the destination node $ v $.
LEDA::set< edge > edges_from_to (int id_u, int id_v) const
 Returns the set of all edges from the source node to the destination node.
int LongestPath () const
 Returns the value of the longest path of the DAG.
int LongestPath (LEDA::list< node > &nl) const
 Returns the value of the longest path of the DAG.
int LongestPath (list< edge > &el) const
 Returns the value of the longest path of the DAG.
int CriticalPath ()
 This is an alias of the method DAG::LongestPath(). It returns the value of the longest (critical) path.
int CriticalPath (LEDA::list< node > &nl)
 Returns the value of the longest (critical) path.
int CriticalPath (LEDA::list< edge > &el)
 Returns the value of the longest (critical) path.
int LongestPathTo (node) const
 Returns the value of the longest path from the top of the DAG (sources) up to a node given as argument.
int LongestPathFrom (node) const
 Returns the value of the longest path from a node given as argument to the bottom the DAG (sinks).
int ShortestPathTo (node) const
 Returns the value of the shortest path from the top of the DAG (sources) up to a node given as argument.
int ShortestPathFrom (node) const
 Returns the value of the shortest path from a node given as argument to the bottom the DAG (sinks).
int lp (node u, node v) const
 Returns the value of the longest path from a node $ u $ to a node $ v $ given as arguments*.
LEDA::set< node > get_down (node u) const
 Returns the set $ \downarrow u$ (the set of all descending nodes)., see Notation and Definitions on DAGs.
LEDA::set< node > get_up (node u) const
 Returns the set $ \uparrow u $.(the set of all ascenfing nodes), see Notation and Definitions on DAGs.
LEDA::set< node > get_parents (node u) const
 Returns the set $ \Gamma^+_G(u) $ (set of children), see Notation and Definitions on DAGs.
LEDA::set< node > get_children (const node u) const
 Returns the set $ \Gamma^-_G(u) $ (set of parents), see Notation and Definitions on DAGs.
node node_with_id (int i) const
 Returns the node with the integer identifier given as argument.
node node_with_name (std::string name) const
 Returns the node with the name given as argument.
bool is_value (node n) const
 Returns true if the node is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).
bool is_value (int i, int t) const
 Returns true if the node defined by its indentifier is an instruction writing into a register of type t (i.e. if it belongs to the $ {V_R,t} $ set).
bool is_value (node n, int t) const
 Returns true if the node is an instruction writing into a register of type t (i.e. if it belongs to the $ V_{R,t} $ set).
bool is_value (int i) const
 Returns true if the node defined by its indentifier is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).
bool is_flow (edge e) const
 Returns true if the edges is a flow dependence (not necessarily through registers).
bool is_flow_reg (edge e) const
 Returns true if the edges is a flow dependence through a register. This is the case of a flow edge having a source writing into a register.
bool is_flow_reg (edge e, int t) const
 Returns true if the edges is a flow dependence through a register of type t. This is the case of a flow edge having a source writing into a register.
int get_register_type_id (edge e) const
 Returns the register type of a flow edge.
DDG::edge_type etype (edge e) const
 Returns the type of the edge $ e $. (flow, serial, antidep, ...).
set< node > get_V_R () const
 Returns the set $ V_R \subseteq V $ of instructions (nodes) writing into registers.
set< node > get_V_R (int t) const
 Returns the set $ V_ {R,t}\subseteq V $ of instructions (nodes) writing into registers of type t (given by its id).
LEDA::list
< REGISTER_TYPES > 		T () const
LEDA::set< edge > get_E_R () const
 Returns the set $ E_R \subseteq E $ of flow dependence edges through registers.
LEDA::set< edge > get_E_R (int t) const
 Returns the set $ E_{R,t} \subseteq E $ of flow dependence edges through registers of type t (given by its id).
LEDA::set< node > get_Sources () const
 Returns the set of nodes which are the sources of the DAG.
LEDA::set< node > get_Targets () const
 Returns the set of nodes which are the targetsof (sinks) of the DAG.
LEDA::set< node > get_Cons (node u) const
 Returns the set of consumers of a node.
LEDA::set< node > get_Cons (node u, int id_regtype) const
 Returns the set of consumers of a node writing inside a register of a given type.
LEDA::set< int > get_Sources_id () const
 Returns the set of nodes identifiers which are the sources of the DAG.
LEDA::set< int > get_Targets_id () const
 Returns the set of nodes identifiers which are the targetsof (sinks) the DAG.
LEDA::set< int > all_nodes_id ()
 Returns the set of nodes identifiers.
int source_id (edge e) const
 Returns the integer identifier of the edge source.
int target_id (edge e) const
 Returns the integer identifier of the edge target.
ARCHITECTURE get_ISA () const
 Returns the ARCHITECTURE of the DAG.
int delta (edge e) const
 Returns the latency $ \delta(e) $ of the edge $ e $.
int latency (node n) const
 Returns the latency $ latency(n) $ of the generic instruction of the node $ n $.
int delta_r (node n) const
 Returns the reading latency $ \delta_r(n) $ of the node $ n $.
int delta_r (int idn) const
 Returns the reading latency $ \delta_r(idn) $ of the node given by its id.
int delta_w (node n) const
 Returns the writing latency $ \delta_w(n) $ of the node $ n $.
int delta_w (int idn) const
 Returns the writing latency $ \delta_w(idn) $ of the node given by its id.
int delta_w (node n, int regtype_id) const
 Returns the writing latency $ \delta_{w,t}(n) $ of the node $ n $.
int delta_w (int idn, int regtype_id) const
 Returns the writing latency $ \delta_{w,t}(idn) $ of the node given by its id.
int id (node n) const
 Returns the integer identifier of the node $ n $.
INSTRUCTIONS_TYPES instruction_type (node n) const
 Returns an INSTRUCTIONS_TYPES object attached to the node $ n $.
INSTRUCTIONS_TYPES instruction_type (int id) const
 Returns an INSTRUCTIONS_TYPES object attached to the node given by its $ id $.
std::string get_string_attribute (node n) const
 Returns the textual attribute of the node $ n $.
const INFO_NODE & inf (node v) const
 Returns the information of node $ v $.
const INFO_EDGE & inf (edge e) const
 Returns the information of node $ e $.
const INFO_NODE & operator[] (node v) const
 Returns a reference to the information of $ v $.
INFO_NODE & operator[] (node v)
const INFO_EDGE & operator[] (edge e) const
 Returns a reference to the information of $ e $.
INFO_EDGE & operator[] (edge e)
int outdeg (node v) const
 Returns the number of edges leaving to node $ v $.
int indeg (node v) const
 Returns the number of edges entering $ v $.
int degree (node v) const
 Returns $ outdeg(v) + indeg(v) $.
node source (edge e) const
 Returns the source node of edge $ e $.
node target (edge e) const
 Returns the target node of edge $ e $.
node opposite (node v, edge e) const
 Returns $ target(e) $ if $ v = source(e) $ and $ source(e) $ otherwise.
node opposite (edge e, node v) const
 Returns $ target(e) $ if $ v = source(e) $ and $ source(e) $ otherwise.
int number_of_nodes () const
 Returns the number of nodes in the DAG.
int number_of_edges () const
 Returns the number of edges in the DAG.
const LEDA::list
< node > & 		all_nodes () const
 Returns the list of all nodes in the DAG.
const LEDA::list
< edge > & 		all_edges () const
 Returns the list of all edges in the DAG.
LEDA::list< edge > out_edges (node v) const
 Returns the list of edges leaving the node $ v $.
LEDA::list< edge > in_edges (node v) const
 Returns the list of edges entering the node $ v $.
node first_node () const
 Returns the first node in the DAG.
node last_node () const
 Returns the last node in the DAG.
node choose_node () const
 Returns a random node of the DAG (nil if empty).
node succ_node (node v) const
 Returns the successor of node $ v $ (nil if it does not exist).
node pred_node (node v) const
 Returns the predecessor of node $ v $ (nil if it does not exist).
edge first_edge () const
 Returns the first edge in the DAG.
edge last_edge () const
 Returns the last edge in the DAG.
edge choose_edge () const
 Returns a random edge of the DAG (nil if empty).
edge succ_edge (edge e) const
 Returns the successor of edge $ e $ (nil if it does not exist).
edge pred_edge (edge e) const
 Returns the predecessor of edge $ e $ (nil if it does not exist).
bool empty () const
 Returns true if the DAG is empty.
bool member (node v) const
 Returns true if the node $ v $ belongs to the DAG.
bool member (edge e) const
 Returns true if the edge $ e $ belongs to the DAG.
bool is_hidden (edge e) const
 Returns true if $ e $ is hidden, false otherwise. See DAG::hide_edge(edge e).
bool is_hidden (node v) const
 Returns true if $ v $ is hidden, false otherwise. See DAG::hide_node(node v).
LEDA::list< edge > hidden_edges () const
 Returns the list of all hidden edges.
LEDA::list< node > hidden_nodes () const
 Returns the list of all hidden nodes.
int max_delta (node u, node v) const
 Returns the maximal edge latency between to nodes, i.e., $ \max_{e=(u,v)} \delta(e) $.
int max_delta (int u, int v) const
 Returns the maximal edge latency between to nodes (given by their ids), i.e., $ \max_{e=(u,v)} \delta(e) $.
int min_delta (node u, node v) const
 Returns the minimal edge latency between to nodes, i.e., $ \min_{e=(u,v)} \delta(e) $.
int min_delta (int u, int v) const
 Returns the minimal edge latency between to nodes (given by their ids), i.e., $ \min_{e=(u,v)} \delta(e) $.
INSTRUCTIONS_TYPES search_instruction_type (const std::string opcode) const
 Looks for the instruction type (inside the DAG ISA) that has the opcode given as argument. If not found, it returns an INSTRUCTIONS_TYPES object with opcode_id equal to -1.
INSTRUCTIONS_TYPES search_instruction_type (int opcode_id) const
 Looks for the instruction type (inside the DAG ISA) that has the opcode id given as argument. Returns NULL if not found. If not found, it returns an INSTRUCTIONS_TYPES object with opcode_id equal to -1.
NodeFlag node_flag (node n) const
 Returns the node flag of n.
Update Operations
Returns the list of register types of the ISA of the DAG. The ISA object should be attached to the DAG before calling this function. See the DAG construtor method, or the DDG:DAG:set_ISA method. LEDA::list<REGISTER_TYPES> T() const ;

/**

int new_node (int it_id)
 Creates a new node.
int new_node (int it_id, std::string text_inst)
 Creates a new node.
int new_node (int it_id, int n_id)
 Creates a new node.
int new_node (int it_id, int n_id, std::string text_inst)
 Creates a new node.
void del_node (node)
 Deletes the node given as argument.
void del_node (int node_id)
 Deletes the node whose id is given as argument.
edge new_edge (int s, int t, INFO_EDGE ie)
 Creates a new edge.
edge new_edge (node s, node t, INFO_EDGE ie)
 Creates a new edge.
void del_edge (edge e)
 Deletes the edge given as argument.
void copy (const DAG &G2)
 Duplicates a DAG.
void copy (const DAG &G2, node_map< node > &mn, edge_map< edge > &me)
 Duplicates a DAG.
void get_loop_body (const LOOP &G2, node_map< node > &mn, edge_map< edge > &me)
 Retrieves a loop body.
void get_loop_body (const LOOP &G2)
 Retrieves a loop body.
void set_ISA (ARCHITECTURE isa)
 Sets the set of generic instruction types (ISA) encapsulated inside the DAG.
void set_delta (edge e, int l)
 Sets a latency $ \delta(e) $ to the edge $ e $.
void set_instruction_type (node n, int it_id)
 Sets an INSTRUCTIONS_TYPES object (given by its opcode id) attached to the node $ n $.
void set_string_attribute (node u, std::string inst_text)
 Sets a textual attribute to the node $ n $. For instance, this textual attribute can be used to associate the textual code of the instruction.
void set_etype (edge e, DDG::edge_type et)
 Sets an edge type (flow, serial, antidep, etc.).
void hide_edge (edge e)
 Removes temporarily the edge $ e $. The edge can be restored by DAG::restore_edge(edge e).
void hide_edges (const LEDA::list< edge > &el)
 Hides all edges in the list el.
void restore_edge (edge e)
 Restores the hidden edge $ e $ .
void restore_edges (const LEDA::list< edge > &el)
 Restores all edges in the list el.
void restore_all_edges ()
 Restores all hidden edges.
void hide_node (node v)
 Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node v).
void hide_node (node v, LEDA::list< edge > &h_edges)
 Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node n).
void hide_nodes (const LEDA::list< node > &nl)
 Hides all nodes in the list nl.
void restore_node (node v)
 Restores the hidden node $ v $. Note that no edge adjacent to v that was hidden by G.hide_node(v) is restored by this operation.
void restore_all_nodes ()
 Restores all hidden nodes. Note that no adjacent edges to the hidden nodes are restored by this operation.
void del_all_edges ()
 Deletes all edges from the DAG.
void move_edge (edge e, node v, node w)
 Moves the edge $ e $ to source $ v $ and target $ w $.
void set_node_flag (node n, const NodeFlag theValue)
 Set the flag of the node n.
Import and Export Methods


void write_to_xml (const char *filename)
 Exports the DAG to an XML description.

Protected Attributes

unsigned int cpt_nodes
LEDA::d_array< int,
LEDA::set< node > > 		V_R
LEDA::d_array< int,
LEDA::set< edge > > 		E_R
ARCHITECTURE ISA
node_array< set< node > > down
node_array< set< node > > up
node_array< int > longuest_path_from
node_array< int > longuest_path_to
node_matrix< int > lp_array
node_array< int > shortest_path_from
node_array< int > shortest_path_to
set< node > Sources
set< node > Targets
map2< node, int, set
< node > > 		Cons
LEDA::map< int, node > node_index_table

Constructor & Destructor Documentation

LOOP (  ) 

Default constructor.

Creates an empty LOOP object. A default ISA is assumed.

LOOP ( ARCHITECTURE  isa  ) 

Constructs an empty LOOP object encapsulating a user-defined generic description of the architecture (ISA).

Parameters:
[in] isa ISA object, see ISA_xml.
Exceptions:
InvalidISADesc When the ISA description file is corrupted, and object of class DDG::InvalidISADesc is thrown.

Member Function Documentation

LEDA::set<edge> flow_from_to ( int  id_u,
int  id_v 
) const

Returns the set of all flow edges (not necessarily through registers) from the source node to the destination node. Formally equal to $ \{ e=(u,v)\in E | e \textrm {is a flow edge} \} $.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.

LEDA::set<edge> flow_reg_from_to ( node  u,
node  v 
) const

Returns the set of all flow edges through registers from the source node $ u $ to the destination node $ v $. Formally equal to $ \{ e=(u,v)\in E_R \} $.

Precondition:
A unique register type exists.
Exceptions:
NonUniqueRegisterType 

LEDA::set<edge> flow_reg_from_to ( int  id_u,
int  id_v 
) const

Returns the set of all flow edges through registers from the source node to the destination node. Formally equal to $ \{ e=(u,v)\in E_R \} $.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
Precondition:
A unique register type exists.
Exceptions:
NonUniqueRegisterType 

LEDA::set<edge> flow_reg_from_to ( int  id_u,
int  id_v,
int  t 
) const

Returns the set of all flow edges through registers from the source node to the destination node. Formally equal to $ \{ e=(u,v)\in E_R \} $.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
[in] t considered register type

int max_dist ( node  u,
node  v 
) const

Returns the maximal distance between two nodes (in terms of number of iterations). Formally equal to $ \max_{e=(u,v)\in E} \lambda(e)$.

Warning:
Returns -MAXINT if no edge exists between u and v.

int max_dist ( int  id_u,
int  id_v 
) const

Returns the maximal iteration distance between two nodes. Formally equal to $ \max_{e=(u,v)\in E} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
Warning:
Returns 0 if no edge exists between u and v.

int max_flow_dist ( node  u,
node  v 
) const

Returns the maximal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \max_{\textrm{a flow edge } e=(u,v)\in E} \lambda(e)$.

Warning:
Returns -MAXINT if no edge exists between u and v.

int max_flow_dist ( int  id_u,
int  id_v 
) const

Returns the maximal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \max_{\textrm{a flow edge } e=(u,v)\in E} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
Warning:
Returns -MAXINT if no edge exists between u and v.

int max_flow_reg_dist ( node  u,
node  v 
) const

Returns the maximal iteration flow distance through registers between two nodes. Formally equal to $ \max_{e=(u,v)\in E_R} \lambda(e)$.

Warning:
Returns -MAXINT if no edge exists between u and v.
Precondition:
A unique register type exists in the ISA
Exceptions:
NonUniqueRegisterType 

int max_flow_reg_dist ( int  id_u,
int  id_v 
) const

Returns the maximal iteration flow distance through registers between two nodes. Formally equal to $ \max_{e=(u,v)\in E_R} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
Warning:
Returns -MAXINT if no edge exists between u and v.
Precondition:
A unique register type exists in the ISA
Exceptions:
NonUniqueRegisterType 

int max_flow_reg_dist ( node  u,
node  v,
int  t 
) const

Returns the maximal iteration flow distance through registers of type t between two nodes. Formally equal to $ \max_{e=(u,v)\in E_{R,t}} \lambda(e)$.

Warning:
Returns -MAXINT if no edge exists between u and v.

int max_flow_reg_dist ( int  id_u,
int  id_v,
int  t 
) const

Returns the maximal iteration flow distance through registers between two nodes. Formally equal to $ \max_{e=(u,v)\in E_{R,t}} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
[in] t considered register type
Warning:
Returns -MAXINT if no edge exists between u and v.

int min_dist ( node  u,
node  v 
) const

Returns the minimal iteration distance between two nodes. Formally equal to $ \min_{e=(u,v)\in E} \lambda(e)$.

Warning:
Returns +MAXINT if no edge exists between u and v.

int min_dist ( int  id_u,
int  id_v 
) const

Returns the minimal iteration distance between two nodes. Formally equal to $ \max_{e=(u,v)\in E} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
Warning:
Returns +MAXINT if no edge exists between u and v.

int min_flow_dist ( node  u,
node  v 
) const

Returns the minimal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \min_{{\textrm a flow edge }e=(u,v)\in E} \lambda(e)$.

Warning:
Returns +MAXINT if no edge exists between u and v.

int min_flow_dist ( int  id_u,
int  id_v 
) const

Returns the minimal iteration flow distance (not necessarily through registers) between two nodes. Formally equal to $ \max_{\textrm{a flow edge } e=(u,v)\in E} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
Warning:
Returns +MAXINT if no edge exists between u and v.

int min_flow_reg_dist ( node  u,
node  v 
) const

Returns the minimial iteration flow distance through registers between two nodes. Formally equal to $ \min_{e=(u,v)\in E_R} \lambda(e)$.

Warning:
Returns +MAXINT if no edge exists between u and v.

int min_flow_reg_dist ( int  id_u,
int  id_v 
) const

Returns the minimal iteration flow distance through registers between two nodes. Formally equal to $ \min_{e=(u,v)\in E_R} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
Warning:
Returns +MAXINT if no edge exists between u and v.

int min_flow_reg_dist ( node  u,
node  v,
int  t 
) const

Returns the minimial iteration flow distance through registers of type t between two nodes. Formally equal to $ \min_{e=(u,v)\in E_{R,t}} \lambda(e)$.

Warning:
Returns +MAXINT if no edge exists between u and v.

int min_flow_reg_dist ( int  id_u,
int  id_v,
int  t 
) const

Returns the minimal iteration flow distance through registers of type t between two nodes. Formally equal to $ \min_{e=(u,v)\in E_{R,t}} \lambda(e)$.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.
[in] t considered register type
Warning:
Returns +MAXINT if no edge exists between u and v.

LEDA::rational CRITICAL_CYCLE (  )  const

Returns the ratio of the critical cycle of the loop.

The critical cycle of a loop is defined by the one maximizing the ratio $ \max_{C\textrm{ a cycle}} \frac{\sum_{e \in C} \delta(e)} {\sum_{e \in C} \lambda(e)}$. Contrary to what it is usually implemented, this method can detect null cycles, i.e., cycles $ C $ such as $ \sum_{e \in C} \delta(e) =0 $ and $ \sum_{e \in C} \lambda(e) \ge 0 $. This method returns -1 if no cycle exists in the graph.

Precondition:
All cycles should have nonnegative distance, that is $ \forall C \textrm{ a cycle in } G, \sum_{e \in C} \lambda(e)\ge 0 $. Note that the edges may have nonpositive latencies ($ \delta(e) $ may be positive or negative).
Remarks:
  • The implemented algorithm is the one published by E.L Lawler in Periodic Optimization (1972, Springer Verlag). Its complexity is $ O(n\times m \times \log(n)) $, where $ n $ is the number of nodes and $ m $ is the number of edges.
  • Since the original algorithm does not try to detect null cycles, we added our own implementation mechanism to do it.
Examples:
loop_example.cpp.

LEDA::rational CRITICAL_CYCLE ( LEDA::list< edge > &  el  )  const

Returns the ratio of the critical cycle of the loop and gives its list of edges.

A critical cycle in a loop data dependence graph is defined as the one which maximizes the ratio $ \max_{C\textrm{ a cycle}} \frac{\sum_{e \in C} \delta(e)} {\sum_{e \in C} \lambda(e)} $. Contrary to what it is usually implemented, this method can detect null cycles, i.e., cycles $ C $ such as $ \sum_{e \in C} \delta(e) =0 $ and $ \sum_{e \in C} \lambda(e) \ge 0 $. This method returns -1 if no cycle exists in the graph.

Parameters:
[out] el Contains the list of edges that belongs to the critical cycle.
Warning:
If the critical cycle has a null latency ($ \sum_{e \in C} \delta(e) =0 $) and a nonnegative distance $ \sum_{e \in C} \lambda(e) > 0 $, then the output list of edges nl is empty and the method returns zero. However, our method is able to build the list of edges belonging to a critical cycle if $ \sum_{e \in C} \delta(e) = \sum_{e \in C} \lambda(e) =0$.
Precondition:
All cycles should have nonnegative distance, that is $ \forall C \textrm{ a cycle in } G, \sum_{e \in C} \lambda(e)\ge 0 $. Note that the edges may have nonpositive latencies ($ \delta(e) $ may be positive or negative).
Remarks:
  • The implemented algorithm is the one published by E.L Lawler in Periodic Optimization (1972, Springer Verlag). Its complexity is $ O(n\times m \times \log(n)) $, where $ n $ is the number of nodes and $ m $ is the number of edges.
  • Since the original algorithm does not try to detect null cycles, we added our own implementation mechanism to do it.

void copy ( const LOOP &  G2  ) 

Duplicates a LOOP.

Parameters:
[in] G2 The current LOOP object will contain a duplicated copy of G2.
Examples:
loop_example.cpp.

void copy ( const LOOP &  G2,
node_map< node > &  mn,
edge_map< edge > &  me 
)

Duplicates a LOOP.

Parameters:
[in] G2 The current LOOP object will contain a duplicated copy of G2.
[out] mn mn is a mapping from the set of nodes of G2 to the set of nodes of the current LOOP. $ \forall u\in G_2, mn[u] $ contains the node belonging to the current LOOP corresponding to its original copy $ u \in G_2 $.
[out] me me is a mapping from the set of edges of G2 to the set of edges of the current LOOP. $ \forall e \in G_2, me[e] $ contains the edge belonging to the current LOOP corresponding to its original copy $ e \in G_2 $.
Remarks:
LOOP::build_internal_structures() is called inside this method.

void build_internal_structures (  ) 

Build internal data structures for the LOOP object.

For internal information consistency, this function member should be called after update operations such as LOOP::new_node(INSTRUCTIONS_TYPES it), LOOP::new_edge(INFO_EDGE), etc. This method compute some internal information returned by other methods (the set $ V_R $, the set of consumers per value, etc.). If the LOOP object is not modified after calling build_internal_structures(), all its internal information remain consistent. remarks For efficiency, the user can group series of update operations before ultimately calling build_internal_structures()

Reimplemented from DAG.

void write_to_vcg ( const char *  filename  )  const

Exports the LOOP DDG to a vcg file in order to be visualized with the xvcg tool. For more information about xvcg, see http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html The user can navigate using vcg on all DDG attrbutes (types of edges, opcodes, etc.).

Import and Export Methods

Parameters:
[in] filename the file name of the DDG in vcg format

Reimplemented from DAG.

Examples:
gl2vcg.cpp, and loop_example.cpp.

void write_to_vcg ( const char *  filename,
int  t 
) const

Exports the LOOP DDG to a vcg file in order to be visualized with the xvcg tool. This function considers one register type.

Parameters:
[in] filename the file name of the DDG in vcg format
[in] t the considered register type For more information about xvcg, see http://rw4.cs.uni-sb.de/users/sander/html/gsvcg1.html The user can navigate using vcg on all DDG attrbutes (types of edges, opcodes, etc.)

Reimplemented from DAG.

void write_to_gl ( const char *  filename  )  const

Exports the LOOP to a gl file. If multiple registers types exist, they are all considered as the same type.

Parameters:
[in] filename the file name of the DDG in gl format

Reimplemented from DAG.

void write_to_gl ( const char *  filename,
int  regtype_id 
) const

Exports the LOOP to a gl file considering one register type.

Parameters:
[in] filename the file name of the DDG in gl format
[in] regtype_id All flow_reg edges through this register type are output to gl as flow_reg. Other flow_reg edges are output as "serial" edges.

Reimplemented from DAG.

bool read_from_gl ( const char *  filename,
int  regtype_id 
)

Imports a DDG loop from a gl file. In case of multiple registers types, this function allows to considere one of them.

Parameters:
[in] filename the file name of the DDG in gl format
[in] regtype_id The flow_reg edges in the gl file are considered as flow_reg through this register type.
Returns:
true if OK
Remarks:

Reimplemented from DAG.

Examples:
gl2vcg.cpp.

bool read_from_gl ( const char *  filename  ) 

Imports a DDG loop from a gl file.

Parameters:
[in] filename the file name of the DDG in gl format
Returns:
true if OK.
Precondition:
A unique register type should exist in the architecture.

Before reading a LOOP from a gl file, it is assumed that the ISA of the LOOP defines all the opcodes ids of the nodes as present in the gl file. The constructor DDG::LOOP(ARCHITECTURE) defines a LOOP with a user defined ISA, otherwise a default ISA is assumed, see ISA_xml.

Remarks:

Reimplemented from DAG.

bool read_from_xml ( const char *  filename  ) 

Imports the LOOP from an XML file.

Returns:
true if ok.

Reimplemented from DAG.

Examples:
dag_example.cpp, and loop_example.cpp.

LEDA::set<edge> edges_from_to ( int  id_u,
int  id_v 
) const [inherited]

Returns the set of all edges from the source node to the destination node.

Parameters:
[in] id_u The integer identifier of the source node.
[in] id_v The integer identifier of the destination node.

int LongestPath ( LEDA::list< node > &  nl  )  const [inherited]

Returns the value of the longest path of the DAG.

Parameters:
[out] nl Contains the list of nodes belonging to the computed longest path.
Warning:
Despite the unicity of its value, the longest path in a DAG may not be unique.

int LongestPath ( list< edge > &  el  )  const [inherited]

Returns the value of the longest path of the DAG.

Parameters:
[out] el Contains the list of edges belonging to the computed longest path.
Warning:
Despite the unicity of its value, the longest path in a DAG may not be unique.

int CriticalPath ( LEDA::list< node > &  nl  )  [inherited]

Returns the value of the longest (critical) path.

Parameters:
[out] nl Contains the list of nodes belonging to the computed longest path.
Warning:
The longest path in a DAG may not be unique

int CriticalPath ( LEDA::list< edge > &  el  )  [inherited]

Returns the value of the longest (critical) path.

Parameters:
[out] el Contains the list of edges belonging to the computed longest path.
Warning:
The longest path in a DAG may not be unique

int lp ( node  u,
node  v 
) const [inherited]

Returns the value of the longest path from a node $ u $ to a node $ v $ given as arguments*.

Precondition:
Such path exists

node node_with_id ( int  i  )  const [inherited]

Returns the node with the integer identifier given as argument.

Exceptions:
IllegalAccessNode If the node id does not exist, or if the node is hidden, then an exception of type DDG:IllegalAccessNode is thrown.

Referenced by DAG::max_delta(), and DAG::min_delta().

node node_with_name ( std::string  name  )  const [inherited]

Returns the node with the name given as argument.

Exceptions:
IllegalAccessNode If the node id does not exist, or if the node is hidden.

bool is_value ( node  n  )  const [inherited]

Returns true if the node is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).

Precondition:
There is a unique register type in the architecture
Exceptions:
NonUniqueRegisterType 

bool is_value ( int  i  )  const [inherited]

Returns true if the node defined by its indentifier is an instruction writing into a register (i.e. if it belongs to the $ V_R $ set).

Precondition:
There is a unique register type in the architecture
Exceptions:
NonUniqueRegisterType 

bool is_flow_reg ( edge  e  )  const [inline, inherited]

Returns true if the edges is a flow dependence through a register. This is the case of a flow edge having a source writing into a register.

Precondition:
There is a unique register type in the architecture
Exceptions:
NonUniqueRegisterType 

Definition at line 383 of file DAG.h.

References ARCHITECTURE::get_the_unique_register_type_id(), DAG::inf(), INFO_EDGE::is_flow_reg(), and DAG::ISA.

int get_register_type_id ( edge  e  )  const [inherited]

Returns the register type of a flow edge.

Precondition:
The edge should be a flow through register (flowdep_reg)

set<node> get_V_R (  )  const [inline, inherited]

Returns the set $ V_R \subseteq V $ of instructions (nodes) writing into registers.

Precondition:
a unique register type should exist in the architecture
Exceptions:
NonUniqueRegisterType 
Examples:
dag_example.cpp, loop_example.cpp, and RS_example.cpp.

Definition at line 408 of file DAG.h.

References ARCHITECTURE::get_the_unique_register_type_id(), DAG::ISA, and DAG::V_R.

set<node> get_V_R ( int  t  )  const [inline, inherited]

Returns the set $ V_ {R,t}\subseteq V $ of instructions (nodes) writing into registers of type t (given by its id).

Exceptions:
BadRegType 

Definition at line 414 of file DAG.h.

References ARCHITECTURE::exist_register_type_id(), DAG::ISA, and DAG::V_R.

LEDA::set<edge> get_E_R (  )  const [inline, inherited]

Returns the set $ E_R \subseteq E $ of flow dependence edges through registers.

Precondition:
A unique register type must exist.
Exceptions:
NonUniqueRegisterType 
Examples:
loop_example.cpp.

Definition at line 426 of file DAG.h.

References DAG::E_R, ARCHITECTURE::get_the_unique_register_type_id(), and DAG::ISA.

LEDA::set<edge> get_E_R ( int  t  )  const [inline, inherited]

Returns the set $ E_{R,t} \subseteq E $ of flow dependence edges through registers of type t (given by its id).

Exceptions:
BadRegType 

Definition at line 432 of file DAG.h.

References DAG::E_R, ARCHITECTURE::exist_register_type_id(), and DAG::ISA.

LEDA::set<node> get_Cons ( node  u  )  const [inline, inherited]

Returns the set of consumers of a node.

Precondition:
A unique register type should exist in the architecture.
Exceptions:
NonUniqueRegisterType 

Definition at line 450 of file DAG.h.

References DAG::Cons, ARCHITECTURE::get_the_unique_register_type_id(), and DAG::ISA.

LEDA::set<node> get_Cons ( node  u,
int  id_regtype 
) const [inline, inherited]

Returns the set of consumers of a node writing inside a register of a given type.

Precondition:
id_regtype is an id of register type in the architetcure
Exceptions:
BadRegType 

Definition at line 458 of file DAG.h.

References DAG::Cons, ARCHITECTURE::exist_register_type_id(), and DAG::ISA.

int delta_w ( node  n  )  const [inherited]

Returns the writing latency $ \delta_w(n) $ of the node $ n $.

Precondition:
a unique register type should exist in the architecture
Examples:
dag_example.cpp, and loop_example.cpp.

int delta_w ( int  idn  )  const [inherited]

Returns the writing latency $ \delta_w(idn) $ of the node given by its id.

Precondition:
a unique register type should exist in the architecture

int new_node ( int  it_id  )  [inherited]

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
Returns:
The integer node identifier.
Remarks:
This method assigns a unique inter identifier for the created node.
See also DAG::build_internal_structures().
Examples:
dag_example.cpp.

int new_node ( int  it_id,
std::string  text_inst 
) [inherited]

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
[in] text_inst A textual attribute of the instruction
Returns:
The integer node identifier.
Remarks:
This method assigns a unique inter identifier for the created node.
See also DAG::build_internal_structures().

int new_node ( int  it_id,
int  n_id 
) [inherited]

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
[in] n_id A unique id for the node to create
Returns:
The integer node identifier. Returns -1 if the there exists an node with the input id.
Exceptions:
NonUniqueNodeID if the input node id already exists
Remarks:
This method creates a node with an identifier given as input.
Precondition:
n_id is positive
See also DAG::build_internal_structures().

int new_node ( int  it_id,
int  n_id,
std::string  text_inst 
) [inherited]

Creates a new node.

Parameters:
[in] it_id The id of the INSTRUCTIONS_TYPES object describing the generic instruction of the node
[in] n_id A unique id for the node to create
[in] text_inst A textual attribute of the instruction
Returns:
The integer node identifier.
Exceptions:
NonUniqueNodeID if the input node id already exists
Remarks:
This method creates a node with an identifier given as input.
Precondition:
n_id is positive
See also DAG::build_internal_structures().

void del_node ( node   )  [inherited]

Deletes the node given as argument.

All the edges incident to the deleted node are removed from the DAG too.

void del_node ( int  node_id  )  [inherited]

Deletes the node whose id is given as argument.

All the edges incident to the deleted node are removed from the DAG too.

See also DAG::build_internal_structures().

edge new_edge ( int  s,
int  t,
INFO_EDGE  ie 
) [inherited]

Creates a new edge.

It takes three arguments. If flow dependence, the inserted edge is added to the set $ E_R $.

Parameters:
[in] s The integer identifier of the source node.
[in] t The integer identifier of the destination node.
[in] ie The INFO_EDGE object describing the edge attribute. See also DAG::build_internal_structures().
Examples:
dag_example.cpp.

edge new_edge ( node  s,
node  t,
INFO_EDGE  ie 
) [inherited]

Creates a new edge.

It takes three arguments. If flow dependence, the inserted edge is added to the set $ E_R $.

Parameters:
[in] s The source node.
[in] t The destination node.
[in] ie The INFO_EDGE object describing the edge attribute. See also DAG::build_internal_structures().

void copy ( const DAG &  G2  )  [inherited]

Duplicates a DAG.

Parameters:
[in] G2 The current DAG object will contain a duplicated copy of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the duplicated DAG is guaranteed.
Remarks:
DAG::build_internal_structures() is called inside this method.
Examples:
dag_example.cpp.

void copy ( const DAG &  G2,
node_map< node > &  mn,
edge_map< edge > &  me 
) [inherited]

Duplicates a DAG.

Parameters:
[in] G2 The current DAG object will contain a duplicated copy of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the duplicated DAG is guaranteed.
[out] mn mn is a mapping from the set of nodes of G2 to the set of nodes of the current DAG. $ \forall u\in G_2, mn[u] $ contains the node belonging to the current DAG corresponding to its original copy $ u \in G_2 $.
[out] me me is a mapping from the set of edges of G2 to the set of edges of the current DAG. $ \forall e \in G_2, me[e] $ contains the edge belonging to the current DAG corresponding to its original copy $ e \in G_2 $.
Remarks:
DAG::build_internal_structures() is called inside this method.

void get_loop_body ( const LOOP &  G2,
node_map< node > &  mn,
edge_map< edge > &  me 
) [inherited]

Retrieves a loop body.

Parameters:
[in] G2 The current DAG object will contain the loop body of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the DAG is guaranteed.
[out] mn mn is a mapping from the set of nodes of G2 to the set of nodes of the current DAG. $ \forall u\in G_2, mn[u] $ contains the node belonging to the current DAG corresponding to its original copy $ u \in G_2 $.
[out] me me is a mapping from the set of edges of G2 to the set of edges of the current DAG. $ \forall e \in G_2, me[e] $ contains the edge belonging to the current DAG corresponding to its original copy $ e \in G_2 $.
Remarks:
DAG::build_internal_structures() is called inside this method. The loop body contains the set of all nodes, but the set of edges contains only the edges with null distance: $ \forall e \textrm{ in the loop body}, \lambda(e)=0 $.

void get_loop_body ( const LOOP &  G2  )  [inherited]

Retrieves a loop body.

Parameters:
[in] G2 The current DAG object will contain the loop body of G2. This method will keep the same node ids, same edge and node information, etc. The internal consistency of the duplicated DAG is guaranteed.
Remarks:
DAG::build_internal_structures() is called inside this method. The loop body contains the set of all nodes, but the set of edges contains only the edges with null distance: $ \forall e \textrm{ in the loop body}, \lambda(e)=0 $.

void set_ISA ( ARCHITECTURE  isa  )  [inline, inherited]

Sets the set of generic instruction types (ISA) encapsulated inside the DAG.

Parameters:
[in] isa An ARCHITECTURE object describing a user-defined ISA.
Warning:
It is better to clear the DAG before changing its ISA. If the ISA of a non empty DAG is modified on-the-fly, the successive behavior of the DAG object would be indefined.

Definition at line 886 of file DAG.h.

void set_string_attribute ( node  u,
std::string  inst_text 
) [inherited]

Sets a textual attribute to the node $ n $. For instance, this textual attribute can be used to associate the textual code of the instruction.

Remarks:
  • Currently, a textual attribute is a single textual line. Hence, it should not contain the newline character \n. If they exist, the current implementation replaces them by white spaces.
  • Double quotes characters " should be specialized. They should be written as \" inside the string attribute.

void hide_edge ( edge  e  )  [inherited]

Removes temporarily the edge $ e $. The edge can be restored by DAG::restore_edge(edge e).

Remarks:
A hidden edge does no longer belong to the list of graph edges

void hide_edges ( const LEDA::list< edge > &  el  )  [inherited]

Hides all edges in the list el.

Remarks:
A hidden edge does no longer belong to the list of graph edges

void restore_edge ( edge  e  )  [inherited]

Restores the hidden edge $ e $ .

Warning:
If an endpoint of $ e $ is hidden, an exception occurs.

void restore_edges ( const LEDA::list< edge > &  el  )  [inherited]

Restores all edges in the list el.

Warning:
If an endpoint of an edge is hidden, an exception occurs.

void restore_all_edges (  )  [inherited]

Restores all hidden edges.

Warning:
If an endpoint of an edge is hidden, an exception occurs.
Examples:
dag_example.cpp, and loop_example.cpp.

void hide_node ( node  v  )  [inherited]

Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node v).

Remarks:
A hidden node does no longer belong to the list of graph nodes
Examples:
dag_example.cpp, and loop_example.cpp.

void hide_node ( node  v,
LEDA::list< edge > &  h_edges 
) [inherited]

Removes temporarily the node $ v $. Leaving and entering edges are also hidden. The node can be restored by DAG::restore_node(node n).

Parameters:
[in] v the node to hide.
[out] h_edges the list of leaving and entering edges hidden in consequence of hiding the node $ v $.
Remarks:
A hidden node does no longer belong to the list of graph nodes

void hide_nodes ( const LEDA::list< node > &  nl  )  [inherited]

Hides all nodes in the list nl.

Remarks:
A hidden node does no longer belong to the list of graph nodes

void del_all_edges (  )  [inherited]

Deletes all edges from the DAG.

See also DAG::empty();

void write_to_xml ( const char *  filename  )  [inherited]

Exports the DAG to an XML description.

All DDG attributes are included into this XML graph format.

January 2009, by Sid Touati (Copyright INRIA and University of Versailles)