Форум программистов, компьютерный форум CyberForum.ru

Генерирование особых графов - C++

Восстановить пароль Регистрация
 
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
03.05.2012, 21:51     Генерирование особых графов #1
кто может привести какой-либо тест(пример в текстовом файле) или алгоритм генерирования тестов для
создания произвольного графа с иерархической структурой ввиде матрицы смежности (желательно чтобы вершин было много) ? (заранее спасибо)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
03.05.2012, 22:17     Генерирование особых графов #2
C++
1
2
3
4
int X[N][N] = {{0}};
int count = 2 * N;
while (--count >= 0)
     X[rand() % N][rand() % N] = 1;
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
03.05.2012, 22:24  [ТС]     Генерирование особых графов #3
так это пример произвольного графа, а мне нужен граф со структурой иерархии
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.05.2012, 06:40     Генерирование особых графов #4
можно например так:
C
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
32
33
34
35
36
37
38
39
40
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N_max 6 // максимальное количество вершин
#define sh 2 // максимальное количество вершин которые могут подчиняться одной вершине
int main ()
{
    srand( time( NULL ) );
    int a[N_max][N_max]={0}, tmp1, Q[N_max*N_max], i_st=0, i_end=1, mas_kontr[N_max]={0};
    int tmp, i, col=1, j;
    tmp1=rand()%N_max;
    mas_kontr[tmp1]=1; Q[0]=tmp1;
    while(col<N_max)
    {
        tmp=rand()%3;
        if(tmp==0 && i_end-i_st==1)
            tmp=1;
        for(i=0; i<tmp; i++)
        {
            tmp1=N_max;
            while(tmp1==N_max)
            {
                tmp1=rand()%N_max;
                for(; tmp1<N_max; tmp1++)
                    if(mas_kontr[tmp1]==0)
                        break;
            }
            mas_kontr[tmp1]=1; Q[i_end++]=tmp1; a[Q[i_st]][tmp1]=1; col++;
        }
        i_st++;
    }
    printf("Matr smegn:\n");
    for(i=0; i<N_max; i++)
    {
        for(j=0; j<N_max; j++)
            printf("%3d", a[i][j]);
        printf("\n");
    }
    return 0;
}
Добавлено через 11 минут
между 18 и 19 строкой вставьте:
C
1
2
        if(tmp>N_max-col)
            tmp=N_max-col;
jhendrix
0 / 0 / 0
Регистрация: 23.02.2010
Сообщений: 184
04.05.2012, 18:46  [ТС]     Генерирование особых графов #5
можете объяснить идею этого решения ?

Добавлено через 3 часа 55 минут
в вашей проге вы определили переменную sh на строке 5, но нигде не используете эту переменную и еще на строке 15 (может быть я ошибаюсь) вы написали tmp=rand()%3; , а неправильно будет сделать вот так: tmp=rand()%N_max;

(заранее спс)
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
04.05.2012, 21:24     Генерирование особых графов #6
Цитата Сообщение от jhendrix Посмотреть сообщение
в вашей проге вы определили переменную sh на строке 5, но нигде не используете эту переменную и еще на строке 15 (может быть я ошибаюсь) вы написали tmp=rand()%3; , а неправильно будет сделать вот так: tmp=rand()%N_max;

Не по теме:

иногда пальцы, набирающие код, опережают мысли (на самом деле они печатают мысли которые уже устарели)


C
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
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N_max 6 // максимальное количество вершин
#define sh 3 // максимальное количество вершин которые могут подчиняться одной вершине
int main ()
{
    srand( time( NULL ) );
    int a[N_max][N_max]={0}, tmp1, Q[N_max*N_max], i_st=0, i_end=1, mas_kontr[N_max]={0};
    int tmp, i, col=1, j;
    tmp1=rand()%N_max;
    mas_kontr[tmp1]=1; Q[0]=tmp1;
    while(col<N_max)
    {
        tmp=rand()%sh;
        if(tmp==0 && i_end-i_st==1)
            tmp=1;
        if(tmp>N_max-col)
            tmp=N_max-col;
        for(i=0; i<tmp; i++)
        {
            tmp1=N_max;
            while(tmp1==N_max)
            {
                tmp1=rand()%N_max;
                for(; tmp1<N_max; tmp1++)
                    if(mas_kontr[tmp1]==0)
                        break;
            }
            mas_kontr[tmp1]=1; Q[i_end++]=tmp1; a[Q[i_st]][tmp1]=1; col++;
        }
        i_st++;
    }
    printf("Matr smegn:\n");
    for(i=0; i<N_max; i++)
    {
        for(j=0; j<N_max; j++)
            printf("%3d", a[i][j]);
        printf("\n");
    }
    return 0;
}
Цитата Сообщение от jhendrix Посмотреть сообщение
tmp=rand()%N_max;
тоже можно - но на Ваше усмотрение.
Yandex
Объявления
04.05.2012, 21:24     Генерирование особых графов
Ответ Создать тему
Опции темы

Текущее время: 12:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru