adjlist.hpp

Go to the documentation of this file.

#ifndef ADJLIST_H
#define ADJLIST_H

#include <vector>
#include <iostream>
using namespace std;

class AdjList {
private:
  vector<vector<int> > m_nodes;
  vector<bool> m_visited;
  typedef vector<vector<int> >::iterator nodeiter;
  typedef vector<bool>::iterator visititer;

public: 

  AdjList(int nodes):m_nodes(nodes),  m_visited(nodes)
  {
    for(visititer i = m_visited.begin(); i != m_visited.end();++i)
    {
      *i = false;
    }
    for(nodeiter i = m_nodes.begin(); i != m_nodes.end(); ++i)
    {
      (*i) = vector<int>();
    }
  }

  inline void 
  adjacent(int n1, int n2)
  {
    m_nodes[n1].push_back(n2);
    m_nodes[n2].push_back(n1);
  }

  inline void 
  visit(int node)
  {
    m_visited[node] = true;
  }
  
  inline 
  bool isVisited(int node) const
  {
    return m_visited[node];
  }
  
  int findNext(int node) const
  {
    for(unsigned int i = 0; i < m_nodes[node].size(); i++)
    {
      if(!m_visited[m_nodes[node][i]])
      {
        return m_nodes[node][i];
      }
    }
    return -1;
  }
  
  vector<int> findAllNext(int node) const
  {
    vector<int> ret = vector<int>();

    for(unsigned int i = 0; i < m_nodes[node].size(); i++)
    {
      if(!m_visited[m_nodes[node][i]] )
      {
        ret.push_back(m_nodes[node][i]);
      }
    }
    return ret;
    
  }

  int findFirst() const
  {
    for(unsigned int i = 0; i < m_nodes.size(); i++)
    {
      if(m_nodes[i].size() == 1) 
      {
        return i;
      }
    }
    return -1;
  }

  vector<int> findAllFirst() const
  {
    vector<int> ret;
    for(unsigned int i = 0; i < m_nodes.size(); i++)
    {
      if(m_nodes[i].size() == 1)
      {
        ret.push_back(i);
      }
    }
    return ret;
  }
          
  void print()
  {
    for(unsigned int i = 0; i < m_nodes.size(); i++)
    {
      cerr << " Node " << i << ":\t";
      for(unsigned int j = 0; j < m_nodes[i].size(); j++)
      {
        cerr << m_nodes[i][j] << " "; 
      }
      cerr << endl;
    }
  }
};

#endif