VPF::Алгоритм Брона-Кербоша или Java перевести на Си...

VAAKAraceGUM

Дата 5.5.2012, 00:09 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 13.2.2012

Репутация: нет
Всего: нет

В общем Алгоритм Брона-Кербоша представляет из себя поиск наибольшего независимого множества вершин в графе... Мне надо написать эту программку на С++. Но у меня имеется алгоритм на Java, если кто умеет можете помочь перевести его на C++, но желательно без всяких классов и тд... Ну или может быть у кого-нибудь просто есть этот алгоритм.

Алгоритм на Java:

Код


import java.util.*;

public class BronKerbosh {

  static void findMaximumIndependentSet(List<Integer> cur, List<Integer> result, boolean[][] graph, int[] oldSet,
      int ne, int ce) {
    int nod = 0;
    int minnod = ce;
    int fixp = -1;
    int s = -1;

    for (int i = 0; i < ce && minnod != 0; i++) {
      int p = oldSet[i];
      int cnt = 0;
      int pos = -1;

      for (int j = ne; j < ce; j++)
        if (graph[p][oldSet[j]]) {
          if (++cnt == minnod)
            break;
          pos = j;
        }

      if (minnod > cnt) {
        minnod = cnt;
        fixp = p;
        if (i < ne) {
          s = pos;
        } else {
          s = i;
          nod = 1;
        }
      }
    }

    int[] newSet = new int[ce];

    for (int k = minnod + nod; k >= 1; k--) {
      int sel = oldSet[s];
      oldSet[s] = oldSet[ne];
      oldSet[ne] = sel;

      int newne = 0;
      for (int i = 0; i < ne; i++)
        if (!graph[sel][oldSet[i]])
          newSet[newne++] = oldSet[i];

      int newce = newne;
      for (int i = ne + 1; i < ce; i++)
        if (!graph[sel][oldSet[i]])
          newSet[newce++] = oldSet[i];

      cur.add(sel);
      if (newce == 0) {
        if (result.size() < cur.size()) {
          result.clear();
          result.addAll(cur);
        }
      } else if (newne < newce) {
        if (cur.size() + newce - newne > result.size())
          findMaximumIndependentSet(cur, result, graph, newSet, newne, newce);
      }

      cur.remove(cur.size() - 1);
      if (k > 1)
        for (s = ++ne; !graph[fixp][oldSet[s]]; s++)
          ;
    }
  }

  public static List<Integer> maximumIndependentSet(boolean[][] graph) {
    int n = graph.length;
    int[] all = new int[n];
    for (int i = 0; i < n; i++)
      all[i] = i;
    List<Integer> res = new ArrayList<Integer>();
    findMaximumIndependentSet(new ArrayList<Integer>(), res, graph, all, 0, n);
    return res;
  }

  // Usage example
  public static void main(String[] args) {
    int n = 4;
    boolean[][] g = new boolean[n][n];

    // create a simple cycle
    g[0][1] = g[1][0] = true;
    g[1][2] = g[2][1] = true;
    g[2][3] = g[3][2] = true;
    g[3][0] = g[0][3] = true;

    List<Integer> res = maximumIndependentSet(g);

    List<Integer> expectedResult = new ArrayList<Integer>();
    Collections.addAll(expectedResult, 0, 2);
    System.out.println(expectedResult.equals(res));
  }
}

Это сообщение отредактировал(а) VAAKAraceGUM - 5.5.2012, 00:12

disputant

Дата 5.5.2012, 05:52 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 210
Регистрация: 28.11.2011

Репутация: нет
Всего: 3

Тут не смотрели?

VAAKAraceGUM

Дата 5.5.2012, 16:01 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 13.2.2012

Репутация: нет
Всего: нет

Я смотрел этот алгоритм, но я еще не настолько силен в языке, чтобы разобраться в нем, тем более, что возникает ошибочка.
Сам алгоритм с того сайта :

Можно ли в этой функции как-нибудь изменить: list<set<int> >kerbosh(int **&a,int SIZE), например на int kerbosh(int mas[][] , int SIZE) - это ничего не изменит? И что такое происходит тут : std::set<int> Stack2[100]; ? Тут можно под стандартный стиль программирования переделать ? И что за функции : .begin(); .find(i); .end(); .insert(v); - где они лежат ?

Код


list<set<int> >kerbosh(int **&a,int SIZE)
{
   set <int> M,G,K,P;
   list<set<int> > REZULT;
   for (int i=0; i<SIZE;i++)   
  {
       K.insert(i);   
  }   
int v,Count=0,cnt=0;   
int Stack1[100];   
std::set<int> Stack2[100];  
std::set<int>::iterator theIterator;
theIterator=K.begin();   
while ((K.size()!=0)||(M.size()!=0))   
{
       if (K.size()!=0)       
      {           
           theIterator=K.begin();
           v=*theIterator;
           Stack2[++Count]=M;
           Stack2[++Count]=K;
           Stack2[++Count]=P;
           Stack1[++cnt]=v;
           M.insert(v);
           for (int i=0;i<SIZE;i++)
           {
               if (a[v][i]) 
              {
                   theIterator=K.find(i);
                   if (theIterator!=K.end())
                   {
                       K.erase(theIterator);
                   }
                   theIterator=P.find(i);
                   if (theIterator!=P.end())
                   {
                       P.erase(theIterator);
                   }
               }
           }
           theIterator=K.find(v);
           if (theIterator!=K.end())
           {
               K.erase(theIterator);
           }
       }
       else
       {
           if (P.size()==0)
           {
               REZULT.push_back(M);
           }
           v=Stack1[cnt--];
           P=Stack2[Count--];
           K=Stack2[Count--];
           M=Stack2[Count--];
           theIterator=K.find(v);
           if (theIterator!=K.end())
           {
               K.erase(theIterator);
           }
           P.insert(v);
       }
   }
   return  REZULT;
}

mes

Дата 5.5.2012, 16:17 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(VAAKAraceGUM @ 5.5.2012, 15:01

)

И что за функции : .begin(); .find(i); .end(); .insert(v); - где они лежат ?

http://cplusplus.com/reference/stl/set
http://cplusplus.com/reference/stl/list

--------------------

http://opendots.net

VAAKAraceGUM

Дата 5.5.2012, 16:55 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 13.2.2012

Репутация: нет
Всего: нет

А можно ли эту задачу свести к задаче поиска максимальной клики, а потом просто вывести вершины, которые не относятся ко множеству максимальной клики... И мы тем самым получаем множество максимальных вершин...

VAAKAraceGUM

Дата 5.5.2012, 21:14 (ссылка)

(голосов:1)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 9
Регистрация: 13.2.2012

Репутация: нет
Всего: нет

Все, сделал...

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »