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