Обход иерархического дерева вниз., дерево из QTreeWidgetItem Опции

[Andrewshkovskii]

Как всегда рассчитываю на помощь volvo
Есть дерево, в нем возможны 3 элемента
3. Элемент типа 1003 - критерий, у этого элемента есть некоторое значение.
2. Элемент типа 1002 - это подгруппа (т.е. у неё есть род. группа) и она содержит только элементы типа 1003, у неё есть значение(вес).
1. Элемент типа 1001 - Группа верхнего уровня (в неё входят либо только элементы 1002 - подгруппы, либо только элементы 1003 - критерии), у него есть значение(вес).

Глубина/вложенность дерева может быть бесконечно глубокой.

Какой проход необходимо реализовать :
1. Необходимо подсчитать значениях все элементов 1003. (значение_критериев_группы)
2. Умножить значение элементов группы на родительскую группу. (значение_группы или значение_подгруппы)
2.1 Если эта группа вложена в другую группу(т.е. является подгруппой) необходимо умножить её значение на значение родительской группы
3. И так , пока не дойдем до корня.
Вот пример изображения на картинке, как элементы взаимодействуют с собой(это QTreeWidget).


Я набрасал логику алгоритма в текстовом блокнотике в виде "псевдокода", хотелось бы что бы мне помогли понять, правильно ли я понял алгоритм

Код

Подсчитать группы, для этого нужен рекурсивный алгоритм обхода дерева групп критерией :
        //Берем список топ-левел айтемов.
        //для каждого айтема этого списка
        //обнулить : значение_группы, значение_критериев_подгруппы, значение_критериев_группы.
        //получаем список его чилдов
          //функция_1(список айтемов) :
            //для каждого из списка
            //если тип айтема 1001(группа, у неё есть подгруппы либо только критерии) получаем количество его чилдов если оно >0 (это исключит пустые группы)
                //получаем список чилдов.
                  //вызываем функция_1 для этого списка.
                //если значение_критериев_подгруппы != 0 (Значит была подсчитана подгруппа)
                    // значение_группы+=вес_группы*значение_подгру
ппы.
                //иначе (значит не было подгрупп)
                    // значение_группы+=вес_группы*значение_критер
иев_группы
            //иначе если тип айтема 1002(подгруппа) получаем количество его чилдов если оно >0 (это исключит пустые группы), все его чилды 100% критерии
                //для каждого критерия(чилда)
                    //если его значение !=0
                        // значение_критериев_группы+=взвешенное_знач�
�ние_критерия_по_году_рейтинга
                // значение_подгруппы=вес_подгруппы*значение_�
�ритериев_группы
            //иначе если тип айтема 1003(критерий) то мы нашли критерий и для него (иначе это пустая группа, но этого лучше не допускать)
                //если его значения !=0 (но этого тоже лучше не допускать)
                    // значение_критериев_группы+=взвешенное_знач�
�ние_критерия_по_году_рейтинга
        //значение верхней группы+=вес_верхней_группы*значение_группы.

Но проблема в том, что в Qt (4.7.1) нельзя просто получить список детей элемента(только итерировать по ним, либо получить, но они удаляться из виджета/айтема). Я попробую написать алгоритм, но прощу помощи здесь, вдруг что-то упустил..

Сообщение отредактировано: Andrewshkovskii - 27.12.2010 5:25

[Andrewshkovskii]

Вот накидал код, по-логике вроде верно, а на деле..сейчас буду проверять..

void MainWindow::function_1(const QTreeWidgetItem* item,const int &year )
{
    QTreeWidgetItem *item2;
    QTreeWidgetItem *item3;
qDebug() << "recursion here";
    for(int i=0;i<item->childCount();++i)
    {
        item2 = item->child(i);
        qDebug() << "for(int i=0;i<item->childCount();++i)" << item2->text(0);
        if(item2->type()==1001 && item2->childCount() > 0)
        {
            qDebug () << "if(item2->type()==1001 && item2->childCount() > 0)";
            for(int j=0;j<item2->childCount();++j)
            {
                item3 = item2->child(j);
                qDebug() << "for(int j=0;j<item2->childCount();++j)" << item3->text(0);
                function_1(item3,year);
            }
           if(subGroupValue!=0)
              groupValue+=groupWeight_(criteriaGroupMap.value(item2))*subGroupValue;
           else
               groupValue+=groupWeight_(criteriaGroupMap.value(item2))*groupCriteriaValue;
        }else if(item2->type()==1002 &&item2->childCount()>0)
                {
                    qDebug() << "else if(item2->type()==1002 &&item2->childCount()>0)";
                    for(int j=0;j<item2->childCount();++j)
                    {
                        item3=item2->child(j);
                        qDebug() << "for(int j=0;j<item2->childCount();++j)" << item3->text(0);
                        groupCriteriaValue+=weightedCriteriaValue_(criteriaMap.value(item3),year);
                    }
                    subGroupValue=groupWeight_(criteriaGroupMap.value(item2))*groupCriteriaValue;//вес группы в которой расположены критерии
                }else if(item2->type()==1003)
                        {
                            qDebug() << "else if(item2->type()==1003)" << item2->text(0);
                            groupCriteriaValue+=weightedCriteriaValue_(criteriaMap.value(item2),year);
                        }
    }
    groupValue+=groupWeight*groupValue;//значения для item, т.е. элемента верхнего уровня.-- подумать о том, что это значения для высшего УРОВНЯ.
}

Добавив отладочный вывод получаю :

Код

recursion here
for(int i=0;i<item->childCount();++i) "Научная работа"
else if(item2->type()==1002 &&item2->childCount()>0)
for(int j=0;j<item2->childCount();++j) "Объем НИОКР"
for(int j=0;j<item2->childCount();++j) "Участие в изобретательской деятельности"
for(int i=0;i<item->childCount();++i) "Подготовка научных кадров"
else if(item2->type()==1002 &&item2->childCount()>0)
for(int j=0;j<item2->childCount();++j) "Научная работа студентов"
for(int j=0;j<item2->childCount();++j) "Подготовка соискателей ученых степеней"
for(int i=0;i<item->childCount();++i) "Научные труды"
else if(item2->type()==1002 &&item2->childCount()>0)
for(int j=0;j<item2->childCount();++j) "Доклады"
for(int j=0;j<item2->childCount();++j) "Монографии"
for(int j=0;j<item2->childCount();++j) "Статьи"

Уровень рекурсии 1, а должен был быть более. Видно что не идет вниз в подгруппах, может сбились типы, проверю завтра, сейчас уже голова не варит, пойду спать..

Сообщение отредактировано: Andrewshkovskii - 27.12.2010 5:42

[volvo]

по-логике вроде верно

Ты действительно думаешь, что тут по логике все верно? Посмотри внимательно, у тебя только один раз в функции происходит рекурсивный вызов:

      if(item2->type()==1001 && item2->childCount() > 0)
      {
         qDebug () << "if(item2->type()==1001 && item2->childCount() > 0)";
         for(int j=0;j<item2->childCount();++j)
         {
            item3 = item2->child(j);
            qDebug() << "for(int j=0;j<item2->childCount();++j)" << item3->text(0);

            function_1(item3,year); // <--- Вот он !!!
         }
         // ...
      }

При каких условиях это происходит? Только тогда, когда у предка type() = 1001. Во всех остальных случаях рекурсивного вызова не будет. Поэтому ты не обходишь дерево полностью...

Я б на твоем месте перенес эту строку вот сюда:

   for(int i=0;i<item->childCount();++i)
   {
      // ... тут все проверки ...

      function_1(item3,year); // <--- Вот именно сюда, в самый конец цикла ....
   }
   groupValue+=groupWeight*groupValue;
}

Понимаешь, что я хочу этим сказать? Проверять - проверяй, когда какие условия выполняются, в зависимости от этого изменяй значения, подсчитывай, но пройти ты должен по всем потомкам узла, и для каждого потомка вызвать finction_1(). Это гарантирует тебе обход всего дерева...

[Andrewshkovskii]

По ограничениям , наложенными на ввод данных интерфейсом, не может быть так, что у элемента с типом 1002 будут элементы с типом, не равным 1003.
А для элемента 1003 не может быть потомков.
А не правильно обработал в прошлый раз из-за того, что типа айтемов сбились..точнее алгоритм их выставления был не верным.
Либо изменять алгоритм обхода (что бы он проверял, есть ли у элемента потопки-подгруппы) ,либо переделывать алгоритм выставления типов.
Вот что выдает обход дерева ,по типам, сейчас :

Код

"Научно-исследовательская работа" 1001
  "Научная работа" 1002
  "Объем НИОКР" 1003
  "Участие в изобретательской деятельности" 1003
"Подготовка научных кадров" 1002 <--вот здесь должен был быть тип 1001, т.к. элемент содержит ПОДгруппу.
"Научная работа студентов" 1002
   "Участие в договорных НИОКР" 1003
   "Доклады на неделе науки и конференциях" 1003
"Подготовка соискателей ученых степеней" 1002 <--вот здесь должен был быть тип 1001, т.к. элемент содержит ПОДгруппу.
"Эффектиновсть подготовки" 1002
   "Эффектиновсть аспирантуры" 1003
   "Эффективность работы по подготовке докторов наук" 1003
"Участие в подготовке научных кадров" 1002
   "Подготовка аспирантов" 1003
   "Участие в советах по защите диссертаций" 1003
"Научные труды" 1002
   "Доклады" 1003
   "Монографии" 1003
   "Статьи" 1003

Я перепроверю алгоритм, и выложу результат сюда (если возникнут проблемы)..
Вот, а за ответ, volvo, спасибо! Ты всегда помогаешь : )

Сообщение отредактировано: Andrewshkovskii - 27.12.2010 14:01

[volvo]

По ограничениям , наложенными на ввод данных интерфейсом, не может быть так, что у элемента с типом 1002 будут элементы с типом, не равным 1003.

А что насчет ограничения на элемент с типом 1001? Какие у него могут быть потомки? Только 1002, да? Однако, в твоем дереве это НЕ выполняется...

А вообще об ограничениях надо предупреждать заранее...

[Andrewshkovskii]

Есть дерево, в нем возможны 3 элемента
3. Элемент типа 1003 - критерий, у этого элемента есть некоторое значение.
2. Элемент типа 1002 - это подгруппа (т.е. у неё есть род. группа) и она содержит только элементы типа 1003, у неё есть значение(вес).
1. Элемент типа 1001 - Группа верхнего уровня (в неё входят либо только элементы 1002 - подгруппы, либо только элементы 1003 - критерии), у него есть значение(вес).

Вот же, о ограничениях , в первом посте
У типа 1001 либо только элементы 1003, либо только элементы типа 1002. (ну,это по логике, на данный момент ситуация иная из-за ошибки в алгоритме выставления типов)

Сообщение отредактировано: Andrewshkovskii - 27.12.2010 14:28

[Andrewshkovskii]

Поправил алгоритм установки типа, теперь все верно.
Вот только алгоритм подсчета работает не верно, и почему-то один узел проходит 2 раза, но по разным критериям..

void MainWindow::function_1(const QTreeWidgetItem* item,const int &year )
{
    QTreeWidgetItem *item2;
    QTreeWidgetItem *item3;
    double mainValue;
    for(int i=0;i<item->childCount();++i)//для каждого чилда верхней группы
    {
        item2 = item->child(i);//получаем чилда
        qDebug () << "for group "+item->text(0);
        if(item2->type()==1001 && item2->childCount() > 0)//если этот чилд - группа, и количество его чилдов >0
        {
            qDebug() << "item " +item2->text(0) + " is mainGroup";
            for(int j=0;j<item2->childCount();++j)//для каждого его чилда
            {
                item3 = item2->child(j);//получаем чилда
                function_1(item3,year);//вызываем рекурсивную функцию.
            }
           if(subGroupValue!=0){//если значение подгруппы !=0 (т.е. были подгруппы)
              groupValue+=groupWeight_(criteriaGroupMap.value(item2))*subGroupValue;
              subGroupValue=0;
            }
           else//иначе не было подгрупп, и считаем чилдов.
              groupValue+=groupWeight_(criteriaGroupMap.value(item2))*groupCriteriaValue;
        }else if(item2->type()==1002 &&item2->childCount()>0)//иначе если айтем является подгруппой, и у него критериев >0
                {
                    qDebug() << item2->text(0) + " is subGroup";
                    for(int j=0;j<item2->childCount();++j)//для каждого из этих критериев
                    {
                        item3=item2->child(j);//получаем критерий
                        qDebug() << item3->text(0) +" is criteria from group " +item2->text(0);
                        groupCriteriaValue+=weightedCriteriaValue_(criteriaMap.value(item3),year);
                    }
                    subGroupValue=groupWeight_(criteriaGroupMap.value(item2))*groupCriteriaValue;//вес группы в которой расположены критерии
                }else if(item2->type()==1003)//иначе в группе толко критерии
                        {
                            qDebug() << item2->text(0) + " is criteria from " + item->text(0);
                            groupCriteriaValue=0;
                            groupCriteriaValue+=weightedCriteriaValue_(criteriaMap.value(item2),year);
                        }
    }
//    groupValue+=groupWeight*groupValue;//значения для item, т.е. элемента верхнего уровня.-- подумать о том, что это значения для высшего УРОВНЯ.
}

видимо надо избавиться от глобальных переменных, и сделать функцию возвращающую значение для каждой группы...

Вот что выводит алгоритм для этих значений :

"for group Научно-исследовательская работа"
"item Подготовка научных кадров is mainGroup"
"for group Подготовка соискателей ученых степеней"
"Эффектиновсть подготовки is subGroup"
"Эффектиновсть аспирантуры is criteria from group Эффектиновсть подготовки"
"Эффективность работы по подготовке докторов наук is criteria from group Эффектиновсть подготовки"
"for group Подготовка соискателей ученых степеней"
"Участие в подготовке научных кадров is subGroup"
"Подготовка аспирантов is criteria from group Участие в подготовке научных кадров"
"Участие в советах по защите диссертаций is criteria from groupУчастие в подготовке научных кадров"
"for group Научная работа студентов"
"Участие в договорных НИОКР is criteria from Научная работа студентов"
"for group Научная работа студентов"
"Доклады на неделе науки и конференциях is criteria from Научная работа студентов"
"for group Научно-исследовательская работа"
"Научная работа is subGroup"
"Объем НИОКР is criteria from group Научная работа"
"Участие в изобретательской деятельности is criteria from group Научная работа"
"for group Научно-исследовательская работа"
"Научные труды is subGroup"
"Доклады is criteria from group Научные труды"
"Монографии is criteria from group Научные труды"
"Статьи is criteria from group Научные труды"

А н нет, это я тупанул, 2 раза не проходит..только считает все равно не верно.
Может стоит оформить эту функцию в таком виде , что бы она возвращала значения подгрупп?
О том, как это все должно считаться :
Приходя в группу типа 1002 или типа 1001 у которой только критерии внутри,
мы суммируем взвешенные значения критериев группы, умножаем на вес группы. Получившиеся значение умножаем на вес родительской группы (если таковая имеется) до тех пор, пока не дойдем до корня, после чего это значение прибавляется результирующему значению всех верхних групп( "совсем" верхних, т.е там будет main +=значение (Научно-исследовательская работа)+etc..)..
Volvo, подскажи

Сообщение отредактировано: Andrewshkovskii - 28.12.2010 2:15

[Andrewshkovskii]

Все, помощь не нужна..все решилось вот так :

double MainWindow::raiting( QTreeWidgetItem* tree,const int &year )
{
      double acc = 0;
      for (int i=0; i<tree->childCount(); ++i) {
         QTreeWidgetItem * subtree = tree->child(i);
        if (subtree->type()==1003) {
          acc += weightedCriteriaValue_(criteriaMap.value(subtree),year);
        } else if ((subtree->type()==1001 || subtree->type()==1002) && subtree->childCount() > 0) {
          acc += raiting(subtree,year)*groupWeight_(criteriaGroupMap.value(subtree));
        }
      }
      return acc * groupWeight_(criteriaGroupMap.value(tree));
    }

[volvo]

Я бы подсказал, если б ты привел минимальный проект, который можно откомпилировать и запустить. А то, что такое weightedCriteriaValue_ - я не знаю, как оно получается и откуда... Что такое criteriaMap и criteriaGroupMap - тоже мне неизвестно. Одно могу сказать точно: я бы однозначно сделал эту функцию именно функцией, а не процедурой (то есть, она бы возвращала именно double, я ведь правильно понимаю, в результате у тебя должно получиться единственное число, являющееся неким коэффициентом для переданного в function_1 (под)дерева?)

[Andrewshkovskii]

Да, все правильно ты понял. В принципе уже не важно, я решил проблему, спасибо тебе за помощь.

[what foods to avoid when taking]

Viagra Roma

[how long does plaquenil stay in]

Cialis 40 Mg Dose

[buy hydroxychloroquine over the]

Kamagra Is It Legal In Uk