1//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// PBQP Graph class.
11//
12//===----------------------------------------------------------------------===//
13
14
15#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
16#define LLVM_CODEGEN_PBQP_GRAPH_H
17
18#include "Math.h"
19
20#include <list>
21#include <map>
22
23namespace PBQP {
24
25  /// PBQP Graph class.
26  /// Instances of this class describe PBQP problems.
27  class Graph {
28  private:
29
30    // ----- TYPEDEFS -----
31    class NodeEntry;
32    class EdgeEntry;
33
34    typedef std::list<NodeEntry> NodeList;
35    typedef std::list<EdgeEntry> EdgeList;
36
37  public:
38
39    typedef NodeList::iterator NodeItr;
40    typedef NodeList::const_iterator ConstNodeItr;
41
42    typedef EdgeList::iterator EdgeItr;
43    typedef EdgeList::const_iterator ConstEdgeItr;
44
45  private:
46
47    typedef std::list<EdgeItr> AdjEdgeList;
48
49  public:
50
51    typedef AdjEdgeList::iterator AdjEdgeItr;
52
53  private:
54
55    class NodeEntry {
56    private:
57      Vector costs;
58      AdjEdgeList adjEdges;
59      unsigned degree;
60      void *data;
61    public:
62      NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
63      Vector& getCosts() { return costs; }
64      const Vector& getCosts() const { return costs; }
65      unsigned getDegree() const { return degree; }
66      AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
67      AdjEdgeItr edgesEnd() { return adjEdges.end(); }
68      AdjEdgeItr addEdge(EdgeItr e) {
69        ++degree;
70        return adjEdges.insert(adjEdges.end(), e);
71      }
72      void removeEdge(AdjEdgeItr ae) {
73        --degree;
74        adjEdges.erase(ae);
75      }
76      void setData(void *data) { this->data = data; }
77      void* getData() { return data; }
78    };
79
80    class EdgeEntry {
81    private:
82      NodeItr node1, node2;
83      Matrix costs;
84      AdjEdgeItr node1AEItr, node2AEItr;
85      void *data;
86    public:
87      EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
88        : node1(node1), node2(node2), costs(costs) {}
89      NodeItr getNode1() const { return node1; }
90      NodeItr getNode2() const { return node2; }
91      Matrix& getCosts() { return costs; }
92      const Matrix& getCosts() const { return costs; }
93      void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
94      AdjEdgeItr getNode1AEItr() { return node1AEItr; }
95      void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
96      AdjEdgeItr getNode2AEItr() { return node2AEItr; }
97      void setData(void *data) { this->data = data; }
98      void *getData() { return data; }
99    };
100
101    // ----- MEMBERS -----
102
103    NodeList nodes;
104    unsigned numNodes;
105
106    EdgeList edges;
107    unsigned numEdges;
108
109    // ----- INTERNAL METHODS -----
110
111    NodeEntry& getNode(NodeItr nItr) { return *nItr; }
112    const NodeEntry& getNode(ConstNodeItr nItr) const { return *nItr; }
113
114    EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
115    const EdgeEntry& getEdge(ConstEdgeItr eItr) const { return *eItr; }
116
117    NodeItr addConstructedNode(const NodeEntry &n) {
118      ++numNodes;
119      return nodes.insert(nodes.end(), n);
120    }
121
122    EdgeItr addConstructedEdge(const EdgeEntry &e) {
123      assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
124             "Attempt to add duplicate edge.");
125      ++numEdges;
126      EdgeItr edgeItr = edges.insert(edges.end(), e);
127      EdgeEntry &ne = getEdge(edgeItr);
128      NodeEntry &n1 = getNode(ne.getNode1());
129      NodeEntry &n2 = getNode(ne.getNode2());
130      // Sanity check on matrix dimensions:
131      assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
132             (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
133             "Edge cost dimensions do not match node costs dimensions.");
134      ne.setNode1AEItr(n1.addEdge(edgeItr));
135      ne.setNode2AEItr(n2.addEdge(edgeItr));
136      return edgeItr;
137    }
138
139    inline void copyFrom(const Graph &other);
140  public:
141
142    /// \brief Construct an empty PBQP graph.
143    Graph() : numNodes(0), numEdges(0) {}
144
145    /// \brief Copy construct this graph from "other". Note: Does not copy node
146    ///        and edge data, only graph structure and costs.
147    /// @param other Source graph to copy from.
148    Graph(const Graph &other) : numNodes(0), numEdges(0) {
149      copyFrom(other);
150    }
151
152    /// \brief Make this graph a copy of "other". Note: Does not copy node and
153    ///        edge data, only graph structure and costs.
154    /// @param other The graph to copy from.
155    /// @return A reference to this graph.
156    ///
157    /// This will clear the current graph, erasing any nodes and edges added,
158    /// before copying from other.
159    Graph& operator=(const Graph &other) {
160      clear();
161      copyFrom(other);
162      return *this;
163    }
164
165    /// \brief Add a node with the given costs.
166    /// @param costs Cost vector for the new node.
167    /// @return Node iterator for the added node.
168    NodeItr addNode(const Vector &costs) {
169      return addConstructedNode(NodeEntry(costs));
170    }
171
172    /// \brief Add an edge between the given nodes with the given costs.
173    /// @param n1Itr First node.
174    /// @param n2Itr Second node.
175    /// @return Edge iterator for the added edge.
176    EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
177                    const Matrix &costs) {
178      assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
179             getNodeCosts(n2Itr).getLength() == costs.getCols() &&
180             "Matrix dimensions mismatch.");
181      return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs));
182    }
183
184    /// \brief Get the number of nodes in the graph.
185    /// @return Number of nodes in the graph.
186    unsigned getNumNodes() const { return numNodes; }
187
188    /// \brief Get the number of edges in the graph.
189    /// @return Number of edges in the graph.
190    unsigned getNumEdges() const { return numEdges; }
191
192    /// \brief Get a node's cost vector.
193    /// @param nItr Node iterator.
194    /// @return Node cost vector.
195    Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
196
197    /// \brief Get a node's cost vector (const version).
198    /// @param nItr Node iterator.
199    /// @return Node cost vector.
200    const Vector& getNodeCosts(ConstNodeItr nItr) const {
201      return getNode(nItr).getCosts();
202    }
203
204    /// \brief Set a node's data pointer.
205    /// @param nItr Node iterator.
206    /// @param data Pointer to node data.
207    ///
208    /// Typically used by a PBQP solver to attach data to aid in solution.
209    void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
210
211    /// \brief Get the node's data pointer.
212    /// @param nItr Node iterator.
213    /// @return Pointer to node data.
214    void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
215
216    /// \brief Get an edge's cost matrix.
217    /// @param eItr Edge iterator.
218    /// @return Edge cost matrix.
219    Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
220
221    /// \brief Get an edge's cost matrix (const version).
222    /// @param eItr Edge iterator.
223    /// @return Edge cost matrix.
224    const Matrix& getEdgeCosts(ConstEdgeItr eItr) const {
225      return getEdge(eItr).getCosts();
226    }
227
228    /// \brief Set an edge's data pointer.
229    /// @param eItr Edge iterator.
230    /// @param data Pointer to edge data.
231    ///
232    /// Typically used by a PBQP solver to attach data to aid in solution.
233    void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
234
235    /// \brief Get an edge's data pointer.
236    /// @param eItr Edge iterator.
237    /// @return Pointer to edge data.
238    void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
239
240    /// \brief Get a node's degree.
241    /// @param nItr Node iterator.
242    /// @return The degree of the node.
243    unsigned getNodeDegree(NodeItr nItr) const {
244      return getNode(nItr).getDegree();
245    }
246
247    /// \brief Begin iterator for node set.
248    NodeItr nodesBegin() { return nodes.begin(); }
249
250    /// \brief Begin const iterator for node set.
251    ConstNodeItr nodesBegin() const { return nodes.begin(); }
252
253    /// \brief End iterator for node set.
254    NodeItr nodesEnd() { return nodes.end(); }
255
256    /// \brief End const iterator for node set.
257    ConstNodeItr nodesEnd() const { return nodes.end(); }
258
259    /// \brief Begin iterator for edge set.
260    EdgeItr edgesBegin() { return edges.begin(); }
261
262    /// \brief End iterator for edge set.
263    EdgeItr edgesEnd() { return edges.end(); }
264
265    /// \brief Get begin iterator for adjacent edge set.
266    /// @param nItr Node iterator.
267    /// @return Begin iterator for the set of edges connected to the given node.
268    AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
269      return getNode(nItr).edgesBegin();
270    }
271
272    /// \brief Get end iterator for adjacent edge set.
273    /// @param nItr Node iterator.
274    /// @return End iterator for the set of edges connected to the given node.
275    AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
276      return getNode(nItr).edgesEnd();
277    }
278
279    /// \brief Get the first node connected to this edge.
280    /// @param eItr Edge iterator.
281    /// @return The first node connected to the given edge.
282    NodeItr getEdgeNode1(EdgeItr eItr) {
283      return getEdge(eItr).getNode1();
284    }
285
286    /// \brief Get the second node connected to this edge.
287    /// @param eItr Edge iterator.
288    /// @return The second node connected to the given edge.
289    NodeItr getEdgeNode2(EdgeItr eItr) {
290      return getEdge(eItr).getNode2();
291    }
292
293    /// \brief Get the "other" node connected to this edge.
294    /// @param eItr Edge iterator.
295    /// @param nItr Node iterator for the "given" node.
296    /// @return The iterator for the "other" node connected to this edge.
297    NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
298      EdgeEntry &e = getEdge(eItr);
299      if (e.getNode1() == nItr) {
300        return e.getNode2();
301      } // else
302      return e.getNode1();
303    }
304
305    /// \brief Get the edge connecting two nodes.
306    /// @param n1Itr First node iterator.
307    /// @param n2Itr Second node iterator.
308    /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
309    ///         otherwise returns edgesEnd().
310    EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
311      for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
312         aeItr != aeEnd; ++aeItr) {
313        if ((getEdgeNode1(*aeItr) == n2Itr) ||
314            (getEdgeNode2(*aeItr) == n2Itr)) {
315          return *aeItr;
316        }
317      }
318      return edges.end();
319    }
320
321    /// \brief Remove a node from the graph.
322    /// @param nItr Node iterator.
323    void removeNode(NodeItr nItr) {
324      NodeEntry &n = getNode(nItr);
325      for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
326        EdgeItr eItr = *itr;
327        ++itr;
328        removeEdge(eItr);
329      }
330      nodes.erase(nItr);
331      --numNodes;
332    }
333
334    /// \brief Remove an edge from the graph.
335    /// @param eItr Edge iterator.
336    void removeEdge(EdgeItr eItr) {
337      EdgeEntry &e = getEdge(eItr);
338      NodeEntry &n1 = getNode(e.getNode1());
339      NodeEntry &n2 = getNode(e.getNode2());
340      n1.removeEdge(e.getNode1AEItr());
341      n2.removeEdge(e.getNode2AEItr());
342      edges.erase(eItr);
343      --numEdges;
344    }
345
346    /// \brief Remove all nodes and edges from the graph.
347    void clear() {
348      nodes.clear();
349      edges.clear();
350      numNodes = numEdges = 0;
351    }
352
353    /// \brief Dump a graph to an output stream.
354    template <typename OStream>
355    void dump(OStream &os) {
356      os << getNumNodes() << " " << getNumEdges() << "\n";
357
358      for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
359           nodeItr != nodeEnd; ++nodeItr) {
360        const Vector& v = getNodeCosts(nodeItr);
361        os << "\n" << v.getLength() << "\n";
362        assert(v.getLength() != 0 && "Empty vector in graph.");
363        os << v[0];
364        for (unsigned i = 1; i < v.getLength(); ++i) {
365          os << " " << v[i];
366        }
367        os << "\n";
368      }
369
370      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
371           edgeItr != edgeEnd; ++edgeItr) {
372        unsigned n1 = std::distance(nodesBegin(), getEdgeNode1(edgeItr));
373        unsigned n2 = std::distance(nodesBegin(), getEdgeNode2(edgeItr));
374        assert(n1 != n2 && "PBQP graphs shound not have self-edges.");
375        const Matrix& m = getEdgeCosts(edgeItr);
376        os << "\n" << n1 << " " << n2 << "\n"
377           << m.getRows() << " " << m.getCols() << "\n";
378        assert(m.getRows() != 0 && "No rows in matrix.");
379        assert(m.getCols() != 0 && "No cols in matrix.");
380        for (unsigned i = 0; i < m.getRows(); ++i) {
381          os << m[i][0];
382          for (unsigned j = 1; j < m.getCols(); ++j) {
383            os << " " << m[i][j];
384          }
385          os << "\n";
386        }
387      }
388    }
389
390    /// \brief Print a representation of this graph in DOT format.
391    /// @param os Output stream to print on.
392    template <typename OStream>
393    void printDot(OStream &os) {
394
395      os << "graph {\n";
396
397      for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
398           nodeItr != nodeEnd; ++nodeItr) {
399
400        os << "  node" << nodeItr << " [ label=\""
401           << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
402      }
403
404      os << "  edge [ len=" << getNumNodes() << " ]\n";
405
406      for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
407           edgeItr != edgeEnd; ++edgeItr) {
408
409        os << "  node" << getEdgeNode1(edgeItr)
410           << " -- node" << getEdgeNode2(edgeItr)
411           << " [ label=\"";
412
413        const Matrix &edgeCosts = getEdgeCosts(edgeItr);
414
415        for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
416          os << edgeCosts.getRowAsVector(i) << "\\n";
417        }
418        os << "\" ]\n";
419      }
420      os << "}\n";
421    }
422
423  };
424
425  class NodeItrComparator {
426  public:
427    bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
428      return &*n1 < &*n2;
429    }
430
431    bool operator()(Graph::ConstNodeItr n1, Graph::ConstNodeItr n2) const {
432      return &*n1 < &*n2;
433    }
434  };
435
436  class EdgeItrCompartor {
437  public:
438    bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
439      return &*e1 < &*e2;
440    }
441
442    bool operator()(Graph::ConstEdgeItr e1, Graph::ConstEdgeItr e2) const {
443      return &*e1 < &*e2;
444    }
445  };
446
447  void Graph::copyFrom(const Graph &other) {
448    std::map<Graph::ConstNodeItr, Graph::NodeItr,
449             NodeItrComparator> nodeMap;
450
451     for (Graph::ConstNodeItr nItr = other.nodesBegin(),
452                             nEnd = other.nodesEnd();
453         nItr != nEnd; ++nItr) {
454      nodeMap[nItr] = addNode(other.getNodeCosts(nItr));
455    }
456
457  }
458
459}
460
461#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
462