Limbo.Algorithms

Table of Contents

• Introduction
  • Graph Partition
  • Graph Coloring
  • Graph Misc
  • Placement
• Examples
  • FM Partition
  • All Examples
• References
  • Graph Partition
  • Graph Coloring
  • Graph Misc
  • Placement

Introduction

This package provides various algorithms that are often used in optimization.

Graph Partition

Partitioning algorithms are included such as FM partitioning [PAR_DAC1982_FM] and its multiway extensions.

Graph Coloring

Various graph coloring algorithms are included such as integer linear programming (ILP) based coloring [TPL_TCAD2015_Yu], semidefinite programming (SDP) based coloring [TPL_TCAD2015_Yu], iterative linear programming (LP) based coloring [TPL_SPIE2016_Lin] , greedy approach [MPL_CACM1979_Brelaz], 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>
#include <limbo/algorithms/partition/FM.h>
 
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');
 
    limbo::algorithms::partition::FM<Node, double> fm; 
    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.print_connection();
    fm(3.0/5, 5.0/3);
    fm.print();
    fm.print_connection();
 
    return 0;
}

Compiling and running commands (assuming LIMBO_DIR and BOOST_DIR are well defined).

g++ -o test_FM test_FM.cpp -I $LIMBO_DIR/include -I $BOOST_DIR/include -L $BOOST_DIR/lib -lboost_regex
# test FM algorithm with a simple graph 
./test_FM 

Output

------- partitions -------
{d c b a | h g f e }
------- connections -------
a - b - c
b - d - e - f
c - f - g
a - g
d - e - h
f - h
######### iteration #0 #########
======= trial phase =======
======= actual phase w. target_cnt = 2 =======
######### iteration #1 #########
======= trial phase =======
======= actual phase w. target_cnt = 0 =======
------- partitions -------
{g c b a | h f e d }
------- connections -------
a - b - c
b - d - e - f
c - f - g
a - g
d - e - h
f - h

All Examples

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

• test/algorithms/test_FM.cpp
• test/algorithms/test_ChromaticNumber.cpp
• test/algorithms/test_GraphSimplification.cpp
• test/algorithms/test_ILPColoring.cpp
• test/algorithms/test_SDPColoring.cpp
• test/algorithms/test_LPColoring.cpp

References

Graph Partition

• limbo/algorithms/partition/FM.h
• limbo/algorithms/partition/FMMultiWay.h

Graph Coloring

• limbo/algorithms/coloring/Coloring.h
• limbo/algorithms/coloring/BacktrackColoring.h
• limbo/algorithms/coloring/ChromaticNumber.h
• limbo/algorithms/coloring/GraphSimplification.h
• limbo/algorithms/coloring/GreedyColoring.h
• limbo/algorithms/coloring/ILPColoring.h
• limbo/algorithms/coloring/ILPColoringLemonCbc.h
• limbo/algorithms/coloring/LPColoring.h
• limbo/algorithms/coloring/SDPColoringCsdp.h

Graph Misc

• limbo/algorithms/GraphUtility.h
• limbo/algorithms/MaxClique.h
• limbo/algorithms/MaxIndependentSet.h

Placement

• limbo/algorithms/placement/GreedySearch.h