Dobra biblioteka algorytmów graficznych Java? [Zamknięte]


237

Czy ktoś miał dobre doświadczenia z dowolnymi bibliotekami Java dla algorytmów Graph. Próbowałem JGraph i okazało się, że jest w porządku, a w Google jest wiele różnych. Czy są jakieś rzeczy, których ludzie używają z powodzeniem w kodzie produkcyjnym, czy też poleciliby?

Aby wyjaśnić, nie szukam biblioteki, która produkuje wykresy / wykresy, szukam takiej, która pomaga w algorytmach graficznych, np. Minimalne drzewo opinające, węzły algorytmu Kruskala, krawędzie itp. Idealnie jedna z kilkoma dobrymi algorytmami / danymi struktury w ładnym API Java OO.

Odpowiedzi:


108

Jeśli korzystasz z JGraph, powinieneś spróbować JGraphT, który jest przeznaczony dla algorytmów. Jedną z jego funkcji jest wizualizacja za pomocą biblioteki JGraph. Nadal jest rozwinięty, ale dość stabilny. Jakiś czas temu analizowałem złożoność algorytmów JGraphT. Niektóre z nich nie są najszybsze, ale jeśli zamierzasz je wdrożyć samodzielnie i chcesz wyświetlić wykres, może to być najlepszy wybór. Bardzo podobało mi się korzystanie z jego interfejsu API, gdy szybko musiałem napisać aplikację, która działała na wykresie i wyświetlała ją później.


JGraph ma teraz pakiet analityczny, który zawiera szereg funkcji analitycznych, jgraph.github.com/mxgraph/java/docs/index.html .
David

63

Podsumowanie:


Wiele z nich jest niezwykle skomplikowanych ... Korzystanie z metod fabrycznych i tak dalej. Potrzebuję tylko czegoś prostego, aby przygotować się do rozmowy kwalifikacyjnej. Jakieś pomysły?
SoftwareSavant

4
Jeśli są one skomplikowane niż praca, jakiej szukasz
maytham-ɯɐɥʇʎɐɯ

1
Algorytmy graficzne są wyjaśnione tutaj geeksforgeeks.org/graph-data-structure-and-algorytmy z prostym kodem
mosh

40

Sprawdź JGraphT, aby uzyskać bardzo prostą i wydajną bibliotekę graficzną Java, która jest całkiem dobrze wykonana i, aby uniknąć wszelkich nieporozumień, różni się od JGraph . Niektóre przykładowy kod :

UndirectedGraph<String, DefaultEdge> g =
        new SimpleGraph<String, DefaultEdge>(DefaultEdge.class);

    String v1 = "v1";
    String v2 = "v2";
    String v3 = "v3";
    String v4 = "v4";

    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);

    // add edges to create a circuit
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);
    g.addEdge(v3, v4);
    g.addEdge(v4, v1);


37

JUNG jest dobrą opcją do wizualizacji, a także ma dość dobry zestaw dostępnych algorytmów graficznych, w tym kilka różnych mechanizmów do tworzenia losowych wykresów, przeinstalowywania itp. Stwierdziłem również, że jest ogólnie dość łatwy do rozszerzenia i dostosowania w razie potrzeby .


Pakiety hep.aida. * To LGPL ( acs.lbl.gov/software/colt/license.html ). Jest to importowane przez colt ( jung.sourceforge.net/download.html ). Zapobiega to wykorzystaniu JUNG w projektach pod parasolem ASF i EFS. Może należy użyć github fork github.com/rortian/jung2 i usunąć tę zależność. github.com/rortian/jung2/commit/… odzwierciedla ostatnie zatwierdzenie CVS. Obecne zatwierdzenia wydają się usuwać funkcje wizualizacji.
koppor


14

Apache Commons oferuje wykres wspólny . Pod http://svn.apache.org/viewvc/commons/sandbox/graph/trunk/ można sprawdzić źródło. Przykładowe użycie interfejsu API znajduje się również w SVN . Zobacz https://issues.apache.org/jira/browse/SANDBOX-458, aby uzyskać listę zaimplementowanych algorytmów, również w porównaniu z Jung, GraphT, Prefuse, jBPT

Google Guava, jeśli potrzebujesz tylko dobrych struktur danych.

JGraphT to biblioteka grafów z wieloma zaimplementowanymi algorytmami i posiadająca (moim zdaniem) dobry model grafów. Przykład Helloworld . Licencja: LGPL + EPL.

JUNG2 jest także biblioteką na licencji BSD o strukturze danych podobnej do JGraphT. Oferuje algorytmy układania, których obecnie brakuje w JGraphT. Najnowszym popełnić jest od 2010 roku i pakiety hep.aida.*są LGPL (za pośrednictwem biblioteki colt , która jest importowana przez JUNG ). Zapobiega to wykorzystaniu JUNG w projektach pod parasolem ASF i EFS. Może należy użyć widelca github i usunąć tę zależność. Zatwierdzenie f4ca0cd odzwierciedla ostatnie zatwierdzenie CVS. Obecne zatwierdzenia wydają się usuwać funkcje wizualizacji. Zatwierdź d0fb491c dodaje .gitignore.

Prefuse przechowuje wykresy przy użyciu struktury macierzowej, która nie jest wydajna pod względem pamięci dla rzadkich wykresów. Licencja: BSD

Eclipse Zest ma wbudowane algorytmy układu wykresów, których można używać niezależnie od SWT. Zobacz org.eclipse.zest.layouts.al algorytmy . Zastosowana struktura grafu to Eclipse Draw2d , w której Węzły są obiektami jawnymi i nie są wstrzykiwane przez Generics (jak ma to miejsce w Apache Commons Graph, JGraphT i JUNG2).



10

W projekcie uniwersyteckim bawiłem się yFiles firmy yWorks i stwierdziłem, że ma całkiem niezłe API.


Użyłem yFiles do wizualizacji współzależności między elementami danych (jako część komercyjnej platformy oprogramowania). Tak naprawdę nie korzystałem z żadnych algorytmów analizy grafów, ale sprawdź, czy pakiet y.algo ma to, czego potrzebujesz: yworks.com/products/yfiles/doc/api
Jonik

2
yFiles nie jest oprogramowaniem typu open source, ale oferuje licencje komercyjne
koppor

9

sprawdź plany :

Blueprints to kolekcja interfejsów, implementacji, uzupełnień i pakietów testowych dla modelu danych wykresu właściwości. Plany są analogiczne do JDBC, ale dla baz danych grafów. W stosie oprogramowania open source TinkerPop Blueprints służy jako podstawowa technologia dla:

Rury : leniwa struktura przepływu danych

Gremlin : język przejścia przez wykres

Ramki : Maper obiekt-wykres

Piec : pakiet algorytmów graficznych

Rexster : serwer grafów



7

JDSL (biblioteka struktur danych w Javie) powinna być wystarczająca, jeśli lubisz algorytmy graficzne - http://www.cs.brown.edu/cgc/jdsl/


Dzięki za to, nigdy tego nie spotkałem. Używasz tego?
Nick Fortescue

1
Tak, używam tego. Zacząłem go używać może 4 lata temu. Jak dotąd tak dobrze, po prostu chciałbym, żeby był taki port dla .NET.
mr.sverrir

Niestety, strona jdsl.org wydaje się teraz stroną ze spamem.
Ross Judson

1
Zaktualizowałem link w oryginalnym poście. Dzięki.
mr.sverrir

5

W zakresie wizualizacji nasza grupa odniosła pewien sukces z fuse . Rozszerzyliśmy go, aby obsługiwał architektoniczne panele podłogowe i diagramy bąbelkowe, i nie narzekał zbytnio. Mają też nowy zestaw narzędzi Flex o nazwie Flare, który używa bardzo podobnego interfejsu API.

AKTUALIZACJA: Muszę się zgodzić z tym komentarzem, w końcu napisaliśmy wiele niestandardowych funkcji / omijając ograniczenia prefuse. Nie mogę powiedzieć, że lepiej byłoby zacząć od zera, ponieważ byliśmy w stanie wykazać postęp od pierwszego dnia, używając prefuse. Z drugiej strony, jeśli robimy drugą implementację tych samych rzeczy, mogę pominąć fuse, ponieważ znacznie lepiej rozumiemy wymagania.


Jakie były twoje osobiste myśli z fuse? W mojej ostatniej pracy projekt zaczął z niego korzystać, ale skończył z ponad 90% przepisaną (i zoptymalizowaną, z dodatkami nowych funkcji) wersją prefuse.
Thomas Owens,


5

Dobrze jest również przekonać się, że wykres można przedstawić w następujący sposób:

class Node {
   int value;
   List<Node> adj;
}

i zaimplementuj większość algorytmów, które uważasz za interesujące. Jeśli wpadniesz na to pytanie w trakcie sesji treningowej na wykresach, to jest najlepsza biblioteka do rozważenia. ;)

Możesz także preferować macierz przylegania dla najpopularniejszych algorytmów:

class SparseGraph {
  int[] nodeValues;
  List<Integer>[] edges;     
}

lub macierz dla niektórych operacji:

class DenseGraph {
  int[] nodeValues;
  int[][] edges;     
}




0

Jeśli faktycznie szukasz bibliotek wykresów, a nie bibliotek Node / Edge Graph, sugerowałbym splurgowanie biblioteki Big Faceless Graph ( BFG ). Jest o wiele łatwiejszy w użyciu niż JFreeChart, wygląda ładniej, działa szybciej, ma więcej opcji wyjściowych, naprawdę nie ma porównania.


Źle zrozumiałeś pytanie: chodzi o rodzaj wykresów, które mają węzły i krawędzie, a nie taki, który ma placki i paski.
amarillion

-1

JGraph z http://mmengineer.blogspot.com/2009/10/java-graph-floyd-class.html

Zapewnia potężne oprogramowanie do pracy z wykresami (bezpośrednie lub pośrednie). Generuje również kod Graphivz, możesz zobaczyć reprezentacje graficzne. Możesz umieścić własne algorytmy kodu w pakiecie, na przykład: kod cofania. Pakiet zawiera kilka algorytmów: Dijkstra, powrót do minimalnego kosztu ścieżki, itp.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.