Eclipse Graph Tools

Eclipse Graph Tools to kontynuacja projektu o którym pisałem w ramach tego posta. Jego celem jest stworzenie dynamicznie rozszerzalnej platformy pozwalającej na modelowanie grafów za pomocą narzędzi graficznych oraz prezentacja popularnych algorytmów grafowych bazujących na podanym modelu. Głównym celem projektu było stworzenie narzędzia które będzie zapewniało prosty sposób modelowania grafów w postaci:

1. Graficznej – za pomocą wbudowanego edytora grafów.
2. Tekstowej – za pośrednictwem popularnej notacji DOT używanej m. in. w narzędziu GraphViz.

Grafy stworzone w ramach takiej reprezentacji miały być przedstawione za pomocą prostego modelu który pozwalał by na przetwarzanie go w ramach dowolnego algorytmu grafowego.
Model ten powinien być na tyle ogólny by pozwolić na ewentualne rozszerzenia: 

Projekt składa się z 3 niezależnych komponentów.

1. Narzędzie do modelowania grafów oraz edytor modelu grafu
   Początek pracy z programem zaczynamy od wizardu dostępnego w menu File >> New >> Other >> EGT
   
   
   
   
   

W ten sposób powstają 2 pliki. Jeden odpowiadający za graficzną reprezentacje grafu (modeler grafu) oraz plik modelu, który domyślnie otwiera edtor pozwalający na podgląd grafu.

Modeler grafu:

Edytor modelu grafu:

2. EDT Core i Visualization plugins

Pluginy core oraz visualization są osobną częścią programu odpowiadającą za komunikacje pomiędzy modelem a algorytmami napisanymi przez zewnętrznych użytkowników.

Aby uruchomić mechanizm wizualizacji w modelerze grafu otwieramy menu kontekstowe i wybieramy opcje "Apply Algorithm".

W nowym oknie wybieramy interesujący nas algorytm oraz sposób wykonywania kolejnych kroków: Krokowy lub Czasowy:

Po wybraniu algorytmu przechodzimy do jego wizualizacji. Poprzez wykonanie kolejnych kroków widzimy przebieg algorytmu na grafie odpowiadającym modelowi. Obecna wersja wspiera tylko model wizualny. Do zaimplementowania pozostała wizualizacja modelu opisanego za pomocą specyfikacji .DOT.

3. Zestaw przykładowych algorytmów wraz z API.

Program został napisany w sposób który maksymalnie upraszcza tworzenie nowych roszrzerzeń algorytmów. Dodatkowo wraz z programem został dołączony oddzielny plugin który zawiera przykładowe implementacje prostych algorytmów. Proces tworzenia nowego algorytmu wymaga utworzenia rozszerzenia zwanego Extension dla dowolnego pluginu Eclipse. Musimy rozszerzyć Extension Point o nazwie pl.zgora.uz.egt.core.algoritm. W ramach rozszerzenia dodajemy nowy element który określa nasz algorytm. Pojedyńczy opis algorytmu w naprostszej wersji zawiera jego nazwe oraz klase która domyślnie implementuje interfejs pl.zgora.uz.egt.core.algoritm.GraphAlgorithm.

Poniższy kod obrazuje przykład implementacji takiego algorytmu:

public class DFS implements GraphAlgorithm {

private GraphModel model;

private GraphNotifier notifier;

private EList<Vertex> vertexes;

protected boolean[] isVertexVisited;

public DFS() {

}

public boolean run() {

prepareAlgoritm();

for (int i = 0; i < vertexes.size(); i++) {

if (vertexes.get(i).getColor().equals(Colors.CLEAN)) {

    vertexes.get(i).setColor(Colors.PERFORMED);

    dfsRun(i);}

}

return true;

}

private void prepareAlgoritm() {

  vertexes = model.getVertexes();

  for (int i = 0; i < vertexes.size(); i++) {

     vertexes.get(i).setColor(Colors.CLEAN);

  }

  isVertexVisited = new boolean[vertexes.size()];

  for (int i = 0; i < vertexes.size(); i++) {

     isVertexVisited[i] = false;

  }

}

public void dfsRun(int start) {

  addVertex(start);

  for (int i = 0; i < vertexes.size(); i++) {

   EList<Edge> edges = vertexes.get(start).getEdges();

  for (Edge e : edges) {

    int index = e.getParentVertex().getIndex();

    if ((isVertexVisited[index] == false)) {

    isVertexVisited[index] = true;

    dfsRun(i);

    }

   }

  }

  postProcess(start);

}

protected void postProcess(int x) {

   Vertex vertex2 = vertexes.get(x);

   vertex2.setColor(Colors.TOUCHED);

   notifier.notifyInputChanged(model);

}

private void addVertex(int position) {

   Vertex vertex2 = vertexes.get(position);

   vertex2.setColor(Colors.PERFORMED);

   notifier.notifyInputChanged(model);

}

public void init(GraphModel model, GraphNotifier notifier) {

  this.model = model;

  this.notifier = notifier;

}

}

Algorytm operue na modelu. Każda jego zmiana wymaga polecenia notifier.notifyInputChanged(model) gdzie model jest głównym elementem modelu (instancją GraphModel). Jest to niewątpliwą wadą tego mechanizmu. Kolejna wersja będzie bazowała na klasach nasłuchujących zmiany w modelu, co nie będzie wymagało bezpośrednich wywołań od strony klientów.

Dalsze plany rozwojowe.

Projekt jest jeszcze we wczesnym stadium rozwoju. Obecna wersja pozwala na modelowanie grafów oraz wizualizacje algorytmów Dijkstry, BFS i DFS. Poniżej lista zmian jakie zostaną wprowadzone w kolejnych wersjach:

1. Integracja projektu ze specyfikacją .dot
   http://marketplace.eclipse.org/content/graphviz-dot-zest-dot4zest
   Zamimpelemtowanie edytora dla .dot we frameworku xtext.
2. Poprawienie mechanizmu komunikacji pomiędzy algorytmem a jego reprezentacją graficzną. Rozszerzanie powinno bazować na klasie abstrakcyjnej a nie na interfejsie.
   Dodatkowo należy rozwinąć sam extension point o definiowanie własnych zestawów, ikon, dodatkowych kolorów, oraz typów wyświetlanych diagramów.
3. Zaimplementowanie nowych algorytmów grafowych.
   
   EGT jest projektem open source (licencja EPL). Jego kod źródłowy zostanie wkrótce opublikowany w ramach google projects. Jeśli jesteś zainteresowany współtworzeniem tego projektu to proszę o kontakt :]