C++, wypełnianie grafu


(matiit) #1

Mam liczbę wierzchołków.

Dajmy na to

int N;

Tworzę graf jako macierz sąsiedztwa.

vector graf[N][N];

Nie potrzeba mi grafu wagowego. Wierzchołek to tylko jego numer. Potrzebuję teraz ustawić krawędzie między wierzchołkami. Czy krawędź jest czy nie ma decyduje jeden warunek. Wierzchołki to tylko liczby, więc jeśli i jest w jakimś tam stosunku do j to

graf[i][j] = true;

Graf jest nieskierowany więc [j] juz nie musze zaznaczać.

Jak to najwydajniej wykonać?

I jeszcze jedno bonusowe pytanie (;

Jeśli trzymam graf jako macierz sąsiedztwa i chcę mieć dla wierzchołków jakieś 3 wartości, np. string nazwa, int id i jeszcze powiedzmy bool is_important, to jak to najlepiej osiągnąć?


(Marcin 110) #2

Zapewnić, że odnosisz się do współrzędnych przez i, j, gdzie i < j, np. przez makro:

#define KRAWEDZ(w, i, j) ((i < j) ? (w)[i][j] : (w)[j][i])

w osobnej tablicy int[N], string[N], itd... Choć pewnie, skoro piszesz w C++, najlepiej byłoby to wszystko zrobić obiektowo.


([alex]) #3

Po pierwsze:

int N;vectorbool graf[N][N]; [/code]Nie skompiluje się no chyba że pod gnu/mingw.
Może miałeś na myśli:
vector graf(N,vector(N));
Z tym że może lepiej nie przydzielać pamięci pod nieistniejące połączenia:[code=php]vectorbool g((N*(N-1))1);// dokładnie tyle ile może być połączeń w grafie z N wierzchołkami

(matiit) #4

Więc lepiej użyć listy sąsiedztwa?


([alex]) #5

Lista jest nawet gorsza.


(matiit) #6

Obiektowo, ale jakoś trzeba reprezentować ten graf, więc jak najlepiej?


([alex]) #7

To stricte zależy od tego co na tym grafie chcesz implementować.

Dla większości algorytmów operujących na grafie, będzie najlepsza clasa Graph zawierającą zbiór wierzchołków Node w postaci równoważonego BST oraz listę krawędzi Edge w postaci listy. Każda krawędź ma wskaźnik do wierzchołku docelowego (dla grafu nieskierowanego krawędzie zdublowane). Każdy wierzchołek ma listę wychodzących krawędzi. Generalnie w pamięci powinno powstać coś w stylu:

struct Edge;struct Node;struct Graph { Node *root; Edge *GraphEdgeFirst; };struct Node { Node *left,*right; Edge *NodeOutEdgeFirst; char *Name; /* ... */ };struct Edge { Node *To; Edge *GraphEdgeNext,*NodeOutEdgeNext; double Weight; /* ... */ }; [/code]Owszem nie dla każdego algorytmu taka struktura danych pasuje idealnie. Oczywiście wszystko w postaci klas aby wszystko samo się pilnowało. Jeżeli zamierzasz wywalać krawędzie i/lub węzły w trakcie działania algorytmu to będą potrzebne dodatkowe składowe.

(matiit) #8

Potrzebuję prostego grafu do BFS, więc myślę że potrzebuję tyle:

I mama teraz tablicę bool tab[9999] powiedzmy.

Potrzebuję dodać wierzchołki. index tab'a jest value wierzchołka, chcę dodać tylko gdzie tab == true.

A potem potrzebuję dodać krawędzie pomiędzy wierzchołkami, których value spełniają jakąś tam zależność np. gdy value dzieląc się dają liczbę mniejszą od 3.

Możesz jeszcze bardziej mnie naprowadzić? Sory, ale już przestaje myśleć o tej porze.


([alex]) #9

Niepotrzebnie wywaliłeś wskaźniki z Node: Edge *NodeOutEdgeFirst; oraz z Edge: Edge *GraphEdgeNext,*NodeOutEdgeNext;

Poza tym skoro masz "wyliczane" z id węzła krawędzie (no chyba że algorytm wyliczania jest skomplikowany, nie dający się odwrócić*) to można się ograniczyć do samej tablicy węzłów, dla prostego przeszukiwania wszerz - wystarczy.

*Chodzi o to że jeżeli masz połączenia pomiędzy węzłami Aid - Bid jeżeli Aid/Bid<3 lub Bid/AId<3 to z Aid łatwo wyliczyć do których węzłów jest z niego przejście.


(pebal) #10
#include 

#include 

#include 


const int N = 100;

std::vector tab(N); // tablica wejściowa


struct Node

{

	int ID;

	std::string Nazwa;

	bool IsImportant;


	std::list Nodes;

	bool Visited;

};


int main()

{

	// docelowe węzły grafu (jeżeli wskaźnik różny od 0)

	std::vector nodes(N, 0);


	for (int i = 0; i < N; ++i)

	{

		for (int j = i + 1; j < N; ++j)

		{

			if (tab[i] && !nodes[i]) nodes[i] = new Node;

			if (tab[j] && !nodes[j]) nodes[j] = new Node;


			if (tab[i] && tab[j])

			{

				bool edge = false;


				// przykładowe warunki na istnienie krawędzi

				if (!(i % 3) && !(j % 3)) edge = true;

				if (!((i + j) % 5)) edge = true;


				if (edge)

				{

					nodes[i]->Nodes.push_back(nodes[j]);

				}

			}

		}

	}


	return 0;

}

(matiit) #11

O dzięki za ten kod (;


([alex]) #12

pebal , jak zawsze podajesz beznadziejny kod, nawet nie przeczytawszy postu.

Wytłumacz mi proszę jak przy takiej organizacji zrealizujesz algorytm BFS?

Jeżeli spytasz czemu beznadziejny:

  1. [*:ydx2pfic]

    if (tab[i] && !nodes[i]) nodes[i] = new Node;if (tab[j] !nodes[j]) nodes[j] = new Node;if (tab[i] tab[j]) { ... [/code]można zamienić na:
    [code=php]if (tab[i] tab[j]) { if(!nodes[i]) nodes[i]=new Node; if(!nodes[j]) nodes[j]=new Node; ... Mniej warunków, czytelniejszy, szybszy.[*:ydx2pfic]

    bool edge = false;if (!(i % 3) !(j % 3)) edge = true;if (!((i + j) % 5)) edge = true;if (edge) [/code]można zamienić na:
    [code=php]if((!(i%3)!(j%3)) || (!((i+j)%5)))

    bez komentarza.


(pebal) #13


([alex]) #14

Wydaje mi się że to ty się wcinasz nie mając nic ciekawszego do powiedzenia.


(pebal) #15

Nie pierwszy raz źle Ci się wydaje.


([alex]) #16

No właśnie podejrzewając to, po twoim wcinaniu się zadałem proste pytanie: - "Wytłumacz mi proszę jak przy takiej organizacji zrealizujesz algorytm BFS?". I okazało się że mam racje, wciąłeś się nie mając nic lepszego do powiedzenia. No chyba że znasz odpowiedź na to pytanie, ale starannie ją ukrywasz :smiley:


(pebal) #17

Nadal uważam, że się wcinasz, na dodatek głupio. Proszę, poniżej pasująca implementacja przeszukiwania BFS, specjalnie dla Ciebie.

bool BFS(Node* node, Node* target)

{

	std::queue queue;


	for(;;)

	{

		std::list::const_iterator i = node->Nodes.begin();

		for(; i != node->Nodes.end(); ++i)

		{

			if (*i == target) return true;


			if (!(*i)->Visited)

			{

				queue.push(*i);

				(*i)->Visited = true;

			}

		}


		if (!queue.empty())

		{

			node = queue.front();

			queue.pop();

		}

		else return false;

	}

}

([alex]) #18

A teraz porównaj sobie, twoje podejście oraz to o którym mówiłem zanim się wciąłeś:

Definicja obiektów (owszem trochę obszerniejsza):

class Node:public list<Node*>

(pebal) #19

Coraz bardziej się kompromitujesz. Najpierw pisałeś, że w mojej implementacji nie da się przeszukiwać wszerz a jak Ci udowodniłem, że się da to piszesz, że Twoje rozwiązanie jest lepsze.

Niestety, masz większe ego od rozumu a nad tym można tylko ubolewać.


([alex]) #20

Właśnie zastanawiam się kto ma problem z rozumem.

Pytanie: - "Wytłumacz mi proszę jak przy takiej organizacji zrealizujesz algorytm BFS?", wcale nie oznacza że nie widzę takiej możliwości, zaś oznacza że będzie to bardziej skomplikowane niż być powinno. Co do wielkości ego, to chyba już wyraźnie udowodniłem że się wciąłeś nie mając nic lepszego do powiedzenia, a ty wciąż tego nie pojmujesz, więc się zastanów kto tu ma rozdmuchane ego.