Graph data structure

This page presents two possible implementations of a directed graph (DG), here called Graph. This graph is constitued of several nodes, here called GraphNode.

In both cases, this DG is implemented as an adjacency list.

1st implementation

Nodes must be derived from a base class, which handles all the necessary dependency operations.

When adding a node, a reference on the object is directly returned. This means that for a Graph<T>, adding a node returns directly a T&.

template <typename T>
class GraphNode {
public:
  const std::vector<const T*> getChildren() const { return m_children; }
  const std::vector<T*> getChildren() { return m_children; }

  void addChildren(...);
  void addParents(...);

protected:
  GraphNode() = default;

  std::vector<T*> m_children {};
};

template <typename NodeT>
class Graph {
  static_assert(std::is_base_of_v<GraphNode<NodeT>, NodeT>, "Error: Graph node type must be derived from GraphNode.");

public:
  Graph() = default;

  NodeT& addNode(...);

private:
  std::vector<std::unique_ptr<NodeT>> m_nodes {};
};

This implementation mandates to have a derived class for any node type. As such, an example of a graph of 'int' would be the following:

struct TestIntNode : public Raz::GraphNode<TestIntNode> {
  TestIntNode(int val) : value{ val } {}

  int value {};
};

TEST_CASE("Graph int test") {
  Raz::Graph<TestIntNode> graph;

  TestIntNode& root  = graph.addNode(0);
  TestIntNode& child = graph.addNode(42);

  root.addChildren(child);
  // ...

  CHECK(root.value == 0);
  CHECK(child.value == 42);
}

Pros

• Nodes are self-handled (modifying one may propagate anything to its children)
• Intuitive to use once set up

Cons

• Each unhandled type must be wrapped in a custom class
  • For example, creating a Graph of integers forces the user to create an intermediate wrapper
• Not that intuitive to set up (the node's template must be the class itself)

2nd implementation

Nodes of a specific type are directly stored in the graph.

When a node is added in the graph, the node object is returned, acting as a wrapper around the value.

template <typename T>
class GraphNode {
public:
  template <typename... Args>
  GraphNode(Args&&... args) : m_value{ std::forward<Args>(args)... } {}

  const std::vector<const T*> getChildren() const { return m_children; }
  const std::vector<T*> getChildren() { return m_children; }

  void addChildren(...);
  void addParents(...);
  const T& getValue() const noexcept { return m_value; }

private:
  T m_value {};
  std::vector<GraphNode*> m_children {};
};

template <typename NodeT>
class Graph {
public:
  Graph() = default;

  GraphNode<NodeT>& addNode(...);

private:
  std::vector<std::unique_ptr<GraphNode<NodeT>>> m_nodes {};
};

For example, a graph of 'int' is trivial with this implementation :

TEST_CASE("Test") {
  Raz::Graph<int> graph;

  Raz::GraphNode<int>& root  = graph.addNode(0);
  Raz::GraphNode<int>& child = graph.addNode(42);

  root.addChildren(child);
  // ...

  CHECK(root.getValue() == 0);
  CHECK(child.getValue() == 42);
}

Pros

• Easier to integrate any type

Cons

• Types don't have knowledge of the other nodes, the dependency chain is harder to set up
  • If a custom wrapper is made to palliate this issue, this removes the advantage of this implementation
  • This is thus mainly interesting for types not available explicitly in RaZ, like primitives & those from external libraries