Mengurangi tepi yang berlebihan dari grafik ketergantungan

8

Saya memiliki DAG dependensi yang berisi banyak tepi yang berlebihan (lihat contoh di bawah). Saya ingin algoritma "cepat" (mis. Dapat menangani grafik dengan beberapa ribu node / tepi) yang menemukan sub grafik minimal.

Sebagai contoh:

A -> B -> C
A -> C

dalam kata-kata A adalah prasyarat untuk B, dan B adalah prasyarat untuk C, dan juga A adalah prasyarat untuk C. Dalam hal ini A -> C berlebihan (karena B sudah perlu untuk mencapai C, dan A perlu untuk mencapai B) .

Sudah lama sejak saya mempelajari algoritma, dan saya tidak yakin harus mulai dari mana.

By the way, itu tidak penting bahwa algoritma menemukan minimum global, minimum lokal baik-baik saja (pengurangan tepi hanya optimasi runtime untuk tahap pemrosesan selanjutnya).

Juga, saya menyadari ini adalah CS QA dan bukan pemrograman, tetapi program saya ditulis dalam Python, jadi saya akan sangat senang mengetahui modul python atau open source untuk melakukan pengurangan ini, kalau-kalau Anda tahu itu.

Terima kasih sebelumnya!

ds.algorithms graph-algorithms transitive-reduction Iftah
sumber
Saya ingin tahu apakah DFS dapat membantu di sini?
Pratik Deoghare
3
Anda mencari "pengurangan transitif" dari grafik ketergantungan Anda.
Dave Clarke
Temukan komponen yang terhubung kuat. Hanya sisakan satu sisi di antara setiap pasang komponen. Untuk setiap komponen yang terhubung kuat, Anda harus menemukan jumlah siklus minimal yang akan menutupinya. Menemukan jumlah minimum siklus tampaknya NP-lengkap karena akan menentukan Hamiltonicity, tetapi karena Anda hanya memerlukan minimal lokal hanya menghapus tepi dari setiap komponen sampai kehilangan konektivitas yang kuat.
Kaveh

Jawaban:

13

Pengurangan Transitif dari Sutradara Grafik AV Aho, MR Garey, dan JD Ullman

Menurut wikipedia , algoritma ini digunakan oleh tredyang merupakan alat untuk reduksi transitif yang tersedia dalam paket GraphViz. Anda dapat menjalankannya di grafik dan mengurangi grafik.

Pertanyaan ini merupakan duplikat dari pertanyaan stackoverflow ini .

kode di sini graphviz/tools/src/tred.c tidak menggunakan DFS. ;-)

Pratik Deoghare
sumber
2
Saya tidak tahu tred, terima kasih.
Anthony Labarre
1
MachineCharmer terima kasih. Saya di luar universitas dan tidak dapat mengunduh makalah tanpa membayar $ 25 ... apakah ada sumber daring gratis yang menjelaskan algoritme ini? Sumber tred kecil dan mudah dibaca, tetapi tanpa penjelasan.
Iftah
Tidak. Tidak ada tautan unduhan gratis untuk makalah itu. Tapi Anda mungkin punya teman di beberapa universitas :)
Pratik Deoghare
-1

Saya akhirnya menyelesaikannya dengan cara ini:

Struktur data saya terbuat dari dependendskamus, dari id node ke daftar node yang bergantung padanya (mis. Pengikutnya di DAG).

Saya belum menghitung kompleksitas persisnya, tetapi menelan grafik saya beberapa ribu dalam sepersekian detik.

_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
sumber