GraphGravity

Implementing a general directed weighted graph (GDWG) in C++

The implementation file is in include/gdwg/graph.hpp.

Write a graph library type in C++, in include/gdwg/graph.hpp.

In this project, a generic directed weighted graph (GDWG) is implemented with value-semantics in C++. Both the data stored at a node and the weight stored at an edge will be parameterised types. The types may be different. For example, here is a graph with nodes storing std::string and edges weighted by int:

using graph = gdwg::graph<std::string, int>;

Formally, this directed weighted graph G = (N, E) will consist of a set of nodes N and a set of weighted edges E.

All nodes are unique, that is to say, no two nodes will have the same value and shall not compare equal using operator==.

Given a node, an edge directed into it is called an incoming edge and an edge directed out of it is called an outgoing edge. The in-degree of a node is the number of its incoming edges. Similarly, the out-degree of a node is the number of its outgoing edges. Given a directed edge from src to dst, src is the source node and dst is known as the destination node.

Edges can be reflexive, that is to say, the source and destination nodes of an edge could be the same.

G is a multi-edged graph, as there may be two edges from the same source node to the same destination node with two different weights. Two edges from the same source node to the same destination node cannot have the same weight.

1 Definitions [gdwg.definitions]

1. Some words have special meaning in this document. This section precisicely defines those words.

   • Preconditions: the conditions that the function assumes to hold whenever it is called; violation of any preconditions results in undefined
   • Effects: the actions performed by the function.
   • Postconditions: the conditions (sometimes termed observable results) established by the function.
   • Returns: a description of the value(s) returned by the function.
   • Throws: any exceptions thrown by the function, and the conditions that would cause the exception.
   • Complexity: the time and/or space complexity of the function.
   • Remarks: additional semantic constraints on the function.
   • Unspecified: the implementation is allowed to make its own decisions regarding what is unspecified, provided that it still follows the explicitly specified wording.

2. An Effects element may specify semantics for a function F in code using the term Equivalent to. The semantics for F are interpreted as follows:

   • All of the above terminology applies to the provided code, whether or not it is explicitly specified. [Example: If F has a Preconditions element, but the code block doesn’t explicitly check them, then it is implied that the preconditions have been checked. —end example]
   • If there is not a Returns element, and F has a non-void return type, all the return statements are in the code block.
   • Throws, Postconditions, and Complexity elements always have priority over the code block.

2 Constructors [gdwg.ctor]

graph();

1. Effects: Value initialises all members.

2. Throws: Nothing.

graph(std::initializer_list<N> il);

3. Effects: Equivalent to: graph(il.begin(), il.end());

template<typename InputIt>
graph(InputIt first, InputIt last);

4. Preconditions: Type InputIt models Cpp17InputIterator and is indirectly readable as type N.
5. Effects: Initialises the graph’s node collection with the range [first, last).

graph(graph&& other) noexcept;

6. Postconditions:

• *this is equal to the value other had before this constructor’s invocation.
• other.empty() is true.
• All iterators pointing to elements owned by *this prior to this constructor’s invocation are invalidated.
• All iterators pointing to elements owned by other prior to this constructor’s invocation remain valid, but now point to the elements owned by *this.

auto operator=(graph&& other) noexcept -> graph&;

7. Effects: All existing nodes and edges are either move-assigned to, or are destroyed.
8. Postconditions:

• *this is equal to the value other had before this operator’s invocation.
• other.empty() is true.
• All iterators pointing to elements owned by *this prior to this operator’s invocation are invalidated.
• All iterators pointing to elements owned by other prior to this operator’s invocation remain valid, but now point to the elements owned by *this.

9. Returns: *this.

graph(graph const& other);

10. Postconditions: *this == other is true.

auto operator=(graph const& other) -> graph&;

11. Postconditions:

    • *this == other is true.
    • All iterators pointing to elements owned by *this prior to this operator’s invocation are invalidated.

12. Returns: *this.

3 Modifiers [gdwg.modifiers]

auto insert_node(N const& value) -> bool;

1. Effects: Adds a new node with value value to the graph if, and only if, there is no node equivalent to value already stored.

2. Postconditions: All iterators are invalidated.

3. Returns: true if the node is added to the graph and false otherwise.

auto insert_edge(N const& src, N const& dst, E const& weight) -> bool;

4. Effects: Adds a new edge representing src → dst with weight weight, if, and only if, there is no edge equivalent to value_type{src, dst, weight} already stored. [Note:⁠ Nodes are allowed to be connected to themselves. —end note]

5. Postconditions: All iterators are invalidated.

6. Returns: true if the node is added to the graph and false otherwise.

7. Throws: std::runtime_error("Cannot call gdwg::graph<N, E>::insert_edge when either src or dst node does not exist") if either of is_node(src) or is_node(dst) are false. [Note: Unlike Assignment 2, the exception message must be used verbatim. —end note]

auto replace_node(N const& old_data, N const& new_data) -> bool;

8. Effects: Replaces the original data, old_data, stored at this particular node by the replacement data, new_data. Does nothing if new_data already exists as a node.

9. Postconditions: All iterators are invalidated.

10. Returns: false if a node that contains value new_data already exists and true otherwise.

11. Throws: std::runtime_error("Cannot call gdwg::graph<N, E>::replace_node on a node that doesn't exist") if is_node(old_data) is false. [Note: Unlike Assignment 2, the exception message must be used verbatim. —end note]

auto merge_replace_node(N const& old_data, N const& new_data) -> void;

12. Effects: The node equivalent to old_data in the graph are replaced with instances of new_data. After completing, every incoming and outgoing edge of old_data becomes an incoming/ougoing edge of new_data, except that duplicate edges shall be removed.

13. Postconditions: All iterators are invalidated.

14. Throws: std::runtime_error("Cannot call gdwg::graph<N, E>::merge_replace_node on old or new data if they don't exist in the graph") if either of is_node(old_data) or is_node(new_data) are false. [Note: Unlike Assignment 2, the exception message must be used verbatim. —end note]

15. [Note: The following examples use the format (N_src, N_dst, E). [Example: Basic example.

• Operation: merge_replace_node(A, B)
• Graph before: (A, B, 1), (A, C, 2), (A, D, 3)
• Graph after : (B, B, 1), (B, C, 2), (B, D, 3)

—end example][Example: Duplicate edge removed example.

• Operation: merge_replace_node(A, B)
• Graph before: (A, B, 1), (A, C, 2), (A, D, 3), (B, B, 1)
• Graph after : (B, B, 1), (B, C, 2), (B, D, 3)

—end example][Example: Diagrammatic example.

—end example] —end note]

auto erase_node(N const& value) -> bool;

16. Effects: Erases all nodes equivalent to value, including all incoming and outgoing edges.

17. Returns: true if value was removed; false otherwise.

18. Postconditions: All iterators are invalidated.

auto erase_edge(N const& src, N const& dst, E const& weight) -> bool;

20. Effects: Erases an edge representing src → dst with weight weight.

21. Returns: true if an edge was removed; false otherwise.

22. Postconditions: All iterators are invalidated.

23. Throws: std::runtime_error("Cannot call gdwg::graph<N, E>::erase_edge on src or dst if they don't exist in the graph") if either is_node(src) or is_node(dst) is false. [Note: Unlike Assignment 2, the exception message must be used verbatim. —end note]

24. Complexity: O(log (n) + e), where n is the total number of stored nodes and e is the total number of stored edges.

auto erase_edge(iterator i) -> iterator;

25. Effects: Erases the edge pointed to by i.

26. Complexity: Amortised constant time.

27. Returns: An iterator pointing to the element immediately after i prior to the element being erased. If no such element exists, returns end().

28. Postconditions: All iterators are invalidated. [Note: The postcondition is slightly stricter than a real-world container to help make the assingment easier (i.e. we won’t be testing any iterators post-erasure). —end note]

auto erase_edge(iterator i, iterator s) -> iterator;

29. Effects: Erases all edges between the iterators [i, s).

30. Complexity O(d), where d=std::distance(i, s).

31. Returns: An iterator equivalent to s prior to the items iterated through being erased. If no such element exists, returns end().

32. Postconditions: All iterators are invalidated. [Note: The postcondition is slightly stricter than a real-world container to help make the assingment easier (i.e. we won’t be testing any iterators post-erasure). —end note]

auto clear() noexcept -> void;

33. Effects: Erases all nodes from the graph.

34. Postconditions: empty() is true.

4 Accessors [gdwg.accessors]

[[nodiscard]] auto is_node(N const& value) -> bool;

1. Returns: true if a node equivalent to value exists in the graph, and false otherwise.

2. Complexity: O(log (n)) time.

[[nodiscard]] auto empty() -> bool;

3. Returns: true if there are no nodes in the graph, and false otherwise.

[[nodiscard]] auto is_connected(N const& src, N const& dst) -> bool;

4. Returns: true if an edge src → dst exists in the graph, and false otherwise.

5. Throws: std::runtime_error("Cannot call gdwg::graph<N, E>::is_connected if src or dst node don't exist in the graph") if either of is_node(src) or is_node(dst) are false. [Note: Unlike Assignment 2, the exception message must be used verbatim. —end note]

[[nodiscard]] auto nodes() -> std::vector<N>;

6. Returns: A sequence of all stored nodes, sorted in ascending order.

7. Complexity: O(n), where n is the number of stored nodes.

[[nodiscard]] auto weights(N const& src, N const& dst) -> std::vector<E>;

8. Returns: A sequence of weights from src to dst, sorted in ascending order.

9. Complexity: O(log (n) + e), where n is the number of stored nodes and e is the number of stored edges.

10. Throws: std::runtime_error("Cannot call gdwg::graph<N, E>::weights if src or dst node don't exist in the graph") if either of is_node(src) or is_node(dst) are false. [Note: Unlike Assignment 2, the exception message must be used verbatim. —end note]

[[nodiscard]] auto find(N const& src, N const& dst, E const& weight) -> iterator;

11. Returns: An iterator pointing to an edge equivalent to value_type{src, dst, weight}, or end() if no such edge exists.

12. Complexity: O(log (n) + log (e)), where n is the number of stored nodes and e is the number of stored edges.

[[nodiscard]] auto connections(N const& src) -> std::vector<N>;

13. Returns: A sequence of nodes (found from any immediate outgoing edge) connected to src, sorted in ascending order, with respect to the connected nodes.

14. Complexity: O(log (n) + e), where e is the number of outgoing edges associated with src.

15. Throws: std::runtime_error("Cannot call gdwg::graph<N, E>::connections if src doesn't exist in the graph") if is_node(src) is false. [Note: Unlike Assignment 2, the exception message must be used verbatim. —end note]

5 Iterator access [gdwg.iterator.access]

[[nodiscard]] auto begin() const -> iterator;

1. Returns: An iterator pointing to the first element in the container.

[[nodiscard]] auto end() const -> iterator;

2. Returns: An iterator denoting the end of the iterable list that begin() points to.

3. Remarks: [begin(), end()) shall denote a valid iterable list.

6 Comparisons [gdwg.cmp]

[[nodiscard]] auto operator==(graph const& other) -> bool;

1. Returns: true if *this and other contain exactly the same nodes and edges, and false otherwise.

2. Complexity: O(n + e) where n is the sum of stored nodes in *this and other, and e is the sum of stored edges in *this and other.

7 Extractor [gdwg.io]

friend auto operator<<(std::ostream& os, graph const& g) -> std::ostream&;

1. Effects: Behaves as a formatted output function of os.

2. Returns: os.

3. Remarks: The format is specified thusly:

[source_node1] [edges1]
[source_node2] [edges2]
...
[source_noden] [edgesn]

[source_node1], …, [source_noden] are placeholders for all nodes that the graph stores, sorted in ascending order. [edges1], …, [edgesn] are placeholders for

(
  [noden_connected_node1] | [weight]
  [noden_connected_node2] | [weight]
  ...
  [noden_connected_noden] | [weight]
)

where [noden_conencted_node1] | [weight], …, [noden_connected_noden] | [weight] are placeholders for each node’s connections and corresponding weight, also sorted in ascending order. [Note: If a node doesn’t have any connections, then its corresponding [edgesn] should be a line-separated pair of parentheses —end note]

[Example:

using graph = gdwg::graph<int, int>;
auto const v = std::vector<graph::value_type>{
  {4, 1, -4},
  {3, 2, 2},
  {2, 4, 2},
  {2, 1, 1},
  {6, 2, 5},
  {6, 3, 10},
  {1, 5, -1},
  {3, 6, -8},
  {4, 5, 3},
  {5, 2, 7},
};

auto g = graph{};
for (const auto& x : v) {
  g.insert_edge(x);
};

g.insert_node(64);
auto out = std::ostringstream{};
out << g;
auto const expected_output = std::string_view(R"(1 (
  5 | -1
)
2 (
  1 | 1
  4 | 2
)
3 (
  2 | 2
  6 | -8
)
4 (
  1 | -4
  5 | 3
)
5 (
  2 | 7
)
6 (
  2 | 5
  3 | 10
)
64 (
)
)");
CHECK(out.str() == expected_output);

—end example ]

8 Iterator [gdwg.iterator]

template<typename N, typename E>
class graph<N, E>::iterator {
public:
  using value_type = graph<N, E>::value_type;
  using reference = value_type;
  using pointer = void;
  using difference_type = std::ptrdiff_t;
  using iterator_category = std::bidirectional_iterator_tag;

  // Iterator constructor
  iterator() = default;

  // Iterator source
  auto operator*() -> reference;

  // Iterator traversal
  auto operator++() -> iterator&;
  auto operator++(int) -> iterator;
  auto operator--() -> iterator&;
  auto operator--(int) -> iterator;

  // Iterator comparison
  auto operator==(iterator const& other) -> bool;
private:
  explicit iterator(unspecified);
};

1. Elements are lexicographically ordered by their source node, destination node, and edge weight, in ascending order.

2. Nodes without any connections are not traversed.

3. [Note: gdwg::graph<N, E>::iterator models std::bidirectional_iterator. —end note]

8.1 Iterator constructor [gdwg.iterator.ctor]

iterator();

1. Effects: Value-initialises all members.

2. Remarks: Pursuant to the requirements of std::forward_iterator, two value-initialised iterators shall compare equal.

explicit iterator(unspecified);

3. Effects: Constructs an iterator to a specific element in the graph.

4. Remarks: There may be multiple constructors with a non-zero number of parameters.

8.2 Iterator source [gdwg.iterator.source]

auto operator*() -> reference;

1. Effects: Returns the current from, to, and weight.

8.3 Iterator traversal [gdwg.iterator.traversal]

auto operator++() -> iterator&;

1. Effects: Advances *this to the next element in the iterable list.

[Example: In this way, your iterator will iterator through a graph like the one below producing the following tuple values when deferenced each time:

gdwg::graph<int, int>

(1, 7, 4)
(1, 12, 3)
(1, 21, 12)
(7, 21, 13)
(12, 19, 16)
(14, 14, 0)
(19, 1, 3)
(19, 21, 2)
(21, 14, 23)
(21, 31, 14)

—end example]

2. Returns: *this.

auto operator++(int) -> iterator;

3. Effects: Equivalent to:

auto temp = *this;
++*this;
return temp;

auto operator--() -> iterator&;

4. Effects: Advances *this to the previous element in the iterable list.

5. Returns: *this.

auto operator--(int) -> iterator;

6. Effects: Equivalent to:

auto temp = *this;
--*this;
return temp;

8.4 Iterator comparison [gdwg.iterator.comparison]

auto operator==(iterator const& other) -> bool;

1. Returns: true if *this and other are pointing to elements in the same iterable list, and false otherwise.