Witam!
Napisałem sobie sekwencyjny programik do topologicznego sortowania grafu skierowanego (DAG).
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Stack;
//DAG
public class GraphTopologicalSorting {
private int V; // Liczba wierzchołków
private LinkedList<Integer> adj[]; // Adjacency List
// konstruktor
GraphTopologicalSorting(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i)
adj[i] = new LinkedList();
}
// Funkcja dodajaca krawedzie do grafu
void addEdge(int v, int w) {
adj[v].add(w);
}
// Funkcja rekurencyjna używana przez topologicalSort
void topologicalSortUtil(int v, boolean visited[], Stack stack) {
// Zaznaczanie bieżącego węzła jako odwiedzony.
visited[v] = true;
Integer i;
// Iterowanie wszystkich wierzcholkow sąsiadujących z tym
// wierzchołkiem
Iterator<Integer> it = adj[v].iterator();
while (it.hasNext()) {
i = it.next();
if (!visited[i])
topologicalSortUtil(i, visited, stack);
}
// zapisz bieżący wierzchołek do stosu, który przechowuje wynik
stack.push(new Integer(v));
}
// Funkcja sortowania topologicznego. Używa
// rekurencyjnej metody topologicalSortUtil()
void topologicalSort() {
Stack stack = new Stack();
// Zaznaczenie wszystkich wierzchołków jako nieodwiedzone
boolean visited[] = new boolean[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// wywołanie rekurencyjnej metody do zapisania
// Topologicznego sortowania startujaca od wszystkich wierzcholkow
// jeden po drugim
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, stack);
// wyświetlenie zawartosci stosu
while (stack.empty() == false)
System.out.print(stack.pop() + " ");
}
public static void main(String args[]) {
// tworzenie grafu
GraphTopologicalSorting g = new GraphTopologicalSorting(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
System.out.println("ponizej topologicznie posortowany graf: ");
g.topologicalSort();
}
}
Problem w tym , że chciałbym teraz przerobić go tak aby wykonywał się przy użyciu załóżmy 4 PC czyli przy użyciu MPI. Prosił bym o pomoc w tej sprawie :-)