path: root/include/llvm/CodeGen/PBQP/Graph.h

//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// PBQP Graph class.
//
//===----------------------------------------------------------------------===//


#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
#define LLVM_CODEGEN_PBQP_GRAPH_H

#include "Math.h"

#include <list>
#include <map>
#include <llvm/ADT/ilist.h>

namespace PBQP {

  /// PBQP Graph class.
  /// Instances of this class describe PBQP problems.
  class Graph {
  private:

    // ----- TYPEDEFS -----
    class NodeEntry;
    class EdgeEntry;

    typedef llvm::ilist<NodeEntry> NodeList;
    typedef llvm::ilist<EdgeEntry> EdgeList;

  public:

    typedef NodeEntry* NodeItr;
    typedef const NodeEntry* ConstNodeItr;

    typedef EdgeEntry* EdgeItr;
    typedef const EdgeEntry* ConstEdgeItr;

  private:

    typedef std::list<EdgeItr> AdjEdgeList;
  
  public:

    typedef AdjEdgeList::iterator AdjEdgeItr;

  private:

    class NodeEntry : public llvm::ilist_node<NodeEntry> {
      friend struct llvm::ilist_sentinel_traits<NodeEntry>;
    private:
      Vector costs;      
      AdjEdgeList adjEdges;
      unsigned degree;
      void *data;
      NodeEntry() : costs(0, 0) {}
    public:
      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
      Vector& getCosts() { return costs; }
      const Vector& getCosts() const { return costs; }
      unsigned getDegree() const { return degree; }
      AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
      AdjEdgeItr edgesEnd() { return adjEdges.end(); }
      AdjEdgeItr addEdge(EdgeItr e) {
        ++degree;
        return adjEdges.insert(adjEdges.end(), e);
      }
      void removeEdge(AdjEdgeItr ae) {
        --degree;
        adjEdges.erase(ae);
      }
      void setData(void *data) { this->data = data; }
      void* getData() { return data; }
    };

    class EdgeEntry : public llvm::ilist_node<EdgeEntry> {
      friend struct llvm::ilist_sentinel_traits<EdgeEntry>;
    private:
      NodeItr node1, node2;
      Matrix costs;
      AdjEdgeItr node1AEItr, node2AEItr;
      void *data;
      EdgeEntry() : costs(0, 0, 0) {}
    public:
      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
        : node1(node1), node2(node2), costs(costs) {}
      NodeItr getNode1() const { return node1; }
      NodeItr getNode2() const { return node2; }
      Matrix& getCosts() { return costs; }
      const Matrix& getCosts() const { return costs; }
      void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
      AdjEdgeItr getNode1AEItr() { return node1AEItr; }
      void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
      AdjEdgeItr getNode2AEItr() { return node2AEItr; }
      void setData(void *data) { this->data = data; }
      void *getData() { return data; }
    };

    // ----- MEMBERS -----

    NodeList nodes;
    unsigned numNodes;

    EdgeList edges;
    unsigned numEdges;

    // ----- INTERNAL METHODS -----

    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
    const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }

    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
    const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }

    NodeItr addConstructedNode(const NodeEntry &n) {
      ++numNodes;
      return nodes.insert(nodes.end(), n);
    }

    EdgeItr addConstructedEdge(const EdgeEntry &e) {
      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
             "Attempt to add duplicate edge.");
      ++numEdges;
      EdgeItr edgeItr = edges.insert(edges.end(), e);
      EdgeEntry &ne = getEdge(edgeItr);
      NodeEntry &n1 = getNode(ne.getNode1());
      NodeEntry &n2 = getNode(ne.getNode2());
      // Sanity check on matrix dimensions:
      assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
             (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
             "Edge cost dimensions do not match node costs dimensions.");
      ne.setNode1AEItr(n1.addEdge(edgeItr));
      ne.setNode2AEItr(n2.addEdge(edgeItr));
      return edgeItr;
    }

    inline void copyFrom(const Graph &other);
  public:

    /// \brief Construct an empty PBQP graph.
    Graph() : numNodes(0), numEdges(0) {}

    /// \brief Copy construct this graph from "other". Note: Does not copy node
    ///        and edge data, only graph structure and costs.
    /// @param other Source graph to copy from.
    Graph(const Graph &other) : numNodes(0), numEdges(0) {
      copyFrom(other);
    }

    /// \brief Make this graph a copy of "other". Note: Does not copy node and
    ///        edge data, only graph structure and costs.
    /// @param other The graph to copy from.
    /// @return A reference to this graph.
    ///
    /// This will clear the current graph, erasing any nodes and edges added,
    /// before copying from other.
    Graph& operator=(const Graph &other) {
      clear();      
      copyFrom(other);
      return *this;
    }

    /// \brief Add a node with the given costs.
    /// @param costs Cost vector for the new node.
    /// @return Node iterator for the added node.
    NodeItr addNode(const Vector &costs) {
      return addConstructedNode(NodeEntry(costs));
    }

    /// \brief Add an edge between the given nodes with the given costs.
    /// @param n1Itr First node.
    /// @param n2Itr Second node.
    /// @return Edge iterator for the added edge.
    EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
                    const Matrix &costs) {
      assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
             getNodeCosts(n2Itr).getLength() == costs.getCols() &&
             "Matrix dimensions mismatch.");
      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs)); 
    }

    /// \brief Get the number of nodes in the graph.
    /// @return Number of nodes in the graph.
    unsigned getNumNodes() const { return numNodes; }

    /// \brief Get the number of edges in the graph.
    /// @return Number of edges in the graph.
    unsigned getNumEdges() const { return numEdges; }

    /// \brief Get a node's cost vector.
    /// @param nItr Node iterator.
    /// @return Node cost vector.
    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }

    /// \brief Get a node's cost vector (const version).
    /// @param nItr Node iterator.
    /// @return Node cost vector.
    const Vector& getNodeCosts(ConstNodeItr nItr) const {
      return getNode(nItr).getCosts();
    }

    /// \brief Set a node's data pointer.
    /// @param nItr Node iterator.
    /// @param data Pointer to node data.
    ///
    /// Typically used by a PBQP solver to attach data to aid in solution.
    void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }

    /// \brief Get the node's data pointer.
    /// @param nItr Node iterator.
    /// @return Pointer to node data.
    void* getNodeData(NodeItr nItr) { return getNode(nItr).getData();