This question is connected with: Using boost connected components with cartesian points
I've made some changes in example to use cartesian points. Here is my current code:
using namespace boost;
typedef adjacency_list <vecS, vecS, undirectedS, cv::Point> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::vertices_size_type VertexIndex;
int main()
{
const int VERTEX_COUNT = 10;
Graph graph(VERTEX_COUNT);
std::vector<VertexIndex> rank(num_vertices(graph));
std::vector<Vertex> parent(num_vertices(graph));
typedef VertexIndex* Rank;
typedef Vertex* Parent;
disjoint_sets<Rank,Parent> ds(&rank[0], &parent[0]);
initialize_incremental_components(graph,ds);
incremental_components(graph,ds);
graph_traits<Graph>::edge_descriptor edge;
bool flag;
std::vector<Vertex> verticesVector;
//vector of points which creates graph
std::vector<cv::Point> points;
points.push_back(cv::Point(0,0));
points.push_back(cv::Point(1,1));
points.push_back(cv::Point(2,2));
points.push_back(cv::Point(3,1));
points.push_back(cv::Point(4,2));
points.push_back(cv::Point(0,2));
points.push_back(cv::Point(2,3));
points.push_back(cv::Point(3,3));
int i = 0;
for(std::vector<cv::Point>::iterator it = points.begin();
it !=points.end();it++, i++)
{
verticesVector.push_back(add_vertex(graph));
graph[i].x = (*it).x;
graph[i].y = (*it).y;
}
typedef component_index<VertexIndex> Components;
Components components(parent.begin(), parent.end());
BOOST_FOREACH(VertexIndex current_index, components)
{
std::cout<<"component "<<current_index<<" contains: ";
BOOST_FOREACH(VertexIndex child_index, components[current_index])
{
std::cout<<child_index<<" "<<" x = "<<graph[current_index].x<<";"<<graph[current_index].y<<"||";
}
std::cout<<std::endl;
}
boost::tie(edge,flag) = add_edge(verticesVector[0],verticesVector[1],graph);
ds.union_set(verticesVector[0],verticesVector[1]);
boost::tie(edge,flag) = add_edge(verticesVector[1],verticesVector[2],graph);
ds.union_set(verticesVector[1],verticesVector[2]);
boost::tie(edge,flag) = add_edge(verticesVector[2],verticesVector[3],graph);
ds.union_set(verticesVector[2],verticesVector[3]);
boost::tie(edge,flag) = add_edge(verticesVector[3],verticesVector[4],graph);
ds.union_set(verticesVector[3],verticesVector[4]);
boost::tie(edge,flag) = add_edge(verticesVector[1],verticesVector[5],graph);
ds.union_set(verticesVector[1],verticesVector[5]);
boost::tie(edge,flag) = add_edge(verticesVector[5],verticesVector[6],graph);
ds.union_set(verticesVector[5],verticesVector[6]);
boost::tie(edge,flag) = add_edge(verticesVector[6],verticesVector[7],graph);
ds.union_set(verticesVector[6],verticesVector[7]);
Components components2(parent.begin(), parent.end());
/*BOOST_FOREACH(Vertex current_vertex, vertices(graph))
{
std::cout<< "representative["<<current_vertex<<"] = "
<< ds.find_set(current_vertex)<<std::endl;
}
std::cout<<std::endl;*/
for(std::vector<Vertex>::iterator it = verticesVector.begin(); it != verticesVector.end(); it++)
{
std::cout<<"representative = "<<ds.find_set((*it))<<std::endl;
}
BOOST_FOREACH(VertexIndex current_index, components2)
{
std::cout<<"component "<<current_index<<" contains: ";
BOOST_FOREACH(VertexIndex child_index, components[current_index])
{
std::cout<<child_index<<" "<<" x,y = "<<graph[current_index].x<<";"<<graph[current_index].y<<"||";
}
std::cout<<std::endl;
}
//write_graphviz(std::cout, graph);
getchar();
return 0;
}
I'm getting exception when trying to union_set(): Access violation reading location... I can not figure out the reason. I've read all topics on boost lib, tried to search in docs.
I've figured it out thanks to this tutorial: Algorithm for selecting all edges and vertices connected to one vertex
The problems was:
Working code:
using namespace boost;
typedef adjacency_list <vecS, vecS, undirectedS, cv::Point> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::vertices_size_type VertexIndex;
int main()
{
Graph graph;
graph_traits<Graph>::edge_descriptor edge;
bool flag;
std::vector<Vertex> verticesVector;
Vertex verticesTable[8];
std::vector<cv::Point> points;
points.push_back(cv::Point(0,0));
points.push_back(cv::Point(1,1));
points.push_back(cv::Point(2,2));
points.push_back(cv::Point(3,1));
points.push_back(cv::Point(4,2));
points.push_back(cv::Point(0,2));
points.push_back(cv::Point(2,3));
points.push_back(cv::Point(3,3));
int i = 0;
for(std::vector<cv::Point>::iterator it = points.begin(); it != points.end(); it++, i++)
{
verticesTable[i] = add_vertex(graph);
graph[verticesTable[i]].x = (*it).x;
graph[verticesTable[i]].y = (*it).y;
}
std::vector<VertexIndex> rank(num_vertices(graph));
std::vector<Vertex> parent(num_vertices(graph));
typedef VertexIndex* Rank;
typedef Vertex* Parent;
disjoint_sets<Rank,Parent> ds(&rank[0], &parent[0]);
initialize_incremental_components(graph,ds);
incremental_components(graph,ds);
typedef component_index<VertexIndex> Components;
Components components(parent.begin(), parent.end());
Graph::vertex_iterator vertexIt, vertexEnd;
boost::tie(vertexIt,vertexEnd) = vertices(graph);
for(;vertexIt != vertexEnd; ++vertexIt)
{
Vertex a = *vertexIt;
cv::Point &b = graph[a];
std::cout<<"Point: "<<b.x<<";"<<b.y<<std::endl;
}
boost::tie(edge,flag) = add_edge(verticesTable[0],verticesTable[1],graph);
ds.union_set(verticesTable[0],verticesTable[1]);
boost::tie(edge,flag) = add_edge(verticesTable[1],verticesTable[2],graph);
ds.union_set(verticesTable[1],verticesTable[2]);
//boost::tie(edge,flag) = add_edge(verticesTable[2],verticesTable[3],graph);
//ds.union_set(verticesTable[2],verticesTable[3]);
boost::tie(edge,flag) = add_edge(verticesTable[3],verticesTable[4],graph);
ds.union_set(verticesTable[3],verticesTable[4]);
boost::tie(edge,flag) = add_edge(verticesTable[1],verticesTable[5],graph);
ds.union_set(verticesTable[1],verticesTable[5]);
boost::tie(edge,flag) = add_edge(verticesTable[5],verticesTable[6],graph);
ds.union_set(verticesTable[5],verticesTable[6]);
boost::tie(edge,flag) = add_edge(verticesTable[6],verticesTable[7],graph);
ds.union_set(verticesTable[6],verticesTable[7]);
BOOST_FOREACH(Vertex current_vertex, vertices(graph))
{
std::cout<< "representative["<<current_vertex<<"] = "
<< ds.find_set(current_vertex)<<std::endl;
}
std::cout<<std::endl;
Components components2(parent.begin(), parent.end());
BOOST_FOREACH(VertexIndex current_index, components2)
{
std::cout<<"component "<<current_index<<" contains: ";
BOOST_FOREACH(VertexIndex child_index, components2[current_index])
{
std::cout<<child_index<<" "<<" x,y = "<<graph[verticesTable[child_index]].x<<";"<<graph[verticesTable[child_index]].y<<"||";
}
std::cout<<std::endl;
}
//write_graphviz(std::cout, graph);
getchar();
return 0;
}
I'm still learning boost Graph so please correct my mistakes, make more elegant solutions. My conclusions also can be not exactly correct.