Reduzieren redundanter Kanten aus einem Abhängigkeitsdiagramm

8

Ich habe eine DAG von Abhängigkeiten, die viele redundante Kanten enthält (siehe Beispiel unten). Ich möchte einen "schnellen" Algorithmus (dh kann ein Diagramm mit mehreren tausend Knoten / Kanten verarbeiten), der ein minimales Subdiagramm findet.

Zum Beispiel:

A -> B -> C
A -> C

in Worten A ist Voraussetzung für B und B ist Voraussetzung für C und auch A ist Voraussetzung für C. In diesem Fall ist A -> C redundant (da B bereits erforderlich ist, um C zu erreichen, und A erforderlich ist, um B zu erreichen) .

Es ist schon eine Weile her, seit ich Algorithmen studiert habe, und ich bin mir nicht sicher, wo ich anfangen soll.

Übrigens ist es nicht kritisch, dass der Algorithmus das globale Minimum findet, das lokale Minimum ist in Ordnung (die Kantenreduzierung ist nur eine Laufzeitoptimierung für die nächste Verarbeitungsstufe).

Mir ist auch klar, dass dies eine CS-Qualitätssicherung ist und keine Programmierung, aber mein Programm ist in Python geschrieben. Daher würde ich mich besonders freuen, wenn ich ein Python-Modul oder Open Source für diese Reduzierung kennenlernen würde, falls Sie davon wissen.

Danke im Voraus!

ds.algorithms graph-algorithms transitive-reduction Iftah
quelle
Ich habe mich gefragt, ob die DFS hier helfen könnte.
Pratik Deoghare
3
Sie suchen nach der "transitiven Reduktion" Ihres Abhängigkeitsgraphen.
Dave Clarke
Finden Sie die stark verbundenen Komponenten. Lassen Sie zwischen jedem Komponentenpaar nur eine Kante. Für jede stark verbundene Komponente müssen Sie eine minimale Anzahl von Zyklen finden, die sie abdecken würden. Das Finden einer Mindestanzahl von Zyklen scheint NP-vollständig zu sein, da dies die Hamiltonizität bestimmt. Da Sie jedoch nur ein lokales Minimum benötigen, entfernen Sie einfach die Kanten von jeder Komponente, bis die starke Konnektivität verloren geht.
Kaveh

Antworten:

13

Die transitive Reduktion eines gerichteten Graphen AV Aho, MR Garey und JD Ullman

Laut Wikipedia wird dieser Algorithmus verwendet, mit dem treddas im GraphViz-Paket verfügbare Tool zur transitiven Reduktion verfügbar ist. Sie können es in Ihrem Diagramm ausführen und ein reduziertes Diagramm erhalten.

Diese Frage ist ein Duplikat dieser Stackoverflow-Frage .

Code hier graphviz/tools/src/tred.c tut DFS Verwendung. ;-);

Pratik Deoghare
quelle
2
Ich wusste es nicht tred, danke.
Anthony Labarre
1
Vielen Dank, dass Sie MachineCharmer. Ich bin außerhalb einer Universität und kann das Papier nicht herunterladen, ohne 25 $ zu zahlen. Gibt es eine kostenlose Online-Quelle, die diesen Algorithmus beschreibt? Die Tred-Quelle ist klein und lesbar, aber ohne Erklärungen.
Iftah
Nein. Für dieses Papier gibt es keinen kostenlosen Download-Link. Aber Sie könnten Freunde an einer Universität haben :)
Pratik Deoghare
-1

Am Ende habe ich es so gelöst:

Meine Datenstruktur besteht aus einem dependendsWörterbuch, von einer Knoten-ID bis zu einer Liste von Knoten, die davon abhängen (dh ihren Followern in der DAG).

Ich habe die genaue Komplexität nicht berechnet, aber es hat meine Grafik von mehreren Tausend in Sekundenbruchteilen verschluckt.

_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]
Iftah
quelle