[Java] Analiza i wizualizacja zależności pomiędzy plikami JAR, część II

W poprzedniej części dowidzieliśmy się, jak utworzyć graf zależności oraz poznaliśmy podstawowe metody wizualizacji. W tym artykule postaram się przedstawić jak różne pojęcia z teorii grafów przekładają się na nasz model (dla przypomnienia – zależności modelujemy jako graf skierowany w którym wierzchołki są plikami JAR i krawędź A→B oznacza, że A zależy od B)

Stopień wierzchołka

Stopień wierzchołka w grafie to liczba krawędzi sąsiadujących z wierzchołkiem. W przypadku grafów skierowanych mówi się o stopniach wyjściowymi i wejściowym – degOut(v), degIn(v) W grafie zależności jest to odpowiednio liczba projektów od których zależy bezpośrednio dany projekt i liczba projektów które zależą od niego.  W mojej opinii najlepszą wizualiacją stopnia jest jego rozmiar, przy czym stopień wejściowy i wyjściowy możemy wizualizować osobno lub łącznie. W przypadku biblioteki Jung najłatwiej osiągnąć to stosując odpowiedni transformer

class VertexShapeTransfomer extends AbstractVertexShapeTransformer
    implements Transformer {

    public Shape transform(Object v) {
        return factory.getEllipse(v)
    }
}
def vst = new VertexShapeTransfomer();
vst.setSizeTransformer(new Transformer() {
    public Integer transform(Object v) {
       return ((g.inDegree(v) + g.outDegree(v)) + 1) * 5
    }
})
vs.getRenderContext().setVertexShapeTransformer(vst)

Efekt zastosowanie dla wcześniejszego przykładu wygląda tak
hibernate-release-4.1.9-dep-vis-vertex-degree

Zbiór zależności modułu s

To nic innego jak zbiór wierzchołków osiągalnych ze źródła s. Do jego wyznaczenia można użyć funkcji DFS-VISIT z algorytmu DFS.

DFS-VISIT(G, u)
   u.color ← GRAY
   time ← time + 1
   u.d ← time
   for each v ∈ G.Adj[u]
      if v.color == WHITE
         v.π ← u
         DFS-VISIT(G,v)
u.color ← BLACK
time ← time + 1
u.f ← time

Zbiór zależności s to te wierzchołki które po wywołaniu DFS-VISIT(G, s) mają kolor inny niż biały (tj. zostały co najmniej odwiedzone). W warstwie prezentacji można to zmieniając kolor wierzchołków, np. na zielony

def vertexColor = new Transformer<Integer,Paint>() {
            public Paint transform(Object v) {
               if(deps.contains(v)) {
                    return Color.GREEN
               } else {
                   return Color.RED
               }
            }
        }
vs.getRenderContext().setVertexFillPaintTransformer(vertexColor)

Zależności (w tym przechodnie) modułu g, isVisited) def selectedNode = 'hibernate-core-4.1.9.Final.jar'
Cykle

W idealnej sytuacji pomiędzy plikami JAR nie powinno być zależności cyklicznych, praktyka pokazuje niestety że czasami jest inaczej. Znalezienie wszystkich cykli w grafie jest samo w sobie ciekawym zagadnienie (patrz Dodatek A), tutaj zastosujemy uproszczony (ale poprawny) algorytm oparty o przeszukiwanie w głąb grafu skierowanego i krawędzie wsteczne

Znając cykle w grafie zależności możemy je zaprezentować na kilka sposobów, co zaprezentują na przykładzie testowego grafu
directed-graph-with-cycles

  • Wyświetlić podgraf grafu zależności składający się tylko w wierzchołków wchodzących w skład jakiegoś cyklu
    directed-graph-with-cycles-only
  • Dla danego wierzchołka u wyświetlić wszystkie cykle w skład których wchodzi.Przykładowo, dla wierzchołka E jest to tylko cykl A→C→E→A
    cycles-containing-vertex-e
  • Wyświetlić podgraf składający się ze wszystkich cykli określonej długości

Dodatek A Znajdowanie cykli w grafie skierowanym.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s