:
Есть матрица остовного дерева
Она собой представляет матрицу смежности графа, где значения в ячейках - вес ребра между двумя вершинами, * - значит ребра для этих вершин нет.
вот так можно представить этот граф
Верщины и вес верщины
"Войновка,Инская" 2732
"Егоршино,Пермь" 4667
"Орехово,Инская" 6588
"Лянгасово,Егоршино" 7489
"Пермь,Войновка" 14946
Ребра, как и кластеры, у меня реализованны следующей структурой
:
Раскрывающийся текст
struct Cluster
{
private :
int value_;
QVector <int> items_;
QPoint centerPos;
bool isPainted;
public :
Cluster();
Cluster(int item1 ,int item2, int nValue);
Cluster(int item1, int nValue);
void setValue(int newValue);
int value(){ return value_; }
const QVector<int> & items() {return items_;};
void setPainted(bool is);
QString toString(QStringList * lst);
void append(Cluster nClust);
bool operator==(Cluster & o){return items_==o.items();};
};
Раскрывающийся текст
Model::Cluster::Cluster(int item1 , int item2, int nValue)
{
value_=nValue;
items_.push_back(item1);
items_.push_back(item2);
}
Model::Cluster::Cluster(int item1 , int nValue)
{
value_=nValue;
items_.push_back(item1);
}
void Model::Cluster::setValue(int newValue)
{
value_=newValue;
}
QString Model::Cluster::toString(QStringList * lst)
{
QString str;
QStringList * list = lst;
int i=0;
for(;i<items_.size()-1;++i)
str.append(list->at(items_.at(i))+",");
str.append(list->at(items_.at(i))+"");
return str;
}
void Model::Cluster::append(Cluster nClust)
{
for(int i=0;i<nClust.items().size();++i)
items_.push_back(nClust.items().at(i));
}
void Model::Cluster::setPainted(bool is)
{
isPainted=is;
}
Model::Cluster::Cluster()
{
}
void Model::outClusters()
{
for(int i=0;i<clusters.size();++i)
{
qDebug() << clusters.at(i).first << ":";
for(int j=0;j<clusters.at(i).second.size();++j)
qDebug() << clusters[i].second[j].value() << ":" << clusters[i].second[j].toString(&vHeaderData);
}
}
Суть алгоритма:
Вершины – объекты минимального остовного дерева группируются в кластеры.
Выбираются два объекта, которым соответствует минимальное ребро.
. Далее эти объекты стягиваются в один кластер (класс, таксон, страту) и
процедура повторяется до тех пор, пока на n-1(n-количество верщин, n-1 - ребер) этапе группирования не будет
сформирован один кластер, объединяющий все объекты.
Вот так :
1. шаг
формируется кластер из "Войновка,Инская" со значением 2732
2.
"Егоршино,Пермь" 4667
3.
"Орехово,Инская,Войновка" 6588
4.
"Лянгасово,Егоршино,Пермь" 7489
5.
"Лянгасово,Егоршино,Пермь,Орехово,Инская,Войновка" 14946
подобрая программа лежит вот тут http://el-niko.ru/lab/1/
Все что я смог реализовать, это нахождение ребер..тоесть я пытался как-то додуматься до реализации этого алгоритма, но заходил в тупик.
Вот немного кода :
Раскрывающийся текст
clusters.clear();// Это вектор пар QVector < QPair <int,QVector<Cluster> > > clusters;
//нужен для отображения срезов кластеров, т.е на значении int у нас есть вектор из кластеров , у которох их значение не привышает заданное, т.е
//в нашем случае, при значении 4667 мы отобразим :
//"Войновка,Инская"
//"Егоршино,Пермь"
// Лянгасово
// Орехово
static bool *isNum = new bool;
int rc = spanningMatrixModel->rowCount();
int sM[rc][rc];
QVector <Cluster> ribs;
QVector <Cluster> items;
for (int i=0;i<rc;++i)
for (int j=0;j<rc;++j)
{
sM[i][j]=spanningMatrixModel->item(i,j)->text().toInt(isNum,10);//переводим данные из таблицы в матрицу
if (sM[i][j]!= 0 )
items.push_back(Cluster(i,sM[i][j]));//записывает значения для каждой вершины
}
for (int i=0;i<rc;++i)
for (int j=i+1;j<rc;++j)
if (sM[i][j]!=0)
ribs.push_back(Cluster(i,j,sM[i][j]));//получаем ребра графа
А вот как дальше быть, я не знаю... Может кто-то уже сталкивался с этой задачей? Просто я в недоумении..