Найти все хордовые циклы в неориентированном графе - PullRequest
Новая
       73

Найти все хордовые циклы в неориентированном графе

27 голосов
/ 26 октября 2010

Как найти все аккордовые циклы в неориентированном графе?

Например, с учетом графика 

0 --- 1
|     | \
|     |  \
4 --- 3 - 2

алгоритм должен возвращать 1-2-3 и 0-1-3-4, но никогда не 0-1-2-3-4.

(Примечание: [1] Этот вопрос не совпадает с обнаружением малого цикла в плоском графе , поскольку график не обязательно является плоским. [2] Я прочитал статью Генерация всех циклов, аккордовых и гамильтоновых циклов с принципом исключения , но я не понимаю, что они делаю :). [3] Я пробовал CYPATH , но программа выдает только счет, алгоритм EnumChordlessPath в readme.txt содержит существенные опечатки, а код C - беспорядок. [4] Я не пытаюсь найти произвольный набор fundametal циклов . Основа цикла может иметь аккорды.)

Ответы [ 5 ]

8 голосов
/ 27 октября 2010

Назначение номеров узлам от 1 до n.

  1. Укажите номер узла 1. Назовите его «A».

  2. Перечисление пар ссылок, выходящих из «A».

  3. Выберите один. Давайте назовем соседние узлы 'B' и 'C', где B меньше C.

  4. Если B и C подключены, выведите цикл ABC, вернитесь к шагу 3 и выберите другую пару.

  5. Если B и C не подключены:

    • Перечислить все узлы, подключенные к B. Предположим, он подключен к D, E и F. Создайте список векторов CABD, CABE, CABF. Для каждого из них:
    • если последний узел подключен к любому внутреннему узлу, кроме C и B, отбросить вектор
    • если последний узел подключен к C, вывести и отбросить
    • если он не подключен, создайте новый список векторов, добавив все узлы, к которым подключен последний узел.

    Повторяйте, пока у вас не закончатся векторы.

  6. Повторите шаги 3-5 для всех пар.

  7. Удалить узел 1 и все ссылки, которые ведут к нему. Выберите следующий узел и вернитесь к шагу 2.

Редактировать: и вы можете покончить с одним вложенным циклом.

Кажется, это работает на первый взгляд, могут быть ошибки, но вы должны понять: 

void chordless_cycles(int* adjacency, int dim)
{
    for(int i=0; i<dim-2; i++)
    {
        for(int j=i+1; j<dim-1; j++)
        {
            if(!adjacency[i+j*dim])
                continue;
            list<vector<int> > candidates;
            for(int k=j+1; k<dim; k++)
            {
                if(!adjacency[i+k*dim])
                    continue;
                if(adjacency[j+k*dim])
                {
                    cout << i+1 << " " << j+1 << " " << k+1 << endl;
                    continue;
                }
                vector<int> v;
                v.resize(3);
                v[0]=j;
                v[1]=i;
                v[2]=k;
                candidates.push_back(v);
            }
            while(!candidates.empty())
            {
                vector<int> v = candidates.front();
                candidates.pop_front();
                int k = v.back();
                for(int m=i+1; m<dim; m++)
                {
                    if(find(v.begin(), v.end(), m) != v.end())
                        continue;
                    if(!adjacency[m+k*dim])
                        continue;
                    bool chord = false;
                    int n;
                    for(n=1; n<v.size()-1; n++)
                        if(adjacency[m+v[n]*dim])
                            chord = true;
                    if(chord)
                        continue;
                    if(adjacency[m+j*dim])
                    {
                        for(n=0; n<v.size(); n++)
                            cout<<v[n]+1<<" ";
                        cout<<m+1<<endl;
                        continue;
                    }
                    vector<int> w = v;
                    w.push_back(m);
                    candidates.push_back(w);
                }
            }
        }
    }
}
4 голосов
/ 27 октября 2010

@ aioobe имеет точку.Просто найдите все циклы, а затем исключите не-аккордовые.Это может быть слишком неэффективно, но пространство поиска может быть сокращено по пути, чтобы уменьшить неэффективность.Вот общий алгоритм: 

void printChordlessCycles( ChordlessCycle path) {

  System.out.println( path.toString() );
  for( Node n : path.lastNode().neighbors() ) {

    if( path.canAdd( n) ) {

      path.add( n);
      printChordlessCycles( path);
      path.remove( n);
    }
  }
}

Graph g = loadGraph(...);
ChordlessCycle p = new ChordlessCycle();
for( Node n : g.getNodes()) {
  p.add(n);
  printChordlessCycles( p);
  p.remove( n);
}

class ChordlessCycle {
   private CountedSet<Node> connected_nodes;
   private List<Node> path;

   ...

   public void add( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.increment( neighbor);
     }
     path.add( n);
   }

   public void remove( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.decrement( neighbor);
     }
     path.remove( n);
   }

   public boolean canAdd( Node n) {
     return (connected_nodes.getCount( n) == 0);
   }
}
1 голос
/ 28 октября 2010

Найти все циклы.

Определение цикла без аккордов - это набор точек, в которых цикл этих точек не существует. Итак, если у вас есть все циклы, проблема состоит в том, чтобы просто устранить циклы, которые имеют подмножество циклов.

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

Кроме того, единственная трудность - понять, как написать алгоритм, который определяет, является ли набор подмножеством другого.

1 голос
/ 27 октября 2010

Просто мысль:

Допустим, вы перечисляете циклы на своем примерном графике и начинаете с узла 0.

Если вы выполняете поиск в ширину для каждого заданного ребра,например, 0 - 1, вы достигаете разветвления в 1. Тогда циклы, которые сначала достигают 0 снова, являются аккордами, а остальные нет и могут быть исключены ... по крайней мере, я думаю, что это так.

Не могли бы вы использовать такой подход?Или есть контрпример?

1 голос
/ 27 октября 2010

Как насчет этого. Во-первых, сведите задачу к нахождению всех аккордовых циклов, которые проходят через данную вершину A. Как только вы найдете все из них, вы можете удалить A из графа и повторять с другой точкой, пока ничего не останется.

А как найти все аккордовые циклы, которые проходят через вершину A? Сократите это, чтобы найти все хордовые пути от B до A, учитывая список разрешенных вершин, и ищите либо в ширину, либо в глубину. Обратите внимание, что при переборе вершин, достижимых (за один шаг) из B, при выборе одной из них вы должны удалить все остальные из списка разрешенных вершин (будьте особенно внимательны, когда B = A, чтобы не исключить три пути).

...