From df8ed8821287fc8172cace28e09c2cac9823bb8a Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Wed, 16 Jul 2014 20:56:49 +0200 Subject: in-place topological sort --- fast/main.cc | 157 ++++++++++++++++++++++++++++++----------------------------- 1 file changed, 80 insertions(+), 77 deletions(-) (limited to 'fast/main.cc') diff --git a/fast/main.cc b/fast/main.cc index c951cd8..372f0f1 100644 --- a/fast/main.cc +++ b/fast/main.cc @@ -34,105 +34,108 @@ main(void) ] } */ + Hg::Hypergraph hg; // nodes - Hg::Node a; a.id = 0; a.symbol = "root"; a.left = false; a.right = false; - Hg::Node b; b.id = 1; b.symbol = "NP"; b.left = 0; b.right = 1; - Hg::Node c; c.id = 2; c.symbol = "V"; c.left = 1; c.right = 2; - Hg::Node d; d.id = 3; d.symbol = "JJ"; d.left = 3; d.right = 4; - Hg::Node e; e.id = 4; e.symbol = "NN"; e.left = 3; e.right = 5; - Hg::Node f; f.id = 5; f.symbol = "NP"; f.left = 2; f.right = 5; - Hg::Node g; g.id = 6; g.symbol = "NP"; g.left = 1; g.right = 5; - Hg::Node h; h.id = 7; h.symbol = "S"; g.left = 0; g.right = 5; - - vector nodes; - nodes.push_back(&a); - nodes.push_back(&b); - nodes.push_back(&c); - nodes.push_back(&d); - nodes.push_back(&e); - nodes.push_back(&f); - nodes.push_back(&g); - nodes.push_back(&h); - - // nodes_by_id - map nodes_by_id; - nodes_by_id[0] = &a; - nodes_by_id[1] = &b; - nodes_by_id[2] = &c; - nodes_by_id[3] = &d; - nodes_by_id[4] = &e; - nodes_by_id[5] = &f; - nodes_by_id[6] = &g; - nodes_by_id[7] = &h; + Hg::Node a; a.id = 0; a.symbol = "root"; a.left = false; a.right = false; a.mark = 0; + Hg::Node b; b.id = 1; b.symbol = "NP"; b.left = 0; b.right = 1; b.mark = 0; + Hg::Node c; c.id = 2; c.symbol = "V"; c.left = 1; c.right = 2; c.mark = 0; + Hg::Node d; d.id = 3; d.symbol = "JJ"; d.left = 3; d.right = 4; d.mark = 0; + Hg::Node e; e.id = 4; e.symbol = "NN"; e.left = 3; e.right = 5; e.mark = 0; + Hg::Node f; f.id = 5; f.symbol = "NP"; f.left = 2; f.right = 5; f.mark = 0; + Hg::Node g; g.id = 6; g.symbol = "NP"; g.left = 1; g.right = 5; g.mark = 0; + Hg::Node h; h.id = 7; h.symbol = "S"; h.left = 0; h.right = 6; h.mark = 0; + + hg.add_node(&a); + hg.add_node(&h); + hg.add_node(&g); + hg.add_node(&c); + hg.add_node(&d); + hg.add_node(&f); + hg.add_node(&b); + hg.add_node(&e); // edges - Hg::Hyperedge q; q.head = nodes_by_id[1]; q.tails.push_back(nodes_by_id[0]); q.score = 0.367879441171; - nodes_by_id[1]->incoming.push_back(&q); - nodes_by_id[0]->outgoing.push_back(&q); - q.arity_ = 1; + Hg::Edge q; q.head = hg.nodes_by_id[1]; q.tails.push_back(hg.nodes_by_id[0]); q.score = 0.367879441171; + hg.nodes_by_id[1]->incoming.push_back(&q); + hg.nodes_by_id[0]->outgoing.push_back(&q); + q.arity = 1; q.mark = 0; + hg.edges.push_back(&q); - Hg::Hyperedge p; p.head = nodes_by_id[2]; p.tails.push_back(nodes_by_id[0]); p.score = 0.606530659713; - nodes_by_id[2]->incoming.push_back(&p); - nodes_by_id[0]->outgoing.push_back(&p); - p.arity_ = 1; + Hg::Edge p; p.head = hg.nodes_by_id[2]; p.tails.push_back(hg.nodes_by_id[0]); p.score = 0.606530659713; + hg.nodes_by_id[2]->incoming.push_back(&p); + hg.nodes_by_id[0]->outgoing.push_back(&p); + p.arity = 1; p.mark = 0; + hg.edges.push_back(&p); - Hg::Hyperedge r; r.head = nodes_by_id[3]; r.tails.push_back(nodes_by_id[0]); r.score = 1.0; - nodes_by_id[3]->incoming.push_back(&r); - nodes_by_id[0]->outgoing.push_back(&r); - r.arity_ = 1; + Hg::Edge r; r.head = hg.nodes_by_id[3]; r.tails.push_back(hg.nodes_by_id[0]); r.score = 1.0; + hg.nodes_by_id[3]->incoming.push_back(&r); + hg.nodes_by_id[0]->outgoing.push_back(&r); + r.arity = 1; r.mark = 0; - Hg::Hyperedge s; s.head = nodes_by_id[3]; s.tails.push_back(nodes_by_id[0]); s.score = 1.0; - nodes_by_id[3]->incoming.push_back(&s); - nodes_by_id[0]->outgoing.push_back(&s); - s.arity_ = 1; + hg.edges.push_back(&r); + + Hg::Edge s; s.head = hg.nodes_by_id[3]; s.tails.push_back(hg.nodes_by_id[0]); s.score = 1.0; + hg.nodes_by_id[3]->incoming.push_back(&s); + hg.nodes_by_id[0]->outgoing.push_back(&s); + s.arity = 1; s.mark = 0; + hg.edges.push_back(&s); - Hg::Hyperedge t; t.head = nodes_by_id[4]; t.tails.push_back(nodes_by_id[0]); t.score = 1.0; - nodes_by_id[4]->incoming.push_back(&t); - nodes_by_id[0]->outgoing.push_back(&t); - t.arity_ = 1; + Hg::Edge t; t.head = hg.nodes_by_id[4]; t.tails.push_back(hg.nodes_by_id[0]); t.score = 1.0; + hg.nodes_by_id[4]->incoming.push_back(&t); + hg.nodes_by_id[0]->outgoing.push_back(&t); + t.arity = 1; t.mark = 0; - Hg::Hyperedge u; u.head = nodes_by_id[4]; u.tails.push_back(nodes_by_id[0]); u.score = 1.0; - nodes_by_id[4]->incoming.push_back(&u); - nodes_by_id[0]->outgoing.push_back(&u); - u.arity_ = 1; + hg.edges.push_back(&t); + + Hg::Edge u; u.head = hg.nodes_by_id[4]; u.tails.push_back(hg.nodes_by_id[0]); u.score = 1.0; + hg.nodes_by_id[4]->incoming.push_back(&u); + hg.nodes_by_id[0]->outgoing.push_back(&u); + u.arity = 1; u.mark = 0; + hg.edges.push_back(&u); - Hg::Hyperedge v; v.head = nodes_by_id[4]; v.tails.push_back(nodes_by_id[3]); v.score = 1.0; - nodes_by_id[4]->incoming.push_back(&v); - nodes_by_id[3]->outgoing.push_back(&v); - v.arity_ = 1; + Hg::Edge v; v.head = hg.nodes_by_id[4]; v.tails.push_back(hg.nodes_by_id[3]); v.score = 1.0; + hg.nodes_by_id[4]->incoming.push_back(&v); + hg.nodes_by_id[3]->outgoing.push_back(&v); + v.arity = 1; v.mark = 0; - Hg::Hyperedge w; w.head = nodes_by_id[4]; w.tails.push_back(nodes_by_id[3]); w.score = 2.71828182846; - nodes_by_id[4]->incoming.push_back(&w); - nodes_by_id[3]->outgoing.push_back(&w); - w.arity_ = 1; + hg.edges.push_back(&v); + + Hg::Edge w; w.head = hg.nodes_by_id[4]; w.tails.push_back(hg.nodes_by_id[3]); w.score = 2.71828182846; + hg.nodes_by_id[4]->incoming.push_back(&w); + hg.nodes_by_id[3]->outgoing.push_back(&w); + w.arity = 1; w.mark = 0; + hg.edges.push_back(&w); - Hg::Hyperedge x; x.head = nodes_by_id[5]; x.tails.push_back(nodes_by_id[4]); x.score = 1.0; - nodes_by_id[5]->incoming.push_back(&x); - nodes_by_id[4]->outgoing.push_back(&x); - x.arity_ = 1; + Hg::Edge x; x.head = hg.nodes_by_id[5]; x.tails.push_back(hg.nodes_by_id[4]); x.score = 1.0; + hg.nodes_by_id[5]->incoming.push_back(&x); + hg.nodes_by_id[4]->outgoing.push_back(&x); + x.arity = 1; x.mark = 0; + hg.edges.push_back(&x); - Hg::Hyperedge y; y.head = nodes_by_id[6]; y.tails.push_back(nodes_by_id[2]); y.tails.push_back(nodes_by_id[5]); y.score = 1.0; - nodes_by_id[6]->incoming.push_back(&y); - nodes_by_id[2]->outgoing.push_back(&y); - nodes_by_id[5]->outgoing.push_back(&y); - y.arity_ = 2; + Hg::Edge y; y.head = hg.nodes_by_id[6]; y.tails.push_back(hg.nodes_by_id[2]); y.tails.push_back(hg.nodes_by_id[5]); y.score = 1.0; + hg.nodes_by_id[6]->incoming.push_back(&y); + hg.nodes_by_id[2]->outgoing.push_back(&y); + hg.nodes_by_id[5]->outgoing.push_back(&y); + y.arity = 2; y.mark = 0; + hg.edges.push_back(&y); - Hg::Hyperedge z; z.head = nodes_by_id[7]; z.tails.push_back(nodes_by_id[1]); z.tails.push_back(nodes_by_id[6]); z.score = 1.0; - nodes_by_id[7]->incoming.push_back(&z); - nodes_by_id[1]->outgoing.push_back(&z); - nodes_by_id[6]->outgoing.push_back(&z); - z.arity_ = 2; + Hg::Edge z; z.head = hg.nodes_by_id[7]; z.tails.push_back(hg.nodes_by_id[1]); z.tails.push_back(hg.nodes_by_id[6]); z.score = 1.0; + hg.nodes_by_id[7]->incoming.push_back(&z); + hg.nodes_by_id[1]->outgoing.push_back(&z); + hg.nodes_by_id[6]->outgoing.push_back(&z); + z.arity = 2; z.mark = 0; + hg.edges.push_back(&z); - // test - Hg::viterbi(nodes, nodes_by_id, nodes_by_id[0]); + Hg::topological_sort(hg.nodes, hg.nodes.begin()); + //Hg::viterbi(nodes, hg.nodes, hg.nodes_by_id(0]); } -- cgit v1.2.3