Создание в C#, C++ и Java сильную версию набранного из питона слабой структуры типизированного

Question

В питоне я следующее:

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] 

это структура, чтобы представить график и что я считаю, хорошо, потому что его структура то же самое, что и один из его узлов, поэтому я могу использовать его непосредственно для инициирования поиска (как в глубине-первой). Печатная версия этого является:

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

И он может быть использован как:

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

Теперь, я хотел бы знать, как бы один реализовать в C++, C# и Java, не прибегая к Трюки «Объект», которые заполняли бы код уродливыми бросками. Для C++ я думал в templatemeta программирования, но что будет генерировать «конечные типы данных», когда то, что нужно что-то вроде

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

Answer 1

Вот простой хак:

#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]; 
    } 
}; 

Мы добавим ostream перегрузкам для печати:

#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; 
} 

E Xample использование:

#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; 
} 

Печать: [(2, [(1, *), (3, *), (8, *)]), (4, *)]

Дополнительные признаки могут быть легко добавлены; на данный момент мне не ясно, хотите ли вы, чтобы все узлы также поддерживали спутниковые данные («значения»), или могут ли только листовые узлы иметь значения или нет каких-либо дополнительных данных.

Answer 2

Для хранения либо дополнительные графики или «терминал» значения (на самом деле, оба эти подхода обобщать arbitarily много типов с любой интерпретации, до тех пор, как они могут быть перечислены в compiletime), можно использовать либо:

• Unions (возможно discriminated), или
• полиморфизм (в частности, подтип полиморфизм)

В любом случае у вас есть тип Graph, за которым вы можете скрыть как вложенные графики, так и сохраненные значения.

В C++, в частности, вы, вероятно, используете бывшие union или Boost::Variant (более типичные и удобные для обработки). Вам может потребоваться переслать объявление класса, чтобы оно было видно в момент его определения. Объединение предлагает достаточно места для хранения одного значения любого типа и (либо неявно в Boost::Variant, либо явно с обычным старым union) «тегом», указывающим, в каком именно случае. Затем вы можете просмотреть любое сохраненное значение и указать, является ли это другим графиком или значением терминала, и извлечь связанное значение.

В Java и C# у вас нет такой поддержки для типов прямого прямого соединения, поэтому вы использовали бы второй вариант. Существует интерфейс (или абстрактный) класс IGraph, с одной реализацией для графов (ссылка на IGraph) и одна для обертывания значений неграфа в другом подтипе IGraph. В основном вы используете политип подтипа. Это возможно и на C++, но создается впечатление, что объединение - это лучшая идея, если возможные типы известны заранее, вряд ли когда-либо изменятся и малочисленны. Это также позволяет избежать некоторых указателей/ссылок - и union s, и Boost::Variant s могут быть сохранены в стеке, в то время как полиморфизм требует косвенности.

Answer 3

В Java я бы пошел с классом Node, который представляет любой узел графика.

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; 
    } 
} 

Если вы хотите график, который будет содержать Int значения вы можете создать его экземпляр и использовать его:

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