Sortowanie topologiczne- C++

Question

Witajcie, próbuję znaleźć błąd u mnie w implementacji Sortowania Topologicznego.

Otóż, na początku generuje macierz trójkątną dolną tak aby otrzymac DAG- czyli Skierowany graf Acykliczny. Rezultat wyświetlony jest w konsoli ( tzn macierz. ) nastepnie tę macierz  sąsiedztwa przeksztalcam do listy sąsiedztwa dla grafu na której później będę operował ( sortując i przeszukiwując sąsiadów ).

Dokonuje tego w konstruktorze.

#include <iostream>
#include<cstdlib>
#include <stdio.h>
#include<stack>
#include<list>
#include <ctime>

using namespace std;



class TopologicGraph{

        int vertex;
        list<int> *neighbourList;
        public:

       TopologicGraph(int** tab, int vert);
       void  DFSutiling(int vert, bool visited[], stack<int> &stak );
       void  TopologicSort();
       void testPrinter();
};


//generacja
  int** generateDAG(int vertex, int percent ){

    int** matrix = new int*[vertex];
        for (int i = 0; i <vertex; ++i) {
       matrix[i] = new int[vertex];
      }
        for(int i = 0; i < vertex; i++) {
            for(int j = 0; j < vertex; j++) {
                if(i <= j) {
                    matrix[i][j] = 0;
                }
                else{
                        int generator= (rand () % 100);
                         matrix[i][j]=( generator < percent ) ? 1:0;
                }
            }
        }
    return matrix;
    }

// wypisanie
    void print(int ** tablica, int rows){
      for(int i = 0; i < rows; i++){
          for(int j = 0; j < rows; j++)
         {
            printf("%d ", tablica[i][j]);
         }
          printf("\n");
     }
    }

  void TopologicGraph::TopologicSort(){
        stack<int> stak;
        bool visited[vertex];

            for (int i = 0; i < vertex; i++)
                visited[i] = false;

        // wywolujemy sortowanie
          for (int i = 0; i < vertex; i++)
                if (visited[i] == false)
                     this->DFSutiling(i, visited, stak);

        //wypisz wyniki sortowania
        while (stak.empty() == false){
            cout << stak.top() << " ";
            stak.pop();
        }
  }

  void TopologicGraph::DFSutiling(int vtx, bool visited[], stack<int>&stak){

            // ustawiamy na true
            visited[vtx]=true;

         list<int>::iterator j;
         for(j=this->neighbourList[vtx].begin(); j!=this->neighbourList[vtx].end();j++)
            if(!visited[*j] )
                DFSutiling(*j,visited, stak);

            stak.push(vtx); // dodajemy rezultat na stos
  }


  TopologicGraph::TopologicGraph(int **tab, int vert){
            this->vertex= vert;
            this->neighbourList= new list<int>[vert];
            for(int i = 0; i < vert; i++)
                for(int j = 0; j < vert; j++)
                    if(tab[i][j] == 1){
                       // cout<<"Zliczaj "<<i<<" ";
                        this->neighbourList[i].push_back(j);
                    }
       // cout<<"\nkoniec\n";
}


    int main (void){

        srand (time (NULL));
         int** table= generateDAG(5,10);

         TopologicGraph g(table, 5);
         print(table,5);
          cout<<endl;
          g.TopologicSort();

         return 0;
    }

Dalej implementacje mam funkcji- problem jest taki, że za kazdym razem wypisywane są " iteracje, - przejscia przez wierzchołki "  do struktury STOSU. Przez co podejrzewam program nie działa poprawnie i/lub cos jest nie tak z listą sąsiedztwa.

Sam algorytm topologiczny jest z http://www.geeksforgeeks.org/topological-sorting/ więc wydaje mi się poprawny.

Na rzeczy musi być coś z przekształcaniem np macierzy na liste, ew z odnoszeniem się do danych

Z góry dzieki za pomoc 

Answer 1

#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#include <list>
#include <ctime>

using namespace std;



class TopologicGraph
{
        int vertex;
        vector<vector<int>> neighbourList;
    public:

        TopologicGraph(int** tab, int vert);
        void  DFSutiling(int vert, vector<bool> &visited, list<int> &return_list);
        list<int> TopologicSort();
};


//generacja
int** generateDAG(int vertex, int percent )
{
    int** matrix = new int*[vertex];
    for (int i = 0; i <vertex; ++i)
    {
        matrix[i] = new int[vertex];
    }

    for(int i = 0; i < vertex; i++)
    {
        for(int j = 0; j < vertex; j++)
        {
            if(i >= j)
            {
                matrix[i][j] = 0;
            }
            else
            {
                int generator= (rand () % 100);
                matrix[i][j]=( generator <= percent ) ? 1:0;
            }
        }
    }
    return matrix;
}

// wypisanie
void print(int ** tablica, int rows)
{
    for(int i = 0; i < rows; i++)
    {
        for(int j = 0; j < rows; j++)
        {
            printf("%d ", tablica[i][j]);
        }
        printf("\n");
    }
}

//zwraca "liste" wierzchołków posortowaną...
vector<vector<int>> sortByTopology(vector<vector<int>> a)
{
    for(auto element: a)
        for(auto elem: a)
            if(element.size() > elem.size()) swap(element, elem);

    return a;
}

list<int> TopologicGraph::TopologicSort()
{
    list<int> return_list;

    neighbourList = sortByTopology(neighbourList);

    vector<bool> was_visited;
    was_visited.resize(vertex);

    for(int i = 0; i<neighbourList.size(); i++)
        DFSutiling(i, was_visited, return_list);

    return return_list;
}

void TopologicGraph::DFSutiling(int current_vertex, vector<bool> &visited, list<int>&return_list)
{
    if(!visited[current_vertex]) visited[current_vertex] = true;
    else return;

    for(int i = 0; i < neighbourList[current_vertex].size(); i++)
        DFSutiling(neighbourList[current_vertex][i], visited, return_list);


    return_list.push_back(current_vertex); //zamienić na push_front() zależnie od oczekiwanego wyniku
}


TopologicGraph::TopologicGraph(int **tab, int vert)
{
    vertex = vert;
    neighbourList.resize(vert);

    for(int i = 0; i < vert; i++)
        for(int j = 0; j < vert; j++)
            if(tab[i][j])
                this->neighbourList[i].push_back(j);


    cout<<"Sąsiedztwa w grafie:"<<endl;

    for(int i = 0; i < vert; i++)
    {
        for(auto elem: neighbourList[i]) cout<<i<<"<-"<<elem<<" ";
        cout<<endl;
    }
}


int main (void)
{

    srand (time (NULL));
    int** table = generateDAG(5,50);

    cout<<"Macierz sąsiedztwa:"<<endl;
    print(table,5);

    TopologicGraph g(table, 5);

    cout<<endl;

    cout<<"Wynik sortowania:"<<endl;

    auto result =  g.TopologicSort();

    while (result.size())
    {
        cout << result.front() << " ";
        result.pop_front();
    }

    return 0;
}

Troszke się pobawiłem i działa :)

oprócz kosmetycznych zmian:

-Generujemy górną połówkę macierzy, nie dolną

-Naprawiony wyciek pamięci -  tablice z listami sąsiadów alokujesz, a nie dealokujesz potem

Ogólnie założenia algorytmu były zaimplementowane poprawnie, ale były jakieś błędy

Comments

O jezu, dziękuje generalnie nie tyle co naprowadzanie mnie- ale za poświęceniem czasu nad moimi wypocinami. W takim razie wszystko przeanalizuje w oparciu o podany kod i wyciagne wnioski. Pozdrawiam. Zastanawiam się jedynie co było powodem  problemów? Wydawało mi się, że tworze macierz sasiedztwa - w momencie tworzenia grafu ( w konstruktorze? )

-Naprawiony wyciek pamięci -  tablice z listami sąsiadów alokujesz, a nie dealokujesz potem

w którym miejscu dochodzi u mnie do de-alokacji ?  

---

pierwszy wyciek pamięci następuje za sprawą tego, że nie usuwasz nigdzie macierzy tworzonej w funkcji generateDAG:

int** generateDAG(int vertex, int percent )
{
    int** matrix = new int*[vertex];
    for (int i = 0; i <vertex; ++i)
    {
        matrix[i] = new int[vertex];
    }

 

drugi natomiast przy tworzeniu list sąsiedztwa:

opologicGraph::TopologicGraph(int **tab, int vert){
            this->vertex= vert;
            this->neighbourList= new list<int>[vert];

 

Ogólnie wszystko co stworzone przy użyciu operatora new należy potem skasować używając delete. Ja nawet zapomniałem o tej macierzy więc możesz ją potem usunąć jak nie będzie potrzebna.

Co do algorytmu to do tego, którego chciałeś użyć trzeba posortować najpierw liste list sąsiedztwa. Przynajmniej to mi powiedziała wikipedia xD Może w tym był problem, oprócz tego to tworze listy w ten sam sposób co ty. Używam tylko innych kontenerów. Zmiana przy tworzeniu list polegała na tym że generuje macierz, która ma pod przekątną zera, a nie nad. Wtedy moje listy pokazują ile połączeń wpada do wierzchołków, a nie wychodzi z nich.

Jeśli dobrze doczytałem to algorytm DFS polega na sortowaniu wierzchołków w ten sposób, że najpierw wybierane są wierzchołki niezależne, więc dzięki temu mamy dane już na tacy :)

---

posortować najpierw liste list sąsiedztwa

ten algorytm jest z geek'a generalnie. I zastanawiam sie jak to zaimplementowac na przypadek dolnej macierzy  gdyz takie mam zadanie.

Jaki jest cel sortowania tablicy sasiadów? Skoro topologiczne sortowanie polega na tym, ze kazdy wezel stoi zawsze przed tym ... do którego idzie sciezka

Z drugiej strony wedlug algorytmu zaczynamy zawsze od tych ktore maja najmniej sasiadów? Stad posortowanie ich tak ? od min-> max?

---

Tak, sortowanie chyba stąd wynika.

Myśle że jak chcesz z dolnej połówki to spróbuj na odwrót wkładać elementy do listy