Graph Class Reference

#include <Graph.hpp>

Public Member Functions
	Graph ()
	~Graph ()
	Graph (const int &npt, const int &nconnect, const std::vector< int > &connect_list)
void	build_path ()
std::vector< bool >	build_cycle ()
const int &	getNbConnectedComponents () const
const std::vector< std::vector< int > > &	getPath () const
const int &	getTotalSize () const
const std::vector< std::vector< int > > &	getAdjList () const
void	print () const

Private Member Functions
std::vector< int >	dfs (int p0, std::vector< int > &)

Private Attributes
int	m_npt
int	m_nconnect
int	m_nb_connected_components
int	m_total_size
std::vector< std::vector< int > >	m_adj_list
std::vector< std::vector< int > >	m_path_diag
std::vector< std::vector< int > >	m_path
std::vector< int >	m_degree
std::vector< int >	m_color

Detailed Description

Definition at line 37 of file Graph.hpp.

Constructor & Destructor Documentation

Graph() [1/2]

Graph::Graph ( )

inline

Definition at line 40 of file Graph.hpp.

{};

~Graph()

Graph::~Graph ( )

inline

Definition at line 42 of file Graph.hpp.

{};

Graph() [2/2]

Graph::Graph	(	const int &	npt,
		const int &	nconnect,
		const std::vector< int > &	connect_list )

Member Function Documentation

build_cycle()

vector< bool > Graph::build_cycle

(

)

Definition at line 108 of file Graph.cpp.

{
  vector<bool> res(m_nb_connected_components, false);
  for (int iconnect(0) ; iconnect < m_nb_connected_components ; ++iconnect) {
    vector<int> degree;
    for (int i(0) ; i < m_path.at(iconnect).size() ; ++i) {
      degree.push_back(m_degree.at(m_path.at(iconnect).at(i)));
    }
    vector<int>::iterator max_it, min_it;
    max_it = max_element(degree.begin(), degree.end());
    min_it = min_element(degree.begin(), degree.end());
    if (*max_it == 2 && *min_it == 2) {
      vector<int> path_new;
      int s0 = m_path.at(iconnect).at(0);
      int sinit = s0;
      int s1, s2;
      s1 = m_adj_list.at(s0).at(0);
      bool ok = true;
      while (ok) {
    path_new.push_back(s0);
    if ((s2 = m_adj_list.at(s1).at(0)) != s0) {
    } else {
      s2 = m_adj_list.at(s1).at(1);
    }
    ok = (path_new.size() != m_path.at(iconnect).size());
    if (!ok && s1 == sinit) {
      res.at(iconnect) = true;
    }
    s0 = s1;
    s1 = s2;
      }
      m_path.at(iconnect) = path_new;
    }
  }
  return res;
}

build_path()

void Graph::build_path

(

)

Definition at line 74 of file Graph.cpp.

                       {
  m_nb_connected_components = 0;
  bool ok = true;
  int s0 = 0;
  while (ok) {
    m_nb_connected_components++;
    vector<int> path;
    path.reserve(m_npt);
    m_path_diag.push_back(dfs(s0, path));
    m_path.push_back(path);
    vector<int>::iterator iter;
    ok = (iter = find(m_color.begin(), m_color.end(), 0)) != m_color.end();
    if (ok) {
      s0 = distance(m_color.begin(), iter);
    }
  }
 
  m_total_size = 0;
  for (int i_connect(0) ; i_connect < m_nb_connected_components ; ++i_connect) {
    // find seed
    vector<int>::iterator iter(find(m_path_diag.at(i_connect).begin(), m_path_diag.at(i_connect).end(), -1));
    if (iter != m_path_diag.at(i_connect).end()) {
      int s0 = distance(m_path_diag.at(i_connect).begin(), iter);
      vector<vector<int>> inver(m_npt, vector<int>());
      for (int ipt(0) ; ipt < m_npt ; ipt++) {
    if (m_path_diag.at(i_connect).at(ipt) >= 0) {
      inver.at(m_path_diag.at(i_connect).at(ipt)).push_back(ipt);
    }
      }
    }
    m_total_size += m_path.at(i_connect).size();
  }
}

dfs()

vector< int > Graph::dfs ( int p0, std::vector< int > &  )

private

Definition at line 45 of file Graph.cpp.

                                                {
  vector<int> res(m_npt, -2);
  // color the points 0: white, 1: gray, 2: black
  m_color.resize(m_npt, 0);
  vector<int> p;
  p.push_back(p0);
  path.push_back(p0);
  m_color.at(p0) = 1;
  res.at(p0) = -1;
  bool ok = true;
  while (ok) {
    int si = *(p.end()-1);
    vector<int>::const_iterator iter = 
      find_if(m_adj_list.at(si).begin(), m_adj_list.at(si).end(), [this](const int& ii) {return (m_color.at(ii) == 0);});
    if (iter != m_adj_list.at(si).end()) {
      int sj = *iter;
      p.push_back(sj);
      m_color.at(sj) = 1;
      path.push_back(sj);
      res.at(sj) = si;
    } else {
      m_color.at(si) = 2;
      p.pop_back();
    }
    ok = !(p.empty());
  }
  return res;
}

getAdjList()

const std::vector< std::vector< int > > & Graph::getAdjList ( ) const

inline

Definition at line 52 of file Graph.hpp.

{return m_adj_list;};

getNbConnectedComponents()

const int & Graph::getNbConnectedComponents ( ) const

inline

Definition at line 49 of file Graph.hpp.

{return m_nb_connected_components;}

getPath()

const std::vector< std::vector< int > > & Graph::getPath ( ) const

inline

Definition at line 50 of file Graph.hpp.

{return m_path;}

getTotalSize()

const int & Graph::getTotalSize ( ) const

inline

Definition at line 51 of file Graph.hpp.

{return m_total_size;};

print()

void Graph::print

(

)

const

Definition at line 145 of file Graph.cpp.

                        {
  cout << "Number of points: " << m_npt << endl;
  cout << "Number of edges: " << m_nconnect << endl;
  cout << "Number of connected components: " << m_nb_connected_components << endl;
  for (int i(0) ; i < m_nb_connected_components ; ++i) {
    cout << "Component " << i << endl;
    cout << "\t";
    for (int j(0) ; j < m_path.at(i).size() ; j++) {
      cout << m_path.at(i).at(j) << " " ;
    }
    cout << endl;
  }
}

Field Documentation

m_adj_list

std::vector<std::vector<int> > Graph::m_adj_list

private

Definition at line 59 of file Graph.hpp.

m_color

std::vector<int> Graph::m_color

private

Definition at line 61 of file Graph.hpp.

m_degree

std::vector<int> Graph::m_degree

private

Definition at line 60 of file Graph.hpp.

m_nb_connected_components

int Graph::m_nb_connected_components

private

Definition at line 57 of file Graph.hpp.

m_nconnect

int Graph::m_nconnect

private

Definition at line 56 of file Graph.hpp.

m_npt

int Graph::m_npt

private

Definition at line 55 of file Graph.hpp.

m_path

std::vector<std::vector<int> > Graph::m_path

private

Definition at line 59 of file Graph.hpp.

m_path_diag

std::vector<std::vector<int> > Graph::m_path_diag

private

Definition at line 59 of file Graph.hpp.

m_total_size

int Graph::m_total_size

private

Definition at line 58 of file Graph.hpp.

---

The documentation for this class was generated from the following files:

• common_source/tools/graphs/Graph.hpp
• common_source/tools/graphs/Graph.cpp