Hejka, od jakiegoś czasu (paru dni), męczę się wszelako z programem, który napisałem. Działą on dobrze, prawie od samego początku, problemem jest jedynie rzeczy, które ma obsługiwać. Jego zadaniem będzie obsługa dużych grafów.... do 100 tys wierzchołków... Eh wrzucając do niego średni graf (10 tys wierzchołków), gość się miota. Z początku bibliotek graphviz4net, wyrzucała stack overflow exception - rozwiązałem to pisząc własny parser (dołączony do repozytorium). Potem wyjątek stack overflow zaczęła wyrzucąć moja pierwsza dobrze działająca na małych grafach wersja, podczas 300-tego wywołania rekurencyjnie funkcji (funkcja ta jest zakomentowana w kodzie). W tym celu zbudowałem tę funkcje na nowo, tylko tym razem w oparciu o rozwiązanie kogoś, a nie samemu kminąc jak to można zrobić. Napisałem algorytm BFS no i on już działa, przynajmniej takie mam wrażenie (nigdy nie doczekałem się końca liczenia przez niego grafu średniego, po 15 min uznałem żę nie ma sensu czekać dłużej). No i tu nie mam pomysłów jak to zrobić, by ten program robił to szybciej. Przepisałem nawet funkcje tak by działała asynchronicznie, ale nic to nie dało :C, albo przynajmniej nie dało tego co chciałbym by dało. Wymaganiem dla programu jest by działał W UWAGA... 30 sek O_O seems impossible for me. On po 15 min ledwo zrobił 500 wierzchołków, gdzie tam do 10 tys, albo 100 tys.
Tu moja prośba może by ktoś bardziej ogarnięty doradził jak to zrobić lepiej, szybciej, sprawniej? =( ja jeszcz spróbuje napisać DFS algorytm, ale wątpie żeby nagle z x min zeszło do minuty :/. Tu link do repo z projektem https://github.com/Jarverr/LookingCapital
Tu fragment kluczowy kodu:
private async static void BFSAlgorithm(List<int> vertices, Dictionary<int, int> edgesSource, Dictionary<int, int> edgesDestination, Dictionary<int, List<int>> edgesConnection, int[][] edges, Dictionary<int, bool> potentialCapital)
{
Queue<int> verteciesToCheck = new Queue<int>();
Dictionary<int, bool> verteciesWhichImAbletAchive = new Dictionary<int, bool>();
//uzupełnieni słowników
foreach (var item in vertices)
{
verteciesWhichImAbletAchive.Add(item, false);
}
List<Task> tasks = new List<Task>();
foreach (var item in vertices)
{
tasks.Add(checkVertex(item,vertices, edgesSource, edgesDestination, edgesConnection, edges, potentialCapital));
}
await Task.WhenAll(tasks);
//return potentialCapital;
}
private async static Task checkVertex(int vertex, List<int> vertices, Dictionary<int, int> edgesSource, Dictionary<int, int> edgesDestination, Dictionary<int, List<int>> edgesConnection, int[][] edges, Dictionary<int, bool> potentialCapital)
{
int counter;
Queue<int> verteciesToCheck = new Queue<int>();
Dictionary<int, bool> verteciesWhichImAbletAchive = new Dictionary<int, bool>();
int vertexWchichICheck;
counter = 0;
verteciesToCheck.Clear();
foreach (var itemToClear in vertices)
{
verteciesWhichImAbletAchive[itemToClear] = false;
}
verteciesWhichImAbletAchive[vertex] = true;
verteciesToCheck.Enqueue(vertex);
while (verteciesToCheck.Count > 0)
{
vertexWchichICheck = verteciesToCheck.Dequeue();
for (int i = 0; i < vertices.Count; i++)
{
if (edgesConnection[i].Contains(vertexWchichICheck) && !verteciesWhichImAbletAchive[i])
{
verteciesWhichImAbletAchive[i] = true;
verteciesToCheck.Enqueue(i);
}
}
}
for (int i = 0; i < vertices.Count; i++)
{
if (verteciesWhichImAbletAchive[i] == true)
counter++;
}
if (counter == vertices.Count)
{
potentialCapital.Add(vertex, true);
}
else
{
potentialCapital.Add(vertex, false);
}
}
Gdyby ktoś znalazł czas, by doradzić czy coś byłbym wdzięczny. Dzięki z góry!
C#