Limbo
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Limbo.Algorithms

Table of Contents

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;
class Node
{
public:
typedef char tie_id_type;
typedef int weight_type;
Node(weight_type const& w, tie_id_type const& id)
{
m_weight = w;
m_id = id;
}
tie_id_type tie_id() const {return m_id;}
weight_type weight() const {return m_weight;}
protected:
tie_id_type m_id;
weight_type m_weight;
};
int main()
{
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)
fm.add_node(vNode[i], 0);
else
fm.add_node(vNode[i], 1);
#else
if (i < 4)
fm.add_node(vNode[i], i%2);
else
fm.add_node(vNode[i], i%2);
#endif
}
// net n1
{
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());
//fm.add_net(1.0/(vNodeNet.size()-1), vNodeNet.begin(), vNodeNet.end());
}
// net n2
{
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());
//fm.add_net(1.0/(vNodeNet.size()-1), vNodeNet.begin(), vNodeNet.end());
}
// net n3
{
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());
//fm.add_net(1.0/(vNodeNet.size()-1), vNodeNet.begin(), vNodeNet.end());
}
// net n4
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[0]);
vNodeNet.push_back(vNode[6]);
fm.add_net(1, vNodeNet.begin(), vNodeNet.end());
//fm.add_net(1.0/(vNodeNet.size()-1), vNodeNet.begin(), vNodeNet.end());
}
// net n5
{
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());
//fm.add_net(1.0/(vNodeNet.size()-1), vNodeNet.begin(), vNodeNet.end());
}
// net n6
{
vector<Node*> vNodeNet;
vNodeNet.push_back(vNode[5]);
vNodeNet.push_back(vNode[7]);
fm.add_net(1, vNodeNet.begin(), vNodeNet.end());
//fm.add_net(1.0/(vNodeNet.size()-1), vNodeNet.begin(), vNodeNet.end());
}
fm.print();
fm(3.0/5, 5.0/3);
fm.print();
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
3 ./test_FM

Output

1 ------- partitions -------
2 {d c b a | h g f e }
3 ------- connections -------
4 a - b - c
5 b - d - e - f
6 c - f - g
7 a - g
8 d - e - h
9 f - h
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 -------
17 {g c b a | h f e d }
18 ------- connections -------
19 a - b - c
20 b - d - e - f
21 c - f - g
22 a - g
23 d - e - h
24 f - h

All Examples

Possible dependencies: Boost, Gurobi, Cbc, Lemon, Csdp, OpenBLAS.

References

Graph Partition

Graph Coloring

Graph Misc

Placement