Creating in c#,c++ and java a strong typed version of a python weak typed structure

Question

In python I have the following:

graph = {}

graph[1] = {}
graph[2] = {}
graph[3] = {}

graph[1][3] = graph[3]

graph[2][1] = graph[1]
graph[2][3] = graph[3]

graph[3][2] = graph[2]

this is a structure to represent a graph and that I find nice because its structure is the same as the one of one of it's nodes so I can use it directly to initiate a search (as in depth-first). The printed version of it is:

{1: {3: {2: {1: {...}, 3: {...}}}}, 2: {1: {3: {2: {...}}}, 3: {2: {...}}}, 3: {
2: {1: {3: {...}}, 3: {...}}}}

And it can be used like:

graph[1][3][2][3][2][1][3][2][1][3][2].keys()

Now, I'm curious to know how would one implement it in C++, C# and Java without resorting to "Object" tricks that would fill the code with ugly casts. For C++ I was thinking in templatemeta programming but that would generate "finite data types" when what is needed is something like

map<int,map<int,...>> or map<int,...>

Answer 1

Here's a simple hack:

#include <map>
#include <memory>

struct GraphNode
{
  std::map<std::size_t, std::unique_ptr<GraphNode>> m;

  GraphNode & operator[](std::size_t i)
  {
    if (!m[i]) { m[i].reset(new GraphNode); }
    return *m[i];
  }
};

We add some ostream overloads for printing:

#include <prettyprint.hpp>

std::ostream & operator<<(std::ostream & o, GraphNode const & g)
{
  if (g.m.empty()) return o << "*";
  return o << g.m;
}
std::ostream & operator<<(std::ostream & o, std::unique_ptr<GraphNode> const & p)
{
  if (!p) return o << "*";
  return o << *p;
}

Example usage:

#include <iostream>

int main()
{
  GraphNode n;

  n[2] = GraphNode();
  n[4] = GraphNode();

  n[2][3] = GraphNode();
  n[2][8] = GraphNode();
  n[2][1] = GraphNode();

  std::cout << n << std::endl;
}

Prints: [(2, [(1, *), (3, *), (8, *)]), (4, *)]

Further features are easily added; at the moment it's not clear to me whether you want all nodes to also support satellite data ("values"), or whether only leaf nodes can have values, or if there isn't any additional data.

Answer 2

In Java, I would go with a Node class which represents any node of a graph.

public class Node<T> {
    private List<Node<T>> children = new ArrayList<Node<T>>();
    private T value;

    public Node(T value) {
        this.value = value;
    }

    public void addChild(Node<T> child) {
        this.children.add(child);
    }

    public Node<T> getChild(int index) {
        return this.children.get(index);
    }

    public List<Node<T>> getChildren() {
        return this.children;
    }

    public T getValue() {
        return this.value;
    }
}

If you want a graph that will contain int values you can instantiate it and use it with:

Node<Integer> graph = new Node<Integer>(10); //value of the first node is 10
graph.addChild(new Node<Integer>(-3));
graph.getChild(0).addChild(new Node<Integer>(5));
System.out.println(graph.getChild(0).getChild(0).getValue()); //prints 5

Answer 3

For storing either further graphs or "terminal" values (actually, both of these approaches generalize to arbitarily many types with any interpretation, as long as they can be enumerated at compiletime), you use either:

• Unions (possibly discriminated), or
• Polymorphism (specifically, subtype polymorphism)

In either case, you have a type Graph behind which you can hide both nested graphs and stored values.

In C++ specifically, you'd probably use the former a union or Boost::Variant (more typesafe and convenient to handle). You may need to forward-declare the class so it's visible at the time you define it. A union offers enough place to store one value of either type, and (either implicitly in Boost::Variant or explicitly with plain old union) a "tag" indicating which one is the case. You can then look at any stored value and tell if it's another graph or a terminal value, and extract the associated value.

In Java and C#, you don't have that much support for straight-forward union types, so you'd use the second option. There's an interface (or abstract) class IGraph, with one implementation for graphs (refering to IGraphs) and one for wrapping non-graph values in another subtype of IGraph. Basically you use subtype polymorphism. This is possible in C++ too, but I get the impression that a union is a better idea if the possible types are known beforehand, unlikely to ever change, and small in number. It also allows you to avoid some pointers/references - both unions and Boost::Variants can be stored on the stack, while polymorphism requires indirection.