Un algoritmo topologia può ordinare una raccolta di dati in base ad alcune serie di regole che hai specificato, dove non tutte le coppie hanno un ordine predefinito.
Tipicamente le regole definiscono solo un ordinamento parziale, quindi ci sono più ordini possibili e l'ordinamento topologico sceglie un arbitrario. Se c'è una contraddizione nelle regole che hai specificato, non ci sarà alcun ordine possibile.
Se puoi dare una risposta vero / falso / non so per qualsiasi coppia di elementi in tempo costante, IIRC ci sono algoritmi sequenziali che ordinano topologicamente in tempo lineare - O (Vertices + Bordi), come menzionato nei commenti qui di seguito.
Una contraddizione nei vincoli sorge se, e solo se, c'è un ciclo nei vincoli. Pertanto, è utile identificare i " principali componenti strongmente connessi " nel digrafo dei vincoli.
Potrebbe anche essere utile far crescere la serie iniziale di vincoli per includere tutti i possibili vincoli che possono essere provati direttamente o indirettamente da quel gruppo di semi. In generale, il set risultante è considerato "chiuso" rispetto alla funzione usata per trovare nuovi membri, quindi gli algoritmi che crescono in questo modo sono "algoritmi di chiusura" - da non confondere con una chiusura lessicale. Particolari chiusure di set spesso citate algebra astratta WRT includono chiusure simmetriche (se a? B è nel tuo set, aggiungi anche b? A), chiusure riflessive (se a? B è nel tuo set, aggiungi anche a? A eb? B) e chiusure transitive (se a? b eb sono nel tuo set, aggiungi anche un? c).
Le relazioni d'ordine sono transitive - se a < be eb < c poi a < c - così la chiusura transitiva di la serie di vincoli potrebbe essere utile.
Potresti anche voler identificare gruppi di elementi che sono ordinati l'uno rispetto all'altro (senza assumere alcuna contraddizione) senza preoccuparsi inizialmente dell'ordine. Questo definisce un partizionamento degli elementi in classi di equivalenza, dato un senso di equivalenza in-the-same-cluster. Per fare ciò, potresti usare una struttura dei set disgiunti / union-find - le classi di equivalenza sono disgiunte le une dalle altre quindi ogni classe di equivalenza è un insieme disgiunto dagli altri. L'operazione dell'unione dall'unione trova fondamentalmente "qualunque sia la classe in cui si trovano questi due elementi, combinare quelle classi in una singola classe, se necessario". Il "find" determina in quale classe si trova un particolare elemento, di solito scegliendo un elemento per rappresentare quella classe.
Un tema comune in tutto questo è la teoria dei grafici, anche se gli aspetti provengono dall'algebra astratta e altrove. Fondamentalmente, la relazione a < b può essere modellata come un bordo su un grafico tra vertici che rappresentano gli elementi a e b. Se ti interessa l'ordine, questo è un grafico diretto.
Ad esempio, una relazione x < y apparirà nella chiusura transitiva del set iniziale di vincoli se entrambi x e y si trovano nella stessa componente strongmente connessa del digramma.
Mi dispiace, mi sono confuso sopra - la relazione x & yt apparirà nella chiusura transitiva se c'è qualche percorso tra xey nel digraph, ma ciò non implica un componente strongmente connesso. Un componente strongmente connesso richiede un ciclo, non solo un percorso.