Как хранить эквивалентности в алгоритме маркировки связных компонентов i Fortran

Мне нужно реализовать алгоритм маркировки подключенных компонентов Fortran. У меня есть четкое представление о том, как сканировать матрицу, но как насчет хранения и восстановления классов эквивалентности? Я предполагаю, что на многих других языках программирования это простая задача, но мне приходится делать это на Фортране. Как мне это сделать?

Первое редактирование: Следование псевдокоду в Википедии об алгоритме подключенных компонентов то, что я понятия не имею, как это сделать на Фортране, это

linked[label] = union(linked[label], L)


algorithm fortran fortran90
person emanuele    schedule 10.05.2012    source источник
comment
Фортран имеет свои сильные и слабые стороны (как и все языки программирования), но я не вижу причин, по которым то, что является простой задачей во многих других языках программирования, должно быть сложной задачей в Фортране. Возможно, если бы вы разместили какой-нибудь псевдокод или даже (шок, ужас!) разрабатываемый вами код на Фортране, мы могли бы помочь.   -  person High Performance Mark    schedule 10.05.2012
comment
Это очень широкий вопрос. Не могли бы вы быть немного более конкретным о том, что вы хотите знать?   -  person talonmies    schedule 10.05.2012
comment
Крики, статья в Википедии о маркировке подключенных компонентов даже содержит псевдокод, который я мог перевести почти построчно прямо на Фортран. В чем проблема ?   -  person High Performance Mark    schedule 10.05.2012
comment
Да, я знаю, что это широкий вопрос, но мне нужно только знать, как хранить классы эквивалентности. По-прежнему нет никакого кода, потому что я не знаю, как выполнить основную задачу, но я могу раскрыть свою проблему с большим количеством деталей.   -  person emanuele    schedule 10.05.2012
comment
@High Performance Mark Да, я видел этот псевдокод. Проблема в том, что я не знаю, как перевести часть, относящуюся к классам эквивалентности.   -  person emanuele    schedule 10.05.2012

Ответы (1)


arrow_upward
3
arrow_downward

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

  1. Используйте целые числа.
  2. Используйте символьные переменные длины 1 (или 2, или что угодно).
  3. Определите тип с любыми компонентами, которые вы хотите, чтобы он имел.

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

  1. Используйте массив меток (массив целых чисел, массив символов (длина = 2), массив типа (метка), не имеет значения), размер которого фиксируется во время компиляции. Вы должны быть достаточно уверены, что размер, который вы запрограммируете, всегда будет достаточно большим. Это не очень привлекательный подход; Я, вероятно, не должен был упоминать об этом.
  2. Используйте массив меток, размер которых задается во время выполнения. Это означает использование размещаемого массива. Вам нужно будет выяснить, как установить правильный размер во время выполнения, если это вообще возможно.
  3. Реализуйте тип, представляющий набор меток. Этот тип может, например, моделировать набор как связанный список. Но это не единственный способ смоделировать набор, тип может моделировать набор меток как массив и при необходимости выполнять некоторые причудливые действия для изменения размера массива. Определяя тип, конечно, вы даете себе свободу изменять внутреннее представление набора без изменения кода, использующего функциональные возможности, предоставляемые типом набора.

В зависимости от сделанного вами выбора должно быть достаточно просто реализовать функцию объединения для добавления новой метки к существующему набору меток.

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

Поскольку вы, кажется, новичок в Fortran, вот список языковых возможностей, с которыми вам необходимо ознакомиться для реализации вышеизложенного.

  1. Какая часть стандарта Fortran 2003 реализована вашим компилятором.
  2. Определение и использование производных типов.
  3. Распределяемые массивы, размещаемые массивы, перемещаемые распределения.
  4. Массивы производных типов.
  5. Процедуры с привязкой к типу.
  6. Указатели и цели.
person High Performance Mark    schedule 10.05.2012