Tworzenie w C#, C++ i Java silną wersję wpisywanych z pytona słabej struktury maszynowy

Question

W python Mam następujący:

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] 

jest to konstrukcja do reprezentowania wykresu i że znajdę dobre, bo jego struktury jest taki sam jak jeden z jego węzłów, więc mogę go użyć bezpośrednio do zainicjowania wyszukiwania (jak na początku). Wydrukowana wersja to jest:

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

i może być używany jak:

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

Teraz jestem ciekaw, jak można by zaimplementować w C++, C# i Java, bez uciekania się do Sztuczki "obiektowe", które wypełniłyby kod brzydkimi rzutami. Dla C++ myślałem w templatemeta programowania ale które generują „typy danych skończone”, kiedy potrzebne jest coś

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

Answer 1

Oto prosty 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]; 
    } 
}; 

Dodajemy kilka przeciążeń ostream do drukowania:

#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 Wykorzystanie:

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

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

Kolejne funkcje są łatwo dodanej; w tej chwili nie jest dla mnie jasne, czy wszystkie węzły mają obsługiwać dane satelitarne ("wartości"), czy też tylko węzły liści mogą mieć wartości lub jeśli nie ma żadnych dodatkowych danych.

Answer 2

do przechowywania albo dalszych wykresów lub wartości „Terminal” (w rzeczywistości, oba te podejścia uogólniać do arbitralnie wiele typów z dowolnej interpretacji, tak długo, jak mogą one być wyliczone na compiletime), należy użyć albo:

• Unions (ewentualnie discriminated) lub
• polimorfizm (konkretnie, polimorfizm podtyp)

W obu przypadkach istnieje typ Graph, za którym można ukryć zarówno zagnieżdżone wykresy, jak i zapisane wartości.

W C++ konkretnie prawdopodobnie używałbyś poprzedniej wersji union lub Boost::Variant (więcej bezpiecznych typów i wygodnych w obsłudze). Być może będziesz musiał przekazać dalej - deklaruj klasę, aby była widoczna w momencie jej zdefiniowania. Związek oferuje wystarczająco dużo miejsca do przechowywania jednej wartości dowolnego typu i (niejawnie w Boost::Variant lub jawnie ze zwykłym starym union) "znacznika" wskazującego, który z nich jest przypadkiem. Następnie można przyjrzeć się dowolnej zapisanej wartości i powiedzieć, czy jest to inny wykres lub wartość końcowa, i wyodrębnić powiązaną wartość.

W Javie i C# nie ma się tak wiele wsparcia dla prostych typów związków, więc używałbyś drugiej opcji. Istnieje interfejs (lub abstrakcyjna) klasa IGraph, z jedną implementacją dla wykresów (odnosząc się do IGraph s) i jedną do zawijania wartości innych niż graf w innym podtypie IGraph. Zasadniczo używasz polimorfizmu podtypu. Jest to również możliwe w C++, ale mam wrażenie, że związek jest lepszym pomysłem, jeśli możliwe typy są znane wcześniej, mało prawdopodobne, aby się kiedykolwiek zmieniły, i niewielka liczba. Pozwala także na uniknięcie niektórych wskazówek/odnośników - zarówno te union jak i Boost::Variant mogą być przechowywane na stosie, podczas gdy polimorfizm wymaga pośrednictwa.

Answer 3

W języku Java wybrałbym klasę węzła reprezentującą dowolny węzeł na wykresie.

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

Jeśli chcesz wykres, który będzie zawierał wartości int można instancji i używać go z:

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