peeling.h

/*
 * vim: ts=4 sw=4 et tw=0 wm=0
 *
 * libdialect - A library for computing DiAlEcT layouts:
 *                 D = Decompose/Distribute
 *                 A = Arrange
 *                 E = Expand/Emend
 *                 T = Transform
 *
 * Copyright (C) 2018  Monash University
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 * See the file LICENSE.LGPL distributed with the library.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 *
 * Author(s):   Steve Kieffer   <http://skieffer.info>
*/

#ifndef DIALECT_PEELING_H
#define DIALECT_PEELING_H

#include <memory>
#include <vector>

#include "libdialect/commontypes.h"
#include "libdialect/graphs.h"

namespace dialect {

class PeeledNode;
struct Stem;

typedef std::shared_ptr<PeeledNode> PeeledNode_SP;
typedef std::shared_ptr<Stem> Stem_SP;

PeeledNode_SP identifyRootNode(const Graph &graph);

class PeeledNode : public GhostNode {
    friend struct Stem;
    friend PeeledNode_SP identifyRootNode(const Graph &graph);
public:
    static PeeledNode_SP allocate(const Node &node) { return PeeledNode_SP(new PeeledNode(node)); }

    PeeledNode &operator=(const PeeledNode&) = default;

    virtual ~PeeledNode(void) = default;

private:
    PeeledNode(void) = delete;

    PeeledNode(const PeeledNode&) = delete;

    PeeledNode(const Node &node)
      : GhostNode(node),
        m_treeSerialNumber(nextTreeSerialNumber++) {}

    static id_type nextTreeSerialNumber;
    id_type m_treeSerialNumber;
    void updateSerialNumber(void) { m_treeSerialNumber = nextTreeSerialNumber++; }

};


struct Stem {
    Stem(const Node_SP &leaf, const Node_SP &root) : m_plain_leaf(leaf), m_plain_root(root) {}
    Node_WP m_plain_leaf;
    Node_WP m_plain_root;
    void addSelfToGraph(Graph &H);
};

std::vector<Stem_SP> makeStemsFromLeaves(const NodesById &leaves);

struct NodeBuckets {
    NodeBuckets(Graph &graph);

    NodesById takeLeaves(void);

    bool moveNode(id_type id, unsigned oldDegree, unsigned newDegree);

    void severNodes(const NodesById &nodes);

    Graph &m_graph;
    unsigned m_maxDegree;
    std::vector<NodesById> m_buckets;
};

Trees peel(Graph &G);

} // namespace dialect

#endif // DIALECT_PEELING_H