2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Разделить граф
Сообщение14.05.2016, 19:00 


13/01/13
15
Подскажите как решить следующую задачу: Дан связный граф состоящий из подграфов, необходимо выделить эти подграфы и выделить узел (суставной) который их соединяет. С какой стороны подступиться? Какой алгоритм можно использовать в данном случае? Какие средства реализации посоветуете? Boost Graph Library поможет решить данную задачу?

 Профиль  
                  
 
 Re: Разделить граф
Сообщение15.05.2016, 00:01 
Заслуженный участник


26/05/14
981
Начните отсюда: https://ru.wikipedia.org/wiki/%D0%A8%D0%B0%D1%80%D0%BD%D0%B8%D1%80_(%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2)

 Профиль  
                  
 
 Re: Разделить граф
Сообщение15.05.2016, 18:57 


13/01/13
15
Огромное спасибо вам :-) искал в разных книгах и в гугле как такие узлы называются, не мог найти

 Профиль  
                  
 
 Re: Разделить граф
Сообщение19.05.2016, 19:27 


13/01/13
15
Написал небольшую программу для поиска шарниров, вот теперь возник вопрос как можно распараллелить этот алгоритм?.
Почитал о поиске в глубину, пишут что алгоритм плохо поддается распараллеливанию, но плохо не значит что не поддается :-)
Код:
[syntax lang="cpp"]
//#include "stdafx.h"
#include <iostream>
#include<vector>
#include<fstream>
#include <algorithm>
using namespace std;
const int MAXN = 20001;
vector<int> g[MAXN], g1[MAXN];     
bool used[MAXN],is_added[MAXN];
int timer, tin[MAXN], fup[MAXN], points[MAXN];
int results[MAXN];
int k = 0;
void null(bool mas[MAXN]){
   for (int i = 0; i<MAXN; i++)
      mas[i] = false;
}
void null(int m[MAXN]){
   for (int i = 0; i<MAXN; i++)
      m[i] = -1;
}

void init(int m[MAXN], int n){
   for (int i = 0; i<n; i++)
      m[i] = -1;
}
void dfs(int v, int p = -1) {  //поиск шарниров
   used[v] = true;
   tin[v] = fup[v] = timer++;
   int children = 0;
   for (size_t i = 0; i<g[v].size(); ++i) {
      int to = g[v][i];
      if (to == p)  continue;
      if (used[to])
         fup[v] = min(fup[v], tin[to]);
      else {
         dfs(to, v);
         fup[v] = min(fup[v], fup[to]);
         if (fup[to] >= tin[v] && p != -1){
            if (!is_added[v]) {
               points[k] = v;
               is_added[v] = true;
               k++;
            }
         }
         ++children;
      }
   }
   if (p == -1 && children > 1){
      if (!is_added[v]) {
         points[k] = v;
         is_added[v] = true;
         k++;
      }
   }
}
void read(int& n){   
   ifstream in("input.txt");
   int m, a, b;
   in >> n >> m;
   for (int i = 0; i<m; i++){
      in >> a >> b;
      g[a - 1].push_back(b - 1);
      g[b - 1].push_back(a - 1);
   }

}

void bubble_sort(int *data, int size) {
   int i, j;
   for (i = 0; i < size; ++i) {
      for (j = size - 1; j > i; --j) {
         if (data[j] > data[j - 1]) {
            int t = data[j - 1];
            data[j - 1] = data[j];
            data[j] = t;
         }
      }
   }
}

int main() {
   int n; int i; vector<int> g1[MAXN];
   ofstream out("output.txt");
   null(points);
   read(n);
//   init(results, n);
   timer = 0;
   for (i = 0; i < n; i++){
      used[i] = false;
      is_added[i] = false;
   }
   dfs(0);

   i = 0;
   bubble_sort(points, MAXN);
   while ((i<MAXN) && (points[i] != -1)){
      i++;
   }
   out << i << endl;
   i = MAXN-1;
   while ((i >= 0)){
      if (points[i] != -1)
         out << points[i] + 1 << endl;
         i--;
      
   }

   return 0;
}
[/syntax]

 Профиль  
                  
 
 Re: Разделить граф
Сообщение20.05.2016, 16:25 


27/08/14
206
grelik в сообщении #1124556 писал(а):
Написал небольшую программу для поиска шарниров, вот теперь возник вопрос как можно распараллелить этот алгоритм?
А это действительно необходимо? Можно придумать алгоритм, который возможно сможет быстрее обойти граф при параллельном обходе, при этом эффект будет тем больше, чем больше в графе шарниров. Навскидку приходит следующая идея: спускаясь вниз, если позади осталось достаточно много вершин, для самых ранних можно запустить обход по дочерним узлам в отдельных потоках. При этом если два потока встречаются на одной вершине - более ранний должен обойти вершины более позднего, а более поздний должен прекратить обход (ну или обойти свой кусок вместо более раннего потока, но это уже детали реализации). Из этого следует, что эффект будет только от тех потоков, которые начнут обход с шарнирных узлов.
P.S. syntax не нужно вкладывать в code

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 5 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group