Как реализовать на python в виде списка смежности такой граф?

Question

[habrdima]

в интернете не нашел реализацию именно с разными ориентациями, по отдельности примеры слишком похожи

Answer 1

[Vindicar]

Если именно список смежности - то это список пар вида "исходная вершина - конечная вершина". Тогда для связи между A и C будет две пары - одна в одну сторону, одна в другую.
С точки зрения структур данных это будет список кортежей (я бы использовал typing.NamedTuple или collections.namedtuple, ну или хотя бы dataclass).

Если речь про таблицу смежности, то будет обычная двухмерная таблица (например, список списков), только она будет несимметричной. Т.е. наличие 1 в элементе i,j не означает наличия 1 в элементе j,i.

Comments

[habrdima]

мне надо понять как различать разные стрелки
(A,B)
(B,A)
(B,B)
что делать для C-D и D->B?
(C,D)
(D,"->", B)
правильно? или есть более адекватное решение?

[Vindicar]

habrdima, ну это тебя надо спрашивать, чем C-D отличается от A<->С. Рисунок-то кривой.
Для B всё просто, там куда стрелку ни направь, результат один.
А так направление перехода определяется автоматически по начальной и конечной вершине. Двусторонние переходы - это на самом деле два перехода, скажем, (A,B) и (B,A).

[habrdima]

Vindicar, я хочу знать как люди в целом обозначают ориентированную дугу если в графе есть и неориентированная дуга

[Vindicar]

habrdima, я же написал. Если в графе есть ориентированные дуги - значит, граф ориентированный. А раз так, то неориентированная дуга - это должна быть пара ориентированных дуг, идущих в противоположных направлениях.

[habrdima]

Vindicar, так вопрос как это показать в коде python, а вы про картинку и термины

А так направление перехода определяется автоматически по начальной и конечной вершине.

если взять C-D то можно это показать как (C,D), но D->B уже так (D,B)не показать, иначе разницу не понять
может быть так сделать?
{"n": (C,D)} #неориентированный граф
{"o": (D,B)} #ориентированный граф
{"oo": [(A,C),(C,A)]} #ориентированный в обе стороны

есть лучше решение?

[Vindicar]

habrdima,
C-D можно показать как ..., (C, D), (D, C), ...
D->B будет просто ..., (D, B), ...
А вопросы про картинку и термины, потому что если неясно задание, то неясен и ответ.

[habrdima]

Vindicar, об этом варианте я думал

C-D можно показать как ..., (C, D), (D, C), ...
D->B будет просто ..., (D, B), ...

но как тогда совместить (C,D),(D,C) с A->C, C->A? ведь надо указать что есть одна дуга в обе стороны, и две дуги

[Vindicar]

habrdima, ну тогда добавь какой-то третий признак, например, ориентированность ребра графа.
Скажем, (A, B, True) будет означать ориентированное ребро из A в B, а (A, B, False) будет означать неориентированное ребро между A и B.

[habrdima]

Vindicar, так то разные конечно можно придумать варианты, просто думал что есть известный вариант котор используют все, но почему то ни где не нахожу

[Vindicar]

habrdima, смешанные графы вообще редкая штука, обычно они либо ориентированные, либо неориентированные.