Introduction
This package provides various algorithms that are often used in optimization.
Graph Partition
Partitioning algorithms are included such as FM partitioning [3] and its multiway extensions.
Graph Coloring
Various graph coloring algorithms are included such as integer linear programming (ILP) based coloring [6], semidefinite programming (SDP) based coloring [6], iterative linear programming (LP) based coloring [4] , greedy approach [2], etc. It also provides graph simplification algorithms for the coloring problem, which can also be applied to other graph algorithms.
Graph Misc
Implementation of graph utilities and some other graph algorithms such as maximum clique and maximum independent set.
Placement
Useful VLSI placement strategies.
Examples
FM Partition
See documented version: test/algorithms/test_FM.cpp
#include <iostream>
using std::cout;
using std::endl;
{
public:
typedef char tie_id_type;
typedef int weight_type;
Node(weight_type
const& w, tie_id_type
const&
id)
{
}
protected:
};
{
array<Node*, 8> vNode;
vNode[0] =
new Node (1,
'a');
vNode[1] =
new Node (1,
'b');
vNode[2] =
new Node (1,
'c');
vNode[3] =
new Node (1,
'd');
vNode[4] =
new Node (1,
'e');
vNode[5] =
new Node (1,
'f');
vNode[6] =
new Node (1,
'g');
vNode[7] =
new Node (1,
'h');
for (unsigned int i = 0; i < vNode.size(); ++i)
{
#if 1
if (i < 4)
else
#else
if (i < 4)
else
#endif
}
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[0]);
vNodeNet.push_back(vNode[1]);
vNodeNet.push_back(vNode[2]);
fm.
add_net(1, vNodeNet.begin(), vNodeNet.end());
}
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[1]);
vNodeNet.push_back(vNode[3]);
vNodeNet.push_back(vNode[4]);
vNodeNet.push_back(vNode[5]);
fm.
add_net(1, vNodeNet.begin(), vNodeNet.end());
}
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[2]);
vNodeNet.push_back(vNode[5]);
vNodeNet.push_back(vNode[6]);
fm.
add_net(1, vNodeNet.begin(), vNodeNet.end());
}
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[0]);
vNodeNet.push_back(vNode[6]);
fm.
add_net(1, vNodeNet.begin(), vNodeNet.end());
}
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[3]);
vNodeNet.push_back(vNode[4]);
vNodeNet.push_back(vNode[7]);
fm.
add_net(1, vNodeNet.begin(), vNodeNet.end());
}
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[5]);
vNodeNet.push_back(vNode[7]);
fm.
add_net(1, vNodeNet.begin(), vNodeNet.end());
}
fm(3.0/5, 5.0/3);
return 0;
}
Compiling and running commands (assuming LIMBO_DIR and BOOST_DIR are well defined).
1 g++ -o test_FM test_FM.cpp -I $LIMBO_DIR/include -I $BOOST_DIR/include -L $BOOST_DIR/lib -lboost_regex
2 # test FM algorithm with a simple graph
Output
1 ------- partitions -------
3 ------- connections -------
10 ######### iteration #0 #########
11 ======= trial phase =======
12 ======= actual phase w. target_cnt = 2 =======
13 ######### iteration #1 #########
14 ======= trial phase =======
15 ======= actual phase w. target_cnt = 0 =======
16 ------- partitions -------
18 ------- connections -------
All Examples
Possible dependencies: Boost, Gurobi, Cbc, Lemon, Csdp, OpenBLAS.
References
Graph Partition
Graph Coloring
Graph Misc
Placement