Thuật toán giảm chuyển tiếp: mã giả?

Question

Tôi đã tìm kiếm một thuật toán để thực hiện việc giảm chuyển tiếp trên biểu đồ, nhưng không thành công. Không có gì trong thuật toán của tôi kinh thánh (Giới thiệu về thuật toán của Cormen et al) và trong khi tôi đã nhìn thấy rất nhiều mã giả đóng cửa chuyển tiếp, tôi đã không thể theo dõi bất cứ điều gì để giảm. Gần nhất tôi đã có là có một trong "Algorithmische Graphentheorie" của Volker Turau (ISBN: 978-3-486-59057-9), nhưng tiếc là tôi không có quyền truy cập vào cuốn sách này! Wikipedia là vô ích và Google vẫn chưa bật lên bất cứ điều gì. :?.^(

Có ai biết của một thuật toán để thực hiện giảm bắc cầu

Answer 1

Các Wikipedia article trên điểm giảm bắc cầu để thực hiện một trong GraphViz (đó là mã nguồn mở) Không hẳn là giả, nhưng có lẽ một nơi nào đó để bắt đầu ?

LEDA bao gồm transitive reduction algorithm. Tôi không có bản sao của LEDA book nữa và chức năng này có thể đã được thêm sau khi sách được xuất bản. Nhưng nếu ở đó, sẽ có mô tả hay về thuật toán.

Google trỏ đến an algorithm mà ai đó đã đề xuất đưa vào Boost. Tôi không cố gắng đọc nó, vì vậy có lẽ không đúng?

Ngoài ra, this có thể đáng xem.

Answer 2

Các ý chính cơ bản của thuật toán giảm bắc cầu tôi sử dụng là

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

Thuật toán đóng bắc cầu tôi sử dụng trong cùng một kịch bản rất giống nhưng dòng cuối cùng là

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

Answer 3

Thuật toán của "girlwithglasses" quên rằng một cạnh dự phòng có thể kéo dài một chuỗi ba cạnh. Để sửa, tính Q = R x R + trong đó R + là đóng cửa chuyển tiếp và sau đó xóa tất cả các cạnh từ R hiển thị trong Q. Xem thêm bài viết trên Wikipedia.

Answer 4

Xem Harry Hsu. "Thuật toán tìm đồ thị tương đương tối thiểu của một biểu đồ", Tạp chí ACM, 22 (1): 11-16, January 1975. Thuật toán khối đơn giản dưới đây (sử dụng ma trận đường N x N) đủ cho DAG, nhưng Hsu tổng quát nó thành đồ thị tuần hoà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; 

Answer 5

thuật toán Depth-đầu tiên trong pseudo-python:

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) 

Thuật toán là phụ tối ưu, nhưng giao dịch với các vấn đề đa cạnh nhịp trong những giải pháp trước. Kết quả rất giống với kết quả của graphviz.

Answer 6

Dựa trên tham chiếu do Alan Donovan cung cấp, cho biết bạn nên sử dụng ma trận đường dẫn (có 1 nếu có đường dẫn từ nút i đến nút j) thay vì ma trận kề (chỉ có 1) có một cạnh từ nút i đến nút j).

Một số mã python mẫu sau bên dưới để hiển thị sự khác biệt giữa các giải pháp

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') 

Output:

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 

Answer 7

được chuyển đến java/jgrapht, mẫu python trên trang này từ @ 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))); 
       } 
      } 
     } 
    } 
} 

kiểm tra đơn vị:

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); 
     } 
    } 
} 

kiểm tra 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