shared pointers - undirected graphs..

[DrJones]

Hi guys.. i am trying to build an undirected graph, at which i want to try to use Smart pointer, as it seems smarter than the "normal pointer".

But i am a bit unsure whether i should create an edge class which contains all neighbors for each vertex, or the smart pointer (shared pointer) are able to contain that information (if so hallelujah).

[MiiNiPaa]

Smart pointers are similar to normal pointers with added RAII capabilities (ownership). That is all to them. If you cannot make something work using raw pointers, smart pointers will not allow you to make it happen by themselves.

[DrJones]

So to sum it up, I need to make an edge class, which contains each go there pointers?...

so my edge class would be some thing like this

class Edge {
public:
    Vertex Start;
    Vertex End;
public:
    Edge(Vertex start, Vertex end);
};

and 

class Vertex {
    int x;
    int y;
    char element;
    int num_Edges;
    boost::shared_ptr<Vertex> pointer;
public:
    Vertex();
    Vertex(int x, int y, char element);
    boost::shared_ptr<Vertex> getVertex(){
        return pointer;
    }
... (get functions)
}


Edge::Edge(Vertex start, Vertex end)
{
   if (abs(start.getX() - end.getX()) == 0 || abs(start.getX() - end.getX()) == 1 || abs(start.getY() - end.getY()) == 0 || abs(start.getY() - end.getY()) == 1 )
{
    Cout << "neighbours found" << endl; 
    Start = start;
    End = end;
}

}

if so.. it doesn't work.. i can't include my edge.h in my vertex.h... I think, it thinks that something is circular dependent..!!?

[MiiNiPaa]

You have severe problems with your graph representation:
1) Edge owns two Vertex objects. This means that
1.a) Each edge has two unique vertices (it is impossible for two edges to link to same vertex)
1.b) Vertex should be defined before Edge.
2) Everything is passed by value, making many copies. This is probably unintended.

Naive graph representation rarely works. Use data structure line Adjancncy matrix/list http://www.geeksforgeeks.org/graph-and-its-representations/

Or use boost::adjacency_list
http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/adjacency_list.html
http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/using_adjacency_list.html

[DrJones]

I kinda see the issue, but at the same time not..

I start by creating all vertex object, which is saved in vector which the class graph contains ..

but yeah.. from there to create the edges, between the vertices is where i am stuck.

[MiiNiPaa]

Here is quick example of representing graph: http://coliru.stacked-crooked.com/a/03522937ddb6d843

And another one using boost: http://coliru.stacked-crooked.com/a/9aee6b9aaaad5ecc

[DrJones]

your boost implementation seems interesting..As i can see you already provide it the the edges, how would you find the edges in my case.. I have a vector of vertices.

[MiiNiPaa]

Firs of all, before building your graph you should prepare a list of vertices (already done) and list of edges. You need to make that list beforehand (simple "which points are closer than certain distance" algorithm will suffice)

Example: http://coliru.stacked-crooked.com/a/14e671662a8d5b7e

[DrJones]

I manages to create a list of vertices and list containing edges(from,to) which can be seen here

class Vertex {
    int x;
    int y;
    char element;
    int num_Edges;
public:
    Vertex();
    Vertex(int x, int y, char element);
    int getX(){
        return x;
    }
    int getY(){
        return y;
    }
    char getElement()
    {
        return element;
    }
    int getNumEdges(){
        return num_Edges;
    }
};

using grapht = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
    Vertex>;
    vector<Vertex> vertices;
    vector<pair<Vertex, Vertex>> edges;
    int col = map.getCol();
    int row = map.getRow();
    for(int y = 0; y < col; y++){
        for (int x = 0; x < row; x++) {
            char temp = map.getChar(x, y);
            if (isitTrue(temp)) {
                cout << "possible vertex found" << endl;
                vertices.emplace_back(Vertex(x,y,temp));
                if (x < row)
                {
                    if (isitTrue(map.getChar(x+1,y))) {
                        cout << "edge found - 1" << endl;
                        edges.emplace_back(Vertex(x, y,temp),Vertex(x+1, y,map.getChar(x+1, y)));
                    }
                }
                if (x >= 0)
                {
                    if (isitTrue(map.getChar(x-1,y))) {
                        cout << "edge found - 2" << endl;
                        edges.emplace_back(Vertex(x, y,temp),Vertex(x-1, y,map.getChar(x-1, y)));
                    }
                    
                }
                if (y >= 0)
                {
                    if (isitTrue(map.getChar(x,y-1))) {
                        cout << "edge found - 3" << endl;
                        edges.emplace_back(Vertex(x, y,temp),Vertex(x, y-1,map.getChar(x, y-1)));
                    }
                    
                }
                if (y < col)
                {
                    if (isitTrue(map.getChar(x,y+1))) {
                        cout << "edge found - 4" << endl;
                        edges.emplace_back(Vertex(x, y,temp),Vertex(x, y+1,map.getChar(x, y+1)));
                    }
                }
            }
        }
    }
    cout << edges.size() << endl;
    grapht graph(edges.begin(), edges.end(),edges.size());
    std::cout << "Hello, World!\n";

Problem is though , when i call grapht graph(edges.begin(), edges.end(),edges.size());

It gives me an error stating i cannot add_edge.

[MiiNiPaa]

An edge is a pair of numbers {x, y} denoting that edge is connecting vertices number x and y.

Also adjacency list constructor takes a pair of edge iterators and number of vertices, not edges. Note that it will create vertices without data. If you want to add vertices with data, create empty graph and add vertices manually. Look at my previous code.

[DrJones]

Hmm.. I think it makes sense..
The edges iterate the vertex vector, and if first element is a neighbor to the 4 an pair<1,4> will be created indicating vertex at position 1 and 4 are connected.

[DrJones]

Would you be able to move from one vertex -> vertex..
I should be possible using boost::adjacent_vertice, but cannot see how i should as am not quite sure of its type.. I can only access first and second, which make me think its a pair, but it capable of outputting more than 2 adjacent vertices for one vertex.. so that can't be it..

[MiiNiPaa]

I can only access first and second, which make me think its a pair

It is a pair of iterator denoting beginning and end of range as per usual STL style.

Look at part of my code:

auto adj_vert = boost::adjacent_vertices(*it, graph);
for(auto v = adj_vert.first; v != adj_vert.second; ++v)
	std::cout << *v << ' ';

Here I getting a list of adjanced vertices and loop through it. I output it here, but you can use it as index to get vertex itself and do anything you like with it.