Factory for constructing directed graphs in C++

up vote
4
down vote

favorite

I want to implement a directed graph which has 3 main kind of edges:

self referencing edges

non directional edges between two nodes

directional edges between two nodes

Three-node graph. A has a self-edge, a bidirectional edge with B, and a unidirectional edge to C.

Also I want to be able to do global operations on the graph, like e.g. counting or removing all edges fulfilling certain criteria.

The easiest program structure I came up with is:

#include <unordered_set>

using namespace std;

struct Edge;

struct Node

 Node(std::string name):name(name)
 string name;
 std::unordered_set<Edge*> edges;
;

struct Edge

 Edge(Node * node1): node1(node1)
 double weight;
 Node * node1;
;

struct EdgeBetweenTwoNodes: public Edge

 EdgeBetweenTwoNodes(Node * node1, Node * node2 ): Edge(node1), node2(node2)
 Node * node2;
;

struct DirectionalEdge: public EdgeBetweenTwoNodes

 DirectionalEdge(Node * node1, Node * node2, bool direction ): EdgeBetweenTwoNodes(node1,node2), direction(direction)
 bool direction;
;

struct EdgesContainer

 std::unordered_set<Edge*> all_edges;

 void register_new_edge(Edge * edge)
 
 all_edges.insert(edge);
 

 //do all kind of manipulations on all edges of a cetain type...
;


struct EdgeFactory

 EdgeFactory()

 void create_edge(Node* node1,EdgesContainer & edge_container)
 
 Edge * edge = new Edge(node1);
 node1->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, EdgesContainer & edge_container)
 
 EdgeBetweenTwoNodes * edge = new EdgeBetweenTwoNodes(node1,node2);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, bool direction, EdgesContainer & edge_container)
 
 DirectionalEdge * edge = new DirectionalEdge(node1,node2,direction);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 
;


int main()

 Node * A = new Node("A");
 Node * B= new Node("B");
 Node * C= new Node("C");

 EdgesContainer edges;

 EdgeFactory edge_factory;
 edge_factory.create_edge(A,edges);
 edge_factory.create_edge(A,B,edges);
 edge_factory.create_edge(A,C,1,edges);

 return 0;

What do you think about it? Is this the correct use of a so called "Factory?"

edited 12 mins ago

200_success

125k14145406

asked 7 hours ago

newandlost

1243

New contributor

1

Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
â€“Â Mast
3 hours ago

1

Can I add more information about the classes s.t. the use-case is clearer?
â€“Â newandlost
2 hours ago

1

As long as it doesn't invalidate the existing answer.
â€“Â Mast
2 hours ago

add a commentÂ |Â

up vote
4
down vote

favorite

I want to implement a directed graph which has 3 main kind of edges:

self referencing edges

non directional edges between two nodes

directional edges between two nodes

Three-node graph. A has a self-edge, a bidirectional edge with B, and a unidirectional edge to C.

Also I want to be able to do global operations on the graph, like e.g. counting or removing all edges fulfilling certain criteria.

The easiest program structure I came up with is:

#include <unordered_set>

using namespace std;

struct Edge;

struct Node

 Node(std::string name):name(name)
 string name;
 std::unordered_set<Edge*> edges;
;

struct Edge

 Edge(Node * node1): node1(node1)
 double weight;
 Node * node1;
;

struct EdgeBetweenTwoNodes: public Edge

 EdgeBetweenTwoNodes(Node * node1, Node * node2 ): Edge(node1), node2(node2)
 Node * node2;
;

struct DirectionalEdge: public EdgeBetweenTwoNodes

 DirectionalEdge(Node * node1, Node * node2, bool direction ): EdgeBetweenTwoNodes(node1,node2), direction(direction)
 bool direction;
;

struct EdgesContainer

 std::unordered_set<Edge*> all_edges;

 void register_new_edge(Edge * edge)
 
 all_edges.insert(edge);
 

 //do all kind of manipulations on all edges of a cetain type...
;


struct EdgeFactory

 EdgeFactory()

 void create_edge(Node* node1,EdgesContainer & edge_container)
 
 Edge * edge = new Edge(node1);
 node1->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, EdgesContainer & edge_container)
 
 EdgeBetweenTwoNodes * edge = new EdgeBetweenTwoNodes(node1,node2);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, bool direction, EdgesContainer & edge_container)
 
 DirectionalEdge * edge = new DirectionalEdge(node1,node2,direction);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 
;


int main()

 Node * A = new Node("A");
 Node * B= new Node("B");
 Node * C= new Node("C");

 EdgesContainer edges;

 EdgeFactory edge_factory;
 edge_factory.create_edge(A,edges);
 edge_factory.create_edge(A,B,edges);
 edge_factory.create_edge(A,C,1,edges);

 return 0;

What do you think about it? Is this the correct use of a so called "Factory?"

edited 12 mins ago

200_success

125k14145406

asked 7 hours ago

newandlost

1243

New contributor

1

Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
â€“Â Mast
3 hours ago

1

Can I add more information about the classes s.t. the use-case is clearer?
â€“Â newandlost
2 hours ago

1

As long as it doesn't invalidate the existing answer.
â€“Â Mast
2 hours ago

add a commentÂ |Â

up vote
4
down vote

favorite

I want to implement a directed graph which has 3 main kind of edges:

self referencing edges

non directional edges between two nodes

directional edges between two nodes

Three-node graph. A has a self-edge, a bidirectional edge with B, and a unidirectional edge to C.

Also I want to be able to do global operations on the graph, like e.g. counting or removing all edges fulfilling certain criteria.

The easiest program structure I came up with is:

#include <unordered_set>

using namespace std;

struct Edge;

struct Node

 Node(std::string name):name(name)
 string name;
 std::unordered_set<Edge*> edges;
;

struct Edge

 Edge(Node * node1): node1(node1)
 double weight;
 Node * node1;
;

struct EdgeBetweenTwoNodes: public Edge

 EdgeBetweenTwoNodes(Node * node1, Node * node2 ): Edge(node1), node2(node2)
 Node * node2;
;

struct DirectionalEdge: public EdgeBetweenTwoNodes

 DirectionalEdge(Node * node1, Node * node2, bool direction ): EdgeBetweenTwoNodes(node1,node2), direction(direction)
 bool direction;
;

struct EdgesContainer

 std::unordered_set<Edge*> all_edges;

 void register_new_edge(Edge * edge)
 
 all_edges.insert(edge);
 

 //do all kind of manipulations on all edges of a cetain type...
;


struct EdgeFactory

 EdgeFactory()

 void create_edge(Node* node1,EdgesContainer & edge_container)
 
 Edge * edge = new Edge(node1);
 node1->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, EdgesContainer & edge_container)
 
 EdgeBetweenTwoNodes * edge = new EdgeBetweenTwoNodes(node1,node2);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, bool direction, EdgesContainer & edge_container)
 
 DirectionalEdge * edge = new DirectionalEdge(node1,node2,direction);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 
;


int main()

 Node * A = new Node("A");
 Node * B= new Node("B");
 Node * C= new Node("C");

 EdgesContainer edges;

 EdgeFactory edge_factory;
 edge_factory.create_edge(A,edges);
 edge_factory.create_edge(A,B,edges);
 edge_factory.create_edge(A,C,1,edges);

 return 0;

What do you think about it? Is this the correct use of a so called "Factory?"

edited 12 mins ago

200_success

125k14145406

asked 7 hours ago

newandlost

1243

New contributor

I want to implement a directed graph which has 3 main kind of edges:

self referencing edges

non directional edges between two nodes

directional edges between two nodes

Three-node graph. A has a self-edge, a bidirectional edge with B, and a unidirectional edge to C.

Also I want to be able to do global operations on the graph, like e.g. counting or removing all edges fulfilling certain criteria.

The easiest program structure I came up with is:

#include <unordered_set>

using namespace std;

struct Edge;

struct Node

 Node(std::string name):name(name)
 string name;
 std::unordered_set<Edge*> edges;
;

struct Edge

 Edge(Node * node1): node1(node1)
 double weight;
 Node * node1;
;

struct EdgeBetweenTwoNodes: public Edge

 EdgeBetweenTwoNodes(Node * node1, Node * node2 ): Edge(node1), node2(node2)
 Node * node2;
;

struct DirectionalEdge: public EdgeBetweenTwoNodes

 DirectionalEdge(Node * node1, Node * node2, bool direction ): EdgeBetweenTwoNodes(node1,node2), direction(direction)
 bool direction;
;

struct EdgesContainer

 std::unordered_set<Edge*> all_edges;

 void register_new_edge(Edge * edge)
 
 all_edges.insert(edge);
 

 //do all kind of manipulations on all edges of a cetain type...
;


struct EdgeFactory

 EdgeFactory()

 void create_edge(Node* node1,EdgesContainer & edge_container)
 
 Edge * edge = new Edge(node1);
 node1->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, EdgesContainer & edge_container)
 
 EdgeBetweenTwoNodes * edge = new EdgeBetweenTwoNodes(node1,node2);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 

 void create_edge(Node* node1, Node* node2, bool direction, EdgesContainer & edge_container)
 
 DirectionalEdge * edge = new DirectionalEdge(node1,node2,direction);
 node1->edges.insert(edge);
 node2->edges.insert(edge);

 edge_container.register_new_edge(edge);
 
;


int main()

 Node * A = new Node("A");
 Node * B= new Node("B");
 Node * C= new Node("C");

 EdgesContainer edges;

 EdgeFactory edge_factory;
 edge_factory.create_edge(A,edges);
 edge_factory.create_edge(A,B,edges);
 edge_factory.create_edge(A,C,1,edges);

 return 0;

What do you think about it? Is this the correct use of a so called "Factory?"

c++ graph

edited 12 mins ago

200_success

125k14145406

asked 7 hours ago

newandlost

1243

New contributor

edited 12 mins ago

200_success

125k14145406

asked 7 hours ago

newandlost

1243

New contributor

edited 12 mins ago

200_success

125k14145406

edited 12 mins ago

200_success

125k14145406

edited 12 mins ago

200_success

125k14145406

asked 7 hours ago

newandlost

1243

New contributor

asked 7 hours ago

newandlost

1243

asked 7 hours ago

newandlost

1243

New contributor

newandlost is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

1

Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
â€“Â Mast
3 hours ago

1

Can I add more information about the classes s.t. the use-case is clearer?
â€“Â newandlost
2 hours ago

1

As long as it doesn't invalidate the existing answer.
â€“Â Mast
2 hours ago

add a commentÂ |Â

1

Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
â€“Â Mast
3 hours ago

1

Can I add more information about the classes s.t. the use-case is clearer?
â€“Â newandlost
2 hours ago

1

As long as it doesn't invalidate the existing answer.
â€“Â Mast
2 hours ago

Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers.
â€“Â Mast
3 hours ago

Can I add more information about the classes s.t. the use-case is clearer?
â€“Â newandlost
2 hours ago

As long as it doesn't invalidate the existing answer.
â€“Â Mast
2 hours ago

add a commentÂ |Â

2 Answers
2

active

oldest

votes

up vote
4
down vote

Don't use using namespace std; it pollutes the namespace and creates name collisions. Only do this with concrete classes and only within a namespace or cpp file.

new without delete => leaks. Instead use smart pointers or store them by value where it makes sense.

There is no need to create a class hierarchy for the edges, instead use a enum to differentiate: enumBIDIR, FROM_1_TO_2, FROM_2_TO_1 and a self referential edge is a BIDIR and nodes 1 and 2 are equal.

unordered_set is far from the best data structure, it's slow to iterate over, access is very often a cache miss or two. Instead prefer data structures like std::vector where it is very fast to iterate over.

The best data structure depends a lot on what operations you will be doing on it, which you didn't mention so I can't really judge beyond saying that unordered_set is most likely a bad choice.

answered 6 hours ago

ratchet freak

11.5k1240

1

With the enum you mean I should give the Edge class a type member which has a value from enumBIDIR, FROM_1_TO_2, FROM_2_TO_1?
â€“Â newandlost
3 hours ago

1

yeah, that lets you do away with the hierarchy and just replace it with a switch/if/else in places where that matters instead of a dynamic cast.
â€“Â ratchet freak
3 hours ago

1

I will add more specifications to my question.
â€“Â newandlost
3 hours ago

2

Why is Enum preferable over a class hierarchy? I have not added it to my question yet, but... In my case an Edge gets selected by some algorithm. Each Edge class has its own way how it does update the network structure if selected. Let us call that function update_network_structure. If I us hierarchy I could use virtual functions. If I use Enum I would need to create a vector holding functions pointers?
â€“Â newandlost
3 hours ago

2

@cariehl Thanks! I will do that.
â€“Â newandlost
1 hour ago

Â |Â
show 1 more comment

up vote
1
down vote

At the moment

your edges have an identity.

There are three types.

Abolishing both leads to a simpler implementation:

struct Edge 
 Node* from;
 Node* to;
 double weight;
 // optional: enum EdgeType type;
;

std::unordered_set<Edge> edges;

Circular edges have both pointing to the same node.

Bi-directional edges have a reversed duplicate.

And normal directional edges are simple.

If you actually need to differentiate between those often enough, adding an enum to cache that info is simplicity itself.

If you save your nodes in a container, using indices might be a nice idea.

Implementation:

Never import wholesale any namespace not designed for it, like std. Doing so can lead to conflicts which might silently or hopefully noisily break your code if the implementation changes even slightly.

The Nodes you leak might be a concern, outside this toy-example. At the very least make sure Consider saving them in some container by value (careful of invalidation-rules), or managing them with smart-pointers.

Of more concern are the Edges. If registering an Edge fails, it is leaked. Allocate them with std::make_unique instead, to ensure they are always properly owned.

edited 8 mins ago

answered 20 mins ago

Deduplicator

10.6k1849

add a commentÂ |Â

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);

);

newandlost is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f205142%2ffactory-for-constructing-directed-graphs-in-c%23new-answer', 'question_page');

);

Post as a guest

Name

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

up vote
4
down vote

Don't use using namespace std; it pollutes the namespace and creates name collisions. Only do this with concrete classes and only within a namespace or cpp file.

new without delete => leaks. Instead use smart pointers or store them by value where it makes sense.

The best data structure depends a lot on what operations you will be doing on it, which you didn't mention so I can't really judge beyond saying that unordered_set is most likely a bad choice.

answered 6 hours ago

ratchet freak

11.5k1240

1

With the enum you mean I should give the Edge class a type member which has a value from enumBIDIR, FROM_1_TO_2, FROM_2_TO_1?
â€“Â newandlost
3 hours ago

1

yeah, that lets you do away with the hierarchy and just replace it with a switch/if/else in places where that matters instead of a dynamic cast.
â€“Â ratchet freak
3 hours ago

1

I will add more specifications to my question.
â€“Â newandlost
3 hours ago

2

Why is Enum preferable over a class hierarchy? I have not added it to my question yet, but... In my case an Edge gets selected by some algorithm. Each Edge class has its own way how it does update the network structure if selected. Let us call that function update_network_structure. If I us hierarchy I could use virtual functions. If I use Enum I would need to create a vector holding functions pointers?
â€“Â newandlost
3 hours ago

2

@cariehl Thanks! I will do that.
â€“Â newandlost
1 hour ago

Â |Â
show 1 more comment

up vote
4
down vote

Don't use using namespace std; it pollutes the namespace and creates name collisions. Only do this with concrete classes and only within a namespace or cpp file.

new without delete => leaks. Instead use smart pointers or store them by value where it makes sense.

The best data structure depends a lot on what operations you will be doing on it, which you didn't mention so I can't really judge beyond saying that unordered_set is most likely a bad choice.

answered 6 hours ago

ratchet freak

11.5k1240

1

With the enum you mean I should give the Edge class a type member which has a value from enumBIDIR, FROM_1_TO_2, FROM_2_TO_1?
â€“Â newandlost
3 hours ago

1

yeah, that lets you do away with the hierarchy and just replace it with a switch/if/else in places where that matters instead of a dynamic cast.
â€“Â ratchet freak
3 hours ago

1

I will add more specifications to my question.
â€“Â newandlost
3 hours ago

2

Why is Enum preferable over a class hierarchy? I have not added it to my question yet, but... In my case an Edge gets selected by some algorithm. Each Edge class has its own way how it does update the network structure if selected. Let us call that function update_network_structure. If I us hierarchy I could use virtual functions. If I use Enum I would need to create a vector holding functions pointers?
â€“Â newandlost
3 hours ago

2

@cariehl Thanks! I will do that.
â€“Â newandlost
1 hour ago

Â |Â
show 1 more comment

up vote
4
down vote

Don't use using namespace std; it pollutes the namespace and creates name collisions. Only do this with concrete classes and only within a namespace or cpp file.

new without delete => leaks. Instead use smart pointers or store them by value where it makes sense.

The best data structure depends a lot on what operations you will be doing on it, which you didn't mention so I can't really judge beyond saying that unordered_set is most likely a bad choice.

answered 6 hours ago

ratchet freak

11.5k1240

Don't use using namespace std; it pollutes the namespace and creates name collisions. Only do this with concrete classes and only within a namespace or cpp file.

new without delete => leaks. Instead use smart pointers or store them by value where it makes sense.

The best data structure depends a lot on what operations you will be doing on it, which you didn't mention so I can't really judge beyond saying that unordered_set is most likely a bad choice.

answered 6 hours ago

ratchet freak

11.5k1240

answered 6 hours ago

ratchet freak

11.5k1240

answered 6 hours ago

ratchet freak

11.5k1240

answered 6 hours ago

ratchet freak

11.5k1240

1

With the enum you mean I should give the Edge class a type member which has a value from enumBIDIR, FROM_1_TO_2, FROM_2_TO_1?
â€“Â newandlost
3 hours ago

1

yeah, that lets you do away with the hierarchy and just replace it with a switch/if/else in places where that matters instead of a dynamic cast.
â€“Â ratchet freak
3 hours ago

1

I will add more specifications to my question.
â€“Â newandlost
3 hours ago

2

Why is Enum preferable over a class hierarchy? I have not added it to my question yet, but... In my case an Edge gets selected by some algorithm. Each Edge class has its own way how it does update the network structure if selected. Let us call that function update_network_structure. If I us hierarchy I could use virtual functions. If I use Enum I would need to create a vector holding functions pointers?
â€“Â newandlost
3 hours ago

2

@cariehl Thanks! I will do that.
â€“Â newandlost
1 hour ago

Â |Â
show 1 more comment

1

With the enum you mean I should give the Edge class a type member which has a value from enumBIDIR, FROM_1_TO_2, FROM_2_TO_1?
â€“Â newandlost
3 hours ago

1

yeah, that lets you do away with the hierarchy and just replace it with a switch/if/else in places where that matters instead of a dynamic cast.
â€“Â ratchet freak
3 hours ago

1

I will add more specifications to my question.
â€“Â newandlost
3 hours ago

2

Why is Enum preferable over a class hierarchy? I have not added it to my question yet, but... In my case an Edge gets selected by some algorithm. Each Edge class has its own way how it does update the network structure if selected. Let us call that function update_network_structure. If I us hierarchy I could use virtual functions. If I use Enum I would need to create a vector holding functions pointers?
â€“Â newandlost
3 hours ago

2

@cariehl Thanks! I will do that.
â€“Â newandlost
1 hour ago

With the enum you mean I should give the Edge class a type member which has a value from enumBIDIR, FROM_1_TO_2, FROM_2_TO_1?
â€“Â newandlost
3 hours ago

yeah, that lets you do away with the hierarchy and just replace it with a switch/if/else in places where that matters instead of a dynamic cast.
â€“Â ratchet freak
3 hours ago

I will add more specifications to my question.
â€“Â newandlost
3 hours ago

Why is Enum preferable over a class hierarchy? I have not added it to my question yet, but... In my case an Edge gets selected by some algorithm. Each Edge class has its own way how it does update the network structure if selected. Let us call that function update_network_structure. If I us hierarchy I could use virtual functions. If I use Enum I would need to create a vector holding functions pointers?
â€“Â newandlost
3 hours ago

@cariehl Thanks! I will do that.
â€“Â newandlost
1 hour ago

Â |Â
show 1 more comment

up vote
1
down vote

At the moment

your edges have an identity.

There are three types.

Abolishing both leads to a simpler implementation:

struct Edge 
 Node* from;
 Node* to;
 double weight;
 // optional: enum EdgeType type;
;

std::unordered_set<Edge> edges;

Circular edges have both pointing to the same node.

Bi-directional edges have a reversed duplicate.

And normal directional edges are simple.

If you actually need to differentiate between those often enough, adding an enum to cache that info is simplicity itself.

If you save your nodes in a container, using indices might be a nice idea.

Implementation:

Never import wholesale any namespace not designed for it, like std. Doing so can lead to conflicts which might silently or hopefully noisily break your code if the implementation changes even slightly.

The Nodes you leak might be a concern, outside this toy-example. At the very least make sure Consider saving them in some container by value (careful of invalidation-rules), or managing them with smart-pointers.

Of more concern are the Edges. If registering an Edge fails, it is leaked. Allocate them with std::make_unique instead, to ensure they are always properly owned.

edited 8 mins ago

answered 20 mins ago

Deduplicator

10.6k1849

add a commentÂ |Â

up vote
1
down vote

At the moment

your edges have an identity.

There are three types.

Abolishing both leads to a simpler implementation:

struct Edge 
 Node* from;
 Node* to;
 double weight;
 // optional: enum EdgeType type;
;

std::unordered_set<Edge> edges;

Circular edges have both pointing to the same node.

Bi-directional edges have a reversed duplicate.

And normal directional edges are simple.

If you actually need to differentiate between those often enough, adding an enum to cache that info is simplicity itself.

If you save your nodes in a container, using indices might be a nice idea.

Implementation:

Never import wholesale any namespace not designed for it, like std. Doing so can lead to conflicts which might silently or hopefully noisily break your code if the implementation changes even slightly.

The Nodes you leak might be a concern, outside this toy-example. At the very least make sure Consider saving them in some container by value (careful of invalidation-rules), or managing them with smart-pointers.

Of more concern are the Edges. If registering an Edge fails, it is leaked. Allocate them with std::make_unique instead, to ensure they are always properly owned.

edited 8 mins ago

answered 20 mins ago

Deduplicator

10.6k1849

add a commentÂ |Â

up vote
1
down vote

At the moment

your edges have an identity.

There are three types.

Abolishing both leads to a simpler implementation:

struct Edge 
 Node* from;
 Node* to;
 double weight;
 // optional: enum EdgeType type;
;

std::unordered_set<Edge> edges;

Circular edges have both pointing to the same node.

Bi-directional edges have a reversed duplicate.

And normal directional edges are simple.

If you actually need to differentiate between those often enough, adding an enum to cache that info is simplicity itself.

If you save your nodes in a container, using indices might be a nice idea.

Implementation:

Never import wholesale any namespace not designed for it, like std. Doing so can lead to conflicts which might silently or hopefully noisily break your code if the implementation changes even slightly.

The Nodes you leak might be a concern, outside this toy-example. At the very least make sure Consider saving them in some container by value (careful of invalidation-rules), or managing them with smart-pointers.

Of more concern are the Edges. If registering an Edge fails, it is leaked. Allocate them with std::make_unique instead, to ensure they are always properly owned.

edited 8 mins ago

answered 20 mins ago

Deduplicator

10.6k1849

At the moment

your edges have an identity.

There are three types.

Abolishing both leads to a simpler implementation:

struct Edge 
 Node* from;
 Node* to;
 double weight;
 // optional: enum EdgeType type;
;

std::unordered_set<Edge> edges;

Circular edges have both pointing to the same node.

Bi-directional edges have a reversed duplicate.

And normal directional edges are simple.

If you actually need to differentiate between those often enough, adding an enum to cache that info is simplicity itself.

If you save your nodes in a container, using indices might be a nice idea.

Implementation:

Never import wholesale any namespace not designed for it, like std. Doing so can lead to conflicts which might silently or hopefully noisily break your code if the implementation changes even slightly.

The Nodes you leak might be a concern, outside this toy-example. At the very least make sure Consider saving them in some container by value (careful of invalidation-rules), or managing them with smart-pointers.

Of more concern are the Edges. If registering an Edge fails, it is leaked. Allocate them with std::make_unique instead, to ensure they are always properly owned.

edited 8 mins ago

answered 20 mins ago

Deduplicator

10.6k1849

edited 8 mins ago

answered 20 mins ago

Deduplicator

10.6k1849

answered 20 mins ago

Deduplicator

10.6k1849

answered 20 mins ago

Deduplicator

10.6k1849

add a commentÂ |Â

newandlost is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

newandlost is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

Post as a guest

Name

Search This Blog

Iyfjky