in-place topological sort

1 files changed, 80 insertions, 77 deletions

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<Hg::Node*> 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<unsigned int, Hg::Node*> 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]);
 }