Переходный алгоритм сокращения: псевдокод?

Ответ 1

Смотрите Гарри Хсу. "Алгоритм поиска минимального эквивалентного графа орграфа". Журнал ACM, 22 (1): 11-16, январь 1975 г. Для DAG достаточно простого кубического алгоритма ниже (с использованием матрицы N x N) но Хсу обобщает его на циклические графы.

// reflexive reduction
for (int i = 0; i < N; ++i)
  m[i][i] = false;

// transitive reduction
for (int j = 0; j < N; ++j)
  for (int i = 0; i < N; ++i)
    if (m[i][j])
      for (int k = 0; k < N; ++k)
        if (m[j][k])
          m[i][k] = false;

Ответ 2

Основной смысл используемого алгоритма переходной редукции -

foreach x in graph.vertices
   foreach y in graph.vertices
      foreach z in graph.vertices
         delete edge xz if edges xy and yz exist

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

         add edge xz if edges xy and yz OR edge xz exist

Ответ 3

Статья Википедии о переходных сокращениях указывает на реализацию в GraphViz (который является открытым исходным кодом). Не совсем псевдокод, но, возможно, где-нибудь начать?

LEDA включает в себя переходный алгоритм сокращения. У меня больше нет копии книги LEDA, и эта функция могла быть добавлена ​​после публикации книги. Но если он там, то будет хорошее описание алгоритма.

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

Кроме того, this может стоить внимания.

Ответ 4

Алгоритм "girlwithglasses" забывает, что избыточный край может охватывать цепочку из трех ребер. Чтобы исправить, вычислить Q = R x R +, где R + - транзитивное замыкание, а затем удалить все ребра из R, которые отображаются в Q. См. Также статью в Википедии.

Ответ 5

Основываясь на ссылке, предоставленной Аланом Донованом, в которой говорится, что вы должны использовать матрицу путей (которая имеет 1, если есть путь от node я до node j) вместо матрицы смежности (которая имеет 1, только если есть ребро от node я до node j).

Ниже приведен пример кода примера python, чтобы показать различия между решениями

def prima(m, title=None):
    """ Prints a matrix to the terminal """
    if title:
        print title
    for row in m:
        print ', '.join([str(x) for x in row])
    print ''

def path(m):
    """ Returns a path matrix """
    p = [list(row) for row in m]
    n = len(p)
    for i in xrange(0, n):
        for j in xrange(0, n):
            if i == j:
                continue
            if p[j][i]:
                for k in xrange(0, n):
                    if p[j][k] == 0:
                        p[j][k] = p[i][k]
    return p

def hsu(m):
    """ Transforms a given directed acyclic graph into its minimal equivalent """
    n = len(m)
    for j in xrange(n):
        for i in xrange(n):
            if m[i][j]:
                for k in xrange(n):
                    if m[j][k]:
                        m[i][k] = 0

m = [   [0, 1, 1, 0, 0],
        [0, 0, 0, 0, 0],
        [0, 0, 0, 1, 1],
        [0, 0, 0, 0, 1],
        [0, 1, 0, 0, 0]]

prima(m, 'Original matrix')
hsu(m)
prima(m, 'After Hsu')

p = path(m)
prima(p, 'Path matrix')
hsu(p)
prima(p, 'After Hsu')

Вывод:

Adjacency matrix
0, 1, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 1
0, 0, 0, 0, 1
0, 1, 0, 0, 0

After Hsu
0, 1, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 1
0, 1, 0, 0, 0

Path matrix
0, 1, 1, 1, 1
0, 0, 0, 0, 0
0, 1, 0, 1, 1
0, 1, 0, 0, 1
0, 1, 0, 0, 0

After Hsu
0, 0, 1, 0, 0
0, 0, 0, 0, 0
0, 0, 0, 1, 0
0, 0, 0, 0, 1
0, 1, 0, 0, 0

Ответ 6

Первый алгоритм в псевдопитоне:

for vertex0 in vertices:
    done = set()
    for child in vertex0.children:
        df(edges, vertex0, child, done)

df = function(edges, vertex0, child0, done)
    if child0 in done:
        return
    for child in child0.children:
        edge.discard((vertex0, child))
        df(edges, vertex0, child, done)
    done.add(child0)

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

Ответ 7

портирован на java/jgrapht, образец python на этой странице от @Michael Clerx:

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

import org.jgrapht.DirectedGraph;

public class TransitiveReduction<V, E> {

    final private List<V> vertices;
    final private int [][] pathMatrix;

    private final DirectedGraph<V, E> graph;

    public TransitiveReduction(DirectedGraph<V, E> graph) {
        super();
        this.graph = graph;
        this.vertices = new ArrayList<V>(graph.vertexSet());
        int n = vertices.size();
        int[][] original = new int[n][n];

        // initialize matrix with zeros
        // --> 0 is the default value for int arrays

        // initialize matrix with edges
        Set<E> edges = graph.edgeSet();
        for (E edge : edges) {
            V v1 = graph.getEdgeSource(edge);
            V v2 = graph.getEdgeTarget(edge);

            int v_1 = vertices.indexOf(v1);
            int v_2 = vertices.indexOf(v2);

            original[v_1][v_2] = 1;
        }

        this.pathMatrix = original;
        transformToPathMatrix(this.pathMatrix);
    }

    // (package visible for unit testing)
    static void transformToPathMatrix(int[][] matrix) {
        // compute path matrix 
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) { 
                if (i == j) {
                    continue;
                }
                if (matrix[j][i] > 0 ){
                    for (int k = 0; k < matrix.length; k++) {
                        if (matrix[j][k] == 0) {
                            matrix[j][k] = matrix[i][k];
                        }
                    }
                }
            }
        }
    }

    // (package visible for unit testing)
    static void transitiveReduction(int[][] pathMatrix) {
        // transitively reduce
        for (int j = 0; j < pathMatrix.length; j++) { 
            for (int i = 0; i < pathMatrix.length; i++) {
                if (pathMatrix[i][j] > 0){
                    for (int k = 0; k < pathMatrix.length; k++) {
                        if (pathMatrix[j][k] > 0) {
                            pathMatrix[i][k] = 0;
                        }
                    }
                }
            }
        }
    }

    public void reduce() {

        int n = pathMatrix.length;
        int[][] transitivelyReducedMatrix = new int[n][n];
        System.arraycopy(pathMatrix, 0, transitivelyReducedMatrix, 0, pathMatrix.length);
        transitiveReduction(transitivelyReducedMatrix);

        for (int i = 0; i <n; i++) {
            for (int j = 0; j < n; j++) { 
                if (transitivelyReducedMatrix[i][j] == 0) {
                    // System.out.println("removing "+vertices.get(i)+" -> "+vertices.get(j));
                    graph.removeEdge(graph.getEdge(vertices.get(i), vertices.get(j)));
                }
            }
        }
    }
}

unit test:

import java.util.Arrays;

import org.junit.Assert;
import org.junit.Test;

public class TransitiveReductionTest {

    @Test
    public void test() {

        int[][] matrix = new int[][] {
            {0, 1, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 1, 1},
            {0, 0, 0, 0, 1},
            {0, 1, 0, 0, 0}
        };

        int[][] expected_path_matrix = new int[][] {
            {0, 1, 1, 1, 1},
            {0, 0, 0, 0, 0},
            {0, 1, 0, 1, 1},
            {0, 1, 0, 0, 1},
            {0, 1, 0, 0, 0}
        };

        int[][] expected_transitively_reduced_matrix = new int[][] {
            {0, 0, 1, 0, 0},
            {0, 0, 0, 0, 0},
            {0, 0, 0, 1, 0},
            {0, 0, 0, 0, 1},
            {0, 1, 0, 0, 0}
        };

        System.out.println(Arrays.deepToString(matrix) + " original matrix");

        int n = matrix.length;

        // calc path matrix
        int[][] path_matrix = new int[n][n];
        {
            System.arraycopy(matrix, 0, path_matrix, 0, matrix.length);

            TransitiveReduction.transformToPathMatrix(path_matrix);
            System.out.println(Arrays.deepToString(path_matrix) + " path matrix");
            Assert.assertArrayEquals(expected_path_matrix, path_matrix);
        }

        // calc transitive reduction
        {
            int[][] transitively_reduced_matrix = new int[n][n];
            System.arraycopy(path_matrix, 0, transitively_reduced_matrix, 0, matrix.length);

            TransitiveReduction.transitiveReduction(transitively_reduced_matrix);
            System.out.println(Arrays.deepToString(transitively_reduced_matrix) + " transitive reduction");
            Assert.assertArrayEquals(expected_transitively_reduced_matrix, transitively_reduced_matrix);
        }
    }
}

test ouput

[[0, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1], [0, 1, 0, 0, 0]] original matrix
[[0, 1, 1, 1, 1], [0, 0, 0, 0, 0], [0, 1, 0, 1, 1], [0, 1, 0, 0, 1], [0, 1, 0, 0, 0]] path matrix
[[0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 1], [0, 1, 0, 0, 0]] transitive reduction