transitive algorithme de réduction: pseudo-code?

J'ai été à la recherche d'un algorithme pour effectuer une réduction transitive sur un graphique, mais sans succès. Il n'y a rien dans mon algorithmes de la bible (Introduction Aux Algorithmes par Cormen et al) et même si j'ai vu l'abondance de la fermeture transitive de pseudo, je n'ai pas été en mesure de traquer n'importe quoi pour une réduction. Le plus proche que j'ai est qu'il y en a un dans "Algorithmische Graphentheorie" de Volker Turau (ISBN:978-3-486-59057-9), mais malheureusement je n'ai pas accès à ce livre! Wikipédia est inutile et Google est encore rien. :^(

Personne ne sait d'un algorithme pour l'exécution d'une réduction transitive?

InformationsquelleAutor i alarmed alien | 2009-11-06

14

Voir Harry Hsu. "Un algorithme pour trouver un minimum de graphe équivalent d'un digraphe.", Journal de l'ACM, 22(1):11-16, janvier 1975. Le simple cube algorithme ci-dessous (à l'aide d'un N x N chemin de la matrice) suffit pour les DAGs, mais Hsu généralise à cycliques graphiques.
```
//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;
```
- (pour les DAGs) En d'autres termes: regarder chaque arête (i,j), les supprimer si il y a une raison pour ne pas être dans la réduction transitive. Les bords pas enlevé doit être à l'intérieur de la réduction transitive.
- Selon la référence que vous citez, vous devriez commencer à partir de la trajectoire de la matrice, et non pas la matrice de contiguïté
- Cela ne fonctionne pas pour tous les cas. Dans un graphe dont les arêtes (A,B), (B,C), (C,D) et (A,D) la dernière arête (A,D) devrait être supprimé. Il n'est pas, car il n'y a pas de combinaison des deux bords (m[i][j] et m[j][k]) qui mène de A à D.
- tout à fait raison, je voulais dire le chemin de la matrice. Merci d'avoir signalé l'erreur. Si vous disposez d'une matrice de contiguïté, appliquer Warshal du premier algorithme de transitivement la fermer.
InformationsquelleAutor Alan Donovan
8

Le sens de base de la transitives algorithme de réduction que j'ai utilisé est
```
foreach x in graph.vertices
   foreach y in graph.vertices
      foreach z in graph.vertices
         delete edge xz if edges xy and yz exist
 
```
La fermeture transitive de l'algorithme que j'ai utilisé dans le même script est très similaire, mais la dernière ligne est
```
         add edge xz if edges xy and yz OR edge xz exist
```
- Vous devez ajouter if (x,z) != (x,y) && (x,z) != (y,z) avant delete edge... d'éviter les erreurs de délétions dans le cas de cycles. Autre que cela, et bien que ce serait mieux d'avoir un linéaire plus rapide en temps de l'algorithme, j'aime cette réponse: simple et sympathique.
- Aussi, si le graphe a des cycles, cet algorithme ne permet pas toujours de produire le minimum transitive de réduction. Par exemple, essayez sur [0,1,2,3,4,5] où Un des points de B pour tous A et B (même quand ils sont les mêmes). Il devrait produire quelque chose comme 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 0, mais l'exécution de cet algorithme (avec mon tweak) apporte 5 -> 2 et 5 -> 4 en plus de l'0 -> ... -> 5 -> 0. Le courant sans mon tweak ne produit pas de bords à tous.
- J'aurais dit que mon code inclus vérifie l'identique les bords que vous avez mentionné, et aussi que je suis en train de travailler uniquement avec les groupes de disponibilité, de sorte que les cycles ne sont pas un problème.
- Êtes-vous sûr de votre algorithme de fermeture transitive? Pour cette tâche, je l'utiliserais de Floyd-Warshall de l'algorithme, qui est foreach y in graph.vertices: foreach x in graph.vertices: foreach z in graph.vertices: add edge xz if edges xy and yz exist OR edge xz exist. Remarque l'ordre différent dans x et y. Je pensais que l'ordre d'importance. Il n'en a pas?
- Comme l'a noté le cmn, thi algorithme est clair arêtes qui relient les nœuds qui sont également reliés par un chemin qui a plus de deux bords. Exemple: A -> B -> C -> D; A -> C; A-> D. L'algorithme clair -> C, mais pas Un -> D.
- Yep, cela ne fonctionne pas pour tous les groupes de disponibilité. Voir Penz/cmn
InformationsquelleAutor i alarmed alien
3

La Article de Wikipedia sur transitive de réduction de points pour une mise en œuvre au sein de GraphViz (qui est open source). Pas exactement de pseudo, mais peut-être un endroit où commencer?

LEDA comprend un transitive algorithme de réduction. Je n'ai pas de copie de la LEDA livre, et de plus, cette fonction pourrait avoir été ajouté après le livre a été publié. Mais si il est là, puis il y aura une bonne description de l'algorithme.

Google points de un algorithme que quelqu'un a suggéré d'inclure dans Boost. Je n'ai pas essayer de le lire, donc peut-être pas correct?

Aussi, cette peut-être en valeur un regard.
- Merci (en retard!) pour votre réponse. En fin de compte, j'ai contacté l'auteur de l'un des algorithmes de livre et lui a demandé de vérifier si certains pseudo-code que j'ai écrit est correct, qu'il a gentiment fait.
- Le tred code source est à peine lisible grâce à l'absence de tout commentaire dans le code.
InformationsquelleAutor Eric
3

L'algorithme de "girlwithglasses" oublie que redondant bord pourrait s'étendre sur une chaîne de trois bords. Pour corriger, calculer Q = R x R+ R+ est la fermeture transitive, puis supprimez tous les bords de R dans Q. Voir aussi l'article de Wikipedia.
- Pouvez-vous suggérer quelques pseudo-code pour faire cela? La transitives algorithme de réduction affichés ci-dessous irait sur la fermeture transitive graphique, donc, pour une arête de x-y, qui peut également être atteint par x-A-En, vous aussi, vous avez x-A-y et x-Par.
- Qu'est-ce que Q censé représenter? Que faites-vous avec elle?
InformationsquelleAutor cmh
3

Basé sur la référence fournie par Alan Donovan, qui dit que vous devez utiliser le chemin d'accès de la matrice (qui a un 1 s'il existe un chemin d'accès du nœud i au nœud j) au lieu de la matrice de contiguïté (qui a 1 seulement si il existe une arête du nœud i au nœud j).

Quelques exemples de code python ci-dessous pour afficher les différences entre les solutions
```
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')
```
De sortie:
```
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
```
- Je suis perplexe, car il semble que, si vous avez supprimé les bords dans le bon ordre, vous pourriez obtenir le droit de retour à l'original (redondant) matrice de contiguïté par l'application de l'algorithme sur le chemin de la matrice. Donc, fondamentalement, vous avez obtenu nulle part. Voir cet exemple: i.imgur.com/fbt6oK1.png Dites que vous commencez avec seulement les bords noirs, et bien sûr, vous voulez éliminer le pointillé noir/vert. Si vous ajoutez les bords rouges pour obtenir le chemin d'accès de la matrice. Ensuite, vous enlevez les bords rouges, car ils peuvent à la fois être retiré par l'algorithme. Et maintenant, vous êtes coincé.
- À l'aide de m = [[0, 1, 0, 1], [0, 0, 1, 0], [0, 0, 0, 1], [0, 0, 0, 0]] comme entrée fonctionne très bien 🙂
- Je pense qu'Il peut travailler aussi longtemps que vous n'êtes pas malheureux sur les bords de qui sont supprimés en premier.
- L'essayer, la commande ne fait aucune différence.
- OK, désolé, vous avez raison, je ne trouve pas de cas où le pointillé noir/vert est supprimé avant que les deux rouges eges. Quand je rentre à la maison ce soir, je vais essayer de comprendre pourquoi cela se produit.
InformationsquelleAutor Michael Clerx

Profondeur d'abord de l'algorithme en 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)

L'algorithme n'est pas optimal, mais il traite avec le multi-bord-span problème des solutions précédentes. Les résultats sont très similaires à ce tred de graphviz produit.

InformationsquelleAutor Penz

porté à java /jgrapht, le python échantillon sur cette page à partir de @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)));
                }
            }
        }
    }
}

de test de l'unité :

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 de sortie

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

Pour votre information, une demande d'extraction avec une version remaniée de ce code a été soumis, accepté et fusionnés en jgrapht. github.com/jgrapht/jgrapht/commit/...

InformationsquelleAutor cthiebaud

Vous devez vous connecter pour publier un commentaire.