Implement a weighted digraph with an adjacency map

[mwermelinger]

You may copy and adapt code from Section 18.2.2 of the M269 book. You may divide the tasks below with others, to reduce workload.

Create a file paddles/digraph.py with a class AdjacencyMapWeightedDiGraph:

• The docstring of the module explains the Digraph ADT.
• Write inspector methods to
  • return the number of nodes and of edges
  • check if a given node or edge exists
  • return the in- and out-degree of a node (raise ValueError if the node doesn't exist)
  • return the in- and out-neighbours of a node (raise ValueError if the node doesn't exist)
  • return the weight of a given edge (raise ValueError if the edge – i.e. either node – doesn't exist)
• Write modifier methods to
  • add a node (raise ValueError if the node already exists)
  • remove a node and all its edges (raise ValueError if the node to remove doesn't exist)
  • add an edge (raise ValueError if the edge is between the same node – a loop)
  • remove an edge (raise ValueError if the edge to remove doesn't exist)

Create a file tests/test_digraph.py:

• Write a test for each modifier method, using the inspector methods to check the behaviour.

[mwermelinger]

The add edge method may take an optional weight with default value 1 so that the class can also be used as an unweighted graph. However, pedagogically it may be better to have a simpler superclass for unweighted graphs. The exact class hierarchy for un/weighted di/graphs requires a bit of thinking. It would be good to allow extension in future to non-simple graphs.

In networkx, digraph is a subclass of undirected and stores both the out- and in-neighbours. Arbitrary attributes can be attached to a graph, a node or an edge. Weight is just an attribute like any other. Both classes allow loops. There are two separate classes for graphs with multi-edges.