Narzędzia użytkownika

Narzędzia witryny


graph_import_export

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

#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[] = {
		4,
		2, 1, 5,
		3,
		3, 1, 2,
		9,
		2,
		2,
		6,
		6
	};
 
	// 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;
}

Graf użyty w przykładzie w kodzie:

graph_import_export.txt · ostatnio zmienione: 2009/04/10 12:53 przez sgasioro