Subversion Repositories an-fpga-implementation-of-low-latency-noc-based-mpsoc

#ifndef GRAPH_H

#define GRAPH_H

#include <stdint.h>

#include <vector>

#include <list>

#include <stdio.h>

#include "queue.h"

class graph {

        public:

                graph() {}

                graph(uint32_t n, uint32_t m) {reset(n, m);}

                graph(const graph & g);

                void reset(uint32_t n, uint32_t m);

                void copy(const graph & g);

                struct edge;

                TAILQ_HEAD(edgelist, edge);

                struct node {

                        uint32_t id;

                        edgelist out, in;

                        uint32_t ind, outd;

                };

                struct edge {

                        node *parent, *child;

                        uint32_t id;

                        bool bound;

                        TAILQ_ENTRY(edge) from, to;

                };

                void bind(uint32_t k, uint32_t n, uint32_t m) {bind(getedge(k), getnode(n), getnode(m));}

                void

                bind(edge *e, node *n, node *m)

                {

                        TAILQ_INSERT_TAIL(&n->out, e, from);

                        TAILQ_INSERT_TAIL(&m->in, e, to);

                        n->outd++;

                        m->ind++;

                        e->bound = true;

                        e->parent = n;

                        e->child = m;

                }

                void

                unbind(edge *e)

                {

                        TAILQ_REMOVE(&e->parent->out, e, from);

                        TAILQ_REMOVE(&e->child->in, e, to);

                        e->parent->outd--;

                        e->child->ind--;

                        e->bound = false;

                }

                void

                unbind(node *n)

                {

                        while (!TAILQ_EMPTY(&n->out)) unbind(TAILQ_FIRST(&n->out));

                        while (!TAILQ_EMPTY(&n->in)) unbind(TAILQ_FIRST(&n->in));

                }

                node * getnode(uint32_t i) {return &m_nodes[i];}

                edge * getedge(uint32_t i) {return &m_edges[i];}

        protected:

                const graph & operator = (const graph & ) {return *this;}

                typedef std::vector<node> nodevector;

                typedef std::vector<edge> edgevector;

                nodevector m_nodes;

                edgevector m_edges;

};

class agony

{

        public:

                struct node {

                        uint32_t id;

                        uint32_t label;

                        uint32_t rank;

                        uint32_t newrank;

                        uint32_t diff;

                        node *parent;

                        uint32_t paredge;

                        uint32_t count;

                        TAILQ_ENTRY(node) entries, active;

                };

                TAILQ_HEAD(nodehead, node);

                struct edge {

                        bool eulerian;

                        uint32_t id;

                        uint32_t slack;

                        TAILQ_ENTRY(edge) entries;

                };

                TAILQ_HEAD(edgehead, edge);

                uint32_t size() const {return m_nodes.size();}

                node * getnode(uint32_t i) {return &m_nodes[i];}

                edge * getedge(uint32_t i) {return &m_edges[i];}

                void cycledfs();

                void initagony();

                void initrank();

                void read(FILE *f);

                void writeagony(FILE *f);

                void relief(uint32_t edge);

                void minagony();

                uint32_t primal() const {return m_primal;}

                uint32_t dual() const {return m_dual;}

                uint32_t cost();

        protected:

                uint32_t slack(node *v, node *u) const {return u->rank > v->rank + 1 ? u->rank - v->rank - 1 : 0;}

                uint32_t newslack(node *v, node *u) const {return u->newrank > v->newrank + 1 ? u->newrank - v->newrank - 1 : 0;}

                uint32_t slack(uint32_t eid) {return slack(from(eid), to(eid));}

                void deleteslack(uint32_t eid);

                void addslack(uint32_t eid);

                typedef std::vector<node> nodevector;

                typedef std::vector<edge> edgevector;

                typedef std::vector<nodehead> nodequeue;

                typedef std::vector<edgehead> edgequeue;

                typedef std::list<node *> nodelist;

                void updaterelief(nodelist & nl);

                void resetrelief(nodelist & nl);

                void shiftrank(nodelist & nl, uint32_t s);

                void extractcycle(uint32_t edge);

                node *from(uint32_t eid) {return getnode(m_graph.getedge(eid)->parent->id);}

                node *to(uint32_t eid) {return getnode(m_graph.getedge(eid)->child->id);}

                nodevector m_nodes;

                edgevector m_edges;

                graph m_graph;

                graph m_dag, m_euler;

                edgequeue m_slacks;

                int32_t m_curslack;

                uint32_t m_dual;

                uint32_t m_primal;

                //uint32_t m_minid;

};

#endif