Генерация Всех Независимых Множеств Графа

vladis222

Active member
06.12.2011
31
0
#1
Здравствуйте,обращаюсь к вам по поводу проблемы с написанием курсовой работы на тему "Генерация независимых множеств " на языке С++. Дело в том,что я прочитал внимательно алгоритм,на Паскале для такой задачи, пытался запрограммировать все на С++,написал такие же функции(пока что не писал меню программы),но проблема возникла в том,что на языке С++, в отличие от языка Паскаль нет удобного SEt.Там есть std::set,но мне не удобно его использовать.Я выбрал динамические массивы для использования, но имеются некоторые ошибки в теле функций.Посмотрите,пожалуйста,мой код:
C++:
#include<iostream>
using namespace std;
#include<conio.h>
#include<math.h>
#include<locale>
#include<algorithm>
const int N=10;
int **A=new int *[N];
int Ss[N];
void print(int k)
{
int i;
for(i=0;i<k;i++) 
{
cout<<Ss[i];//вывод решения на экран
}
}

int number(int **A)
{
int i,cnt;
cnt=0;
for(i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if (A[i][j]==i)
cnt++;
return cnt;
}
}
}

void Find(int k,int *Qp=new int[N],int * Qm=new int [N])
{
int *Gg=new int[N];
int i;
if(Qp==NULL && Qm==NULL)
print(k);
if(Qm!=NULL)
if(Qp==NULL && Qm==NULL)
print(k);
else Gg=Qp;
/*Формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm -"черный ящик A"*/
i=0;
while(i<N)
{
for(int j=0;j<N;j++)
{
if (Gg[i]=i)
{
Ss[k]=i;
Find(k+1,Qp-i-A[i][j],Qm-i-A[i][j]);
/*Изменение Qp,Qm для этого уровня (значения k) и соотвественно,изменеие множества кандидатов Gg-"черный ящик Б"*/
Qp=Qp-i;
Qm=Qm+i;
Gg=Qp *(A[i][j]);/*Здесь я хочу продемонстрировать пересечение множества Qp и вершины множества A[i](двумерный массив,отображаюший множество вершин,смежных с i-той вершиной*/
}
i++;
}
}
int delt=N+1;
for(int j=0;j<N;j++)
{
if (Qm[j]==j)
if(number(A[i][j] * Qp)<delt)/*Здесь также видимо неправильно я отобразил пересечение*/
{
i=j;
delt=number(A[j]*Qp);/*Здесь также видимо неправильно я отобразил пересечение*/
}
Gg=Qp* A[i];/*Здесь также видимо неправильно я отобразил пересечение*/
}
/*Окончательная логика "черного ящика А"*/
}


int main()
{
setlocale(LC_ALL,"Rus");
int choice;
cout<<("	Меню программы	 ")<<endl;
cout<<("------------------------")<<endl;
cout<<("1.Создать граф")<<endl;
cout<<("2.Ввести множества смежных вершин")<<endl;
cout<<("3.Вывести на экран множества независимых вершин графа")<<endl;
cout<<("3.Вывести независимые множества графа")<<endl;
cout<<("4.Выход.");
switch(choice)
case 1:{
cout<<"Введите множества смежных вершин для каждой из графа : "<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout<<A[i][j];
cin>>A[i][j];
}
}

}
break;

getch();

}
 
R

rrrFer

#2
Там есть std::set,но мне не удобно его использовать.Я выбрал динамические массивы для использования, но имеются некоторые ошибки в теле функций.Посмотрите,пожалуйста,мой код:
ошибки будут потом, используй set.
приводи коды и описания ошибок.

Добавлено:
Код:
const int N=10;
int **A=new int *[N];
int Ss[N];
не используй глобальных переменных.

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

vladis222

Active member
06.12.2011
31
0
#3
ошибки будут потом, используй set.
приводи коды и описания ошибок.

Добавлено:
Код:
const int N=10;
int **A=new int *[N];
int Ss[N];
не используй глобальных переменных.

то что ты написал вообще работать не должно. new выполняется во время выполнения, для этого этот код должен быть засунуто в какую-то функцию. Надеяться на то что компилятор оптимизирует этот бред не стоит.
У меня есть написанный код при помощи set,но он обнаруживает ошибки. Вот он:
C++:
#include<iostream>
using namespace std;
#include<conio.h>
#include<math.h>
#include<locale>
#include<set>
const int N=10;
multiset <int > A[N]; 
void Print(int k) 
{
int i;
int Ss[N];//Решение хранится в этом массиве
for(i=0;i<k;i++) 
{
cout<<Ss[i];//вывод решения на экран
}
}
void Find(int k,set<int> Qp,set <int> Qm)
{
set<int> Gg;
int i;
if(Qp.empty()==true && Qm.empty()==true)
Print(k);
/*Формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm -"черный ящик A"*/
i=0;
while(i<=N)
if (Gg.find(i)!=Gg.end())
{
Ss[k]=i;
Find(k+1,Qp.erase(A[i],i))/*Ошибка в удалении множества вершин смежной с данной и самой вершины, я не знаю как это записать,я объявил А как multiset(в нем хранятсямножества вершин,смежной с i-той вершиной.*/
}
}
int Number( set <int> A)
{
int i;
int cnt;
cnt=0;
for(i=1;i<N;i++)
{
if(A.find(i)!=A.end())
cnt++;
return cnt;
}
}

void Find(int k,set<int>Qp,set<int>Qm)
{
set<int>Gg;
int delt=N+1;
int i;
int j;
if (Qp.empty()==true && Qm.empty()==true)
Print(k);
if(Qm.size()!=0)
if (Qp.empty()==true && Qm.empty()==true)
Print(k);
else 
Gg=Qp;
for(j=1;j<=N;j++)
{
if (Qm.find(j)!=Qm.end())
if (Number (A[j].find(j))*Qp < delt )/*Здесь я не знал как изображить пересечение вершин,смежных с i-той и множества Qp*/
{
i=j;
delt=Number(A.find(j)*Qp);
}
Gg=Qp*A.find(i);
}
//черный ящик А
exit(-1);
//формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm
i=1;
while(i<N)
{
if(Gg.find(i)!=Gg.end())
{
Ss[k]=i;
Find(k+1,Qp.erase(A.find(i),i),Qm.erase(A[N].find(i),i));
//Черный ящик Б//
i++;
}
}
}
int Number( set <int> A)
{
int i;
int cnt;
cnt=0;
for(i=1;i<N;i++)
{
if(A.find(i)!=A.end())
cnt++;
return cnt;
}
}

int main()
{ setlocale(LC_ALL,"Rus");

int choice;
cout<<("	Меню программы	 ")<<endl;
cout<<("------------------------")<<endl;
cout<<("1.Создать граф")<<endl;
cout<<("2.Ввести множества смежных вершин")<<endl;
cout<<("3.Вывести на экран множества независимых вершин графа")<<endl;
cout<<("3.Вывести независимые множества графа")<<endl;
cout<<("4.Выход.");
switch(choice)
case 1:{
cout<<"Введите множества смежных вершин для каждой из графа : "<<endl;
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
cout<<A[i][j];
cin>>A[i][j];
}
}

}
break;

getch();

}
 
R

rrrFer

#4
2 первых ошибки:
main.cpp:27:7: error: 'Ss' was not declared in this scope
Код:
void Find(int k, set<int> Qp, set <int> Qm) {
set<int> Gg;
int i;
if (Qp.empty() == true && Qm.empty() == true)
Print(k);
/*Формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm -"черный ящик A"*/
i = 0;
while (i <= N)
if (Gg.find(i) != Gg.end()) {
Ss[k] = i;
Find(k + 1, Qp.erase(A[i], i))/*Ошибка в удалении множества вершин смежной с данной и самой вершины, я не знаю как это записать,я объявил А как multiset(в нем хранятсямножества вершин,смежной с i-той вершиной.*/
}
}
а что ты хочешь? - у тебя Ss не объявлено, std::set тут непричем. Компилятор тебе сообщает об ошибке - значит надо исправлять.

main.cpp:28:35: error: no matching function for call to 'std::set<int>::erase(std::multiset<int>&, int&)'
это следующая строка в приведенном коде. И тут, как и в прошлый раз, компилятор тебе нормально сообщает об ошибке.
http://www.cplusplus.com/reference/set/set/erase/
void erase ( iterator position );
size_type erase ( const key_type& x );
void erase ( iterator first, iterator last );

Erase elements
Removes from the set container either a single element or a range of elements ([first,last)).
а ты что за ерунду пихаешь в erase? - он принимает 2 итератора или значение удаляемого узла, ты передаешь значение и еще какую-то ерунду.

2 последних ошибки связаны с:
Код:
multiset <int > A[N];
//...
cout << A[i][j];
объявлен массив множеств
A - валидно, ты получаешь i-тое множество
но ты не можешь дергать элемент множества через оператор [] (элементы во множестве располагаются не в том порядке, в которым ты их туда поместил - если тебе надо что-то другое, используй не множества, а списки или вектора)

ну и стопицот ошибок между первыми и последними я пропустил, компилятор пишет синим по белому, я думаю ты сам прочитаешь и исправишь.

Добавлено:
Я выбрал динамические массивы для использования, но имеются некоторые ошибки в теле функций.Посмотрите,пожалуйста,мой код:
если добавишь 2 одинаковых элемента в set - то добавится лишь первый (потому что это множество), но в массив добавилось бы оба элемента
 

vladis222

Active member
06.12.2011
31
0
#5
2 первых ошибки:

Код:
void Find(int k, set<int> Qp, set <int> Qm) {
set<int> Gg;
int i;
if (Qp.empty() == true && Qm.empty() == true)
Print(k);
/*Формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm -"черный ящик A"*/
i = 0;
while (i <= N)
if (Gg.find(i) != Gg.end()) {
Ss[k] = i;
Find(k + 1, Qp.erase(A[i], i))/*Ошибка в удалении множества вершин смежной с данной и самой вершины, я не знаю как это записать,я объявил А как multiset(в нем хранятсямножества вершин,смежной с i-той вершиной.*/
}
}
а что ты хочешь? - у тебя Ss не объявлено, std::set тут непричем. Компилятор тебе сообщает об ошибке - значит надо исправлять.


это следующая строка в приведенном коде. И тут, как и в прошлый раз, компилятор тебе нормально сообщает об ошибке.
http://www.cplusplus.com/reference/set/set/erase/

а ты что за ерунду пихаешь в erase? - он принимает 2 итератора или значение удаляемого узла, ты передаешь значение и еще какую-то ерунду.

2 последних ошибки связаны с:
Код:
multiset <int > A[N];
//...
cout << A[i][j];
объявлен массив множеств
A - валидно, ты получаешь i-тое множество
но ты не можешь дергать элемент множества через оператор [] (элементы во множестве располагаются не в том порядке, в которым ты их туда поместил - если тебе надо что-то другое, используй не множества, а списки или вектора)

ну и стопицот ошибок между первыми и последними я пропустил, компилятор пишет синим по белому, я думаю ты сам прочитаешь и исправишь.

Добавлено:
если добавишь 2 одинаковых элемента в set - то добавится лишь первый (потому что это множество), но в массив добавилось бы оба элемента


Вот исправил что-то, но все равно есть проблемы. Вот исправленный код:
C++:
#include<iostream>
using namespace std;
#include<conio.h>
#include<math.h>
#include<locale>
#include<set>
#include<algorithm>
#include<iterator>
const int N=10;
multiset <int > A[N];
set<int>::iterator it;
set<int>::iterator it2;
set<int>::iterator it3;
int Ss[N];//Решение хранится в этом массиве

void Print(int k) 
{
int i;
int Ss[N];
for(i=0;i<k;i++) 
{
cout<<Ss[i];//вывод решения на экран
}
}

int Number( set <int> A)
{
int i;
int cnt;
cnt=0;
for(i=1;i<N;i++)
{
if(A.find(i)!=A.end())
{
cnt++;
return cnt;
}
}
}

void Find(int k,set<int>Qp,set<int>Qm)
{
set<int>Gg;
set <int> out;
set <int> out2;
int delt=N+1;
int i;
int j;
it=set_intersection(A[j].begin(),A[j].end(),Qp.begin(),Qp.end(),out.begin());
it2=set_intersection(Qp.begin(),Qp.end(),A[i].begin(),A[i].end(),out2.begin());

/* if (Qp.empty()==true && Qm.empty()==true)
Print(k);
if(Qm.size()!=0)
if (Qp.empty()==true && Qm.empty()==true)
Print(k);
else 
Gg=Qp;*/
for(j=1;j<=N;j++)
{
if (Qm.find(j)!=Qm.end())
if (Number(out)<delt)/*Здесь я не знал как изображить пересечение вершин,смежных с i-той и множества Qp*/
{
i=j;
delt=Number(out);
}
Gg=out2;
}


//черный ящик А
exit(-1);
//формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm
i=0;
while(i<N)
{
if(Gg.find(i)!=Gg.end())
{
Ss[k]=i;
Qp.erase(i);
Qm.erase(i);
if()
/*Отладил почти только не понимаю,как удалить из множества Qm,элементы принадлежащие множеству A[i],это нужно для функции Find*/

} 

}

}

int main()
{ setlocale(LC_ALL,"Rus");

int choice;
cout<<("	Меню программы	 ")<<endl;
cout<<("------------------------")<<endl;
cout<<("1.Создать граф")<<endl;
cout<<("2.Ввести множества смежных вершин")<<endl;
cout<<("3.Вывести на экран множества независимых вершин графа")<<endl;
cout<<("3.Вывести независимые множества графа")<<endl;
cout<<("4.Выход.");
switch(choice)
case 1:{
cout<<"Введите множества смежных вершин для каждой из графа : "<<endl;
for(int i=0;i<N;i++)
{
cout<<"Для "<<i<<"вершины : ";
cin>>A[i];
}


getch();

}
Вопросы:1)Как удалить из множества Qp вершины множества A?Как так задать чтобы компилятор понял что я хочу... 2)Как ввести множества смежностей для каждой вершины,если нельзя напрямую обратиться к вершине в множестве?
 
R

rrrFer

#6
1)Как удалить из множества Qp вершины множества A?Как так задать чтобы компилятор понял что я хочу...

я ж приводил ссылку: http://www.cplusplus.com/reference/set/set/erase/
и вобще, пользуйся поиском, я не понимаю как ты там код пишешь и почему ты думаешь что компилятор должен как-то угадать что ты хочешь.

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


ЗЫ. ты какой алгоритм реализовать пытаешь?

Добавлено:
/*Отладил почти только не понимаю,как удалить из множества Qm,элементы принадлежащие множеству A,это нужно для функции Find*/


Код:
for (auto val : A[i])
Qm.erase(val);
не проверял, но вроде бы должно работать
 

vladis222

Active member
06.12.2011
31
0
#7
я ж приводил ссылку: http://www.cplusplus.com/reference/set/set/erase/
и вобще, пользуйся поиском, я не понимаю как ты там код пишешь и почему ты думаешь что компилятор должен как-то угадать что ты хочешь.


да мы с компилятором вместе не можем угадать что ты хочешь ) формулируй нормально.


ЗЫ. ты какой алгоритм реализовать пытаешь?

Добавлено:

Код:
for (auto val : A[i])
Qm.erase(val);
не проверял, но вроде бы должно работать
Алгоритм Брона-Кэрбоша

Добавлено: А скажите,пожалуйста val это тип set?

Добавлено:
Алгоритм Брона-Кэрбоша

Добавлено:
А скажите,пожалуйста val это тип set?
Ну просто вначале я хочу ввести множества смежностей для каждой из вершин множества А.И немного затрудняюсь,как это сделать в коде...
 
R

rrrFer

#8
А скажите,пожалуйста val это тип set?
это тип int

Добавлено:
Код:
for (auto val : A[i])
Qm.erase(val);
замени на:
Код:
for (std::set<int>::iterator it = A[i].begin(); A[i].end() != it; ++it) 
Qm.erase(it);
если компилятор c++11 не поддерживает
 

vladis222

Active member
06.12.2011
31
0
#9
это тип int

Добавлено:
Код:
for (auto val : A[i])
Qm.erase(val);
замени на:
Код:
for (std::set<int>::iterator it = A[i].begin(); A[i].end() != it; ++it) 
Qm.erase(it);
если компилятор c++11 не поддерживает
Спасибо большое,отладил код,ничего уже не подчеркивает,просто при запуске возникают 2 ошибки:
1)Ошибка 2 error C3892: std::_Tree_const_iterator<_Mytree>::eek:perator *: невозможно присваивать значения переменной, которая объявлена как константа c:\program files\microsoft visual studio 10.0\vc\include\algorithm 4494 mnva 1
2)Ошибка 3 error C3892: std::_Tree_const_iterator<_Mytree>::eek:perator *: невозможно присваивать значения переменной, которая объявлена как константа c:\program files\microsoft visual studio 10.0\vc\include\algorithm 4494 mnva 1

Вот новый код:
C++:
#include<iostream>
using namespace std;
#include<conio.h>
#include<math.h>
#include<locale>
#include<set>
#include<algorithm>
#include<iterator>
const int N=10;
multiset <int > A[N];
set<int>::iterator it;
multiset<int>::iterator it2;
multiset<int>::iterator it3;

int Ss[N];//Решение хранится в этом массиве

void Print(int k) 
{
int i;
int Ss[N];
for(i=0;i<k;i++) 
{
cout<<Ss[i];//вывод решения на экран
}
}

int Number( set <int> A)
{
int i;
int cnt;
cnt=0;
for(i=1;i<N;i++)
{
if(A.find(i)!=A.end())
{
cnt++;
return cnt;
}
}
}

void Find(int k,multiset<int>Qp,multiset<int>Qm)
{
multiset<int>Gg;
set <int> out;
multiset <int> out2;
int delt=N+1;
int i;
int j;
it=set_intersection(A[j].begin(),A[j].end(),Qp.begin(),Qp.end(),out.begin());
it2=set_intersection(Qp.begin(),Qp.end(),A[i].begin(),A[i].end(),out2.begin());

if (Qp.empty()==true && Qm.empty()==true)
Print(k);
if(Qm.size()!=0)
if (Qp.empty()==true && Qm.empty()==true)
Print(k);
else 
Gg=Qp;
for(j=1;j<=N;j++)
{
if (Qm.find(j)!=Qm.end())
if (Number(out)<delt)
{
i=j;
delt=Number(out);
}
Gg=out2;
}


//черный ящик А
exit(-1);
//формирование множества кандидатов Gg для расширения текущего решения (k элементов в массиве Ss) по значениям Qp и Qm
i=0;
while(i<N)
{
if(Gg.find(i)!=Gg.end())
{
Ss[k]=i;
Qp.erase(i);
Qm.erase(i);
for (it3=A[i].begin();A[i].end()!=it3;++it)
Qp.erase(it3);
for (it3=A[i].begin();A[i].end()!=it3;++it)
Qm.erase(it3);
Find(k+1,Qp,Qm);

} 

}

}

int main()
{ setlocale(LC_ALL,"Rus");

int choice;
cout<<("	Меню программы	 ")<<endl;
cout<<("------------------------")<<endl;
cout<<("1.Создать граф")<<endl;
cout<<("2.Ввести множества смежных вершин")<<endl;
cout<<("3.Вывести на экран множества независимых вершин графа")<<endl;
cout<<("3.Вывести независимые множества графа")<<endl;
cout<<("4.Выход.");
switch(choice)
case 1:{
cout<<"Введите множества смежных вершин для каждой из графа : "<<endl;
for(int i=0;i<N;i++)
{
cout<<"Для "<<i<<"вершины : ";

}break;

}



getch();
}
 

vladis222

Active member
06.12.2011
31
0
#11
Qp.erase(it3);
попробуй на
Qp.erase(*it3);
заменить
попробовал, но ошибки есть, мне кажется насколько я понял,что когда я объявлял переменную для создания пересечения множеств,то допустил какие-то ошибки,правда вот не знаю,как теперь написать без ошибок,посмотрите пожалуйста.
 
R

rrrFer

#12
Алгоритм Брона-Кэрбоша
тут он компактно описан: http://ru.wikipedia.org/wiki/%D0%90%D0%BB%...%BE%D1%88%D0%B0
тут есть реализация на С++ : http://dictionary.sensagent.com/%D0%B0%D0%...88%D0%B0/ru-ru/
и эта реализация встретилась мне на 3 из 5 первых ссылок гугла по запросу "брона кербоша С++".

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