Logo Search packages:      
Sourcecode: tagcoll version File versions  Download package

Implications.cc

/*
 * Collection of tag implications and a Filter to apply or compress them
 *
 * Copyright (C) 2003,2004,2005  Enrico Zini <enrico@debian.org>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307  USA
 */

#include <tagcoll/Implications.h>

#include <algorithm>

using namespace std;
using namespace Tagcoll;

template<class TAG>
00029 OpSet<TAG> Implications<TAG>::getDestinations(const TAG& tag, const OpSet<TAG>& seen) const
{
      typename impl_t::const_iterator i = implications.find(tag);
      if (i == implications.end())
            return OpSet<TAG>();

      // res <- the union of all the destinations of the tag
      OpSet<TAG> res;
      for (typename OpSet<TAG>::const_iterator t = i->second.begin();
                  t != i->second.end(); t++)
      {
            // If the tag is already in res, then also all his destinations are
            // already there
            if (!res.contains(*t) && !seen.contains(*t))
            {
                  res += *t;
                  res += getDestinations(*t, seen + tag);
            }
      }

      return res;
}

template<class TAG>
00053 bool Implications<TAG>::reaches(const TAG& tag1, const TAG& tag2, const OpSet<TAG>& seen) const
{
      // Check if we've reached the target
      if (tag1 == tag2)
            return true;
      
      // No: see if we have other paths to follow
      typename impl_t::const_iterator i = implications.find(tag1);
      if (i == implications.end())
            return false;

      // Try all paths
      for (typename OpSet<TAG>::const_iterator t = i->second.begin();
                  t != i->second.end(); t++)
            if (!seen.contains(*t) && reaches(*t, tag2, seen + tag1))
                  return true;

      // Nothing has been found
      return false;
}

// Remove unnecessary arcs from the dag
template <class TAG>
void Implications<TAG>::pack()
{
      // For every tag
      for (typename impl_t::iterator i = implications.begin();
                  i != implications.end(); i++)
      {
            OpSet<TAG> redundant;

            // For every couple of parents A and B, if A -> B but not B -> A, then B is redundant
            // I need to check every combination; however, I can ignore in the
            // search items that have already been found as redundant

            OpSet<TAG> candidates = i->second;
            while (candidates.size() > 1)
            {
                  typename OpSet<TAG>::const_iterator a = candidates.begin();
                  typename OpSet<TAG>::const_iterator b = a;
                  OpSet<TAG> got;
                  for (++b; b != candidates.end(); b++)
                  {
                        bool ab = reaches(*a, *b);
                        bool ba = reaches(*b, *a);
                        if (ab && !ba)
                        {
                              got += *b;
                              break;
                        } else if (ba && !ab) {
                              got += *a;
                              break;
                        }
                  }
                  candidates -= got;
                  redundant += got;
                  if (!candidates.empty())
                        candidates.erase(candidates.begin());
            }

            i->second -= redundant;
      }
}

template <class TAG>
00118 OpSet<TAG> Implications<TAG>::compress(const OpSet<TAG>& tags) const
{
      // Create the union of the expansion sets of each single tag, without the tag
      // tags = tags - this union
      OpSet<TAG> redundant;
      for (typename OpSet<TAG>::const_iterator t = tags.begin();
                  t != tags.end(); t++)
      {
            OpSet<TAG> expanded = expand(*t);
            for (typename OpSet<TAG>::const_iterator i = expanded.begin();
                        i != expanded.end(); i++)
                  if (*i != *t)
                        redundant.insert(*i);
      }
      return tags - redundant;
}

#ifndef INSTANTIATING_TEMPLATES
#include <string>

namespace Tagcoll {
      template class Implications<std::string>;
      template class AddImplied<std::string, std::string>;
      template class RemoveImplied<std::string, std::string>;
}
#endif


#ifdef COMPILE_TESTSUITE

#include <tests/test-utils.h>

#include <tagcoll/InputMerger.h>

namespace tut {
using namespace tut_tagcoll;

struct tagcoll_implications_shar {
};
TESTGRP(tagcoll_implications);


template<> template<>
void to::test<1>()
{
      std::string input_coll(
                  "a: coffee, milk\n"
                  "b: tea, milk\n"
                  "c: coffee, milk, sugar\n"
                  "d: sugar\n"
                  );
      std::string input_impl(
                  "sugar: sweet\n"
                  "coffee: awake, bitter\n"
                  "tea: awake\n"
                  );
      std::string output_coll(
                  "a: coffee, milk, awake, bitter\n"
                  "b: tea, milk, awake\n"
                  "c: coffee, milk, sugar, awake, sweet, bitter\n"
                  "d: sugar, sweet\n"
                  );
      InputMerger<string, string> result;
      AddImplied<string, string> filter(result);

      outputCollection(input_impl, filter.implications());
      outputCollection(input_coll, filter); 

      InputMerger<string, string> reference;
      outputCollection(output_coll, reference); 

      ensure_coll_equal(reference, result);
}

template<> template<>
void to::test<2>()
{
      std::string input_coll(
                  "a: coffee, milk, awake, bitter\n"
                  "b: tea, milk, awake\n"
                  "c: coffee, milk, sugar, awake, sweet, bitter\n"
                  "d: sugar, sweet\n"
                  );
      std::string input_impl(
                  "sugar: sweet\n"
                  "coffee: awake, bitter\n"
                  "tea: awake\n"
                  );
      std::string output_coll(
                  "a: coffee, milk\n"
                  "b: tea, milk\n"
                  "c: coffee, milk, sugar\n"
                  "d: sugar\n"
                  );
      InputMerger<string, string> result;
      RemoveImplied<string, string> filter(result);

      outputCollection(input_impl, filter.implications());
      outputCollection(input_coll, filter); 

      InputMerger<string, string> reference;
      outputCollection(output_coll, reference); 

      ensure_coll_equal(reference, result);
}

}

#endif

// vim:set ts=4 sw=4:

Generated by  Doxygen 1.6.0   Back to index