algoritmo di riduzione transitivo: pseudocodice?

Question

Ho cercato un algoritmo per eseguire una riduzione transitoria su un grafico, ma senza successo. Non c'è nulla nella mia Bibbia degli algoritmi (Introduzione agli algoritmi di Cormen et al) e mentre ho visto molti pseudocodici di chiusura transitiva, non sono stato in grado di rintracciare nulla per una riduzione. Il più vicino che ho è che ce n'è uno in "Algorithmische Graphentheorie" di Volker Turau (ISBN: 978-3-486-59057-9), ma sfortunatamente non ho accesso a questo libro! Wikipedia è inutile e Google deve ancora rivelare nulla. :?.^(

Qualcuno sa di un algoritmo per l'esecuzione di una riduzione transitiva

Answer 1

La Wikipedia article sui punti di riduzione transitiva a un'implementazione entro GraphViz (che è open source) Non esattamente pseudocodice, ma forse da qualche parte per iniziare ?

LEDA include uno transitive reduction algorithm. Non ho più una copia di LEDA book e questa funzione potrebbe essere stata aggiunta dopo la pubblicazione del libro. Ma se è lì, quindi ci sarà una buona descrizione del Algoritmo

Google punta a an algorithm che qualcuno ha suggerito per l'inclusione in Boost. Non ho provato a leggerlo, quindi forse non è corretto?

Inoltre, this potrebbe valere la pena dare un'occhiata.

Answer 2

La sostanza di base dell'algoritmo di riduzione transitiva che ho usato è

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

L'algoritmo chiusura transitiva ho usato nello stesso script è molto simile, ma l'ultima riga è

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

Answer 3

L'algoritmo di "girlwithglasses" dimentica che un bordo ridondante può estendersi su una catena di tre bordi. Per correggere, calcola Q = R x R + dove R + è la chiusura transitiva e poi elimina tutti i bordi da R che appaiono in Q. Vedi anche l'articolo di Wikipedia.

Answer 4

Vedere Harry Hsu. "Un algoritmo per trovare un grafico equivalente minimo di un digrafo.", Journal of the ACM, 22 (1): 11-16, January 1975. Il semplice algoritmo cubico di seguito (usando una matrice di percorso N x N) è sufficiente per i DAG, ma Hsu lo generalizza ai grafici ciclici.

// 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

algoritmo Depth-first in pseudo-pitone:

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) 

L'algoritmo è sub-ottimale, ma affronta il problema multi-bordo-portata delle soluzioni precedenti. I risultati sono molto simili a quelli prodotti da graphviz.

Answer 6

Sulla base del riferimento fornito da Alan Donovan, che dice che dovresti usare la matrice di percorso (che ha un 1 se c'è un percorso dal nodo i al nodo j) invece della matrice di adiacenza (che ha un 1 solo se c'è un vantaggio dal nodo I al nodo j).

Alcuni codice Python di esempio segue qui sotto per mostrare le differenze tra le soluzioni

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

uscita:

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

portato su java/JGraphT, il campione pitone in questa pagina da @ 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:

01.235.164,106174 millions

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

prova 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