Problem mit Fibonacci Heap

[fr33way]

Hallo,

ich möchte die Fibonacci Heap implementierung von Dietmar Kuehl nutzen und habe folgendes Problem:

Header Datei:

// -*-C++-*- boost/f_heap.hpp
// <!!---------------------------------------------------------------------->
// <!! Copyright (C) 1999 Dietmar Kuehl, Claas Solutions GmbH >
// <!!>
// <!! Permission to use, copy, modify, distribute and sell this >
// <!! software for any purpose is hereby granted without fee, provided >
// <!! that the above copyright notice appears in all copies and that >
// <!! both that copyright notice and this permission notice appear in >
// <!! supporting documentation. Dietmar Kuehl and Claas Solutions make no >
// <!! representations about the suitability of this software for any >
// <!! purpose. It is provided "as is" without express or implied warranty. >
// <!!---------------------------------------------------------------------->

// Author: Dietmar Kuehl dietmar.kuehl@claas-solutions.de
// Title:  Declaration for Fibonacci Heaps
// Version: $Id: f_heap.hpp,v 1.1.1.1 1999/08/19 23:18:24 kuehl Exp $

// --------------------------------------------------------------------------
// This implementation is based on the description found in "Network Flow",
// R.K.Ahuja, T.L.Magnanti, J.B.Orlin, Prentice Hall. The algorithmic stuff
// should be basically identical to this description, however, the actual
// representation is not.
// --------------------------------------------------------------------------

#ifndef FHEAP_H_
#define FHEAP_H_

#include <functional>
#include <vector>

namespace boost
{

// --------------------------------------------------------------------------
// The template class fibonacci_heap_base defines everything which does
// not depend on the compare type. Thus, the actual algorithmic stuff
// is in the template class fibonacci_heap. However, the definition of
// the nodes and the iterator type is in fibonacci_heap_base.

template <typename T> class fibonacci_heap_base {
protected:
  struct node;

public:
  typedef T                                      value_type;
  typedef T&                                     reference;
  typedef T const&                               const_reference;
  typedef typename std::vector<node*>::size_type size_type;
  typedef node*                                  pointer;
  class                                          iterator;
  typedef iterator                               const_iterator;

  friend class iterator;

protected:
  class node {
    friend class iterator;

  public:
    node(T const& data): m_parent(0), m_lost_child(0), m_data(data) { m_children.reserve(8); }
    ~node() {}
    void destroy();

    node*     join(node* tree); // add tree as a child
    void      cut(node* child); // remove the child
    int       lost_child() const { return m_lost_child; }
    void      clear()            { m_parent = 0; m_lost_child = 0; }
    size_type rank() const       { return m_children.size(); }
    bool      is_root() const    { return m_parent == 0; }
    node*     parent() const     { return m_parent; }
    void      remove_all()       { m_children.erase(m_children.begin(), m_children.end()); }

    T const& data() const        { return m_data; }
    template <typename K> void data(K const& data) { m_data = data; }

    typename std::vector<node*>::const_iterator begin() const { return m_children.begin(); }
    typename std::vector<node*>::const_iterator end() const   { return m_children.end(); }

  private:
    size_type          m_index;  // index of the object in the parent's vector
    node*              m_parent; // pointer to the parent node
    std::vector<node*> m_children;
    int                m_lost_child;
    T                  m_data;

    node(node const&);
    void operator= (node const&);
  };

public:
  class iterator {
    // : public std::iterator<std::forward_iterator_tag, T const, size_type, T const*, T const&>
  public:
    iterator(): m_heap(0), m_node(0) {}
    iterator(fibonacci_heap_base const* h);
    iterator(fibonacci_heap_base const* h, node const* n): m_heap(h), m_node(n) {}

    // generated copy ctor, copy assignment, dtor are appropriate

    bool operator== (iterator const& it) const { return m_node == it.m_node; }
    bool operator!= (iterator const& it) const { return m_node != it.m_node; }
    T const& operator* () const  { return m_node->data(); }
    T const* operator-> () const { return &m_node->data(); }

    iterator &operator++ ();
    iterator operator++ (int);

  private:
    node const* find_root(typename std::vector<node*>::const_iterator) const;
    node const* find_leaf(node const*) const;

    fibonacci_heap_base const* m_heap;
    node const*                m_node;
  };

public:
  fibonacci_heap_base(): m_size(0) {}
  ~fibonacci_heap_base();

  bool      empty() const { return m_size == 0; }
  size_type size() const  { return m_size; }

  iterator begin() const { return iterator(this); }
  iterator end() const   { return iterator(this, 0); }

protected:
  std::vector<node*> m_roots;
  size_type          m_size;

private:
  fibonacci_heap_base(fibonacci_heap_base const&); // deliberately not implemented
  void operator=(fibonacci_heap_base const&);      // deliberately not implemented
};

// --------------------------------------------------------------------------
// The template class fibonacci_heap implements all algorithmic ingredients
// for an Fibonacci heap.

template <typename T, typename Comp = std::less<T> > class fibonacci_heap: public fibonacci_heap_base<T> {
  typedef typename fibonacci_heap_base<T>::node           node;

public:
  typedef typename fibonacci_heap_base<T>::size_type      size_type;
  typedef node*                                           pointer;
  typedef T                                               value_type;
  typedef T&                                              reference;
  typedef T const&                                        const_reference;
  typedef typename fibonacci_heap_base<T>::iterator       iterator;
  typedef typename fibonacci_heap_base<T>::const_iterator const_iterator;
  typedef Comp                                            compare_type;

  explicit fibonacci_heap(Comp const& comp = Comp()): m_compare(comp) {}

  pointer  push(T const& data);
  void     pop();
  T const& top() const;
  template <typename K> void     change_top(K const& data);

  template <typename K> void     change(pointer, K const&);
  template <typename K> void     decrease(pointer, K const&);
  template <typename K> void     increase(pointer, K const&);
  void     remove(pointer);

private:
  void add_root(node* n);
  void find_min() const;
  void cut(node* n);

  Comp  m_compare;
  mutable node* m_min;
};

// --------------------------------------------------------------------------

} // boost

#endif /* BOOST_F_HEAP_HPP */

und die passende Source Datei:

// -*-C++-*- boost/f_heap.cc
// <!!---------------------------------------------------------------------->
// <!! Copyright (C) 1998 Dietmar Kuehl, Claas Solutions GmbH >
// <!!>
// <!! Permission to use, copy, modify, distribute and sell this >
// <!! software for any purpose is hereby granted without fee, provided >
// <!! that the above copyright notice appears in all copies and that >
// <!! both that copyright notice and this permission notice appear in >
// <!! supporting documentation. Dietmar Kuehl and Claas Solutions make no >
// <!! representations about the suitability of this software for any >
// <!! purpose. It is provided "as is" without express or implied warranty. >
// <!!---------------------------------------------------------------------->

// Author: Dietmar Kuehl dietmar.kuehl@claas-solutions.de
// Title:  Implementation of a Fibonacci heap
// Version: $Id: f_heap.cc,v 1.1.1.1 1999/08/19 23:18:24 kuehl Exp $

// --------------------------------------------------------------------------

#  include "fheap.h"

namespace boost
{

// --- implementation of the iterator class for Fibonacci heaps -------------

template <typename T> inline fibonacci_heap_base<T>::node const* fibonacci_heap_base<T>::iterator::find_root(typename std::vector<node*>::const_iterator it) const
{
  for (; it != m_heap->m_roots.end(); ++it)
    if ((*it) != 0)
      return (*it);
  return 0;
}

template <typename T> inline fibonacci_heap_base<T>::node const* fibonacci_heap_base<T>::iterator::find_leaf(node const* n) const
{
  if (n == 0)
    return 0;

  while (n->m_children.size() != 0)
    n = n->m_children[0];

  return n;
}

template <typename T> inline fibonacci_heap_base<T>::iterator::iterator(fibonacci_heap_base<T> const* h):
  m_heap(h),
  m_node(0)
{
  if (m_heap->m_size == 0)
    return;

  m_node = find_leaf(find_root(m_heap->m_roots.begin()));
}

template <typename T> inline fibonacci_heap_base<T>::iterator& fibonacci_heap_base<T>::iterator::operator++ ()
{
  if (m_node->is_root())
    m_node = find_leaf(find_root(m_heap->m_roots.begin() + m_node->rank() + 1));
  else if (m_node->m_parent->m_children.size() == m_node->m_index + 1)
    m_node = m_node->m_parent;
  else
    m_node = find_leaf(m_node->m_parent->m_children[m_node->m_index + 1]);

  return *this;
}

template <typename T> inline fibonacci_heap_base<T>::iterator fibonacci_heap_base<T>::iterator::operator++ (int)
{
  iterator rc(*this);
  operator++ ();
  return rc;
}

// --- implementation of Fibonacci heap's node member functions ----------------

template <typename T> inline fibonacci_heap_base<T>::pointer fibonacci_heap_base<T>::node::join(node* tree)
{
  tree->m_index  = m_children.size();
  tree->m_parent = this;
  m_children.push_back(tree);
  m_lost_child = 0;

  return this;
}

template <typename T> inline void fibonacci_heap_base<T>::node::cut(node* child)
{
  size_type index = child->m_index;
  if (m_children.size() > index + 1)
    {
      m_children[index] = m_children[m_children.size() - 1];
      m_children[index]->m_index = index;
    }
  m_children.pop_back();
  ++m_lost_child;
}

template <typename T> inline void fibonacci_heap_base<T>::node::destroy()
{
  typename std::vector<node*>::size_type idx = m_children.size();
  while (idx-- != 0)
    if (m_children[idx] != 0)
      {
	m_children[idx]->destroy();
	delete m_children[idx];
      }
}

template <typename T> inline fibonacci_heap_base<T>::~fibonacci_heap_base()
{
  if (m_size == 0)
    return;

  typename std::vector<node*>::size_type idx = m_roots.size();
  while (idx-- != 0)
    if (m_roots[idx] != 0)
      {
	m_roots[idx]->destroy();
	delete m_roots[idx];
      }
}

// --- implementation of auxiliary the Fibonacci heap member functions ---------

template <typename T, typename Comp> inline void fibonacci_heap<T, Comp>::add_root(node* n)
{
  size_type rank = n->rank();
  if (m_roots.size() <= rank)
    {
      while (m_roots.size() < rank)
        m_roots.push_back(0);
      m_roots.push_back(n);
      n->clear();
    }
  else if (m_roots[rank] == 0)
    {
      m_roots[rank] = n;
      n->clear();
    }
  else
    {
      node* r = m_roots[rank];
      m_roots[rank] = 0;
      if (m_compare(n->data(), r->data()))
	{
	  n->clear();
	  add_root(r->join(n));
	}
      else
	{
	  r->clear();
	  add_root(n->join(r));
	}
    }
}

template <typename T, typename Comp> inline void fibonacci_heap<T, Comp>::find_min() const
{
  if (m_size == 0)
    m_min = 0;
  else
    {
      typename std::vector<node*>::const_iterator end = m_roots.end();
      typename std::vector<node*>::const_iterator it = m_roots.begin();
      while (*it == 0)
        ++it;
      m_min = *it;

      for (++it; it != end; ++it)
        if (*it != 0 && m_compare(m_min->data(), (*it)->data()))
          m_min = *it;
    }
}

template <typename T, typename Comp> inline void fibonacci_heap<T, Comp>::cut(node* n)
{
  node* p = n->parent();
  p->cut(n);
  if (p->is_root())
    {
      m_roots[p->rank() + 1] = 0;
      add_root(p);
    }
  else if (p->lost_child() == 2)
    {
      cut(p);
      add_root(p);
    }
}

// --- implementation of Fibonacci heap's modifying member functions -----------

template <typename T, typename Comp> template <typename K> inline void fibonacci_heap<T, Comp>::decrease(pointer n, K const& data)
{
  n->data(data);
  typename std::vector<node*>::const_iterator it = n->begin();
  typename std::vector<node*>::const_iterator end = n->end();
  for (; it != end; ++it)
    if (m_compare(n->data(), (*it)->data()))
      {
	if (n->is_root())
	  m_roots[n->rank()] = 0;
	else
	  cut(n);

	for (it = n->begin(); it != end; ++it)
	  add_root(*it);
	n->remove_all();

	add_root(n);
	break;
      }
  m_min = 0;
}

template <typename T, typename Comp> template <typename K> inline void fibonacci_heap<T, Comp>::increase(pointer n, K const& data)
{
  n->data(data);
  if (!n->is_root() && m_compare(n->parent()->data(), n->data()))
    {
      cut(n);
      add_root(n);
    }
  m_min = 0;
}

template <typename T, typename Comp> template <typename K> inline void fibonacci_heap<T, Comp>::change(pointer n, K const& data)
{
  T comp(n->data());
  comp = data;

  if (m_compare(n->data(), comp))
    increase(n, data);
  else
    decrease(n, data);
}

template <typename T, typename Comp> template <typename K> inline void fibonacci_heap<T, Comp>::change_top(K const& data)
{
  if (m_min == 0)
    find_min();
  change(m_min, data);
}

template <typename T, typename Comp> inline void fibonacci_heap<T, Comp>::remove(pointer n)
{
  if (n->is_root())
    m_roots[n->rank()] = 0;
  else
    cut(n);

  typename std::vector<node*>::const_iterator it = n->begin();
  typename std::vector<node*>::const_iterator end = n->end();
  for (it = n->begin(); it != end; ++it)
    add_root(*it);

  m_min = 0;
  delete n;
}

// --- implementation of basic heap interface for Fibonacci heaps --------------

template <typename T, typename Comp> inline T const& fibonacci_heap<T, Comp>::top() const
{
  if (m_min == 0)
    find_min();
  return m_min->data();
}

template <typename T, typename Comp> inline typename fibonacci_heap<T, Comp>::pointer fibonacci_heap<T, Comp>::push(T const& data)
{
  node* n = new node(data);
  ++m_size;
  add_root(n);

  m_min = 0;
  return n;
}

template <typename T, typename Comp> inline void fibonacci_heap<T, Comp>::pop()
{
  if (m_min == 0)
    find_min();

  node* del = m_min;
  m_roots[m_min->rank()] = 0;

  typename std::vector<node*>::const_iterator end = del->end();

  for (typename std::vector<node*>::const_iterator it = del->begin(); it != end; ++it)
    add_root(*it);
  --m_size;

  delete del;
  m_min = 0;
}

// -----------------------------------------------------------------------------

} // namespace boost

Beim kompilieren bekomme ich aber folgenden Fehler:

/fheap.cpp:27: error: expected initializer before ‘const’
/fheap.cpp:35: error: expected initializer before ‘const’
/fheap.cpp:56: error: expected initializer before ‘&’ token
/fheap.cpp:68: error: expected initializer before ‘fibonacci_heap_base’
/fheap.cpp:77: error: expected initializer before ‘fibonacci_heap_base’
/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::add_root(typename boost::fibonacci_heap_base<T>::node*)’:
/fheap.cpp:129: error: ‘m_roots’ was not declared in this scope
/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::find_min() const’:
/fheap.cpp:160: error: ‘m_size’ was not declared in this scope
/fheap.cpp:164: error: ‘m_roots’ was not declared in this scope
/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::cut(typename boost::fibonacci_heap_base<T>::node*)’:
/fheap.cpp:182: error: ‘m_roots’ was not declared in this scope
/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::decrease(typename boost::fibonacci_heap_base<T>::node*, const K&)’:
/fheap.cpp:203: error: ‘m_roots’ was not declared in this scope
/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::remove(typename boost::fibonacci_heap_base<T>::node*)’:
/fheap.cpp:249: error: ‘m_roots’ was not declared in this scope
/fheap.cpp: In member function ‘typename boost::fibonacci_heap_base<T>::node* boost::fibonacci_heap<T, Comp>::push(const T&)’:
/fheap.cpp:274: error: ‘m_size’ was not declared in this scope
/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::pop()’:
/fheap.cpp:287: error: ‘m_roots’ was not declared in this scope
/fheap.cpp:293: error: ‘m_size’ was not declared in this scope
make: *** [fheap.o] Fehler 1

Ich vermute, dass ein Fehler im Header vorliegt, aber leider kann ich ihn nicht finden.

Sieht einer von euch, wo das Problem ist?

grüße,

fr33way

[Bashar]

Fehlt vor fibonacci_heap_base<T>::node in Zeile 27 nicht ein typename ?

[fr33way]

du meinst fibonacci_heap_base<typename T>::node ?

das wirft nen fehler: /fheap.cpp:27: error: template argument 1 is invalid

[Bashar]

fr33way schrieb:

du meinst fibonacci_heap_base<typename T>::node ?

Nein, davor. Also

template <typename T> inline typename fibonacci_heap_base<T>::node const* fibonacci_heap_base<T>::iterator::find_root(typename std::vector<node*>::const_iterator it) const

[fr33way]

danke, das reduziert schon mal einen Teil der Fehlermeldungen.
Was jetzt bleibt sind die:

src/cex/pathfinder/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::add_root(typename boost::fibonacci_heap_base<T>::node*)’:
src/cex/pathfinder/fheap.cpp:129: error: ‘m_roots’ was not declared in this scope
src/cex/pathfinder/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::find_min() const’:
src/cex/pathfinder/fheap.cpp:160: error: ‘m_size’ was not declared in this scope
src/cex/pathfinder/fheap.cpp:164: error: ‘m_roots’ was not declared in this scope
src/cex/pathfinder/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::cut(typename boost::fibonacci_heap_base<T>::node*)’:
src/cex/pathfinder/fheap.cpp:182: error: ‘m_roots’ was not declared in this scope
src/cex/pathfinder/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::decrease(typename boost::fibonacci_heap_base<T>::node*, const K&)’:
src/cex/pathfinder/fheap.cpp:203: error: ‘m_roots’ was not declared in this scope
src/cex/pathfinder/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::remove(typename boost::fibonacci_heap_base<T>::node*)’:
src/cex/pathfinder/fheap.cpp:249: error: ‘m_roots’ was not declared in this scope
src/cex/pathfinder/fheap.cpp: In member function ‘typename boost::fibonacci_heap_base<T>::node* boost::fibonacci_heap<T, Comp>::push(const T&)’:
src/cex/pathfinder/fheap.cpp:274: error: ‘m_size’ was not declared in this scope
src/cex/pathfinder/fheap.cpp: In member function ‘void boost::fibonacci_heap<T, Comp>::pop()’:
src/cex/pathfinder/fheap.cpp:287: error: ‘m_roots’ was not declared in this scope
src/cex/pathfinder/fheap.cpp:293: error: ‘m_size’ was not declared in this scope
make: *** [fheap.o] Fehler 1

Aber was ich nicht ganz verstehe, denn über die friend angaben dürfte das doch gar nicht auftreten? (Bzw weil fibonacci_heap ja direkt von fibonacci_heap_base erbt)

gruß

[Michael E.]

IIRC musst du da explizit this-> schreiben, weil die Basisklasse eine Templateklasse ist.

[camper]

fibonacci_heap_base<T> ist eine abhängige Basis, die folglich bei der in der Templatedefinition von fibonacci_heap<T, Comp>::add_root nicht durchsucht werden kann.
m_roots ist aber kein abhängiger Name und wird folglich bereits bei der Templatedefinition gebunden. Abhilfe wird dadurch geschaffen, dass m_roots durch einen abhängigen Ausdruck ersetzt wird (14.6.2.2/3):
- durch Qualifizierung: fibonacci_heap_base<T>::m_roots, oder
- durch explizite Verwendung von this: this->m_roots

[fr33way]

hi,

danke! das hat das problem gelöst.

nun bleibe nur noch eine Kleinigkeit, das Programm kompiliert korrekt, aber beim linken kriege ich undefined references.

ich erzeuge ein Objekt per

boost::fibonacci_heap<Vertex<PTYPE>*, CompareDistance> remainingNodes;
remainingNodes.push(someNode);

Und im weiteren Programmverlauf erfolgen diverse weitere zugriffe

search.cpp:(.text+0xc95): undefined reference to `boost::fibonacci_heap<proj::Vertex<double>*, proj::CompareDistance>::push(proj::Vertex<double>* const&)'
search.cpp:(.text+0xcb1): undefined reference to `boost::fibonacci_heap<proj::Vertex<double>*, proj::CompareDistance>::top() const'
search.cpp:(.text+0xd07): undefined reference to `boost::fibonacci_heap<proj::Vertex<double>*, proj::CompareDistance>::pop()'
search.cpp:(.text+0x1b18): undefined reference to `boost::fibonacci_heap<proj::Vertex<double>*, proj::CompareDistance>::push(proj::Vertex<double>* const&)'
search.cpp:(.text+0x1e7e): undefined reference to `boost::fibonacci_heap_base<proj::Vertex<double>*>::~fibonacci_heap_base()'
search.cpp:(.text+0x2470): undefined reference to `boost::fibonacci_heap_base<proj::Vertex<double>*>::~fibonacci_heap_base()'
collect2: ld returned 1 exit status
make: *** [project] Fehler 1

weiterhin danke für eure hilfe

[Bashar]

Was für eine Ursache können denn diese Fehler haben? Der Code ist alt, aber älter als 2-Phase-Lookup sicher nicht, denn in der Parameterliste der ersten Methode (Zeile 27) schreibt er ja typename std::vector<node*>::const_iterator it . Hats da mal Änderungen gegeben?

[camper]

Templatedefinitionen nicht im Header platziert, dafür eine Menge überflüssige inlines.

[fr33way]

hat noch einer eine idee zu meinem linker problem?

Es sind ja lediglich Dateien die im cpp file definiert worden. ich nutze autotools zum erstellen eines Makefiles, in die Makefile.am habe ich meine neue cpp Datei eingetragen.

gruß

[seldon]

Das liegt, wie camper richtig bemerkt, stumpf daran, dass die gesamte Klassenvorlage dem Compiler bekannt sein muss, damit er sie für scc_cex::Vertex<double>* konkretisieren kann. Sofern du nicht auf explicit instantiation zurückgreifen willst, muss die gesamte Template in den Header; eine Aufspaltung in Header und Quellcodedatei, wie man sie andernfalls kennt, ist mit Templates nicht möglich.

[fr33way]

Hi,

danke, hatte leider die eine Antwort nicht so verstanden.

Das hat auf jeden Fall mein Problem behoben und die Sache läuft.

Also Danke für Eure Hilfe.

gruß