43 #include <boost/config.hpp>
44 #include <boost/graph/adjacency_list.hpp>
45 #include <boost/graph/cuthill_mckee_ordering.hpp>
46 #include <boost/graph/properties.hpp>
47 #include <boost/graph/bandwidth.hpp>
55 namespace MultiRegions
79 const unsigned int bndPatch,
91 m_leftDaughterGraph (),
92 m_rightDaughterGraph()
94 static int offset = -5;
97 int recurLevel = sepTree[offset+0];
98 int nLeftIntDofs = sepTree[offset+2];
99 int nRightIntDofs = sepTree[offset+3];
100 int nBndDofs = sepTree[offset+4];
102 bool daughtersConstructed[2] = {
false,
false};
104 if ((offset + 5) < sepTree.num_elements())
106 while (sepTree[offset+5] > recurLevel)
108 switch (sepTree[offset+6])
115 daughtersConstructed[0] =
true;
123 daughtersConstructed[1] =
true;
131 if ((offset + 5) >= sepTree.num_elements())
140 if (!daughtersConstructed[0] && nLeftIntDofs)
146 if (!daughtersConstructed[1] && nRightIntDofs)
160 const int nPartition)
168 m_leftDaughterGraph(),
169 m_rightDaughterGraph()
179 static int nBndDofs = 0;
180 static int level = 0;
195 returnval = nBndDofs;
208 static int level = 0;
209 static int offset = 0;
233 static int level = 0;
235 cout <<
"LEVEL " << level <<
" " <<
m_BndDofs->GetNverts() << endl;
250 std::vector<SubGraphSharedPtr>& leaves)
const
269 leaves.push_back(leave);
293 static int level = 0;
294 static int nLeaves = 0;
347 static int level = 0;
348 static int nLeaves = 0;
398 const int nVerts) : m_IntBlocks(), m_daughterGraph()
405 for (
int i = 0 ; i < nVerts; i++)
414 const int nPartition) :
432 topDownGraph->SetGlobalNumberingOffset();
434 topDownGraph->CutEmptyLeaves();
443 int ncuts = topDownGraph->CutLeaves();
459 graph->CutEmptyLeaves();
461 ncuts = graph->CutLeaves();
476 static int nIntDofs = 0;
477 static int level = 0;
492 returnval = nIntDofs;
505 static int level = 0;
508 cout <<
"LEVEL " << level << endl;
509 cout <<
"interior blocks" << endl;
544 for (
int i=0; i < nDofs; i++)
546 iperm[i] = iperm1[iperm[i]];
554 static int offset = 0;
555 static int level = 0;
567 for(
int j = 0; j <
m_IntBlocks[i]->GetNverts(); j++)
569 iperm[GlobIdOffset+j] = offset;
584 static int offset = 0;
585 static int level = 0;
595 int OrigGlobIdOffset =
m_IntBlocks[i]->GetIdOffset();
600 for(
int j = 0; j <
m_IntBlocks[i]->GetNverts(); j++)
602 newNverts += wgts[OrigGlobIdOffset+j];
603 offset += wgts[OrigGlobIdOffset+j];
631 const int leveltomask,
634 static int level = 0;
637 if(level < leveltomask)
641 else if(level == leveltomask)
649 for(
int j = 0; j < nVerts; j++)
651 maskarray[GlobIdOffset+j] = (
NekDouble) i;
658 "If statement should not arrive here");
665 const int whichlevel)
const
668 static int level = 0;
671 if(level < whichlevel)
676 else if(level == whichlevel)
683 "If statement should not arrive here");
692 const int whichlevel,
695 static int level = 0;
698 if(level < whichlevel)
702 else if(level == whichlevel)
705 "Array dimension not sufficient");
709 outarray[i] = (
unsigned int)
m_IntBlocks[i]->GetNverts();
715 "If statement should not arrive here");
722 const int whichlevel,
const int patch)
const
725 static int level = 0;
728 if(level < whichlevel)
732 else if(level == whichlevel)
739 "If statement should not arrive here");
750 std::vector<SubGraphSharedPtr> returnval;
751 static int level = 0;
754 if(level < whichlevel)
758 else if(level == whichlevel)
765 "If statement should not arrive here");
773 const int whichlevel)
const
776 static int level = 0;
779 if(level < whichlevel)
783 else if(level == whichlevel)
791 "If statement should not arrive here");
802 static int level = 0;
809 returnval = max(returnval,level);
819 return g->GetNverts() == 0;
829 typedef boost::adjacency_list<
830 boost::setS, boost::vecS, boost::undirectedS> BoostGraph;
831 typedef boost::graph_traits<BoostGraph>::vertex_descriptor
833 typedef boost::graph_traits<BoostGraph>::vertex_iterator
835 typedef boost::graph_traits<BoostGraph>::adjacency_iterator
836 BoostAdjacencyIterator;
843 int nGraphVerts = boost::num_vertices(graph);
845 ASSERTL1(perm. num_elements() >= nGraphVerts &&
846 iperm.num_elements() >= nGraphVerts,
847 "Non-matching dimensions");
851 std::vector<BoostVertex> reorderedVerts(nGraphVerts);
852 boost::cuthill_mckee_ordering(graph, reorderedVerts.rbegin());
855 for(
int i = 0; i < nGraphVerts; i++)
857 perm[i] = reorderedVerts[i];
858 iperm[ reorderedVerts[i] ] = i;
863 const BoostGraph &graph,
867 std::set<int> partVerts,
870 int nGraphVerts = boost::num_vertices(graph);
871 int nGraphEdges = boost::num_edges (graph);
873 ASSERTL1(perm. num_elements() >= nGraphVerts &&
874 iperm.num_elements() >= nGraphVerts,
875 "Non-matching dimensions");
912 int nPartition = partVerts.size();
913 int nNonPartition = nGraphVerts - partVerts.size();
914 BoostVertexIterator vertit, vertit_end;
915 BoostAdjacencyIterator adjvertit, adjvertit_end;
927 for (i = cnt = 0; i < nGraphVerts; ++i)
929 if (partVerts.count(i) == 0)
931 initial_perm [i] = cnt;
932 iinitial_perm[cnt++] = i;
936 for (i = 0; i < nGraphVerts; ++i)
938 if (partVerts.count(i) > 0)
940 initial_perm [i] = cnt;
941 iinitial_perm[cnt++] = i;
946 boost::property_map<BoostGraph, boost::vertex_index_t>::type
947 index =
get(boost::vertex_index, graph);
949 for (boost::tie(vertit, vertit_end) = boost::vertices(graph);
950 vertit != vertit_end; ++vertit)
952 if (partVerts.count(index[*vertit]) > 0)
957 for (boost::tie(adjvertit, adjvertit_end) =
958 boost::adjacent_vertices(*vertit,graph);
959 adjvertit != adjvertit_end;
962 if (partVerts.count(index[*adjvertit]) > 0)
966 adjncy[acnt++] = initial_perm[*adjvertit];
975 int sizeSeparatorTree = nGraphVerts*10;
995 nNonPartition,xadj,adjncy,perm_tmp,iperm_tmp,
996 septreeTmp, mdswitch);
1001 "Error in calling metis (the size of the separator"
1002 " tree might not be sufficient)");
1006 for (i = 0; i < nGraphVerts; ++i)
1008 if (partVerts.count(i) == 0)
1010 iperm[i] = iperm_tmp[initial_perm[i]];
1015 for (i = nNonPartition, it = partVerts.begin();
1016 it != partVerts.end(); ++it, ++i)
1022 for (i = 0; i < nGraphVerts; ++i)
1025 "Perm error " + boost::lexical_cast<std::string>(i));
1029 int trueSizeSepTree = 0;
1030 for (i = 0; septreeTmp[i] != -1; i++)
1058 substructgraph->UpdateBottomUpReordering(perm,iperm);
1064 for(
int i = 0; i < nGraphVerts; i++)
1078 int nGraphVerts = boost::num_vertices(graph);
1080 ASSERTL1(perm. num_elements() >= nGraphVerts &&
1081 iperm.num_elements() >= nGraphVerts,
1082 "Non-matching dimensions");
1084 for (
int i = 0; i < nGraphVerts; i++)
Array< OneD, NekDouble > m_sign
int GetNpatchesWithInterior(const int whichlevel) const
#define ASSERTL0(condition, msg)
int GetNdaughterGraphs() const
#define NEKERROR(type, msg)
Assert Level 0 – Fundamental assert which is used whether in FULLDEBUG, DEBUG or OPT compilation mod...
void MaskPatches(const int leveltomask, Array< OneD, NekDouble > &maskarray) const
void GetNintDofsPerPatch(const int whichlevel, Array< OneD, unsigned int > &outarray) const
void MultiLevelBisectionReordering(const BoostGraph &graph, Array< OneD, int > &perm, Array< OneD, int > &iperm, BottomUpSubStructuredGraphSharedPtr &substructgraph, std::set< int > partVerts, int mdswitch)
static boost::shared_ptr< DataType > AllocateSharedPtr()
Allocate a shared pointer from the memory pool.
#define sign(a, b)
return the sign(b)*a
General purpose memory allocation routines with the ability to allocate from thread specific memory p...
int GetNumGlobalDofs(const int whichlevel) const
MultiLevelBisectedGraph(const Array< OneD, const int > sepTree)
void DumpNBndDofs(void) const
boost::shared_ptr< BottomUpSubStructuredGraph > BottomUpSubStructuredGraphSharedPtr
void CuthillMckeeReordering(const BoostGraph &graph, Array< OneD, int > &perm, Array< OneD, int > &iperm)
BottomUpSubStructuredGraph(const Array< OneD, const int > septree, const int nPartition)
boost::shared_ptr< MultiLevelBisectedGraph > MultiLevelBisectedGraphSharedPtr
void CollectLeaves(std::vector< SubGraphSharedPtr > &leaves) const
boost::shared_ptr< SubGraph > SubGraphSharedPtr
static void as_onmetis(int nVerts, Nektar::Array< Nektar::OneD, int > xadj, Nektar::Array< Nektar::OneD, int > adjncy, Nektar::Array< Nektar::OneD, int > perm, Nektar::Array< Nektar::OneD, int > iperm, Nektar::Array< Nektar::OneD, int > map, int mdswitch=1)
SubGraphSharedPtr m_BndDofs
Array< OneD, unsigned int > m_bndPatch
void ExpandGraphWithVertexWeights(const Array< OneD, const int > &wgts)
MultiLevelBisectedGraphSharedPtr m_rightDaughterGraph
void SetGlobalNumberingOffset()
std::vector< SubGraphSharedPtr > GetInteriorBlocks() const
std::vector< SubGraphSharedPtr > m_IntBlocks
BottomUpSubStructuredGraphSharedPtr m_daughterGraph
StandardMatrixTag boost::call_traits< LhsDataType >::const_reference rhs typedef NekMatrix< LhsDataType, StandardMatrixTag >::iterator iterator
Array< OneD, int > m_dofId
void UpdateBottomUpReordering(Array< OneD, int > &perm, Array< OneD, int > &iperm) const
bool SubGraphWithoutVerts(const SubGraphSharedPtr g)
Array< OneD, int > m_patchId
MultiLevelBisectedGraphSharedPtr m_leftDaughterGraph
~MultiLevelBisectedGraph(void)
~BottomUpSubStructuredGraph(void)
void SetBottomUpReordering(Array< OneD, int > &iperm) const
#define ASSERTL1(condition, msg)
Assert Level 1 – Debugging which is used whether in FULLDEBUG or DEBUG compilation mode...
void Vcopy(int n, const T *x, const int incx, T *y, const int incy)
void SetPatchMap(const int n, const int patchId, const int dofId, const unsigned int bndPatch, const NekDouble sign)
int GetInteriorOffset(const int whichlevel, const int patch=0) const
void NoReordering(const BoostGraph &graph, Array< OneD, int > &perm, Array< OneD, int > &iperm)