Graph Drawing Toolkit
#include <rm3_dire_graph.h>
Definition at line 48 of file rm3_dire_graph.h.
| dire_graph::dire_graph | ( | ) |
Empty constructor.
| dire_graph::dire_graph | ( | const undi_graph & | ) |
Constructor from the undi_graph class.
PRECONDITIONS: all undi_graph-edges must be directed.
| dire_graph& dire_graph::operator= | ( | const undi_graph & | ) |
operator from the undi_graph class
PRECONDITIONS: all undi_graph-edges must be directed
Reimplemented from undi_graph.
Reimplemented in flow_dire_graph.
| gdtnode dire_graph::find_source | ( | ) |
Return a source gdtnode (that is a gdtnode without in-edges) if there exists one, else return NULL_NODE.
| gdtnode dire_graph::find_sink | ( | ) |
Return a sink gdtnode (that is a gdtnode without out-edges) if there exists one, else return NULL_NODE.
| void dire_graph::find_shortest_path | ( | gdtnode | s, | |
| gdt::gdtedge_array< int > & | length, | |||
| gdt::gdtnode_array< int > & | distance, | |||
| gdt::gdtnode_array< gdtedge > & | pred_edge | |||
| ) |
Find a shortest path from gdtnode s to all other nodes: length[e] = length of gdtedge e; distance[v] = distance of the shortest path s-->v; pred_edge[v]= previous gdtedge of the gdtnode v in the shortest path s-->v NOTE: if there is not a path from s to a gdtnode v, distance[v] = INFINITE. This method uses Dijkstra method.
| void dire_graph::find_longest_path | ( | gdtnode | s, | |
| gdt::gdtedge_array< int > & | length, | |||
| gdt::gdtnode_array< int > & | distance, | |||
| gdt::gdtnode_array< gdtedge > & | pred_edge | |||
| ) |
Find a longest path from gdtnode s to all the other nodes: length[e] = length of gdtedge e; distance[v] = distance of the longest path s-->v; pred_edge[v]= previous gdtedge of the gdtnode v in the longest path s-->v; PRECONDITIONS: (1) graph must be acyclic; (2) all nodes must be reacheble starting from gdtnode s;
| void dire_graph::find_path_with_minimum_switches | ( | gdtnode | s, | |
| gdt::gdtnode_array< int > & | switches, | |||
| gdt::gdtnode_array< gdtedge > & | pred_edge, | |||
| visit_direction_type | dir | |||
| ) |
Find a path from the gdtnode s to all the other nodes having the minimum number of swithes nodes, that is the minimum number of nodes in which the direction of the edges is reversed, starting from an outgoing gdtedge of s if dir = OUTGOING, and from an incoming gdtedge of s if dir = INCOMING. A directed path is a path with 0 switches. switches[v] = minimum number of swithces needed to reach v from s; pred_edge[v] = previous gdtedge of v in the path s-->v;
| void dire_graph::find_path_with_minimum_switches | ( | gdtnode | s, | |
| gdtnode | t, | |||
| gdt::gdtnode_array< int > & | switches, | |||
| gdt::gdtnode_array< gdtedge > & | pred_edge | |||
| ) |
Find a path from the gdtnode s to gdtnode t having the minimum number of swithes nodes, that is the minimum number of nodes in which the direction of the edges is reversed. A directed path is a path with 0 switches. switches[v] = minimum number of swithces needs to reach v from s; pred_edge[v] = previous gdtedge of v in the path s-->v;
| void dire_graph::Dijkstra | ( | gdtnode | s, | |
| gdt::gdtedge_array< int > & | length, | |||
| gdt::gdtnode_array< int > & | distance, | |||
| gdt::gdtnode_array< gdtedge > & | pred_edge | |||
| ) |
Find a shortest path from gdtnode s to all other nodes: length[e] = length of gdtedge e; distance[v] = distance of the shortest path s-->v; pred_edge[v]= previous gdtedge of the gdtnode v in the shortest path s-->v NOTE: if there is not a path from s to a gdtnode v, distance[v] = INFINITE.
| gdt::gdtlist<gdtedge> dire_graph::simple_DFS | ( | gdtnode | v, | |
| gdt::gdtnode_array< bool > & | reached, | |||
| gdt::gdtnode_array< gdtedge > & | father, | |||
| gdt::gdtlist< gdtnode > & | order, | |||
| visit_direction_type | dt = OUTGOING | |||
| ) |
Execute a DFS visit of the graph, starting from gdtnode v, and return the list of back edges (if this list is empty, the graph is directed acyclic). reached [v] = true if gdtnode v is visited. father [v] = father gdtedge of v in the DFS visit. order = ordered list of the visited nodes.
| bool dire_graph::is_acyclic | ( | ) |
Return true if the graph is directed acyclic.
| gdt::gdtlist<gdtedge> dire_graph::make_acyclic | ( | ) |
Reverse a minimal number of edges in order to make the graph directed acyclic; the inverted edges are returned
| bool dire_graph::topological_sort | ( | gdtnode | v, | |
| gdt::gdtnode_array< bool > & | reached, | |||
| gdt::gdtlist< gdtnode > & | order | |||
| ) |
Execute a topological sort of the graph, starting from gdtnode v, and return false if it is directed acyclic. reached [v] = true if gdtnode v is visited. order = topological ordered list of the visited nodes.
Insert a new directed gdtedge with start v1 and stop v2, and identifier new_id, and return it.
Reimplemented from undi_graph.
| gdtedge dire_graph::new_edge | ( | gdtnode | v1, | |
| gdtedge | e1, | |||
| gdtnode | v2, | |||
| int | new_id = AUTO_ID, |
|||
| int | dir = gdt::after | |||
| ) |
Insert a new directed gdtedge with start v1 and stop v2, and identifier new_id, and return it. Also the gdtedge is inserted after(before) e1 around v1.
Reimplemented from undi_graph.
| gdtedge dire_graph::new_edge | ( | gdtnode | v1, | |
| gdtnode | v2, | |||
| gdtedge | e2, | |||
| int | new_id = AUTO_ID, |
|||
| int | dir = gdt::after | |||
| ) |
Insert a new directed gdtedge with start v1 and stop v2, and identifier new_id, and return it. Also the gdtedge is inserted after(before) e2 around v2.
| gdtedge dire_graph::new_edge | ( | gdtnode | v, | |
| gdtedge | ev, | |||
| gdtnode | w, | |||
| gdtedge | ew, | |||
| int | new_id = AUTO_ID, |
|||
| int | dir = gdt::after | |||
| ) |
Insert a new directed gdtedge with start v1 and stop v2, and identifier new_id, and return it. Also the gdtedge is inserted after(before) e1 around v1 and after(before) e2 around v2.
Reimplemented from undi_graph.
| void dire_graph::clear | ( | ) |
| void dire_graph::steal_from | ( | undi_graph & | ug | ) |
Make *this with the undi_graph ug internal variables and cut these variables from ug. This method is used to make an undi_graph as a dire_graph, manteining the same internal variables. WARNING: ug has an empty body after this method is applied PRECONDITIONS: all edges of ug must be directed
1.5.3