7
\$\begingroup\$

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?"

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Oct 8, 2018 at 17:01
  • 1
    \$\begingroup\$ Can I add more information about the classes s.t. the use-case is clearer? \$\endgroup\$ Commented Oct 8, 2018 at 17:29
  • 1
    \$\begingroup\$ As long as it doesn't invalidate the existing answer. \$\endgroup\$ Commented Oct 8, 2018 at 17:43

2 Answers 2

Reset to default
3
\$\begingroup\$

At the moment

  1. your edges have an identity.
  2. 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.
Until that day, revel in the simplicity of having only a single type.

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

Implementation:

  1. 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.

  2. 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.

  3. 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.

\$\endgroup\$
5
\$\begingroup\$

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: enum{BIDIR, 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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ With the enum you mean I should give the Edge class a type member which has a value from enum{BIDIR, FROM_1_TO_2, FROM_2_TO_1}? \$\endgroup\$ Commented Oct 8, 2018 at 16:51
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Oct 8, 2018 at 16:56
  • 1
    \$\begingroup\$ I will add more specifications to my question. \$\endgroup\$ Commented Oct 8, 2018 at 16:56
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ Commented Oct 8, 2018 at 17:04
  • \$\begingroup\$ @newandlost Code Review generally only looks at the posted code, so if you didn't include a virtual function then we will assume it doesn't exist. In that context, your current hierarchy is more of an "I might use this later" feature. Such code violates the principle of YAGNI, so this answer is more relevant. If you modify your code, I would recommend posting it as a new question, so as not to invalidate any current answers on this one. \$\endgroup\$ Commented Oct 8, 2018 at 18:45

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.