old_graph.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2013:  G-CSC, Goethe University Frankfurt
 * Author: Martin Rupp
 * 
 * This file is part of UG4.
 * 
 * UG4 is free software: you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License version 3 (as published by the
 * Free Software Foundation) with the following additional attribution
 * requirements (according to LGPL/GPL v3 §7):
 * 
 * (1) The following notice must be displayed in the Appropriate Legal Notices
 * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
 * 
 * (2) The following notice must be displayed at a prominent place in the
 * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
 * 
 * (3) The following bibliography is recommended for citation and must be
 * preserved in all covered files:
 * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
 *   parallel geometric multigrid solver on hierarchically distributed grids.
 *   Computing and visualization in science 16, 4 (2013), 151-164"
 * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
 *   flexible software system for simulating pde based models on high performance
 *   computers. Computing and visualization in science 16, 4 (2013), 165-179"
 * 
 * This program 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.
 */
 
#ifndef __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__
#define __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__
 
#include <fstream>
#include <algorithm> // for lower_bound
#include <vector>
#include "lib_algebra/common/stl_debug.h"
 
#include "common/assert.h"
#include "common/log.h"
 
 
 
namespace ug{
class cgraph
{
public:
  typedef stdvector<size_t>::const_iterator const_row_iterator;
  typedef stdvector<size_t>::iterator row_iterator;
public:
  cgraph()
  {
  }
  
  cgraph(size_t n) : m_data(n)
  {
    for(size_t i=0; i<m_data.size(); ++i)
      m_data[i].resize(0);
 
#ifdef FORCE_CREATION
    FORCE_CREATION { print(); pr(0);} 
#endif
  }
  
  void resize(size_t n)
  {
    m_data.resize(n);
    for(size_t i=0; i<m_data.size(); ++i)
      m_data[i].resize(0);
  }
 
  ~cgraph()
  {
    // destructors of std::vector are getting called
  }
 
  size_t num_connections(size_t node) const
  {
    size_check(node);
    return m_data[node].size() ;
  }
 
  bool is_isolated(size_t i) const
  {
    size_check(i);
    return num_connections(i)==0 ||
        (num_connections(i)==1 && m_data[i][0] == i);
  }
 
  bool has_connection(size_t from, size_t to) const
  {
    size_check(from, to);
    return binary_search(begin_row(from), end_row(from), to);
  }
 
  void set_connection(size_t from, size_t to)
  {
    size_check(from, to);
    stdvector<size_t>::iterator it = std::lower_bound(begin_row(from), end_row(from), to);
    if(it == m_data[from].end())
      m_data[from].push_back(to);
    else if((*it) != to)
      m_data[from].insert(it, to);
  }
 
  row_iterator begin_row(size_t row)
  {
    size_check(row);
    return m_data[row].begin();
  }
 
  row_iterator end_row(size_t row)
  {
    size_check(row);
    return m_data[row].end();
  }
 
  const_row_iterator begin_row(size_t row) const
  {
    size_check(row);
    return m_data[row].begin();
  }
 
  const_row_iterator end_row(size_t row) const
  {
    size_check(row);
    return m_data[row].end();
  }
 
  void transpose()
  {
    cgraph G;
    G.set_as_transpose_of(*this);
    swap(m_data, G.m_data);
  }
  
  void set_as_transpose_of(const cgraph &other)
  {
    stdvector<size_t> rowSize(other.size());
    for(size_t i=0; i<other.size(); i++) rowSize[i] = 0;
 
    for(size_t i=0; i<other.size(); i++)
    {
      for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
        rowSize[(*it)]++;
    }
    
    m_data.resize(other.size());
    for(size_t i=0; i<other.size(); i++)
    {
      m_data[i].clear();
      m_data[i].reserve(rowSize[i]);
    }
 
    for(size_t i=0; i < other.size(); i++)
      for(const_row_iterator it = other.begin_row(i); it != other.end_row(i); ++it)
      {
        size_t from = (*it);
        size_t to = i;
        m_data[from].push_back(to);
      }
  }
    
  
  size_t size() const { return m_data.size(); }
  
public:
  // print functions
 
  void pr(size_t i) const
  {
    std::cout << "graph row " << i << ", length " << num_connections(i) << ":" << std::endl;
    for(const_row_iterator it = begin_row(i); it != end_row(i); ++it)
      std::cout << (*it) << " ";
    std::cout << std::endl;
    std::cout.flush();
  }
  void print() const
  {
    std::cout << *this << std::endl;
  }
 
  friend std::ostream &operator << (std::ostream &out, const cgraph &g)
  {
    std::cout << "============= graph ================ " << std::endl;
    for(size_t i=0; i<g.size(); ++i)
    {
      out << "[" << i << "]:  ";
      for(const_row_iterator it = g.begin_row(i); it != g.end_row(i); ++it)
        out << (*it) << " ";
      out << std::endl;
    }
    out.flush();
    return out;
  }
 
  inline void size_check(size_t i) const
  {
    UG_ASSERT(i < m_data.size(), "graph contains " << m_data.size() << " nodes, but trying to access node " << i);
  }
  inline void size_check(size_t a, size_t b) const
  {
    UG_ASSERT(a < m_data.size() || b < m_data.size(), "graph contains " << m_data.size() << " nodes, but trying to access nodes " << a << " and " << b);
  }
 
protected:
  stdvector<stdvector<size_t> > m_data;
};
 
 
} // namespace ug
 
#endif // __H__UG__LIB_DISC__AMG_SOLVER__GRAPH_H__