last day (14 days later) » 

3:28 PM
0
Q: Deep-copy constructor for a new graph

iteongI'm trying to access the edges_ inside my Node Struct, so I can do a for-loop to copy the edges over to a new graph object for my copy constructor. I'm getting the following error which confuses me when I try to access the edges_ in node. tests/Graph.tem:280:24: error: ‘struct std::pair<const s...

 
what is the type of Graph::nodes_? If it is a std::map<std::string, std::shared_ptr<Node>> as your error message suggests, node has type std::pair<std::string, std::shared_ptr<Node>>, so instead of node.edges_ you should use node.second->edges_.
 
std::map< N, std::shared_ptr<Node> > nodes_;
 
so for the first problem, you should replace for (auto edge: node.edges_) by for (auto edge: node.second->edges_).
 
Oh yes it's working! How about the second?
 
The second problem is more complicated: you need a local association map inside your constructor to store the connections between the nodes of g and the nodes of your copy.
 
3:28 PM
If I already got an bool addEdge(const N& src, const N& dst, const E& w); function, which adds a new edge src → dst with weight w. This function returns true if the edge is added and false if the edge (with weight w) already exists in the graph, would that help?
hi
First time I'm using chat lol
I already got an addEdge function, and would like to use it coz thats what I'm told can be used....
it is declared as: bool addEdge(const N& src, const N& dst, const E& w);
 
Hi
 
hi
 
First time for me too.
 
Where u from? =)
 
From France. Have you tried the answer ?
 
3:33 PM
It is highlighting the curly braces....
I'm from Sydney
Is the ... correct?
There is ... inside addEdge
 
yes, i have not looked at the source weight.
 
oh *associativeMap[&*sourceEdge->val_ at the ...?
Also, where does the curly bracket end here:
for (auto sourceEdge: node.second->edges_)
addEdge(*thisNode, *associativeMap[&*sourceEdge->dest], ...);
++thisIter;
 
The ... should be the weight of your source node; maybe (*sourceEdge)->Val_.
    for (auto sourceNode: g.nodes_) {
        Node* thisNode = &*thisIter->second;
        for (auto sourceEdge: sourceNode.second->edges_)
           addEdge(thisNode, associativeMap[&*sourceEdge->dest], ...);
        ++thisIter;
    }
 
template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g):
nodes_{g.nodes_}
{ std::map<Node*, Node*> associativeMap;
std::map<N, std::shared_ptr<Node>>::const_iterator;
thisIter(nodes_.begin()), sourceIter(g.nodes_.begin()), thisIterEnd(nodes_.end()), sourceIterEnd(g.nodes_.end());
for (; thisIter != thisIterEnd; ++thisIter) {
associativeMap.insert(std::make_pair(&*(sourceIter->second), &*(thisIter->second)));
++sourceIter;
}

thisIter = nodes_.begin();
for (auto sourceNode: g.nodes_) {
Like this?
template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g):
nodes_{g.nodes_}
{ std::map<Node*, Node*> associativeMap;
std::map<N, std::shared_ptr<Node>>::const_iterator;
thisIter(nodes_.begin()), sourceIter(g.nodes_.begin()), thisIterEnd(nodes_.end()), sourceIterEnd(g.nodes_.end());
for (; thisIter != thisIterEnd; ++thisIter) {
associativeMap.insert(std::make_pair(&*(sourceIter->second), &*(thisIter->second)));
++sourceIter;
}

thisIter = nodes_.begin();
for (auto sourceNode: g.nodes_) {
oops sorry
how does the code formatting work here in chat? -__
-__-
 
no problem. you just have an extra ; after std::map<N, std::shared_ptr<Node>>::const_iterator. For me, it should be close to the solution
 
3:46 PM
tests/Graph.tem: In copy constructor 'gdwg::Graph<N, E>::Graph(const gdwg::Graph<N, E>&)':
tests/Graph.tem:277:9: error: need 'typename' before 'std::map<N, std::shared_ptr<gdwg::Graph<N, E>::Node> >::const_iterator' because 'std::map<N, std::shared_ptr<gdwg::Graph<N, E>::Node> >' is a dependent scope
std::map<N, std::shared_ptr<Node>>::const_iterator
^
tests/Graph.tem:278:13: error: expected ';' before 'thisIter'
thisIter(nodes_.begin()), sourceIter(g.nodes_.begin()), thisIterEnd(nodes_.end()), sourceIterEnd(g.nodes_.end());
 
typename std::map<N, std::shared_ptr<Node>>::const_iterator
thisIter(nodes_.begin()), sourceIter(g.nodes_.begin()),
thisIterEnd(nodes_.end()), sourceIterEnd(g.nodes_.end());
Due to possible specialization, C++ don't know const_iterator is a type. That is why you should add typename before.
 
tests/Graph.tem: In instantiation of 'gdwg::Graph<N, E>::Graph(const gdwg::Graph<N, E>&) [with N = std::basic_string<char>; E = int]':
tests/test8c.cpp:23:20: required from here
tests/Graph.tem:291:46: error: no match for 'operator*' (operand type is 'std::weak_ptr<gdwg::Graph<std::basic_string<char>, int>::Node>')
addEdge(thisNode, associativeMap[&*sourceEdge->dest], (*sourceEdge)->Val_);
^
tests/Graph.tem:291:66: error: base operand of '->' has non-pointer type 'gdwg::Graph<std::basic_string<char>, int>::Edge'
U there?
 
Yes, no idea for the first error, I was looking at weak_ptr
 
must we use associative map? It looks so complex ...i thought we can just use addEdge simply lol.
 
Yes you should.
 
3:56 PM
what does it do?
 
Yes you have to: I should draw something but it makes the connection between the source nodes and the copy nodes.
 
hmm ok... ill google it later.... just wanna fix this stuff -_-
 
Without it, the targets of your new edges will be on your first graph.
Can you post your code: I will try to compile it.
 
oh... so the first graph will affect the copied graph?
like if the edges are deleted from first graph, the copied graph will also have its edges deleted?
template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g):
nodes_{g.nodes_}
{ std::map<Node*, Node*> associativeMap;

typename std::map<N, std::shared_ptr<Node>>::const_iterator
thisIter(nodes_.begin()), sourceIter(g.nodes_.begin()),
thisIterEnd(nodes_.end()), sourceIterEnd(g.nodes_.end());

for (; thisIter != thisIterEnd; ++thisIter) {
associativeMap.insert(std::make_pair(&*(sourceIter->second), &*(thisIter->second)));
++sourceIter;
}

thisIter = nodes_.begin();
for (auto sourceNode: g.nodes_) {
 
yes but with the header (graph classes) and the main function to test it.
 
4:01 PM
#ifndef _Graph_h
#define _Graph_h

#include <vector>
#include <algorithm>
#include <string>
#include <memory>
#include <iostream>
#include <exception>
#include <map>
#include <set>
#include <typeinfo>


namespace gdwg {

template <typename N, typename E> class Graph; // function prototype for Graph class
template <typename N, typename E> class Node_Iterator {

public:
typedef typename Graph<N, E>::Node Node;

typedef std::ptrdiff_t difference_type;
typedef std::forward_iterator_tag iterator_category;
const typedef N value_type;
const typedef N* pointer;
const typedef N& reference;

// operators for value and reference types
reference operator*() const;
pointer operator->() const;

// operators for pre and post increments
Graph(): nodes_{} {};


/* Copy and Move Constructors
* -------------------
* User-defined or compiler-synthesised copy and move constructors as required.
*/

// copy constructor
Graph(const Graph &g);
private:
std::map< N, std::shared_ptr<Node> > nodes_;



};

//---Static variable to check if mergeReplace is happening
static bool isMergeReplace_{false};

#include "Graph.tem" // definition and implementation of Node_Iterator, Edge_Iterator and Graph classes

}

#endif
This is the Graph.h file. The copy constructor is in a Graph.tem file.
 
Thanks. Answer in 8 minutes.
 
u just need to be able to compile it...
Coz otherwise the main test file needs all the rest of the other functions in .tem
I can try test it once there is no compiling error
 
4:14 PM
for (auto sourceNode: g.nodes_) {
Node* thisNode = &*thisIter->second;
for (auto sourceEdge: sourceNode.second->edges_)
addEdge(thisNode, associativeMap[&*sourceEdge->dest.lock()], sourceEdge->val_);
++thisIter;
}
With this code, the only error message I have is error: ‘addEdge’ was not declared in this scope.
 
ok let me try
tests/Graph.tem: In instantiation of 'gdwg::Graph<N, E>::Graph(const gdwg::Graph<N, E>&) [with N = std::basic_string<char>; E = int]':
tests/test8c.cpp:23:20: required from here
tests/Graph.tem:291:80: error: no matching function for call to 'gdwg::Graph<std::basic_string<char>, int>::addEdge(gdwg::Graph<std::basic_string<char>, int>::Node*&, gdwg::Graph<std::basic_string<char>, int>::Node*&, int&)'
addEdge(thisNode, associativeMap[&*sourceEdge->dest.lock()], sourceEdge->val_);
^
tests/Graph.tem:291:80: note: candidate is:
 
Thanks! I have it. No need for associative map since your addEdge method do its job. Answer in 2 minutes.
 
Thank god lol
 
template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g): nodes_{g.nodes_}
{ for (auto sourceNode: g.nodes_) {
for (auto sourceEdge: sourceNode.second->edges_)
addEdge(sourceNode.second->val_, sourceEdge->dest.lock()->val_, sourceEdge->val_);
}
}

It is your original solution. Sorry for the delay. I will explain it on StackOverflow.
The associative map would have been required if you had an std::vector<std::shared_pointer<Node> > instead of a std::map< N, std::shared_ptr<Node> > nodes_.
 
Oh ok
Hmmm
it compiles alright
but not sure why, the nodes order is messed up and it has the edges from the graph object it copied from after one of the nodes is deleted
i wonder if it is this copy constructor that has problem or my addEdge
or some other problem
This is the test solution:
original graph
a
d
c
b
Edges attached to Node b
a 3
d 4
a 5
original graph after delete
c
d
b
Edges attached to Node b
d 4
copied graph after delete in other graph
a
d
c
b
Edges attached to Node b
a 3
d 4
a 5
copied graph after other graph is deleted
a
d
c
b
This is what I got after the original graph after delete:
original graph after delete
c
d
b
Edges attached to Node b
d 4
copied graph after delete in other graph
a
c
d
b
Edges attached to Node b
d 4
copied graph after other graph is deleted
a
c
d
b
as u can see, the edges attached to the node b which is part of the copied graph, is following the old graph's edges which is weird
This is the test .cpp main file:
do u think the problem is related to the copy constructor?
 
4:34 PM
I don't exactly see the problem. The next step is to use the debugger. I am not sure of the first argument of addEdge. It could be the orig field of it. It could be the addEdge method.
 
oh ok...
probably it's addEdge right?
coz like the copy constructor seems ok to me
 
template <typename N, typename E>
Graph<N, E>::Graph(const Graph &g): nodes_{g.nodes_}
{ for (auto sourceNode: g.nodes_) {
for (auto sourceEdge: sourceNode.second->edges_)
addEdge(sourceEdge->orig.lock()->val_ /*sourceNode.second->val_ */, sourceEdge->dest.lock()->val_, sourceEdge->val_);
}
}

This version should have same problems. If it has, it should be the addEdge method.
 
yeah same issue
and also, the ordering seems wrong.... the original graph when copied, the ordering of nodes when printing is a d c b, but the copied graph prints a c d b.
this only happens after deleting one node
if never delete, the copied graph object's ordering of printing nodes and edges are the same as the original's.
maybe my deleteNode method got something wrong too?
 
You have to define the ordering on shared_ptr<Node>. By default it is pointer comparison.
 
oh... is that why after deleting a node, then it prints out of order?
 
4:43 PM
My previous remark is wrong. your map is on N. Can I have your addEdge method and test.cpp, to also debug it ?
 
Sure
template <typename N, typename E>
bool Graph<N, E>::addEdge(const N& orig, const N& dest, const E& val) {
// check that both orig and dest exist
auto findOrig = nodes_.find(orig);
if (findOrig == nodes_.end()) throw std::runtime_error("addEdge: origin DNE");
auto findDest = nodes_.find(dest);
if (findDest == nodes_.end()) throw std::runtime_error("addEdge: dest DNE");


auto findEdge = std::find_if(findOrig->second->edges_.begin(),findOrig->second->edges_.end(),
[val,dest] (const std::shared_ptr<Edge>& e) {
test file:
// test 8: tests copy construction

#include "Graph.h"

int main() {
auto gHeap = new gdwg::Graph<std::string,int>{};

// add this data into the graph
gHeap->addNode("a");
gHeap->addNode("b");
gHeap->addNode("c");
gHeap->addNode("d");

gHeap->addEdge("b","a",3);
gHeap->addEdge("b","a",5);
gHeap->addEdge("b","d",4);
gHeap->addEdge("c","a",3);
//gHeap->addEdge("a","b",1); // need to delete (to test outgoing edge from deleted node)
std::cout << "original graph" << std::endl;
gHeap->printNodes();
gHeap->printEdges("b");
 
4:55 PM
Just 5 minutes to add the missing methods.
 
ok sure
 
original graph
a
b
c
d
"b": 3 5 4
original graph after delete
b
c
d
"b": 3 5 4
copied graph after delete in other graph
a
b
c
d
"b": 3 5 4
copied graph after other graph is deleted
a
b
c
d
Here is my output. The copy graph has same ordering than the original graph.
 
yeah did u delete a node in the test?
coz everything is ok when a node isn't deleted.
gHeap->deleteNode("a");
this is the one that cause the problem
oh u did delete didn't u
the node was deleted
but the edges printed out for the original graph should be just 4, instead of 3 5 4
but the copied graph is correct
 
Yes the second print is after the node is deleted. I have not your printEdges method, not your remove method. Mine does not update the edges.
 
5:10 PM
oh ok
cool
ill see if this fixes it
asking u to look at the edges will be a bit too much lol. U alr look at so much
so u changed the addEdge method and also some of the copy constructor?
 
Here are my methods:
   void printNodes() const
      {  for (auto node: nodes_)
            std::cout << node.first << std::endl;
      }
   void printEdges(const N& node) const
      {  std::cout << '"' << node << "\": ";
         for (auto edge : nodes_.find(node)->second->edges_) {
            if (!edge->dest.expired() && !edge->orig.expired()) {
               std::cout << edge->val_ << ' ';
               std::cout << edge->dest.lock()->val_ << ' ';
            }
         }
         std::cout << std::endl;
      }
 
so u just changed this? None of the addEdge?
 
I have not changed addEdge, nor the copy constructor.
 
oh really? ok
 
I am on linux and I compile with g++. I don't understand why the Nodes' ordering of your copy is different. It is based on std::string ordering.
 
5:20 PM
template <typename N, typename E>
void Graph<N, E>::printNodes() const {
for (auto it = begin(); it != end(); ++it ) {
std::cout << *it << std::endl;
}
}
This is my printNodes method. Could it be the issue?
 
No. Maybe your deleteNode has issues.
 
Prints the data stored in all the nodes in the graph, with one node per line, starting from the node with the
* smallest outdegree to the node with the largest. If two nodes have the same edge count, then the one with the
* smaller node value determined by the < operator is printed first.
this is what I need for the printNodes()
i think I did not compare during the printing
maybe that is why the ordering is not the same as the solution, which has "a d c b" printed out for the node
 
but you are printing w.r.t. the ordering in nodes_ = "a" "b" "c" "d" in all cases.
 
yeah i think i should be printing a d c b, coz according to this specs, a and d should be first, coz they have 0 out degree, followed by c and b, coz c has 1 out degree and b has 2 outdegree
simple iteration will either just print according to the order it's added to the container, or lexicographically
am I correct?
 
Yes I think you are right.
 
5:28 PM
Yeah I think I missed that...
I just did a normal iteration that is why it was maybe different when copied, and also when iterating through the original when one node is deleted
even if one node is deleted, if there is a comparator inside the printNodes() checking the out degree of each node, then the ordering will be consistent.
 
I have not seen the code behind your "normal iteration".
 
It's okay, I think I sort of figured out from talking to you ha....
the normal iteration is what we have now isn't it
as in code wise
 
I let you finish. From my side, when I compile, I get the error: no begin() method in Graph.
 
Yeah no worries... u already spent so much time helping me.. =) U should go take a breather....
Update the solution and Ill tick it as the answer....
go have a rest* i mean.
 
Yes it should be late in Sidney.
 
5:42 PM
it's 3.41 am. What time is it in France? =)
 
19:43 pm. It is better.
 
7.43 pm you mean.
You spent more than 2 hours helping me lol. Thats amazing. I always wonder how some people are so helpful =P
 
No problem. I like code and I have learned many things about weak_ptr.
 
Hahaha ok =D Cheers!
Have a good night Franck. =)
Feel Free to add me on Facebook if u wanna keep in touch: Ivan Teong
 
Have a good night too. Unfortunately I am not on Facebook ; Facebook takes too much time ;-).
 
5:53 PM
Sure no worries =)
 

last day (14 days later) »