Heuristic graph bi-partitioning algorithm (Fiduccia-Mattheyses). More...
#include <GTL/fm_partition.h>
Inherits: algorithm
This class implements a heuristic graph bi-partitioning algorithm, based on iterative movement, proposed by C. M. Fiduccia and R. M. Mattheyses in 1982.
In the case E is the set of edges of the graph, the algorithm needs
O(|E|)
time to proceed.
See Also: ratio_cut_partition
[public]
Return type of fm_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 fm_partition::check
G | undirected graph. |
edge_weight | weight of each edge. |
node_weight | weight of each node. |
[public]
Sets variables.
Must be executed before fm_partition::check
In order to get good results, init_side
should
almost be in balance.
G | undirected graph. |
init_side | initial bi-partitioning. |
edge_weight | weight of each edge. |
node_weight | weight of each node. |
[public]
Sets variables. Must be executed before fm_partition::check
G | undirected graph. |
fixed | fixed nodes. |
edge_weight | weight of each edge. |
node_weight | weight of each node. |
[public]
Sets variables.
Must be executed before fm_partition::check
In order to get good results, init_side
should
almost be in balance. Fixed nodes are on their fix side, their
initial side is overwritten then.
G | undirected graph. |
fixed | fixed nodes. |
init_side | initial bi-partitioning. |
edge_weight | weight of each edge. |
node_weight | weight of each node. |
[public]
Enables the storing of cut-edges. If enabled the list of cut-edges can be traversed using fm_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 fm_partition:: nodes_on_one_side_iterator.
set |
if true nodes will be stored on their sides.
|
[public virtual]
Checks whether following preconditions are satisfied:
G
is undirected.
G | graph |
algorithm::GTL_OK
on success,
algorithm::GTL_ERROR
otherwise.[public]
Computes a partitioning with G
, that means a
division of its vertices in two sides fm_partition::A
and fm_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 number of passes needed to create a bi-partition with this heuristic.
[public]
Gets side of the node after bi-partitioning.
n | node of graph G. |
fm_partition::A
if n
lies on
side A
, fm_partition::B
otherwise.[public]
Gets side of the node after bi-partitioning.
n | node of graph G. |
fm_partition::A
if n
lies on
side A
, fm_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 fm_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 fm_partition:: store_cut_edges before.
[public]
Iterator type of nodes of a side.
[public]
Iterate through all nodes which belong to side A
.
It is only valid if enabled with fm_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 fm_partition:: store_nodesAB before.
A
.[public]
Iterate through all nodes which belong to side B
,
It is only valid if enabled with fm_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 fm_partition:: store_nodesAB before.
B
.[public virtual]
Resets fm_partition, i.e. prepares the algorithm to be applied to another graph.
Kdoc |