У меня есть несколько узлов и ребер

 nodes = [
  { id: 'n1', propositions: ['p'] },
  { id: 'n2', propositions: ['p'] },
  { id: 'n3', propositions: ['p'] }
];
edges = [
  { source: 'n1', target: 'n2' },
  { source: 'n2', target: 'n1' },
  { source: 'n1', target: 'n3' },
  { source: 'n2', target: 'n3' }
];
  

Как видно из данных, два узла n1 и n2 указывают друг на друга, и оба n1 и n2 указывают друг на n3 друга.

Я пытаюсь реализовать алгоритм на http://homepages.cwi.nl /~jve/courses/lai0506/LAI11.pdf#страница = 25 в JavaScript.

Насколько я понимаю, начальный раздел будет иметь только один блок, содержащий все три узла n1 , n2 , и n3 . Второй раздел будет иметь n1 и n2 в одном подблоке, и n3 в другом подблоке. Третий раздел будет таким же, как и второй раздел, поэтому итерация будет остановлена. И, как я понял, все узлы в подблоке являются избыточными, кроме одного, поэтому я могу просто удалить их и сохранить только один.

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

То, что я придумал до сих пор, это

 /**
 * Initial partition
 **/

// blocks in initial partition
const partition = {};

// group nodes into blocks based on propositions
nodes.forEach(function (node) {
  // use propositions as key
  const key = node.propositions.sort().join();

  // create block if it does not already exists
  if (!partition[key]) {
    partition[key] = [];
  }

  // add node to block
  partition[key].push(node);
});

/**
 * Iterate until P_{i} = P_{i - 1}
 **/

// repeat until Pi_{i} = Pi_{i-1}
while (true) {
  // get ready to partition each block in the partition into subblocks
  const newPartition = {};

  // go through each block in partition
  Object.keys(partition).forEach(function (blockName) {
    // get block by blockName
    const nodesInBlock = partition[blockName];

    // go through each node in the block
    nodesInBlock.forEach(function (sourceNode) {
        // ...
        // ...

        // create subblock if it doesn't already exists
        if (!newPartition[key]) {
          newPartition[key] = [];
        }

        // add node to subblock
        newPartition[key].push(sourceNode);
      });
    }
  });

  // if nothing changed
  if (Object.keys(partition).length === Object.keys(newPartition).length) {
    break;
  } else {
    partition = newPartition;
  }
}
}
  

Но я не знаю, что делать вместо фрагмента, где я написал ... .

Я предполагаю, что я должен получить имя блока, на который указывает узел (т. Е. Имя блока целевого узла), а затем создать ключ из имени блока исходного узла и имени блока целевого узла. Я просто не знаю, как это сделать. Со страницы 27 реализация описана на языке Haskell, но я не понимаю Haskell, поэтому мне это не поможет.

Редактировать

Я думаю, разделы должны выглядеть так

 // data:
nodes = [
  { id: 'n1', propositions: ['p'] },
  { id: 'n2', propositions: ['p'] },
  { id: 'n3', propositions: ['p'] }
];
edges = [
  { source: 'n1', target: 'n2' },
  { source: 'n2', target: 'n1' },
  { source: 'n1', target: 'n3' },
  { source: 'n2', target: 'n3' }
];

// initial partition
initialPartition = [
  { id: 'n1', propositions: ['p'] },
  { id: 'n2', propositions: ['p'] },
  { id: 'n3', propositions: ['p'] }
];

// second partition
secondPartition = [
  [
    { id: 'n1', propositions: ['p'] },
    { id: 'n2', propositions: ['p'] }
  ],
  { id: 'n3', propositions: ['p'] }
];

// third partition
thirdPartition = [
  [
    { id: 'n1', propositions: ['p'] },
    { id: 'n2', propositions: ['p'] }
  ],
  { id: 'n3', propositions: ['p'] }
];
  

Итак, поскольку второй и третий равны, процесс итерации останавливается.