Merge remote-tracking branch 'upstream/master'

1 files changed, 31 insertions, 0 deletions

diff --git a/rst_parser/arc_factored.cc b/rst_parser/arc_factored.cc
new file mode 100644
index 00000000..1e75600b
--- /dev/null
+++ b/rst_parser/arc_factored.cc
@@ -0,0 +1,31 @@
+#include "arc_factored.h"
+
+#include <set>
+
+#include <boost/pending/disjoint_sets.hpp>
+
+using namespace std;
+using namespace boost;
+
+// based on Trajan 1977
+void ArcFactoredForest::MaximumSpanningTree(SpanningTree* st) const {
+  typedef disjoint_sets_with_storage<identity_property_map, identity_property_map,
+      find_with_full_path_compression> DisjointSet;
+  DisjointSet strongly(num_words_ + 1);
+  DisjointSet weakly(num_words_ + 1);
+  set<unsigned> roots, h, rset;
+  vector<pair<short, short> > enter(num_words_ + 1);
+  for (unsigned i = 0; i <= num_words_; ++i) {
+    strongly.make_set(i);
+    weakly.make_set(i);
+    roots.insert(i);
+  }
+  while(!roots.empty()) {
+    set<unsigned>::iterator it = roots.begin();
+    const unsigned k = *it;
+    roots.erase(it);
+    cerr << "k=" << k << endl;
+    pair<short,short> ij; // TODO = Max(k);
+  }
+}
+