Różnice

Różnice między wybraną wersją a wersją aktualną.

--- graph_import_export [2009/04/07 16:25]
sgasioro utworzono
+++ graph_import_export [2009/04/10 12:53] (aktualna)
sgasioro
@@ Linia 1: / Linia 1: @@
-test
+**Boost Graph Import Export**
+Biblioteki Boost Graph udostępniają mechanizmy odczytu i zapisy grafów do formatów GraphML oraz GraphVIZ.
+====== Budowa biblioteki ======
+Aby używać **read_graphml** musimy zbudować bibliotekę z odpowiednimi opcjami, gdyż biblioteki dostępne z Boost Pro nie zawierają GraphML readera (przynajmniej w wersji MSVC8.0).
+Jak większość bibliotek, których główną platformą docelową jest linux, kompilacja ich zajmuje bardzo dużo czasu, gdyż trzeba znaleźć rozwiązania wielu problemów.
+Istnieje duże prawdopodobieństwo, że opisana procedura nie rozwiąże wszystkich problemów, które się pojawią podczas próby doprowadzenia **read_graphml** do działania.
+Musimy mieć biblioteki EXPAT (http://sourceforge.net/projects/expat/) i ustawić zmienne środowiskowe na odpowiednie ścieżki przed kompilacją bibliotek.
+np. (ważne cudzysłowy):\\
+set EXPAT_INCLUDE="...\Expat 2.0.1\Source\lib"\\
+set EXPAT_LIBPATH="...\Expat 2.0.1\Bin"\\
+Następnie możemy budować biblioteki Boost Graph (używając **bjam**, zgodnie z instrukcją Getting Started).
+W odpowiednim katalogu ...\boost\libs\graph\build wywołujemy **bjam**.
+Jeśli pojawiło się ostrzeżenie o braku ścieżek EXPAT ustawiamy je ponownie.
+Sprawdzamy czy nie pojawiły się błędy i jęsli są to je korygujemy (np. nie znaleziono expat.h) ustawiając odpowiednie ścieżki EXPAT, include w kompilatorze itp.
+Jeśli kompilacja się nie powiodą z powodu braku biblioteki expat.lib otwieramy plik **.../boost/libs/graph/build/Jamfile.v2** i zmieniamy **<find-shared-library>expat** na **<find-shared-library>libexpat** lub inne np. libexpatMT, libexpatw, libexpatwMT w zależności od naszego celu (czy biblioteka wielowątkowa, czy debug itd.).
+Kolejna przydatną rzeczą jest po linii **<define>BOOST_GRAPH_NO_LIB** dodanie **<define>XML_STATIC**, dzięki czemu nie będziemy musieli mieć pliki **libexpat.dll** przy uruchamianiu programu.
+Nie zawsze to jednak działa i można to osiągnąć również dodają linię **#define XML_STATIC** w pliku **graphml.cpp** przed **#include <expat.h>**
+Gdy udało się skompilować możemy dodawać tę bibliotekę np. **boost_graph-vc80-gd-1_38.lib** do naszego programu. Wtedy będzie potrzebny nam jednak plik dll.
+Jeśli chcemy dodać procedury do naszego kodu wynikowego dołączamy np. **libboost_graph-vc80-mt-gd-1_38.lib**.
+Do kompilacji potrzebne jest również dołączenie biblioteki **libexpat.lib**.
+Jeśli jednak chcemy mieć tylko jedne biblioteki Boost, musimy zbudować całe biblioteki Boost, w tym celu w katalogu **.../boost/** wywołujemy **bjam** z odpowiednimi parametrami (instrukcja w Getting Started). Pamiętajmy o ustawieniu zmiennych **EXPAT_INCLUDE** i **EXPAT_LIBPATH** przed wywołaniem **bjam**.
+Dobrze jest jednak najpierw skompilować samą bibliotekę Graph by zobaczyć czy kompiluje się bez błędów, ponieważ jeśli pojawią się błędy np. związane z biblioteką EXPAT, biblioteki Boost zbudują się bez obsługi GraphML readera.
+====== Ograniczenia ======
+Wczytywanie różnych grafów, np. z plików znalezionych w internecie, wymaga określenia różnych parametrów, co w praktyce wiąże się z zajrzeniem do pliku z grafem i ręczne określenie np. co jest głownym identyfikatorem węzła lub jakie każdy węzeł lub krawędź ma właściwości (np. "name", "color", "weight"). Nie ma jednej funkcji do wczytania dowolnego grafu, a przynajmniej nie ma takiej opisanej w dokumentacji. Jest to z góry narzucone przez niefortunny sposób opisu grafów w tych bibliotekach, który zakłada, że atrybuty grafu będą znane podczas kompilacji.
+Jest to wielka wada, gdyż praktycznie uniemożliwia wykorzystanie tej biblioteki do wczytywania grafów stworzonych przez innych.
+====== Przykład ======
+<code cpp>
+#include <iostream>
+#include <string>
+#include <boost/graph/graphml.hpp>
+using namespace std;
+using namespace boost;
+// definiujemy typ grafu
+typedef adjacency_list< vecS, vecS, directedS,
+    property< vertex_name_t, string >,
+    property< edge_weight_t, int >
+    > Graph;
+void CreateGraph(Graph &g, dynamic_properties &dp)
+{
+	// nazwy wierzcholkow
+	const char* name[] = { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "10" };
+	// definiujemy typ krawedzi
+	typedef std::pair<int,int> Edge;
+	// tworzymy krawedzie grafu
+	Edge my_edges[] = {
+	Edge(0, 1),
+        Edge(1, 2), Edge(1, 5), Edge(1, 8),
+        Edge(2, 3),
+        Edge(3, 2), Edge(3, 4), Edge(3, 6),
+        Edge(6, 7),
+		Edge(7, 8),
+        Edge(8, 7),
+        Edge(9, 10),
+        Edge(10, 9)
+     };
+	// tworzymy wagi odpowienich krawedzi
+	int my_wages[] = {
+,
+, 1, 5,
+,
+, 1, 2,
+,
+,
+,
+,
+
+	};
+	// ilosc krawedzi
+	const int nedges = sizeof(my_edges)/sizeof(Edge);
+	// tworzymy graf z wierzcholkow
+	g = Graph(my_edges, my_edges + nedges, 10);
+	// ustawiamy wartosci wierzcholkow (tutaj np. stringi)
+	graph_traits<Graph>::vertex_iterator v, v_end;
+	for (tie(v,v_end) = vertices(g); v != v_end; ++v)
+	    put(vertex_name_t(), g, *v, name[*v]);
+	// ustawiamy wagi krawedzi
+	graph_traits<Graph>::edge_iterator e, e_end;
+	int index = 0;
+	for (tie(e,e_end) = edges(g); e != e_end; ++e, ++index)
+	    put(edge_weight_t(), g, *e, my_wages[index]);
+	// ustawiamy, ze wierzcholki beda mialy pole name a krawedzie weight
+	dp.property("name", get(vertex_name_t(), g));
+	dp.property("weight", get(edge_weight_t(), g));
+}
+void SaveGraphML(Graph &g, dynamic_properties &dp, const char *filename)
+{
+	ofstream ofile(filename);
+	// skladnia:
+	//void write_graphml(std::ostream& out, const Graph& g, const dynamic_properties& dp,
+	//          bool ordered_vertices=false)
+	// zapis do strumienia
+	write_graphml(ofile, g, dp, true);
+	ofile.close();
+}
+void LoadGraphML(Graph &g, dynamic_properties &dp, const char *filename)
+{
+	ifstream ifile(filename);
+	// musimy dodac wlasnosci recznie
+	dp.property("name", get(vertex_name_t(), g));
+	dp.property("weight", get(edge_weight_t(), g));
+	// lapiemy mozliwe wyjatki
+	try
+	{
+		read_graphml(ifile, g, dp);
+	}
+	catch (bad_parallel_edge &ge)
+	{
+		cout << "bad_parallel_edge from " << ge.from << " to " << ge.to << endl;
+	}
+	catch (directed_graph_error&)
+	{
+		cout << "directed_graph_error" << endl;
+	}
+	catch (undirected_graph_error&)
+	{
+		cout << "undirected_graph_error" << endl;
+	}
+	catch (parse_error&)
+	{
+		cout << "parse_error" << endl;
+	}
+	catch (property_not_found &ge)
+	{
+		cout << "property_not_found " << ge.property << endl;
+	}
+	ifile.close();
+}
+void SaveGraphVIZ(Graph &g, dynamic_properties &dp, const char *filename)
+{
+	ofstream ofile(filename);
+	// zapis do strumienia, "name" jako identyfikator wezla
+	write_graphviz(ofile, g, dp, string("name"));
+	ofile.close();
+}
+void LoadGraphVIZ(Graph &g, dynamic_properties &dp, const char *filename)
+{
+	ifstream ifile(filename);
+	// nalezy recznie dodac wlasnosci
+	dp.property("name", get(vertex_name_t(), g));
+	dp.property("weight", get(edge_weight_t(), g));
+	// skladnia:
+	// bool read_graphviz(std::istream& in, MutableGraph& graph,
+	//               dynamic_properties& dp,
+	//               std::string const& node_id = "node_id")
+	// lapiemy mozliwe wyjatki
+	try
+	{
+		// odczyt ze strumienia, "name" jako identyfikator wezla
+		read_graphviz(ifile, g, dp, "name");
+	}
+	catch (bad_parallel_edge &ge)
+	{
+		cout << "bad_parallel_edge from " << ge.from << " to " << ge.to << endl;
+	}
+	catch (directed_graph_error&)
+	{
+		cout << "directed_graph_error" << endl;
+	}
+	catch (undirected_graph_error&)
+	{
+		cout << "undirected_graph_error" << endl;
+	}
+	catch (parse_error&)
+	{
+		cout << "parse_error" << endl;
+	}
+	catch (property_not_found &ge)
+	{
+		cout << "property_not_found " << ge.property << endl;
+	}
+	ifile.close();
+}
+void CheckGraphs(Graph &g1, Graph &g2)
+{
+	assert(num_vertices(g2) == num_vertices(g1));
+	assert(num_edges(g2) == num_edges(g1));
+	graph_traits<Graph>::vertex_iterator v, v_end;
+	for (tie(v,v_end) = vertices(g1); v != v_end; ++v)
+        assert(get(vertex_name_t(), g1, *v) == get(vertex_name_t(), g2, *v));
+	graph_traits<Graph>::edge_iterator e, e_end;
+	for (tie(e,e_end) = edges(g1); e != e_end; ++e)
+        assert(get(edge_weight_t(), g1, *e) == get(edge_weight_t(), g2, *e));
+}
+int main(int argc, char *argv[])
+{
+	Graph g;
+	dynamic_properties dp;
+	CreateGraph(g, dp);
+	// zapisujemy graph do pliku
+	SaveGraphML(g, dp, "graph.xml");
+	// odczytujemy nowy graf
+	Graph g2;
+	dynamic_properties dp2;
+	LoadGraphML(g2, dp2, "graph.xml");
+	// sprawdzenie czy dobrze zostalo zapisane i wczytane
+	CheckGraphs(g, g2);
+	// --------------------------------------------------
+	// zapisujemy graph do pliku
+	SaveGraphVIZ(g, dp, "graph_viz.dot");
+	Graph g3;
+	dynamic_properties dp3;
+	LoadGraphVIZ(g3, dp3, "graph_viz.dot");
+	// sprawdzenie czy dobrze zostalo zapisane i wczytane
+	CheckGraphs(g, g3);
+	// wypisujemy na ekran
+	write_graphml(cout, g3, dp3, true);
+	return 0;
+}
+</code>
+Graf użyty w przykładzie w kodzie:\\
+{{:graf1.gif|}}

zpr c++ quick reference

Narzędzia użytkownika

Narzędzia witryny

Różnice

Narzędzia strony