объекта на основе граф представление в питоне

Question

В лекции Стэнфордского Алгоритмы, Prof Roughgarden перечислил следующие ингредиенты для списка смежности:

1. массива или список вешины
2. массив или список ребер
3. Каждой вершины Список вершин указывает на ребра, падающие на него.
4. Каждое ребро в списке краев указывает на его граничные точки.

Как это реализовать в python, особенно сочетание 3 и 4? Это было для меня проблемой. Я сделал это на C++ с указателями. Я могу думать об одном пути, пожалуйста, дайте мне знать, если вы считаете, что это правильно. Число 4 может быть выполнено с помощью набора кортежей Edges = [(1,2),(3,2),(4,1)] или добавить еще один элемент в кортеж для значения веса. Как заставить список вершин указывать на связанные с ним ребра? Vertices = {1 : [0,2] 2: [0,1] 3: [1] 4:[3]} Здесь Вершины - это словарь, а значение каждой клавиши (вершины) - это список индексов Edges, содержащих ключ (Vertex). Это кажется разумным?

Хорошо, я также дам его реализацию на С ++.

struct Node; 
struct Arcs; //Forward declarations as each of them references each other 
using namespace std 
struct SimpleGraph // Has all the nodes 
{ 
    set<Node *> nodes; 
    set<Arc *> arcs; 
} 
//Node contains node_number and the set of arcs/edges from this node. 
struct Node 
{ 
    int node_number; 
    set<Arc *> arcs; 
} 
// Arc contains start and finish node and the cost associated with the Arc/Edge 
struct Arc 
{ 
    Node* start; 
    Node* finish; 
    double cost; 
} 

Поскольку мы используем указатели на C++, изменение в Arc информации отражается в узле автоматически. Недостаток указателей затрудняет это в python. Поэтому я пытался сделать все, что мог.

Answer 1

В python в основном все есть объект, поэтому списки, дикты и карты также являются объектами и поэтому доступны через их адрес (так же, как C++ делает это, когда вы используете вызов по ссылке).

Посмотрите на следующий пример кода, который демонстрирует, что:

list_a = ['a', 'b', 'c'] 
list_b = ['d', 'e', 'f'] 

one_dict = {'entry1': list_a, 'entry2': list_b} 

def add_entry(target_list, entry): 
    target_list.append(entry) 

print("Our example dict:") 
print(one_dict) 

print("Modifying 'list_a' and 'list_b'.") 
list_a[1] = 'B' 
list_b[2] = 'F' 
print(list_a) 
print(list_b) 

print("Appending new entries to 'list_a' and 'list_b'") 
add_entry(list_a, 'q') 
add_entry(list_b, list_a) 
print(list_a) 
print(list_b) 

print("'list_a' and 'list_b' can still being accessed via 'one_dict'.") 
print(one_dict) 

Это выход, где вы можете ясно видеть, что one_dict держит ссылки на эти списки:

Our example dict: 
{'entry2': ['d', 'e', 'f'], 'entry1': ['a', 'b', 'c']} 
Modifying 'list_a' and 'list_b'. 
['a', 'B', 'c'] 
['d', 'e', 'F'] 
Appending new entries to 'list_a' and 'list_b' 
['a', 'B', 'c', 'q'] 
['d', 'e', 'F', ['a', 'B', 'c', 'q']] 
'list_a' and 'list_b' can still being accessed via 'one_dict'. 
{'entry2': ['d', 'e', 'F', ['a', 'B', 'c', 'q']], 'entry1': ['a', 'B', 'c', 'q']} 

Таким образом, реализация довольно проста, как и ваш код на C++.