CannibalSmith ([info]cannibalsmith) rakstīja [info]koderi kopienā,
@ 2008-04-05 11:42:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
darbs ar kokiem (grafiem) un Boost
Sagribējās izmantot Boost nevis kārtējo reizi gudrot riteni pašam. Gribu izmantot Graph bibliotēku, bet nekā nejēdzu. Tā bibliotēka ir nejēgā sarežģīta. Ko es gribu (pseido c++ kodā):
Graph graph;
Node root = graph.add_node(); // koka sakne
Node i = root;
while (whatever)
{
	// staigājam pa grafu, izrēķinam, kur pievienot nākamo pēcteci
	i.create_child();
}
// izvadam koka vizualizāciju SVG formātā
Varbūt man izmantot citu valodu vai vidi, kur šādas lietas jau ir atstrādātas?

(Ierakstīt jaunu komentāru)


[info]bubu
2008-04-05 19:20 (saite)
Jautājums - kāpēc tu to gribi C++ valodā? Vai tai ir kādas priekšrocības tavai problēmai?
Man jau šķiet, ka šai gadījumā būtu izdevīgāka kāda dinamiska valoda. Piemēram, Python. Tur tu grafus varētu ātri un vielgi būvēt no parastiem dict vai list objektiem (std::map un std::vector veida konteineri).

Bet ja nu gribi C++'ā ar boostu, tad RTFM: Boost C++ Libraries - Table of Contents: Boost Graph Library (tur tiešām ir viss, kas vajadzīgs)
Nekas sarežģīts principā tur nav. Viss jau arī atkarīgs kā tu tur gribi staigāt pa grafu. Daudzi apstaigāšanas algoritmi ir jau boosta graphā iekšā. Atliek tikai tos pareizi pielietot savām vajadzībām.
Bet ja nu gribi manuāli, tad to dara aptuveni šādi:
// orientēts grafa tips
typedef adjacency_list<vecS, vecS, directedS, std::string, int> Graph;

// virsotnes un šķautnes tips
typedef Graph::vertex_descriptor Node;
typedef Graph::edge_descriptor Edge;

Graph graph;

Node root = add_vertex(graph);
graph[root] = "root_dati";
Node i = root;

while (whatever)
{

   // iterē pa visiem i kaimiņiem
    BOOST_FOREACH(Edge edge, out_edges(i, graph))
    {
        Node j = target(edge, graph);
 
        // kautko dari virsotnei j
        // ...
    }
             
    Node new_node = add_vertex(graph);
    graph[new_node] = "jaunas nodes dati";
    Edge e = add_edge(i, new_node, graph).first; // pieliek šķautni no i uz new_node
    graph[e] = 666; // var protams neko nelikt šķautnes datos un tos tipā vispār nenorādīt, ja nevajag
}

(Atbildēt uz šo)

Neesi iežurnalējies. Iežurnalēties?