Generowanie losowej sieci przepływowej (spójny graf skierowany)

Witam,

Chciałbym napisać algorytm, który będzie mi generował sieć przepływową (spójny graf skierowany, w którym wyróżniony jest wierzchołek początkowy i wierzchołek końcowy). Coś takiego:

Ogólnie potrzebne jest mi to do analizy algorytmów na znajdowanie maksymalnego przepływu i najtańszego.
Na wejściu podana będzie ilość wierzchołków i krawędzi (ewentualnie coś jeszcze). Chciałbym, aby było to generowane za pomocą macierzy sąsiedztw, gdzie indeksy tablicy odpowiadałyby numerom wierzchołków, a zawartością tablicy byłyby przepustowości krawędzi. I teraz ważne jest, że musi istnieć przynajmniej jedna droga z wierzchołka początkowego do wierzchołka końcowego. A najlepiej jakby było ich kilka, tak jak na rysunku, równomiernie rozłożonych kilka dróg. I teraz nie bardzo wiem jak się do tego zabrać z tym generowaniem losowym, aby w miarę rozsądne sieci tworzyło. Przed chwilą wpadłem na pomysł, żeby po kolei tworzyć całe ścieżki z początku do końca i tak w kółko, aż nie zostaną przekroczone wartości wejściowe.
Ma ktoś jeszcze jakiś dobry pomysł jakbym mógł to ugryźć?
Z góry dziękuję za pomoc i zainteresowanie problemem.

Losujesz minimalny graf rozpinający:

1. Lista wierzcholków zawierająca wszystkie wierzchołki każdy z przypisanym unikalnym numerkiem np od 1, nazwijmy ten numerek grupą.
2. Sprawdzasz czy masz więcej niż jedną grupę, jeżeli została tylko jedna to koniec.
3. Losujesz dwa wierzchołki A i B, jeżeli należą do tej samej grupy to powtórz losowanie.
4. Łączysz A z B krawędzią
5. Dla wszystkich wierzchołków grupa których jest taka jak grupa B (łącznie z samym B) zmieniasz na taką grupę jaką ma A.
6. Powtórz od punktu 2.
   Teraz każdy z wierzchołków połączony z każdym tylko jedną drogą.
   Możesz dolosować jeszcze kilka krawędzi.

Dziękuję za odpowiedź. Sam na pewno bym tego nie wymyślił. Po dodaniu jeszcze kilku krawędzi sieć powinna być ładnie utworzona. Jeszcze takie pytanie. Bo wymyśliłem też pewien sposób. Jakbyś mógł rzucić na niego okiem i powiedzieć, czy również jest w miarę dobry. Mniej więcej zamysł tego jest taki, aby po kolei losować drogę od wierzchołka początkowego do wierzchołka końcowego.

1. Losujemy wierzchołek o indeksie wyższym niż aktualny (na początku naszym aktualnym indeksem jest 1, czyli wierzchołek początkowy). (Dla uproszczenia przyjąłem, że będą losowane krawędzie w kierunku od indeksu niższego do wyższego).
2. Jeżeli pomiędzy tymi wierzchołkami nie ma krawędzi to ją tworzymy, a aktualny wierzchołek ustawiamy na wcześniej wylosowany.
3. Powtarzamy od punktu 1, dopóki nie osiągniemy wierzchołka końcowego, czyli o maksymalnym indeksie (po osiągnięciu maksymalnego indeksu mamy utworzoną drogę z wierzchołka początkowego do końcowego).
4. Ustawiamy aktualny indeks znowu na 1 i powtarzamy od punktu 1, aż do osiągnięcia zamierzonej liczby krawędzi.

Nie wiem, czy jest to dobrym pomysłem, dlatego byłbym wdzięczny, gdybyś to skomentował, bo niewątpliwie posiadasz większą wiedzę w tym temacie ode mnie. Innych, zainteresowanych użytkowników forum również proszę o opinię.

Ten algorytm ma same wady, najważniejsza polega na tym że algorytm nie gwarantuje że graf będzie spójny.

Rozumiem. Zapomnijmy o tym pomyśle.
Przeanalizowałem Twój algorytm i wyszła mi taka sytuacja. Dla 6-wierzchołkowego grafu, losując kolejno krawędzie (s,d), (s,a), (b,c), (c,t), (d,t), (kierunek krawędzi jest w kierunku zgodnym z kolejnością wypisywanych liter) otrzymujemy następujący graf:

Wierzchołek s jest początkowym wierzchołkiem, a t końcowym. Jak widać mamy tylko jedną drogę, wierzchołki b i c można powiedzieć, że wiszą w powietrzu, bo i tak nie mogą być wykorzystane. Teraz jedynym rozwiązaniem jest jakoś umiejętnie dolosować kolejne krawędzie, aby tych możliwych dróg było trochę więcej. I się zastanawiam, czy po prostu zupełnie losowo dodać kolejne krawędzie, czy może przyjąć jeszcze jakieś warunki podczas losowania.

1. Losujesz
2. Notujesz jakoś na boku te krawędzie
3. Usuwasz wszystkie krawędzie
4. Losujesz po raz drugi
5. Odtwarzasz zanotowane krawędzie.

• masz gwarantowane dwie drogi.

Okej. Dzięki. Jeszcze tak dla pewności, to z tym losowaniem, to masz na myśli cały algorytm, który napisałeś w pierwszym poście, tak? A nie to losowanie tych dodatkowych krawędzi. To postaram się to napisać w miarę szybko. W razie problemów będę pisał.
Pozdrawiam.

Tak a propos, ponieważ masz graf skierowany losować wierzchołek A w przedstawionym przeze mnie algorytmie powinieneś tylko z grupy 1 czyli tej do której należy wierzchołek S.

Napisałem algorytm do generowania tego minimalnego grafu rozpinającego. Ogólnie wynik jest dobry, jednak wydaje mi się, że dosyć długo trwa to generowanie. Dla 6 wierzchołków średni czas to około 6 sekund. Komputer mam dosyć dobry. Dodatkowo przy losowaniu wierzchołków podszedłem do tego w taki sposób, żeby losować krawędzie od wierzchołka o niższym indeksie w kierunku wierzchołka o indeksie wyższym. Z tego względu, że przy dolosowywaniu krawędzi, bądź nakładaniu się wyników z dwukrotnego przeprowadzenia całego algorytmu mogłyby się pojawić cykle, a takiej sytuacji niestety być nie może. Innego sposobu na ominięcie tego nie znam. Mógłbyś Dragon spojrzeć na mój kod i zobaczyć, czy da radę jakoś go przyspieszyć?

 
#include <cstdlib>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <time.h>

#define w 6 //ilosc wierzcholkow
#define k 5 //ilosc krawedzi

using namespace std;

int macierz[w][w];
int wierzcholki[w];

int generowanie() {
    int i,j,a,b,bz;
    int wierzcholki[w];
    bool jest;
    
    //wypelnianie macierzy
    for (i=0;i<w;i++)
        for (j=0;j<w;j++)
            macierz[i][j] = -1; 
    
    //przypisanie wierzcholkow do osobnych grup
    for (i=0;i<w;i++)
        wierzcholki[i]=i;
    
    do {
       jest = false; //zakladamy, ze nie istnieje wiecej niz jedna grupa
   
       //sprawdzanie czy jest wiecej niz jedna grupa wierzcholkow    
       for (i=0;i<w-1;i++) {
           if (wierzcholki[i]!=wierzcholki[i+1]) {
              jest=true;
              break;    
           }
       }
       
       if (!jest) return 0; //jezeli jest tylko jedna grupa, to zakoncz algorytm
    
       //losowanie 2 wierzchokow z roznych grup
       do {
          srand(time(NULL));
          a = rand()%(w-1);  //losujemy pierwszy wierzcholek o indeksie z przedzialu [1,w-1]
          b = (rand()%(w-a-1))+a+1; //losujemy drugi wierzcholek o indeksie wyzszym niz wierzcholek poprzedni
          /*a = rand()%(w-1);
          b = (rand()%(w-1))+1;
          */
       } while (wierzcholki[a] == wierzcholki[b]);
    
       macierz[a][b] = 0; //laczenie krawedzia wylosowanych wierzcholkow
    
       //wszystkie wierzcholki z grupy wierzcholka b otrzymuja nowa grupe taka jaka ma wierzcholek a
       bz = wierzcholki[b];
       for (i=0;i<w;i++)
           if (wierzcholki[i] == bz) wierzcholki[i] = wierzcholki[a];
    } while (jest);
    
    return 0;
}



int main(int argc, char *argv[])
{   int i,j;

    generowanie();
    for (i=0;i<w;i++) {
        for (j=0;j<w;j++)
            cout << macierz[i][j] << "  ";
        cout << "\n";    
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

1. Przenieś srand(time(NULL)); na początek main'a i już będzie o wiele szybsze.
2. Losowanie masz pochrzanione, ma być:

a=rand()%w; 
b=rand()%w;

i już.
3. Ma sens trzymać liczniki węzłów z których masz wylosować "a" i z których masz wylosować "b", przyspieszy algorytm to w kilku miejscach.
4. Jeżeli graf masz skierowany to ta metoda niezbyt pasuje, bo masz szansę dostać brak połączenia, pisałem już ci o tym.
5. Połać sprawdzanie czy masz wszystkie takie same z nadpisywaniem.
6. Jeżeli masz coś takiego wierzcholki[a] w pętli w której to "a" się nie zmienia ani "wierzcholki[a]" się nie zmienia to przed pętlą zapisz wierzcholki[a] do zmiennej a w pętli porównaj to z tą zmienną.
7. Generalnie nie istnieje żaden znany algorytm dla grafów którego realizacja była by szybsza na macierze sąsiedztwa niż na dobrze przemyślanej liście. Ten algorytm jest też jednym z algorytmów dla grafów.