Предложения по графоподобной структуре данных

Question

Мне нужна структура данных для представления графа в виде модели.

• У него есть узлы с входами и выходами.
• Эти входы и выходы могут быть связаны по ссылкам.
• Один вход может быть подключен максимум к одному выходу.
• Один выход может быть подключен к нескольким входам.

Две операции над выполненными чаще всего:

• Объединение двух моделей (связывание некоторых входов с выходами).
• Замена подграфа другим.

Какая структура данных лучше всего подходит для представления этой модели?

EDIT

Я буду использовать его как часть моего компилятора. Эта модель представляет вычисления, где узлы являются вычислительными блоками, а ссылки - это данные, передаваемые между ними.

Мне нужно построить эту модель из исходного кода. Вот почему мне нужно объединить работу. Я буду обрабатывать исходный код оператор за оператором и корректировать модель, добавляя новые этапы вычислений.

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

Answer 1

Используя комбинацию модульной системы Haskells и конструктора newtype, определите newtype, который оборачивает граф, но не экспортирует его конструктор из модуля. Вместо того, чтобы предоставлять конструктор, предоставьте методы для построения и работы с вашей графоподобной структурой, которая реализует требуемые инварианты. Это будет выглядеть примерно так:

module SpecialGraph 
  ( SpecialGraph --not e.g. SpecialGraph(..)
  , specialGraph) where

import Graph

newtype SpecialGraph = Sg Graph 

specialGraph :: Graph -> Maybe SpecialGraph
specialGraph gr = ...

Базовая библиотека Graph, на которой вы будете основывать свой новый тип, может быть одной из нескольких библиотек, найденных в Hackage. Я использовал fgl, «Библиотека функциональных графов», и мне нравится.

В вашем компиляторе вы бы импортировали этот модуль и работали с SpecialGraph через функции, которые он предоставляет.

Это стандартный подход к решению проблем, который не имеет простого представления только для ADT. Общая идея здесь заключается в том, что мы ограничиваем более общую структуру данных на уровне терминов (нормальные выражения haskell). Графики fgl реализованы аналогичным образом, являясь ограничениями и утилитами для различных типов Maps, которые, в свою очередь (я считаю), основаны на ограничениях и утилитах на базовых деревьях.

Answer 2

У вас действительно есть большая свобода делать то, что вы хотите здесь: главная проблема, которую нужно обойти, состоит в том, что простые ADT не дают вам изменяемые ссылки. Вот несколько примеров, которые вы могли бы использовать, чтобы начать. Вы можете даже захотеть использовать более одного и конвертировать между ними.

-- Here we have a pair of int indexed maps: the first one associates each
-- vertex index with a vertex value and a list of edge indices, and the
-- second one associates each edge index with an edge value and a pair of
-- vertex indices.
data Graph e v = Graph (M.Map Int (v, [Int])) (M.Map Int (e,Int,Int))

-- Here we use mutable references
newtype Graph s e v = Graph (STRef s (v,[(e,Graph s e v)]))

-- Here we use a single map and assume each vertex value is unique
newtype Graph e v = Graph (M.map v [(e,v)])

-- Single map again: but using ints to distinguish the vertices
newtype Graph e v = Graph (M.map Int (v,[(e,Int)]))

Answer 3

Вот косвенный ответ. Неопределенность вашего вопроса указывает на то, что вы можете быть новичком в Хаскеле, простите меня, если я ошибся.

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

Вот ADT для очень простого императивного языка, чтобы подогреть аппетит:

data Statement
    = Assign String Expr
    | Print Expr
    | If Expr Statement Statement
    | Block [Statement]

data Expr
    = Variable String
    | Add Expr Expr
    | Multiply Expr Expr
    | Constant Integer

Обычный способ сделать язык - определить подобный тип, соответствующий возможностям вашего языка, и организовать большую часть работы вокруг этого типа. Вы используете парсер , чтобы получить реальный исходный код для этого представления.

Я слышал хорошие новости о Создание схемы за 48 часов как введение в Haskell, так и простая реализация языка программирования с использованием стандартных инструментов.

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

Удачи!