EnGPar
Partitioning using the N-Graph
 All Classes Files Pages
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 
37  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 
126 
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 
139 
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 
157 
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 
223 
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);
258 
260 
266  lid_t degree(GraphVertex* vtx,etype t=0) const;
272  EdgeIterator* edges(GraphVertex* vtx,etype t=0) const;
279  GraphIterator* adjacent(GraphVertex* vtx, etype t=0) const;
280 
285  lid_t degree(GraphEdge* edge) const;
290  PinIterator* pins(GraphEdge* edge) const;
291 
296  void create_vev_adjacency(etype t, bool compress = true);
301  void create_eve_adjacency(etype t, bool compress = true);
302 
309  VEVIterator* vev_begin(GraphVertex* vtx, etype t=0) const;
310  VEVIterator* vev_end(GraphVertex* vtx, etype t=0) const;
316  EVEIterator* eve_begin(GraphEdge* edge) const;
317  EVEIterator* eve_end(GraphEdge* edge) const;
318 
320 
322 
327  GraphTag* createIntTag(etype t=VTX_TYPE);
332  GraphTag* createDoubleTag(etype t=VTX_TYPE);
337  GraphTag* createLongTag(etype t=VTX_TYPE);
338 
339  typedef int (*IntGhostTag)(Ngraph*, GraphVertex*);
340  GraphTag* createIntGhostTag(IntGhostTag callback);
341  typedef double (*DoubleGhostTag)(Ngraph*, GraphVertex*);
342  GraphTag* createDoubleGhostTag(DoubleGhostTag callback);
343  typedef long (*LongGhostTag)(Ngraph*, GraphVertex*);
344  GraphTag* createLongGhostTag(LongGhostTag callback);
348  void destroyTag(GraphTag* t);
354  int getIntTag(GraphTag* tag,GraphVertex* v) const;
360  int getIntTag(GraphTag* tag,GraphEdge* e) const;
366  double getDoubleTag(GraphTag* tag,GraphVertex* v) const;
372  double getDoubleTag(GraphTag* tag,GraphEdge* e) const;
378  long getLongTag(GraphTag* tag,GraphVertex* v) const;
384  long getLongTag(GraphTag* tag,GraphEdge* e) const;
390  void setIntTag(GraphTag* tag,GraphVertex* v,int val);
396  void setIntTag(GraphTag* tag,GraphEdge* e,int val);
402  void setDoubleTag(GraphTag* tag,GraphVertex* v,double val);
408  void setDoubleTag(GraphTag* tag,GraphEdge* e,double val);
414  void setLongTag(GraphTag* tag,GraphVertex* v,long val);
420  void setLongTag(GraphTag* tag,GraphEdge* e,long val);
421 
429  void shareTag(GraphTag* tag, etype t=VTX_TYPE);
431 
433 
437  VertexIterator* begin() const;
441  GhostIterator* beginGhosts() const;
442  // \cond
443  GraphVertex* findGID(gid_t gid) const;
444  // \endcond
449  EdgeIterator* begin(etype t) const;
454  GraphVertex* iterate(VertexIterator*& vitr) const;
459  GraphVertex* iterate(GhostIterator*& vitr) const;
460 
461  GraphVertex* iterate(VEVIterator*& vevItr) const;
466  GraphEdge* iterate(EdgeIterator*& eitr) const;
471  GraphVertex* iterate(PinIterator*& pitr) const;
476  GraphVertex* iterate(GraphIterator*& gitr) const;
481  GraphEdge* edge(GraphIterator* gitr) const;
482  GraphEdge* iterate(EVEIterator*& eveItr) const;
483  //Destroys iterator
487  void destroy(EdgeIterator* eitr) const;
488  //Destroys iterator
492  void destroy(PinIterator* eitr) const;
496  void destroy(GraphIterator* gitr) const;
498 
499 
504  bool isEqual(GraphVertex* vtx1,GraphVertex* vtx2) const;
509  bool isEqual(GraphEdge* edge1,GraphEdge* edge2) const;
511 
513 
517  virtual PartitionMap* getPartition();
518  WeightPartitionMap* getWeightPartition();
519 
520  // \cond
521  void migrate(Migration* plan, MigrationTimers* mt = NULL);
522  void migrate(WeightMigration* plan, MigrationTimers* mt = NULL);
523  // \endcond
524  void repartition(part_t* partition);
526  void changeOwners(int* newRanks);
527 
528  void printStats() const;
529  protected:
530 
531  GraphTag* ghost_weights;
532 
533  // \cond
534  Ngraph();
535  Ngraph(const Ngraph&) {throw std::runtime_error("Copying Ngraph not supported");}
536  Ngraph& operator=(const Ngraph&) {
537  throw std::runtime_error("Assignment of Ngraph not supported");
538  }
539  void destroyData();
540  // \endcond
541 
542  // \cond
546  etype addEdgeType() {assert(num_types!=MAX_TYPES);return num_types++;}
547 
552  void makeEdgeArray(etype t,int count);
559  void setEdge(lid_t l,gid_t g,wgt_t w,etype t);
560 
561  // \endcond
562 
563  // \cond PRIVATE
564  private:
565  void updateGhostOwners(Migration*);
566  void sendVertex(GraphVertex*, part_t);
567  void recvVertex(std::vector<gid_t>&,std::vector<wgt_t>&,
568  std::vector<part_t>&);
569  void sendCoord(GraphVertex*, part_t);
570  void recvCoord(coord_t*,lid_t& size);
571  void sendEdges(Migration*,std::unordered_set<GraphEdge*>&);
572  void recvEdges(std::unordered_set<gid_t>&,std::vector<gid_t>&,
573  std::vector<wgt_t>&,std::vector<lid_t>&,
574  std::vector<gid_t>&,std::unordered_map<gid_t,part_t>&,
575  etype);
576 
577  WeightPartitionMap wp_map;
578  // \endcond
579 };
580 
583 Ngraph* createEmptyGraph();
584 
588 void destroyGraph(Ngraph* g);
589 
593 bool checkValidity(Ngraph* g);
594 
595  void writeVTK(Ngraph* g,const char* prefix,GraphTag* tag=NULL,etype t=NO_TYPE);
596 
597 } //namespace
598 
599 #endif
Generated by   doxygen 1.8.5