Fraxinus  17.12-rc3
An IGT application
adjlist.hpp
Go to the documentation of this file.
1 #ifndef ADJLIST_H
2 #define ADJLIST_H
3 
4 #include <vector>
5 #include <iostream>
6 using namespace std;
7 
11 class AdjList {
12 private:
14  vector<vector<int> > m_nodes;
16  vector<bool> m_visited;
17  typedef vector<vector<int> >::iterator nodeiter;
18  typedef vector<bool>::iterator visititer;
19 
20 public:
21 
27  AdjList(int nodes):m_nodes(nodes), m_visited(nodes)
28  {
29  for(visititer i = m_visited.begin(); i != m_visited.end();++i)
30  {
31  *i = false;
32  }
33  for(nodeiter i = m_nodes.begin(); i != m_nodes.end(); ++i)
34  {
35  (*i) = vector<int>();
36  }
37  }
38 
44  inline void
45  adjacent(int n1, int n2)
46  {
47  m_nodes[n1].push_back(n2);
48  m_nodes[n2].push_back(n1);
49  }
50 
55  inline void
56  visit(int node)
57  {
58  m_visited[node] = true;
59  }
60 
66  inline
67  bool isVisited(int node) const
68  {
69  return m_visited[node];
70  }
71 
77  int findNext(int node) const
78  {
79  for(unsigned int i = 0; i < m_nodes[node].size(); i++)
80  {
81  if(!m_visited[m_nodes[node][i]])
82  {
83  return m_nodes[node][i];
84  }
85  }
86  return -1;
87  }
88 
94  vector<int> findAllNext(int node) const
95  {
96  vector<int> ret = vector<int>();
97 
98  for(unsigned int i = 0; i < m_nodes[node].size(); i++)
99  {
100  if(!m_visited[m_nodes[node][i]] )
101  {
102  ret.push_back(m_nodes[node][i]);
103  }
104  }
105  return ret;
106 
107  }
108 
113  int findFirst() const
114  {
115  for(unsigned int i = 0; i < m_nodes.size(); i++)
116  {
117  if(m_nodes[i].size() == 1)
118  {
119  return i;
120  }
121  }
122  return -1;
123  }
124 
129  vector<int> findAllFirst() const
130  {
131  vector<int> ret;
132  for(unsigned int i = 0; i < m_nodes.size(); i++)
133  {
134  if(m_nodes[i].size() == 1)
135  {
136  ret.push_back(i);
137  }
138  }
139  return ret;
140  }
141 
145  void print()
146  {
147  for(unsigned int i = 0; i < m_nodes.size(); i++)
148  {
149  cerr << " Node " << i << ":\t";
150  for(unsigned int j = 0; j < m_nodes[i].size(); j++)
151  {
152  cerr << m_nodes[i][j] << " ";
153  }
154  cerr << endl;
155  }
156  }
157 };
158 
159 #endif
vector< int > findAllFirst() const
Definition: adjlist.hpp:129
void print()
Definition: adjlist.hpp:145
void adjacent(int n1, int n2)
Definition: adjlist.hpp:45
int findNext(int node) const
Definition: adjlist.hpp:77
AdjList(int nodes)
Definition: adjlist.hpp:27
bool isVisited(int node) const
Definition: adjlist.hpp:67
void visit(int node)
Definition: adjlist.hpp:56
vector< int > findAllNext(int node) const
Definition: adjlist.hpp:94
int findFirst() const
Definition: adjlist.hpp:113