RFpro.ru: Программирование на C / C++ (comp.soft.prog.cplus) : Рассылка : Subscribe.Ru

Подписаться Бесплатная «Золотая» новостная рассылка . Подписчиков 5.423 RSS

← Май 2010 →
	1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

За последние 60 дней ни разу не выходила

Сайт рассылки: http://prog.rusfaq.ru/C
Открыта: 14-03-2002

Автор

Калашников О.А.

Статистика

5.423 подписчиков
0 за неделю

← Все выпуски →

RFpro.ru: Программирование на C / C++

Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гаряка Асмик
Статус: Специалист
Рейтинг: 3636
∙ повысить рейтинг »

lamed
Статус: Бакалавр
Рейтинг: 2570
∙ повысить рейтинг »

Boriss
Статус: Академик
Рейтинг: 2303
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И ПО / Программирование / C/C++

Номер выпуска:	1531
Дата выхода:	16.05.2010, 19:30
Администратор рассылки:	Verena, Профессионал
Подписчиков / экспертов:	437 / 164
Вопросов / ответов:	1 / 1
IRC-канал по теме:	#C

Вопрос № 178336: Здравствуйте, уважаемые эксперты! Прошу помочь в написании алгоритма Хошена-Копельмана для маркировки кластеров. Есть его реализация на С, но надо на С++(Visual Studio). Очень надеюсь на вашу помощь. Заранее большое спасибо....

Вопрос № 178336:

Здравствуйте, уважаемые эксперты!
Прошу помочь в написании алгоритма Хошена-Копельмана для маркировки кластеров. Есть его реализация на С, но надо на С++(Visual Studio).
Очень надеюсь на вашу помощь. Заранее большое спасибо.

Отправлен: 11.05.2010, 19:10
Вопрос задал: Yulesik, 1-й класс
Всего ответов: 1
Страница вопроса »

Отвечает amnick, Студент :
Здравствуйте, Yulesik.

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

Алгоритм Х-К по сути является версией алгоритма объединение-поиск для двумерной решетки. Алгоритм объединение-поиск используется для объединения элементов множества в подмножества. Он содержит две процедуры: union(x, y), которая задает отношение эквивалентности двух элементов, т. е. определяет, что они принадлежат одному подмножеству и find(x), которая возвращает члена-представителя данного класса эквивалентности.

Реализация алгоритма:
1. Алгоритм Х-К для двумерной решетки. График количество кластеров - вероятность заполнения клетки. Реализация на C. http://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelm an/hoshenkopelman.html
2. Распараллеливание алгоритма Х-К с использованием конечного автомата. - http://www.cs.utk.edu/~berry/parhk/index.html

В приложении приведен вариант реализации алгоритма на C++, основанный на (1). Программа протестирована в MSVC++ 6.0, должна компилироваться (возможно, с минимальными изменениями) и другими компиляторами C++.

Чтобы не вводить матрицу вручную, создайте файл, содержащий матрицу в требуемом формате (см. комментарии в теле программы) и воспользуйтесь
перенаправлением ввода:
178336.exe < file_with_matrix

Успехов!

Приложение:
/* Реализация алгоритма Хошена-Копельмана для маркировки кластеров на С++. Based on Tobin Fricke\'s implementation of the Hoshen-Kopelman algorithm for cluster labeling: http://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hk.c Описание алгоритма (на английском): http://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html */ #include <conio.h> #include <iostream> // заменить на iostream.h для Borland C++ #include <assert.h> using namespace std; // удалить для Borland C++ // ------------------------------------------------------------------- // Implementation of Union-Find Algorithm class UnionFind { public: UnionFind( int max_labels ); ~UnionFind(); int find( int x ); int Union( int x, int y ); int make_set(); int getNumLabels() const { return m_nLabels; } /* The \'labels\' array has the meaning that labels[x] is an alias for the label x; by following this chain until x == labels[x], you can find the canonical name of an equivalence class. The labels start at one; labels[0] is a special value indicating the highest label already used. */ protected: int* labels; int m_nLabels; // length of the labels array }; // the constructor sets up the data structures needed by the union-find implementation. UnionFind::UnionFind( int max_labels ) { m_nLabels = max_labels; labels = new int[m_nLabels]; labels[0] = 0; } // The destructor frees the memory used by the union-find data structures UnionFind::~UnionFind() { m_nLabels = 0; delete labels; labels = 0; } // find returns the canonical label for the equivalence class containing x int UnionFind::find(int x) { int y = x; while (labels[y] != y) y = labels[y]; while (labels[x] != x) { int z = labels[x]; labels[x] = y; x = z; } return y; } // Union joins two equivalence classes and returns the canonical label of the resulting class. int UnionFind::Union(int x, int y) { return labels[find(x)] = find(y); } // make_set creates a new equivalence class and returns its label int UnionFind::make_set() { labels[0] ++; assert(labels[0] < m_nLabels); labels[labels[0]] = labels[0]; return labels[0]; } // End Union-Find implementation // ------------------------------------------------------------------- class Matrix { public: Matrix( int nRows, int nCols ); ~Matrix(); int hoshen_kopelman(); void check_labelling(); // Оператор ввода friend istream& operator>>( istream& stream, Matrix& m ); // Оператор вывода friend ostream& operator<<( ostream& stream, const Matrix& m ); protected: int m_nRows, m_nCols; int** matrix; }; Matrix::Matrix( int nRows, int nCols ) : m_nRows( nRows ), m_nCols( nCols ) { matrix = (int **)calloc( nRows, sizeof(int*) ); for( int i=0; i < nRows; i++ ) matrix[i] = (int *)calloc( nCols, sizeof(int) ); } Matrix::~Matrix() { for( int i=0; i < m_nRows; i++ ) free( matrix[i] ); free( matrix ); } istream& operator>>( istream& stream, Matrix& m ) { for( int i=0; i < m.m_nRows; i++ ) for( int j=0; j < m.m_nCols; j++ ) stream >> m.matrix[i][j]; return stream; } /* operator<< prints out a matrix that is set up in the "pointer to pointers" scheme (aka, an array of arrays); this is incompatible with C\'s usual representation of 2D arrays, but allows for 2D arrays with dimensions determined at run-time */ ostream& operator<<( ostream& stream, const Matrix& m ) { for( int i=0; i < m.m_nRows; i++ ) { for( int j=0; j < m.m_nCols; j++ ) { stream.width(3); stream << m.matrix[i][j]; } stream << endl; } return stream; } #define max(a,b) (a>b?a:b) #define min(a,b) (a>b?b:a) // Label the clusters in "matrix". Return the total number of clusters found. int Matrix::hoshen_kopelman() { UnionFind uf( m_nRows*m_nCols/2 ); /* scan the matrix */ for( int i=0; i<m_nRows; i++ ) for (int j=0; j<m_nCols; j++) if( matrix[i][j] ) { // if occupied ... int up = (i==0 ? 0 : matrix[i-1][j]); // look up int left = (j==0 ? 0 : matrix[i][j-1]); // look left switch (!!up + !!left) { case 0: matrix[i][j] = uf.make_set(); // a new cluster break; case 1: // part of an existing cluster matrix[i][j] = max(up,left); // whichever is nonzero is labelled break; case 2: // this site binds two clusters matrix[i][j] = uf.Union(up, left); break; } } /* apply the relabeling to the matrix */ /* This is a little bit sneaky.. we create a mapping from the canonical labels determined by union/find into a new set of canonical labels, which are guaranteed to be sequential. */ int* new_labels = new int[uf.getNumLabels()]; // allocate array, initialized to zero memset( new_labels, 0, sizeof(int)*uf.getNumLabels() ); for( i=0; i < m_nRows; i++) for (int j=0; j < m_nCols; j++) if (matrix[i][j]) { int x = uf.find(matrix[i][j]); if (new_labels[x] == 0) { new_labels[0]++; new_labels[x] = new_labels[0]; } matrix[i][j] = new_labels[x]; } int total_clusters = new_labels[0]; delete new_labels; return total_clusters; } // This procedure checks to see that any occupied neighbors of an occupied site // have the same label. void Matrix::check_labelling() { for( int i=0; i < m_nRows; i++ ) for( int j=0; j < m_nCols; j++ ) if (matrix[i][j]) { int N = ( i==0 ? 0 : matrix[i-1][j] ); int S = ( i==m_nRows-1 ? 0 : matrix[i+1][j] ); int E = ( j==m_nCols-1 ? 0 : matrix[i][j+1] ); int W = ( j==0 ? 0 : matrix[i][j-1] ); assert( N==0 || matrix[i][j]==N ); assert( S==0 || matrix[i][j]==S ); assert( E==0 || matrix[i][j]==E ); assert( W==0 || matrix[i][j]==W ); } } /* The sample program reads in a matrix from standard input, runs the HK algorithm on it, and prints out the results. The form of the input is two integers giving the dimensions of the matrix, followed by the matrix elements (with data separated by whitespace). a sample input file is the following: 8 8 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 this sample input gives the following output: --input-- 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 --output-- 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 2 0 0 0 0 2 0 1 2 0 0 2 0 2 0 1 2 0 0 2 0 2 0 1 2 0 0 2 2 2 0 1 2 2 2 2 0 0 0 1 0 0 0 2 2 2 0 1 HK reports 2 clusters found */ int main() { /* Read in the matrix from standard input The whitespace-deliminated matrix input is preceeded by the number of rows and number of columns */ int m, n; cin >> m >> n; // m = rows, n = columns Matrix matrix( m, n ); cin >> matrix; // print out an initial matrix cout << " --input-- \n" << matrix; // Process the matrix int clusters = matrix.hoshen_kopelman(); // Output the result cout << " --output-- \n" << matrix; matrix.check_labelling(); cout << "HK reports " << clusters << " clusters found\n"; getch(); return 0; }

Ответ отправил: amnick, Студент
Ответ отправлен: 11.05.2010, 20:51
Номер ответа: 261343

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?

Отправить SMS #thank 261343 на номер 1151 (Россия) | Еще номера »

Отправить WebMoney:

Оценить выпуск »
Нам очень важно Ваше мнение об этом выпуске рассылки!

Задать вопрос экспертам этой рассылки »

Скажите "спасибо" эксперту, который помог Вам!

Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
на короткий номер 1151 (Россия)
Номер ответа и конкретный текст СМС указан внизу каждого ответа.

Полный список номеров »

* Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
*** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

© 2001-2010, Портал RFpro.ru, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
Хостинг: Компания "Московский хостер"
Версия системы: 2010.6.14 от 03.03.2010

В избранное

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} {#if $P.login_register_tab == 1} <form class="authentication-form" method="post" action="/MEMBERLOGIN_authen_cred"> <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <h1>Войти на сайт</h1> {* {#include js_tmpl_auth_reg_button} *} {#include js_tmpl_auth_reg_action} <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones"><p>{#include js_tmpl_auth_reg_descr} </p></div> <div class="logreg_advice noPhones"> Если вы еще не с нами, то начните с <a href="#" onclick="rgNav('js_tab_reg');return false;" class="dashed" data-func="registr">регистрации</a> </div> <br><br> <a class="dashed auth-enter" href="/manage/author/"><b>Вход для авторов</b></a> </dt> </dl> </form> {#/if} {#if $P.login_register_tab == 2} <div class="rg_block_options"> <div id="js_tap_panel_auth"> <h1>Регистрация</h1> <div class="social_reg"> {* <div class="rg_description">{#include js_tmpl_soc_auth_reg_descr}</div> *} {#include js_tmpl_auth_reg_soc} <div class="rg_soc_auth_agree">{#include js_tmpl_auth_reg_agree}</div> </div> <div class="subscribe_reg"> {* <div class="rg_description"> #include js_tmpl_auth_reg_descr </div> *} {#include js_tmpl_auth_reg_action} </div> {* {#include js_tmpl_auth_reg_button} *} <div class="clr"> </div> <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones">{#include js_tmpl_auth_reg_descr} {#include js_tmpl_soc_auth_reg_descr} </div> </div> </div> {#/if} </div> {* <div class="gray_bg register_shadow"></div> *} </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_auth" class="{#if $P.login_register_tab == 1} rg_active_nav {#/if} rg_first_nav"><a onclick="rgNav('js_tab_auth');return false;" href="">Вход на сайт</a></li> <li id="js_tab_reg" class="{#if $P.login_register_tab == 2} rg_active_nav {#/if}"><a onclick="rgNav('js_tab_reg');return false;" href="">Регистрация </a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_action} {#if $P.login_register_tab == 1} {#include js_tmpl_auth_reg_soc} {#/if} <div class="rg_forms"> <input type="hidden" id="login_register_destination" value="{$P.login_register_destination}"/> {#if $P.login_register_tab == 1} <div class="rg_for_input"> <span class="rg_text_inner">E-mail или код подписчика</span> <input id="credential_0" class="js_keydown_selector rg_input_text" data-js_submit="no" data-js_next_input_name="credential_1" name="" type="text" /> </div> <div class="rg_for_input"> <span class="rg_text_inner">Пароль</span> <input id="credential_1" class="js_keydown_selector rg_input_text" data-js_submit="yes" data-js_action="js_loginFormBut" name="" type="password" onkeyup="showAttention(this,!!window.event.shiftKey)" /> <span class="pswd_attention" id="attention_pswd"> <span class="icon_attention"></span> <span class="pswd_attention-text" id="attention-text_pswd1">Русская раскладка клавиатуры!</span> <span class="pswd_attention-text" id="attention-text_pswd2">У вас включен Caps Lock!</span> <span class="pswd_attention-text" id="attention-text_pswd3">У вас включен Caps Lock и русская раскладка клавиатуры!</span> </span> </div> <div class="rg_for_input input-alien"> <span class="chk noPhones"><input id="chk_alien" name="" type="checkbox" /></span><label for="chk_alien" class="noPhones"> Чужой компьютер</label> <a class="forgot_pass" href="/member/totalrecall">Забыли пароль?</a> </div> <div class="rg_for_input"> <em id="auth_msg" class="reg_error"></em> <input id="lf_typeauthid" value="email" type="hidden"> <input type="submit" class="button button-red logreg_submit" id="js_loginFormBut" value="Войти">  <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} {#if $P.login_register_tab == 2} <div class="rg_for_input"> <span class="rg_text_inner">E-mail</span> <input id="arfemail" class="js_keydown_selector rg_input_text" name="" type="text" data-js_submit="yes" data-js_action="js_regFormBut"/> </div> <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a> </label> <br /> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_personal' type="checkbox" data-js_submit="yes" /></span> Нажимая на кнопку "Готово!", я даю <a class="link_txd logreg_accLink" href="/faq/persverordnung.html">согласие на обработку персональных данных</a> </label> </div> {* <div style="float: left;position: absolute;left: 11em;"> <img src="http://www.kupivip.ru/images/vip/logo.png?1604" style="width: 86px; vertical-align: middle;display: block;"> </div> <div class="rg_for_input rg_set_lineh"> <label class="js_tap_panel_checkbox"><input name="" id="js_tap_panel_checkbox_kupivip" type="checkbox" data-js_submit="yes"> Я хочу получать новости о скидках на одежду</label> </div> *} <div class="rg_for_input"> <em id="reg_msg" class="reg_error rg_for_input_wide"></em> <em id="reg_msg2" class="reg_error rg_for_input_wide"></em> <input id="rf_typeauthid" value="email" type="hidden"> <a class="button button-red logreg_submit" id="js_regFormBut" href="#">Готово!</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} </div> {#/template js_tmpl_auth_reg_action} {#template js_tmpl_auth_reg_agree} <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms_reg' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a></label> <em id="reg_msg_soc" class="reg_error rg_for_input_wide"></em> </div> {#/template js_tmpl_auth_reg_agree} {#template js_tmpl_auth_reg_button} <div class="rg_butons_socials"> {#if $P.login_register_tab == 1} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} {#if $P.login_register_tab == 2} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} </div> {#/template js_tmpl_auth_reg_button} {#template js_tmpl_auth_reg_descr} {#if $P.login_register_tab == 1} Для оформления подписки на выбранную рассылку, работы с интересующей вас группой или доступа в нужный вам раздел, просим авторизоваться на Subscribe.ru {#/if} {#if $P.login_register_tab == 2} Для регистрации укажите ваш e-mail адрес. Адрес должен быть действующим, на него сразу после регистрации будет отправлено письмо с инструкциями и кодом подтверждения. {#/if} {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_soc_auth_reg_descr} Или зарегистрируйтесь через социальную сеть. {#/template js_tmpl_soc_auth_reg_descr} {#template js_tmpl_auth_reg_soc} <div class="rg_soc"> {#if $P.login_register_tab == 1} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/login/vk/&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} {#if $P.login_register_tab == 2} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/join/vk&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} </div> {#/template js_tmpl_auth_reg_soc}

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <p class="rg_description">{#include js_tmpl_auth_reg_descr}</p> <div class="clr"> </div> {#include js_tmpl_auth_reg_action} <div class="clr"> </div> </dt> </dl> </div>  </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_reg" class="rg_active_nav rg_first_nav"><a href="" onclick="return false;" >Регистрация</a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_descr} <strong>Пожалуйста, подтвердите ваш адрес.</strong><br><br>Вам отправлено письмо для подтверждения вашего адреса {$P.register_confirm_mail}.<br>Для подтверждения адреса перейдите по ссылке из этого письма. {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_auth_reg_action} <div class="rg_forms confirm_code_from_letter"> <div class="rg_for_input"> <span class="rg_inp_descr" style="width:15em;">Или введите код из письма:</span> <input type="text" value="" id="confirm_code" name="" data-js_submit="yes" data-js_action="js_confirmFormBut" class="js_keydown_selector rg_input_text_conf" > </div> <div class="rg_for_input"><label>Не пришло письмо? <b>Пожалуйста, проверьте папку Спам</b><br /> (папку для нежелательной почты).</label><br /> <a href="" onclick="ajax_recall_code();return false" >Вышлите мне письмо еще раз!</a></div> <div class="rg_for_input"> <em class="reg_error" id="confirm_msg"></em> <a href="#" class="button button-red" id="js_confirmFormBut">Готово</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> <br> </div> </div> {#/template js_tmpl_auth_reg_action}