Возможны ли иные операции на графах кроме тех, что уже используются? Возможны.
В первую очередь хотелось бы сказать, что суть очень проста. Используется запись Y=F(X) или, другими словами, next_state=action(current_state).
Два графа. Первый задан тремя вершинами {С, A, B} и тремя ребрами {(С,A), (A,B) (B,C)}, каждое из которых суть действие F. Имеем множество переходов {A=F(C), B=F(A), C=F(B)} и переменную Т, значением которой будет одно из состояний (вершин графа). Аналогично для нижнего графа. Переменная С будет принимать одно из состояний {R,W}. Таким образом, С является как переменной, так и состоянием (значением) переменной T. Что позволяет конструировать иерархические структуры.
В частности, описывать выражения языка типа: деревянный стол, стол отца или же функцию глагола как смену состояний. Подробнее здесь
Демонстрация раскрытия переменной
import tkinter as tk
import time
root=tk.Tk()
root.title('Раскрытие переменной на графе')
canvas=tk.Canvas(root,width=460,height=300)
canvas.pack()
canvas_text_T = canvas.create_text(
50, 30, font="DejavuSansLight",
text="T"
)
canvas_text_C = canvas.create_text(
50, 180, font="DejavuSansLight",
text="C"
)
canvas.create_oval(50,50,80,80,outline="blue",fill="white")
canvas.create_oval(90,90,120,120,outline="blue",fill="white")
canvas.create_oval(150,50,180,80,outline="blue",fill="white")
canvas.create_line(75, 75, 95, 95, arrow=tk.LAST)
canvas.create_line(118, 97, 155, 75, arrow=tk.LAST)
canvas.create_line(150, 65, 80, 65, arrow=tk.LAST)
canvas_text_c = canvas.create_text(35, 80, text="C")
canvas_text_f = canvas.create_text(90, 130, text="A")
canvas_text_b = canvas.create_text(190, 70, text="B")
circle_t = canvas.create_oval(50,50,80,80,outline="white",fill="blue")
###
canvas.create_oval(50,200,80,230,outline="blue",fill="white")
canvas.create_oval(150,200,180,230,outline="blue",fill="white")
canvas.create_line(80, 205, 153, 205, arrow=tk.LAST)
canvas.create_line(80, 225, 153, 225, arrow=tk.FIRST)
canvas_text_R = canvas.create_text(45, 235, text="R")
canvas_text_W = canvas.create_text(185, 235, text="W")
canvas.create_text(120, 215, text="E")
circle_c = canvas.create_oval(50,200,80,230,outline="white",fill="blue")
###
canvas.create_line(300, 70, 440, 70)
canvas.create_line(340, 40, 340, 110)
canvas.create_text(320, 50, text="T", font="DejavuSansLight", fill="blue")
canvas.create_text(360, 50, text="C", font="DejavuSansLight")
canvas.create_text(390, 50, text="A", font="DejavuSansLight")
canvas.create_text(420, 50, text="B", font="DejavuSansLight")
canvas.create_text(320, 90, text="F", font="DejavuSansLight")
canvas.create_text(360, 90, text="A", font="DejavuSansLight")
canvas.create_text(390, 90, text="B", font="DejavuSansLight")
canvas.create_text(420, 90, text="C", font="DejavuSansLight")
canvas.create_line(300, 230, 410, 230)
canvas.create_line(340, 200, 340, 270)
canvas.create_text(320, 210, text="C", font="DejavuSansLight", fill="blue")
canvas.create_text(360, 210, text="R", font="DejavuSansLight")
canvas.create_text(390, 210, text="W", font="DejavuSansLight")
canvas.create_text(320, 250, text="E", font="DejavuSansLight")
canvas.create_text(360, 250, text="W", font="DejavuSansLight")
canvas.create_text(390, 250, text="R", font="DejavuSansLight")
###
time1 = 0
time2 = 0
def new():
global time1, time2
if time1 %3 == 0:
canvas.move(circle_t,40,40)
canvas.itemconfigure(canvas_text_T, text="T=A")
if time1 %3 == 1:
canvas.move(circle_t,60,-40)
canvas.itemconfigure(canvas_text_T, text="T=B")
if time1 %3 == 2:
canvas.move(circle_t,-100,0)
canvas.itemconfigure(canvas_text_T, text="T=C")
if time2 %2 == 0:
canvas.itemconfigure(canvas_text_c, text="C=W")
canvas.itemconfigure(canvas_text_C, text="C=W")
canvas.move(circle_c,100,0)
else:
canvas.itemconfigure(canvas_text_c, text="C=R")
canvas.itemconfigure(canvas_text_C, text="C=R")
canvas.move(circle_c,-100,0)
time2 +=1
time1 +=1
def redraw():
canvas.after(1000,redraw)
new()
canvas.after(1000,redraw)
root.mainloop()В диаграммах состояниях UML часто рисуют кружок с чёрной точкой внутри. Смысл - отобразить прекращёние существования объекта, а не только отдельных состояний.
Вот типичный пример. Как только телефонный разговор перейдёт в состояние final state, то этого телефонного разговора уже нет, его ноль. Как такое выразить аналитически? Всегда ложной формулой (Х != Х). И наоборот, о телефонном разговоре можно сказать, что он есть, выразив формулой, которая всегда истина (Х == Х).
Более того, если мы говорим, что нет ничего третьего, предполагая смену разных состояний (Y после Х), то как это выразить аналитически? Так же! Всегда ложной формулой (X == Y), показывающей, что не бывает такого Х, которое было бы not X, и не бывает такого Y, которое было бы not Y. Подробнее здесь.
P.S. Спираль логики)) О выше сказанном.
n = int(input()) #размерность
mat = [[0]*n for i in range(n)] #матрица будет заполнена нулями
def spr(arr, k=0, num=1, t=0):
'''arr - заполняемая матрица
k - номер квадрата: если матрица 5*5, то 3 квадрата
(внешний, т.е. самый большой имеет k=0)
t - величина уменьшения стороны квадрата
num - число от 1 до n'''
n = len(arr) #размерность матрицы
for i in range(n-1 -t): #верхкняя сторона квадрата
arr[k][i+k] = num; num +=1
for i in range(n-1 -t): #правая сторона квадрата
arr[i+k][n-1 -k] = num; num +=1
for i in range(n-1 -t, 0, -1): #нижняя сторона квадрата
arr[n-1 -k][i+k] = num; num +=1
for i in range(n-1 -t, 0, -1): #левая сторона квадрата
arr[i+k][k] = num; num +=1
if not n%2 and num > n**2: #выход из рекурсии
return
if n%2 and num == n**2:
arr[n//2][n//2] = n**2
return
spr(arr, k+1, num, t+2) #рекурсия
spr(mat)
for i in mat:
print(*i)По сути, речь идёт о фазовом пространстве. Разница лишь в том, что каждое из состояний может либо быть, либо не быть. Это вырождённый случай количественных отношений в отношении (только) 0 и 1, в которых эти состояния могут находиться.
Для справки ... Фазовое пространство в математике и физике - пространство, каждая точка которой соответсвует одному и только одному состоянию из множества всех возможных состояний системы. Точка пространства, соответствующая состоянию системы называется изображающей или представляющей.
Причем, каждое из состояний или действий этого фазового пространства может быть переменной.
Комментарии (35)
gdt
06.04.2022 08:36+1Поздравляю, вы изобрели конечные автоматы
bvv2311 Автор
06.04.2022 08:43Можете дать ссылку где всЁ могло быть переменной, включая F?
gdt
06.04.2022 08:49Ссылку не дам, так как не совсем до конца понимаю, о чем идет речь (что есть F в вашей терминологии?) :) Однако конечные автоматы описываются конечным набором параметров - таких как функция перехода, множество допустимых состояний и т. д., и при определённом желании можно все их сделать переменными. Или например управлять одним конечным автоматом из другого.
bvv2311 Автор
06.04.2022 09:00F:X->Y ... о смысле F, где это F может быть переменной со своими значениями. Да, конечно автоматы. .... Были ли похожие реализации? Скорее всего да. ... В обобщенном виде не встречал. Ссылок вот Вы тоже не видели. ... Что дает? То, что избавившись от конкретики (того же телефонного автомата) можно работать с этой тройкой ... и выяснять что из них что: что F, что X, что Y (не зная заранее)
gdt
06.04.2022 08:57Вот смотря в код - у вас по факту два бесконечных автомата, состояние первого описывается выражением time1 % 3, второго - time2 % 2, соответственно когда первый автомат находится в третьем состоянии - он дает команду второму перейти в следующее состояние.
bvv2311 Автор
06.04.2022 09:22Все верно. Просто демонстрация для наглядности. ... Но автомат нижний не меняет состояния верхнего. С в нем остается С. Но при желании его можно трактовать и как смену R, W. (о монете можно сказать: монета, монета в состоянии решка, в состоянии орел) И то, и то верно... Такая логика применима к всему, включая F, E (в этой демонстрации). ... Соль не в этих конкретностях. Основное же - все есть переменная, сам подход (появляются иные возможности)
gdt
08.04.2022 10:00Вот допустим в своих шарпах я объявлю интерфейс провайдера значений, который возвращает произвольное значение (упрощенно, для наглядности):
interface IValueProvider<TValue> { TValue Get(); }Затем определим пару реализаций:
class First : IValueProvider<FirstState> { private FirstState _state = default; public enum FirstState { A, B, C } public void MoveNext() { _state = _state switch { FirstState.A => FirstState.B, FirstState.B => FirstState.C, FirstState.C => FirstState.A, } } public FirstState Get() { return _state; } } class Second : IValueProvider<SecondState> { private readonly IValueProvider<First.FirstState> _sourceStateProvider; private SecondState _state = default; public enum SecondState { R, W } public Second(IValueProvider<First.FirstState> sourceStateProvider) { _sourceStateProvider = sourceStateProvider; } public void MoveNext() { var sourceState = _sourceStateProvider.Get(); if (sourceState != First.FirstState.C) { return; } _state = _state switch { SecondState.R => SecondState.W, SecondState.W => SecondState.R, } } public SecondState Get() { return _state; } }Конечно придётся руками вызывать MoveNext для обоих классов, это легко обойти путем введения интерфейса по типу IValueChangedProvider. Используем наши классы:
var first = new First(); var second = new Second(first); for (var i = 0; i < 1000; i++) { first.MoveNext(); second.MoveNext(); Console.WriteLine("#{0} Step. First value - {1}, second value - {2}", i, first.Get(), second.Get()); }Вот если бы что-то такое было в статье, а не какой-то код рисующий два объекта, перемещающихся по строго заданной траектории, было бы гораздо проще. И согласитесь, графы тут совершенно ни при чем - можно нарисовать какие-то графы для этого кода, но нет никакой необходимости в графах, чтобы реализовать то, о чем вы говорите.
bvv2311 Автор
08.04.2022 10:25Не согласен. Вы мыслите как программист. ... Но в этой (очень короткой и наглядной) я больше о логике. .... Представьте мир, в котором вы видите только поток данных (см. здесь рис.3). Как в в таком мире узреть объекты, которые ... и влияют друг на друга, и могут являться частями друг друга? Повторюсь, данная статья в картинках (детская, можно сказать), но я хотел в ней показать саму парадигму, иначе взглянуть на происходящее, а именно: 1) что все есть переменная 2)что базовые вещи: быть, не-быть 3) и что фазовое пространство представимо именно графом.
gdt
08.04.2022 10:33Тут на самом деле неважно, как выполняется реализация. Это можно было сделать по ФП-шному, в процедурном стиле или ещё как-то - по крайней мере, это наглядный и доступный пример, взглянув на который сразу понятно, что происходит. ООП в данной ситуации - абстракция над потоками данных (как ни крути, а если хочется с этими потоками работать - какую-никакую абстракцию делать придётся). Собственно недопонимание у меня потому что:
все есть переменная
Это утверждение никак не связано с графами, как две произвольные прямые в пространстве - иногда они параллельные, иногда пересекаются, а иногда - скрещиваются.
базовые вещи: быть, не-быть
Наверное мне не достаёт контекста, вообще не понимаю о чем речь, и главное - при чем тут графы в первую очередь
фазовое пространство представимо именно графом
У меня к сожалению очень скудные знания на тему фазовых пространств, вы постулируете это утверждение и допустим я согласен. Что нам это дает, и как это связано с первоначальной мыслью о том, что все - переменная?
bvv2311 Автор
08.04.2022 11:04Единичный переход: F:X->Y
Из Х следует Y, при действии F (вершина-состояние, стрелка-действие, вершина-следующая )
И строим граф любой сложности. Причем это может делать сам алгоритм
P>S. причем F,Х,Y сами могут быть графами, если взглянуть внутрь них
bvv2311 Автор
08.04.2022 11:111) Y=F(X) простейший ориентированный граф: 2 вершины (Х, Y) и ориентированное ребро (F). 2) Каждое из них, в свою очередь, может быть тоже Y=F(X).
bvv2311 Автор
08.04.2022 11:16фазовое пространство Теперь представьте, что каждая точка его - это другое фазовое пространство, как и фазовое пространство - любая стрелка (очень маленькая на рис), и траектории которых получаются из (очень маленьких стрелок)
ЗЫ. Обычно такие вещи описываются диф. уравнениями. Если рассматривать только 0,1 ... а именно о них идет речь, все эти совокупности изменения (представляющей точки) описаны таблицами в состояниях (вырожденный случай количественных отношения в пределах лишь 0,1)
gdt
08.04.2022 11:25Да я понимаю, учился в университете на технической специальности, и всё это у нас было (правда давненько уже). Непонятно чего мы хотим добиться - ну можем сделать абстракцию над значением, позволяющую добавлять логику любой сложности так, чтобы снаружи это выглядело как просто значение - это классная мысль, но не новость, в ООП называется инкапсуляция такой подход. Можем воспользоваться формальной логикой для описания предметной области - эта идея тоже в целом не нова. Ну можем описать фазовое пространство графами, чего мы можем добиться теперь?
bvv2311 Автор
08.04.2022 11:34Спрошу в ответ: можете дать ссылку, где было бы показано ... как из потока данных понять ... что считать объектами и как эти объекты влияют друг на друга? ... Только не приводите конкретные примеры (лампа, стол, ...), нужно именно абстрактное решение
gdt
08.04.2022 11:37Справедливости ради у вас не абстрактное решение - а отрисовка двух объектов, которые двигаются по строго заданным траекториям. Вы хотите сказать, что граф сам себя построит и проанализирует любые потоки данных?) В любом случае придётся создавать абстракцию для таких задач. А как вы говорите, это больше на нейросети похоже
gdt
08.04.2022 12:00Ну все равно у вас по сути там набор конечных автоматов, которые кто-то должен описать и соединить между собой прежде всего и наполнить данными, анализ всего этого это отдельная тема. Этап формирования таблиц и связей между ними как мне кажется упущен, там сразу постулируется - вот у нас есть такие-то таблицы)
gdt
08.04.2022 12:20Исходные данные представлены на рис.1 и собраны в 3 таблицы: таблица 10, таблица 20, таблица 30. Верхняя строка каждой таблицы отображает одно из возможных текущих состояний, левый столбец таблицы ее возможное действие.
Если собрать все переходы, то получим таблицу Замогилья.
Выходит все же кто-то должен собирать таблицу переходов, этого к сожалению не увидел.
gdt
08.04.2022 12:27Так и я о том же, у вас на рис. 1 уже данные собраны в таблицы, с состояниями, действиями и возможными переходами
bvv2311 Автор
08.04.2022 12:54в 1 таб чем эти три объекта являются.... Далее как мы их первоначально видим (рис 3) ... И далее из анализа этого потока данных алгоритм понимает что и как перед ним
gdt
08.04.2022 12:40Понятно, спасибо, всегда интересно поговорить с умным человеком, вы уж меня извините за дотошность, очень хотелось понять что происходит. Написали комментариев уже ещё на парочку таких статей :) Предлагаю добавить в статью ссылки на другие ваши статьи, чтобы была возможность понять, к чему это всё.
gdt
08.04.2022 11:39Лучше покажите конкретный пример, как вы делаете то, что описываете, при помощи этого аппарата, как этот аппарат понимает, что считать объектами, и как они влияют друг на друга? Только не приводите конкретные примеры, как в статье (лампа, стол, ...)
gdt
08.04.2022 11:57Вот по этим ссылкам более конкретно, факт, однако первый комментарий передает то, что я хотел сказать.
alex103
Вы бы хоть предметную область ваших графов описали..
А то граф - это толи картинка, толи муж графини.. Операции возможны и там и там..
Предположу: граф-процессы? сети Петри? Конечные автоматы?
bvv2311 Автор
Вход F, выход Y в зависимости от Х. Каждое из этих Y, F, Х может быть выражены своими переходами. Поэтому суть: Y, F, Х могут быть тоже переменными.
zuko3d
В универе нам рассказывали, что граф - это множество вершин и рёбер. При чём тут входы, выходы и переменные?
bvv2311 Автор
При том, что такой подход позволяет из множества не структурированных данных получать на выходе объекты, в том числе иерархично устроенные. Как здесь