Heuristic graph bi-partitioning algorithm (Wei-Cheng). More...
#include <GTL/ratio_cut_partition.h>
Inherits: algorithm
This class implements a heuristic graph bi-partitioning algorithm using the ratio cut method proposed by Y. C. Wei and C. K. Cheng in 1991.
In the case E is the set of edges of the graph, the algorithm needs
O(|E|)
time to proceed.
See Also: fm_partition
[public]
Return type of ratio_cut_partition::get_side_of_node
[public]
Fix type of each node.
FIXA
means fixed on side A
, FIXB
on side B
and UNFIXED
means not
fixed on any side.
[public]
Default constructor.
[public virtual]
Destructor.
[public]
Sets variables.
Must be executed before ratio_cut_partition::check
source_node
and target_node
will be
determined automatically.
G | undirected graph. |
edge_weight | weight of each edge. |
node_weight | weight of each node. |
[public]
Sets variables. Must be executed before ratio_cut_partition::check In order to get good results, you should take two graph theoretically far away nodes as source and target.
G | undirected graph. |
target_node |
end-node, remains on side B .
|
edge_weight | weight of each edge.. |
node_weight | weight of each node. |
source_node |
start-node, remains on side A .
|
[public]
Sets variables.
Must be executed before ratio_cut_partition::check
In order to get good results, you should take two graph
theoretically far away nodes as source and target. Additionally
init_side
should nearly be in balance.
source_node
must be on side A
in
init_side
and target_node
on side B
respectively.
G | undirected graph. |
init_side | initial bi-partitioning. |
target_node |
end-node, remains on side B .
|
edge_weight | weight of each edge.. |
node_weight | weight of each node. |
source_node |
start-node, remains on side A .
|
[public]
Sets variables.
Must be executed before ratio_cut_partition::check
In order to get good results, you should take two graph
theoretically far away nodes as source and target.
source_node
must not be fixed on side B
.
target_node
must not be fixed on side A
.
G | undirected graph. |
fixed | fixed nodes. |
target_node |
end-node, remains on side B .
|
edge_weight | weight of each edge.. |
node_weight | weight of each node. |
source_node |
start-node, remains on side A .
|
[public]
Sets variables.
Must be executed before ratio_cut_partition::check
In order to get good results, you should take two graph
theoretically far away nodes as source and target. Additionally
init_side
should nearly be in balance. Fixed nodes
are on their fix side, their initial side is overwritten then.
source_node
must be on side A in init_side
and target_node
on side B respectively.
source_node
must not be fixed on side B
.
target_node
must not be fixed on side A
.
G | undirected graph. |
fixed | fixed nodes. |
init_side | initial bi-partitioning. |
target_node |
end-node, remains on side B .
|
edge_weight | weight of each edge.. |
node_weight | weight of each node. |
source_node |
start-node, remains on side A .
|
[public]
Enables the storing of cut-edges. If enabled the list of cut-edges can be traversed using ratio_cut_partition:: cut_edges_iterator.
set |
if true cut_edges will be stored.
|
[public]
Enables the storing of nodes on their side. If enabled the nodes of each side can be traversed using ratio_cut_partition:: nodes_on_one_side_iterator.
set |
if true nodes on their side will be stored.
|
[public virtual]
Checks whether following preconditions are satisfied:
G
is undirected.
source_node
and target_node
are 2 distinct nodes with node weights > 0.
G
has more than 2 nodes, then at least
two of them have a weight > 0.
fixed[source_node]
is FIXA
.
fixed[target_node]
is FIXB
.
G | graph |
algorithm::GTL_OK
on success,
algorithm::GTL_ERROR
otherwise.[public]
Computes a partitioning of G
, that means a division
of its vertices in two sides ratio_cut_partition::A
and ratio_cut_partition::B
.
G | graph |
algorithm::GTL_OK
on success,
algorithm::GTL_ERROR
otherwise.[public]
Gets the size of the cut after bi-partitioning.
[public]
Gets the ratio of the cut after bi-partitioning as defined in [WeiChe91].
[public]
Gets side of the node after bi-partitioning.
n | node of graph G. |
ratio_cut_partition::A
if n
lies on side A
, ratio_cut_partition::B
otherwise.[public]
Gets side of the node after bi-partitioning.
n | node of graph G. |
ratio_cut_partition::A
if n
lies on side A
, ratio_cut_partition::B
otherwise.[public]
Gets the sum of all node weights from nodes on side A
.
G | graph |
node_weight_on_sideA
[public]
Gets the sum of all node weights from nodes on side B
.
G | graph |
node_weight_on_sideB
[public]
Iterator type for edges which belong to the cut.
[public]
Iterate through all edges which belong to the cut, that means all edges with end-nodes on different sides. It is only valid if enabled with ratio_cut_partition:: store_cut_edges before.
[public]
End-Iterator for iteration through all edges which belong to the cut. It is only valid if enabled with ratio_cut_partition:: store_cut_edges before.
[public]
Iterator type for nodes of a side.
[public]
Iterate through all nodes which belong to side A
,
It is only valid if enabled with ratio_cut_partition:: store_nodesAB before.
A
.[public]
End-Iterator for iteration through all nodes which belong to side
A
,
It is only valid if enabled with ratio_cut_partition:: store_nodesAB before.
A
.[public]
Iterate through all nodes which belong to side B
,
It is only valid if enabled with ratio_cut_partition:: store_nodesAB before.
B
.[public]
End-Iterator for iteration through all nodes which belong to side
B
,
It is only valid if enabled with ratio_cut_partition:: store_nodesAB before.
B
.[public virtual]
Resets ratio_cut_partition, i.e. prepares the algorithm to be applied to another graph.
Kdoc |