Galois: PMetis.h Source File

00001 
00024 #ifndef PMETIS_H_
00025 #define PMETIS_H_
00026 
00027 #include "GMetisConfig.h"
00028 #include "MetisGraph.h"
00029 #include "Coarsening.h"
00030 #include "defs.h"
00031 class PMetis{
00032 public:
00033         PMetis(int coasenTo, int maxVertexWeight):coarsener(true, coasenTo, maxVertexWeight) {
00034         }
00035 
00036 //      /**
00037 //       * Partition the graph using PMetis
00038 //       */
00039 //      void partition(MetisGraph* metisGraph, int nparts){
00040 //              int maxVertexWeight = (int) (1.5 * ((metisGraph->getGraph()->size()) / Coarsener::COARSEN_FRACTION));
00041 //              float* totalPartitionWeights = new float[nparts];
00042 //              arrayFill(totalPartitionWeights, nparts, 1 / (float) nparts);
00043 //              metisGraph->computeAdjWgtSums();
00044 //              //    PMetis pmetis = new PMetis(maxVertexWeight, 20);
00046 //      }
00047 
00048 //private:
00049 //      int* mincutCollection;
00050 //
00051 //      void mlevelBisection(MetisGraph* metisGraph, int nparts, float* totalPartWeights, int tpindex,
00052 //                      int partStartIndex){
00053 //
00054 //              GGraph* graph = metisGraph->getGraph();
00055 //              int totalVertexWeight = 0;
00056 //              for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00057 //                      GNode node = *ii;
00058 //                      totalVertexWeight += node.getData().getWeight();
00059 //              }
00060 //
00061 //
00062 //              float vertexWeightRatio = 0;
00063 //              for (int i = 0; i < nparts / 2; i++) {
00064 //                      vertexWeightRatio += totalPartWeights[tpindex + i];
00065 //              }
00066 //              int bisectionWeights[2];
00067 //              bisectionWeights[0] = (int) (totalVertexWeight * vertexWeightRatio);
00068 //              bisectionWeights[1] = totalVertexWeight - bisectionWeights[0];
00069 //
00070 //              MetisGraph* mcg = coarsener.coarsen(metisGraph);
00071 //              bisection(mcg, bisectionWeights, coarsener.getCoarsenTo());
00072 //              refineTwoWay(mcg, metisGraph, bisectionWeights);
00073 //
00074 //              if (nparts <= 2) {
00075 //                      for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00076 //                              GNode node = *ii;
00077 //                              assert(node.getData().getPartition()>=0);
00078 //                              node.getData().setPartition(node.getData().getPartition() + partStartIndex);
00079 //                      }
00080 //              } else {
00081 //                      for (int i = 0; i < nparts / 2; i++) {
00082 //                              totalPartWeights[i + tpindex] *= (1 / vertexWeightRatio);
00083 //                      }
00084 //                      //nparts/2 may not be equal to nparts-nparts/2
00085 //                      for (int i = 0; i < nparts - nparts / 2; i++) {
00086 //                              totalPartWeights[i + tpindex + nparts / 2] *= (1 / (1 - vertexWeightRatio));
00087 //                      }
00088 //                      MetisGraph* subGraphs = new MetisGraph[2];
00090 //                      splitGraph(metisGraph, subGraphs);
00091 //                      if (nparts > 3) {
00092 //                              mlevelRecursiveBisection(&subGraphs[0], nparts / 2, totalPartWeights, tpindex, partStartIndex);
00093 //                              mlevelRecursiveBisection(&subGraphs[1], nparts - nparts / 2, totalPartWeights, tpindex + nparts / 2,
00094 //                                              partStartIndex + nparts / 2);
00095 //                              metisGraph->setMinCut(metisGraph->getMinCut() + subGraphs[0].getMinCut() + subGraphs[1].getMinCut());
00096 //                      } else if (nparts == 3) {
00097 //                              for (GGraph::active_iterator ii = subGraphs[0].getGraph()->active_begin(), ee = subGraphs[0].getGraph()->active_end(); ii != ee; ++ii) {
00098 //                                      GNode node = *ii;
00099 //                                      MetisNode& nodeData = node.getData(Galois::Graph::NONE);
00100 //                                      nodeData.setPartition(partStartIndex);
00101 //                                      assert(nodeData.getPartition()>=0);
00102 //                              }
00103 //                              mlevelRecursiveBisection(&subGraphs[1], nparts - nparts / 2, totalPartWeights, tpindex + nparts / 2,
00104 //                                              partStartIndex + nparts / 2);
00105 //                              metisGraph->setMinCut(metisGraph->getMinCut() + subGraphs[1].getMinCut());
00106 //                      }
00107 //                      for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00108 //                              GNode node = *ii;
00109 //                              MetisNode& nodeData = node.getData();
00110 //                              nodeData.setPartition(metisGraph->getSubGraphMapTo(nodeData.getNodeId()).getData().getPartition());
00111 //                              assert(nodeData.getPartition()>=0);
00112 //                      }
00114 //                      metisGraph->releaseSubGraphMapTo();
00115 //                      delete subGraphs[0].getGraph();
00116 //                      delete subGraphs[1].getGraph();
00117 //                      delete[] subGraphs;
00118 //              }
00119 //
00120 //
00121 //      }
00122 public:
00127         void mlevelRecursiveBisection(MetisGraph* metisGraph, int nparts, float* totalPartWeights, int tpindex,
00128                         int partStartIndex) {
00129 
00130                 GGraph* graph = metisGraph->getGraph();
00131                 int totalVertexWeight = 0;
00132                 for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00133                         GNode node = *ii;
00134                         totalVertexWeight += node.getData().getWeight();
00135                 }
00136 
00137 //              cout<<"pmtis-----------"<<endl;
00138                 float vertexWeightRatio = 0;
00139                 for (int i = 0; i < nparts / 2; i++) {
00140                         vertexWeightRatio += totalPartWeights[tpindex + i];
00141                 }
00142                 int bisectionWeights[2];
00143                 bisectionWeights[0] = (int) (totalVertexWeight * vertexWeightRatio);
00144                 bisectionWeights[1] = totalVertexWeight - bisectionWeights[0];
00145 
00146                 MetisGraph* mcg = coarsener.coarsen(metisGraph);
00147 //              cout<<"finish coarsening-----------"<<endl;
00148                 bisection(mcg, bisectionWeights, coarsener.getCoarsenTo());
00149                 refineTwoWay(mcg, metisGraph, bisectionWeights);
00150 
00151                 if (nparts <= 2) {
00152                         for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00153                                 GNode node = *ii;
00154                                 assert(node.getData().getPartition()>=0);
00155                                 node.getData().setPartition(node.getData().getPartition() + partStartIndex);
00156                         }
00157                 } else {
00158                         for (int i = 0; i < nparts / 2; i++) {
00159                                 totalPartWeights[i + tpindex] *= (1 / vertexWeightRatio);
00160                         }
00161                         //nparts/2 may not be equal to nparts-nparts/2
00162                         for (int i = 0; i < nparts - nparts / 2; i++) {
00163                                 totalPartWeights[i + tpindex + nparts / 2] *= (1 / (1 - vertexWeightRatio));
00164                         }
00165                         MetisGraph* subGraphs = new MetisGraph[2];
00166 //                      cout<<"split graph"<<endl;
00167                         splitGraph(metisGraph, subGraphs);
00168                         if (nparts > 3) {
00169                                 mlevelRecursiveBisection(&subGraphs[0], nparts / 2, totalPartWeights, tpindex, partStartIndex);
00170                                 mlevelRecursiveBisection(&subGraphs[1], nparts - nparts / 2, totalPartWeights, tpindex + nparts / 2,
00171                                                 partStartIndex + nparts / 2);
00172                                 metisGraph->setMinCut(metisGraph->getMinCut() + subGraphs[0].getMinCut() + subGraphs[1].getMinCut());
00173                         } else if (nparts == 3) {
00174                                 for (GGraph::active_iterator ii = subGraphs[0].getGraph()->active_begin(), ee = subGraphs[0].getGraph()->active_end(); ii != ee; ++ii) {
00175                                         GNode node = *ii;
00176                                         MetisNode& nodeData = node.getData(Galois::NONE);
00177                                         nodeData.setPartition(partStartIndex);
00178                                         assert(nodeData.getPartition()>=0);
00179                                 }
00180                                 mlevelRecursiveBisection(&subGraphs[1], nparts - nparts / 2, totalPartWeights, tpindex + nparts / 2,
00181                                                 partStartIndex + nparts / 2);
00182                                 metisGraph->setMinCut(metisGraph->getMinCut() + subGraphs[1].getMinCut());
00183                         }
00184                         for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00185                                 GNode node = *ii;
00186                                 MetisNode& nodeData = node.getData();
00187                                 nodeData.setPartition(metisGraph->getSubGraphMapTo(nodeData.getNodeId()).getData().getPartition());
00188                                 assert(nodeData.getPartition()>=0);
00189                         }
00190 
00191                         metisGraph->releaseSubGraphMapTo();
00192                         delete subGraphs[0].getGraph();
00193                         delete subGraphs[1].getGraph();
00194                         delete[] subGraphs;
00195                 }
00196         }
00197 
00198         void splitGraph(MetisGraph* metisGraph, MetisGraph* subGraphs) {
00199                 int subGraphNodeNum[2];
00200                 subGraphNodeNum[0] = 0;
00201                 subGraphNodeNum[1] = 0;
00202                 GGraph* graph = metisGraph->getGraph();
00203 
00204                 // = new MetisGraph[2];
00205                 //    subGraphs[0] = new MetisGraph();
00206                 //    subGraphs[1] = new MetisGraph();
00207                 subGraphs[0].setGraph(new GGraph());
00208                 subGraphs[1].setGraph(new GGraph());
00209                 metisGraph->initSubGraphMapTo();
00210                 for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00211                         GNode node = *ii;
00212                         MetisNode& nodeData = node.getData();
00213                         assert(nodeData.getPartition()>=0);
00214                         GNode newNode = subGraphs[nodeData.getPartition()].getGraph()->createNode(
00215                                         MetisNode(subGraphNodeNum[nodeData.getPartition()], nodeData.getWeight()));
00216 //                      nodeData.setSubGraphMap(newNode);
00217                         subGraphs[nodeData.getPartition()].getGraph()->addNode(newNode);
00218                         metisGraph->setSubGraphMapTo(nodeData.getNodeId(), newNode);
00219                         subGraphNodeNum[nodeData.getPartition()]++;
00220                 }
00221 
00222 //              for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00223 //                      GNode node = *ii;
00224 //                      MetisNode& nodeData = node.getData();
00225 //                      subGraphs[nodeData.getPartition()].getGraph()->addNode(metisGraph->getSubGraphMapTo(nodeData.getNodeId()));
00226 //              }
00227 
00228                 subGraphs[0].setNumNodes(subGraphNodeNum[0]);
00229                 subGraphs[1].setNumNodes(subGraphNodeNum[1]);
00230                 assert(subGraphs[0].getNumNodes() == subGraphNodeNum[0]);
00231                 assert(subGraphs[1].getNumNodes() == subGraphNodeNum[1]);
00232 
00233                 for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00234                         GNode node = *ii;
00235                         MetisNode& nodeData = node.getData();
00236                         int index = nodeData.getPartition();
00237                         GGraph* subGraph = subGraphs[index].getGraph();
00238                         metisGraph->getSubGraphMapTo(nodeData.getNodeId()).getData().setAdjWgtSum(nodeData.getAdjWgtSum());
00239                         assert(metisGraph->getSubGraphMapTo(nodeData.getNodeId()).getData().getAdjWgtSum()>=0);
00240                         for (GGraph::neighbor_iterator jj = graph->neighbor_begin(node, Galois::NONE), eejj = graph->neighbor_end(node, Galois::NONE); jj != eejj; ++jj) {
00241                                 GNode neighbor = *jj;
00242 
00243                                 MetisNode& neighborData = neighbor.getData();
00244                                 int edgeWeight = graph->getEdgeData(node, jj);
00245                                 if (!nodeData.isBoundary() || nodeData.getPartition() == neighborData.getPartition()) {
00246 //                                      subGraph->addEdge(nodeData.getSubGraphMap(), neighborData.getSubGraphMap(), edgeWeight);
00247                                         subGraph->addEdge(metisGraph->getSubGraphMapTo(nodeData.getNodeId()), metisGraph->getSubGraphMapTo(neighborData.getNodeId()), edgeWeight);
00248                                 } else {
00249 //                                      nodeData.getSubGraphMap().getData().setAdjWgtSum(
00250 //                                                      nodeData.getSubGraphMap().getData().getAdjWgtSum() - edgeWeight);
00251                                         metisGraph->getSubGraphMapTo(nodeData.getNodeId()).getData().setAdjWgtSum(
00252                                                         metisGraph->getSubGraphMapTo(nodeData.getNodeId()).getData().getAdjWgtSum() - edgeWeight);
00253 
00254                                 }
00255                         }
00256                 }
00257         }
00258         const static double UB_FACTOR = 1;
00259 private:
00260         Coarsener coarsener;
00261 
00262 };
00263 
00264 #endif /* PMETIS_H_ */