EnGPar
Partitioning using the N-Graph
ngraph.h
Go to the documentation of this file.
1 #ifndef NGRAPH_H__
2 #define NGRAPH_H__
3 
4 #include <stdexcept>
5 #include "pngraph.h"
9 namespace agi {
10 
11 class GraphVertex;
12 class GraphEdge;
13 class VertexIterator;
14 class GhostIterator;
15 class PinIterator;
16 class EdgeIterator;
17 class GraphIterator;
18 class VEVIterator;
19 class EVEIterator;
20 class GraphTag;
21 class Migration;
22 class WeightMigration;
23 class MigrationTimers;
24 
32  class Ngraph : protected PNgraph {
33 
34 public:
35 
38  friend Ngraph* createEmptyGraph();
46  void constructVerts(bool isHG,
47  std::vector<gid_t>& verts,
48  std::vector<wgt_t>& weights);
49  void constructVerts(bool isHG, lid_t num_verts,
50  gid_t* verts, wgt_t* weights = NULL);
59  etype constructEdges(std::vector<gid_t>& edge_ids,
60  std::vector<lid_t>& degs,
61  std::vector<gid_t>& pins_to_verts,
62  std::vector<wgt_t>& e_weights);
63  etype constructEdges(gid_t num_edges, gid_t* edge_ids,
64  lid_t* degs, gid_t* pins_to_verts,
65  wgt_t* e_weights = NULL);
71  void constructGhosts(std::unordered_map<gid_t,part_t>& owns);
72  void constructGhosts(lid_t num_ghosts, gid_t* vert_ids, part_t* owns);
85  void constructGraph(bool isHG,
86  std::vector<gid_t>& verts,
87  std::vector<wgt_t>& weights,
88  std::vector<gid_t>& edge_ids,
89  std::vector<lid_t>& degs,
90  std::vector<gid_t>& pins_to_verts,
91  std::unordered_map<gid_t,part_t>& owns);
95  void makeUndirectedGraph();
96 
102  void removeEdges(etype t);
103 
104  // \cond
105  PNgraph* publicize() {return this;}
106  virtual ~Ngraph();
107  // \endcond
108 
114  void saveToFile(const char* prefix);
115  //TODO: put checks for number of files = number of processes
121  void loadFromFile(const char* prefix);
123 
124 
127 
128  gid_t numGlobalVtxs() const {return num_global_verts;}
131  gid_t numGlobalEdges(etype t=0) const {return num_global_edges[t];}
134  gid_t numGlobalPins(etype t=0) const {return num_global_pins[t];}
136  bool isHyper() const {return isHyperGraph;}
138 
140 
141  lid_t numLocalVtxs() const {return num_local_verts;}
143  lid_t numGhostVtxs() const {return num_ghost_verts;}
145  lid_t numTotalVtxs() const {return num_local_verts+num_ghost_verts;}
147  int numEdgeTypes() const {return num_types;}
150  lid_t numLocalEdges(etype t=0) const {return num_local_edges[t];}
153  lid_t numLocalPins(etype t=0) const {return num_local_pins[t];}
155 
158 
162  wgt_t weight(GraphVertex* vtx) const;
166  bool hasCoords() const;
171  const coord_t& coord(GraphVertex* vtx) const;
175  void setCoords(coord_t* cs);
179  void setWeights(wgt_t* wgts);
184  part_t owner(GraphVertex* vtx) const;
185  // \cond
186  part_t originalOwner(GraphVertex* vtx) const;
187  void setOriginalOwners();
188  void setOriginalOwners(std::vector<part_t>&);
189  void resetOwnership();
190  void resetPartition();
191  // \endcond
196  void getResidence(GraphEdge* e,Peers& residence) const;
202  bool isResidentOn(GraphEdge* e,part_t peer) const;
207  bool isCut(GraphEdge* e) const;
212  lid_t localID(GraphVertex* vtx) const;
217  gid_t globalID(GraphVertex* vtx) const;
218  // \cond HACK
219  GraphVertex* find(GraphVertex* vtx) const;
220  // \endcond
222 
224 
228  double weight(GraphEdge* edge) const;
233  lid_t localID(GraphEdge* e) const;
238  gid_t globalID(GraphEdge* e) const;
239  // \cond
240  lid_t u(lid_t,etype t =0) const;
241  // \endcond
246  GraphVertex* u(GraphEdge* edge) const;
251  GraphVertex* v(GraphEdge* edge) const;
256  void setEdgeWeights(std::vector<wgt_t>& wgts, etype t);
261  void setEdgeWeights(wgt_t wgt, etype t);
263 
266 
271  lid_t degree(GraphVertex* vtx,etype t=0) const;
277  EdgeIterator* edges(GraphVertex* vtx,etype t=0) const;
284  GraphIterator* adjacent(GraphVertex* vtx, etype t=0) const;
285 
290  lid_t degree(GraphEdge* edge) const;
295  PinIterator* pins(GraphEdge* edge) const;
296 
301  void create_vev_adjacency(etype t, bool compress = true);
306  void create_eve_adjacency(etype t, bool compress = true);
307 
314  VEVIterator* vev_begin(GraphVertex* vtx, etype t=0) const;
315  VEVIterator* vev_end(GraphVertex* vtx, etype t=0) const;
321  EVEIterator* eve_begin(GraphEdge* edge) const;
322  EVEIterator* eve_end(GraphEdge* edge) const;
323 
325 
328 
332  GraphTag* createIntTag(etype t=VTX_TYPE);
337  GraphTag* createDoubleTag(etype t=VTX_TYPE);
342  GraphTag* createLongTag(etype t=VTX_TYPE);
343 
344  typedef int (*IntGhostTag)(Ngraph*, GraphVertex*);
345  GraphTag* createIntGhostTag(IntGhostTag callback);
346  typedef double (*DoubleGhostTag)(Ngraph*, GraphVertex*);
347  GraphTag* createDoubleGhostTag(DoubleGhostTag callback);
348  typedef long (*LongGhostTag)(Ngraph*, GraphVertex*);
349  GraphTag* createLongGhostTag(LongGhostTag callback);
353  void destroyTag(GraphTag* t);
359  int getIntTag(GraphTag* tag,GraphVertex* v) const;
365  int getIntTag(GraphTag* tag,GraphEdge* e) const;
371  double getDoubleTag(GraphTag* tag,GraphVertex* v) const;
377  double getDoubleTag(GraphTag* tag,GraphEdge* e) const;
383  long getLongTag(GraphTag* tag,GraphVertex* v) const;
389  long getLongTag(GraphTag* tag,GraphEdge* e) const;
395  void setIntTag(GraphTag* tag,GraphVertex* v,int val);
401  void setIntTag(GraphTag* tag,GraphEdge* e,int val);
407  void setDoubleTag(GraphTag* tag,GraphVertex* v,double val);
413  void setDoubleTag(GraphTag* tag,GraphEdge* e,double val);
419  void setLongTag(GraphTag* tag,GraphVertex* v,long val);
425  void setLongTag(GraphTag* tag,GraphEdge* e,long val);
426 
434  void shareTag(GraphTag* tag, etype t=VTX_TYPE);
436 
439 
442  VertexIterator* begin() const;
446  GhostIterator* beginGhosts() const;
447  // \cond
448  GraphVertex* findGID(gid_t gid) const;
449  // \endcond
454  EdgeIterator* begin(etype t) const;
459  GraphVertex* iterate(VertexIterator*& vitr) const;
464  GraphVertex* iterate(GhostIterator*& vitr) const;
465 
466  GraphVertex* iterate(VEVIterator*& vevItr) const;
471  GraphEdge* iterate(EdgeIterator*& eitr) const;
476  GraphVertex* iterate(PinIterator*& pitr) const;
481  GraphVertex* iterate(GraphIterator*& gitr) const;
486  GraphEdge* edge(GraphIterator* gitr) const;
487  GraphEdge* iterate(EVEIterator*& eveItr) const;
488  //Destroys iterator
492  void destroy(EdgeIterator* eitr) const;
493  //Destroys iterator
497  void destroy(PinIterator* eitr) const;
501  void destroy(GraphIterator* gitr) const;
503 
505 
509  bool isEqual(GraphVertex* vtx1,GraphVertex* vtx2) const;
514  bool isEqual(GraphEdge* edge1,GraphEdge* edge2) const;
516 
519 
522  virtual PartitionMap* getPartition();
523  WeightPartitionMap* getWeightPartition();
524 
525  // \cond
526  void migrate(Migration* plan, MigrationTimers* mt = NULL);
527  void migrate(WeightMigration* plan, MigrationTimers* mt = NULL);
528  // \endcond
529  void repartition(part_t* partition);
531  void changeOwners(int* newRanks);
532 
533  void printStats() const;
534  protected:
535 
536  GraphTag* ghost_weights;
537 
538  // \cond
539  Ngraph();
540  Ngraph(const Ngraph&) {throw std::runtime_error("Copying Ngraph not supported");}
541  Ngraph& operator=(const Ngraph&) {
542  throw std::runtime_error("Assignment of Ngraph not supported");
543  }
544  void destroyData();
545  // \endcond
546 
547  // \cond
551  etype addEdgeType() {assert(num_types!=MAX_TYPES);return num_types++;}
552 
557  void makeEdgeArray(etype t,int count);
564  void setEdge(lid_t l,gid_t g,wgt_t w,etype t);
565 
566  // \endcond
567 
568  // \cond PRIVATE
569  private:
570  void updateGhostOwners(Migration*);
571  void sendVertex(GraphVertex*, part_t);
572  void recvVertex(std::vector<gid_t>&,std::vector<wgt_t>&,
573  std::vector<part_t>&);
574  void sendCoord(GraphVertex*, part_t);
575  void recvCoord(coord_t*,lid_t& size);
576  void sendEdges(Migration*,std::unordered_set<GraphEdge*>&);
577  void recvEdges(std::unordered_set<gid_t>&,std::vector<gid_t>&,
578  std::vector<wgt_t>&,std::vector<lid_t>&,
579  std::vector<gid_t>&,std::unordered_map<gid_t,part_t>&,
580  etype);
581 
582  WeightPartitionMap wp_map;
583  // \endcond
584 };
585 
588 Ngraph* createEmptyGraph();
589 
593 void destroyGraph(Ngraph* g);
594 
598 bool checkValidity(Ngraph* g);
599 
600  void writeVTK(Ngraph* g,const char* prefix,GraphTag* tag=NULL,etype t=NO_TYPE);
601 
602 } //namespace
603 
604 #endif
Generated by doxygen 1.9.1