Come ordinare dipendeva oggetti da dipendenza
https://stackoverflow.com/questions/4106862
-
29-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho una collezione:
List<VPair<Item, List<Item>> dependencyHierarchy;
Il primo elemento di una coppia è un oggetto (item) e il secondo è una raccolta dello stesso tipo di oggetti che la prima dipende.Voglio ottenere un List<Item> in ordine di dipendenza, quindi non ci sono elementi che dipendono dal primo elemento e così via (non pedalato dipendenza!).
Ingresso:
Item4 depends on Item3 and Item5 Item3 depends on Item1 Item1 does not depend on any one Item2 depends on Item4 Item5 does not depend on any one
Risultato:
Item1 Item5 Item3 Item4 Item2
Grazie.
SOLUZIONE:
Ordinamento Topologico (grazie a Loïc Février per l'idea)
e
esempio in C#, esempio in Java (grazie a xcud per grandi esempi)
Soluzione
Esempio perfetto per utilizzare un ordinamento topologico:
http://en.wikipedia.org/wiki/Topological_sorting
Gli darà esattamente quello che ti serve.
Altri suggerimenti
Dopo aver lottato con questo per un po ', ecco il mio tentativo di un metodo di estensione Tsort stile Linq:
public static IEnumerable<T> TSort<T>( this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle = false )
{
var sorted = new List<T>();
var visited = new HashSet<T>();
foreach( var item in source )
Visit( item, visited, sorted, dependencies, throwOnCycle );
return sorted;
}
private static void Visit<T>( T item, HashSet<T> visited, List<T> sorted, Func<T, IEnumerable<T>> dependencies, bool throwOnCycle )
{
if( !visited.Contains( item ) )
{
visited.Add( item );
foreach( var dep in dependencies( item ) )
Visit( dep, visited, sorted, dependencies, throwOnCycle );
sorted.Add( item );
}
else
{
if( throwOnCycle && !sorted.Contains( item ) )
throw new Exception( "Cyclic dependency found" );
}
}
C'è un NuGet per che .
Per quelli di noi che non preferiscono di re-inventare la ruota: NuGet uso per installare la libreria QuickGraph .NET, che include più algoritmi grafico compreso topologica sort .
Per utilizzarlo, è necessario creare un'istanza di AdjacencyGraph<,> come AdjacencyGraph<String, SEdge<String>>. Quindi, se si includono le estensioni appropriate:
using QuickGraph.Algorithms;
È possibile chiamare:
var sorted = myGraph.TopologicalSort();
Per ottenere un elenco di nodi ordinati.
Mi è piaciuta la risposta di DMM, ma presuppone che i nodi di input sono le foglie (che può o non può essere quello che ci si aspetta).
Vi metto una soluzione alternativa utilizzando LINQ che non fa questa ipotesi. Inoltre, questo utilizza la soluzione yield return essere in grado di tornare rapidamente le foglie (utilizzando per esempio TakeWhile).
public static IEnumerable<T> TopologicalSort<T>(this IEnumerable<T> nodes,
Func<T, IEnumerable<T>> connected)
{
var elems = nodes.ToDictionary(node => node,
node => new HashSet<T>(connected(node)));
while (elems.Count > 0)
{
var elem = elems.FirstOrDefault(x => x.Value.Count == 0);
if (elem.Key == null)
{
throw new ArgumentException("Cyclic connections are not allowed");
}
elems.Remove(elem.Key);
foreach (var selem in elems)
{
selem.Value.Remove(elem.Key);
}
yield return elem.Key;
}
}
Questo è il mio re-implementazione di topologica ordinamento, l'idea si basa su http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html (Il porting Java consuma codice sorgente troppa memoria, controllando 50k oggetti costi 50k * 50K * 4 = 10 GB che è inaccettabile. Inoltre, ha ancora Java codifica convention alcuni posti)
using System.Collections.Generic;
using System.Diagnostics;
namespace Modules
{
/// <summary>
/// Provides fast-algorithm and low-memory usage to sort objects based on their dependencies.
/// </summary>
/// <remarks>
/// Definition: http://en.wikipedia.org/wiki/Topological_sorting
/// Source code credited to: http://tawani.blogspot.com/2009/02/topological-sorting-and-cyclic.html
/// Original Java source code: http://www.java2s.com/Code/Java/Collections-Data-Structure/Topologicalsorting.htm
/// </remarks>
/// <author>ThangTran</author>
/// <history>
/// 2012.03.21 - ThangTran: rewritten based on <see cref="TopologicalSorter"/>.
/// </history>
public class DependencySorter<T>
{
//**************************************************
//
// Private members
//
//**************************************************
#region Private members
/// <summary>
/// Gets the dependency matrix used by this instance.
/// </summary>
private readonly Dictionary<T, Dictionary<T, object>> _matrix = new Dictionary<T, Dictionary<T, object>>();
#endregion
//**************************************************
//
// Public methods
//
//**************************************************
#region Public methods
/// <summary>
/// Adds a list of objects that will be sorted.
/// </summary>
public void AddObjects(params T[] objects)
{
// --- Begin parameters checking code -----------------------------
Debug.Assert(objects != null);
Debug.Assert(objects.Length > 0);
// --- End parameters checking code -------------------------------
// add to matrix
foreach (T obj in objects)
{
// add to dictionary
_matrix.Add(obj, new Dictionary<T, object>());
}
}
/// <summary>
/// Sets dependencies of given object.
/// This means <paramref name="obj"/> depends on these <paramref name="dependsOnObjects"/> to run.
/// Please make sure objects given in the <paramref name="obj"/> and <paramref name="dependsOnObjects"/> are added first.
/// </summary>
public void SetDependencies(T obj, params T[] dependsOnObjects)
{
// --- Begin parameters checking code -----------------------------
Debug.Assert(dependsOnObjects != null);
// --- End parameters checking code -------------------------------
// set dependencies
Dictionary<T, object> dependencies = _matrix[obj];
dependencies.Clear();
// for each depended objects, add to dependencies
foreach (T dependsOnObject in dependsOnObjects)
{
dependencies.Add(dependsOnObject, null);
}
}
/// <summary>
/// Sorts objects based on this dependencies.
/// Note: because of the nature of algorithm and memory usage efficiency, this method can be used only one time.
/// </summary>
public T[] Sort()
{
// prepare result
List<T> result = new List<T>(_matrix.Count);
// while there are still object to get
while (_matrix.Count > 0)
{
// get an independent object
T independentObject;
if (!this.GetIndependentObject(out independentObject))
{
// circular dependency found
throw new CircularReferenceException();
}
// add to result
result.Add(independentObject);
// delete processed object
this.DeleteObject(independentObject);
}
// return result
return result.ToArray();
}
#endregion
//**************************************************
//
// Private methods
//
//**************************************************
#region Private methods
/// <summary>
/// Returns independent object or returns NULL if no independent object is found.
/// </summary>
private bool GetIndependentObject(out T result)
{
// for each object
foreach (KeyValuePair<T, Dictionary<T, object>> pair in _matrix)
{
// if the object contains any dependency
if (pair.Value.Count > 0)
{
// has dependency, skip it
continue;
}
// found
result = pair.Key;
return true;
}
// not found
result = default(T);
return false;
}
/// <summary>
/// Deletes given object from the matrix.
/// </summary>
private void DeleteObject(T obj)
{
// delete object from matrix
_matrix.Remove(obj);
// for each object, remove the dependency reference
foreach (KeyValuePair<T, Dictionary<T, object>> pair in _matrix)
{
// if current object depends on deleting object
pair.Value.Remove(obj);
}
}
#endregion
}
/// <summary>
/// Represents a circular reference exception when sorting dependency objects.
/// </summary>
public class CircularReferenceException : Exception
{
/// <summary>
/// Initializes a new instance of the <see cref="CircularReferenceException"/> class.
/// </summary>
public CircularReferenceException()
: base("Circular reference found.")
{
}
}
}
I renderebbe questo più facile su me stesso, memorizzando le dipendenze di un elemento all'interno della voce stessa:
public class Item
{
private List<Item> m_Dependencies = new List<Item>();
protected AddDependency(Item _item) { m_Dependencies.Add(_item); }
public Item()
{
}; // eo ctor
public List<Item> Dependencies {get{return(m_Dependencies);};}
} // eo class Item
Poi, dato questo è possibile implementare un ordinamento personalizzato per delegare List che i tipi a seconda che l'oggetto mostrato è contenuto all'interno dell'altro lista delle dipendenze:
int CompareItem(Item _1, Item _2)
{
if(_2.Dependencies.Contains(_1))
return(-1);
else if(_1.Dependencies.Contains(_2))
return(1);
else
return(0);
}
Un un'idea diversa, per i casi con un solo "padre" a seconda:
Invece di dipendenze, che ci si memorizzano i genitori.
Così si può dire molto facilmente se un problema è una dipendenza di qualche altro.
E quindi utilizzare Comparable<T>, che avrebbe rivendicare le dipendenze "minore" e la dipendenza "maggiori".
E poi semplicemente chiamare Collections.sort( List<T>, ParentComparator<T>);
Per lo scenario multi-genitore, un albero di ricerca sarebbe necessario che si tradurrebbe in esecuzione lenta. Ma che potrebbero essere risolti da una cache in una forma di matrice A * ordinamento.
ho fuso l'idea di DMM con l'algoritmo in profondità-ricerca su Wikipedia. Funziona perfetto per quello che mi serviva.
public static class TopologicalSorter
{
public static List<string> LastCyclicOrder = new List<string>(); //used to see what caused the cycle
sealed class ItemTag
{
public enum SortTag
{
NotMarked,
TempMarked,
Marked
}
public string Item { get; set; }
public SortTag Tag { get; set; }
public ItemTag(string item)
{
Item = item;
Tag = SortTag.NotMarked;
}
}
public static IEnumerable<string> TSort(this IEnumerable<string> source, Func<string, IEnumerable<string>> dependencies)
{
TopologicalSorter.LastCyclicOrder.Clear();
List<ItemTag> allNodes = new List<ItemTag>();
HashSet<string> sorted = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
foreach (string item in source)
{
if (!allNodes.Where(n => string.Equals(n.Item, item, StringComparison.OrdinalIgnoreCase)).Any())
{
allNodes.Add(new ItemTag(item)); //don't insert duplicates
}
foreach (string dep in dependencies(item))
{
if (allNodes.Where(n => string.Equals(n.Item, dep, StringComparison.OrdinalIgnoreCase)).Any()) continue; //don't insert duplicates
allNodes.Add(new ItemTag(dep));
}
}
foreach (ItemTag tag in allNodes)
{
Visit(tag, allNodes, dependencies, sorted);
}
return sorted;
}
static void Visit(ItemTag tag, List<ItemTag> allNodes, Func<string, IEnumerable<string>> dependencies, HashSet<string> sorted)
{
if (tag.Tag == ItemTag.SortTag.TempMarked)
{
throw new GraphIsCyclicException();
}
else if (tag.Tag == ItemTag.SortTag.NotMarked)
{
tag.Tag = ItemTag.SortTag.TempMarked;
LastCyclicOrder.Add(tag.Item);
foreach (ItemTag dep in dependencies(tag.Item).Select(s => allNodes.Where(t => string.Equals(s, t.Item, StringComparison.OrdinalIgnoreCase)).First())) //get item tag which falls with used string
Visit(dep, allNodes, dependencies, sorted);
LastCyclicOrder.Remove(tag.Item);
tag.Tag = ItemTag.SortTag.Marked;
sorted.Add(tag.Item);
}
}
}
Questo è il codice refactoring dal post https://stackoverflow.com/a/9991916/4805491 .
// Version 1
public static class TopologicalSorter<T> where T : class {
public struct Item {
public readonly T Object;
public readonly T Dependency;
public Item(T @object, T dependency) {
Object = @object;
Dependency = dependency;
}
}
public static T[] Sort(T[] objects, Func<T, T, bool> isDependency) {
return Sort( objects.ToList(), isDependency ).ToArray();
}
public static T[] Sort(T[] objects, Item[] dependencies) {
return Sort( objects.ToList(), dependencies.ToList() ).ToArray();
}
private static List<T> Sort(List<T> objects, Func<T, T, bool> isDependency) {
return Sort( objects, GetDependencies( objects, isDependency ) );
}
private static List<T> Sort(List<T> objects, List<Item> dependencies) {
var result = new List<T>( objects.Count );
while (objects.Any()) {
var obj = GetIndependentObject( objects, dependencies );
RemoveObject( obj, objects, dependencies );
result.Add( obj );
}
return result;
}
private static List<Item> GetDependencies(List<T> objects, Func<T, T, bool> isDependency) {
var dependencies = new List<Item>();
for (var i = 0; i < objects.Count; i++) {
var obj1 = objects[i];
for (var j = i + 1; j < objects.Count; j++) {
var obj2 = objects[j];
if (isDependency( obj1, obj2 )) dependencies.Add( new Item( obj1, obj2 ) ); // obj2 is dependency of obj1
if (isDependency( obj2, obj1 )) dependencies.Add( new Item( obj2, obj1 ) ); // obj1 is dependency of obj2
}
}
return dependencies;
}
private static T GetIndependentObject(List<T> objects, List<Item> dependencies) {
foreach (var item in objects) {
if (!GetDependencies( item, dependencies ).Any()) return item;
}
throw new Exception( "Circular reference found" );
}
private static IEnumerable<Item> GetDependencies(T obj, List<Item> dependencies) {
return dependencies.Where( i => i.Object == obj );
}
private static void RemoveObject(T obj, List<T> objects, List<Item> dependencies) {
objects.Remove( obj );
dependencies.RemoveAll( i => i.Object == obj || i.Dependency == obj );
}
}
// Version 2
public class TopologicalSorter {
public static T[] Sort<T>(T[] source, Func<T, T, bool> isDependency) {
var list = new LinkedList<T>( source );
var result = new List<T>();
while (list.Any()) {
var obj = GetIndependentObject( list, isDependency );
list.Remove( obj );
result.Add( obj );
}
return result.ToArray();
}
private static T GetIndependentObject<T>(IEnumerable<T> list, Func<T, T, bool> isDependency) {
return list.First( i => !GetDependencies( i, list, isDependency ).Any() );
}
private static IEnumerable<T> GetDependencies<T>(T obj, IEnumerable<T> list, Func<T, T, bool> isDependency) {
return list.Where( i => isDependency( obj, i ) ); // i is dependency of obj
}
}
Non mi piace metodi ricorsivi così DMM è fuori.Krumelur sembra buono, ma sembra di usare un sacco di memoria?Fatta un'alternativa stack in base al metodo che sembra funzionare.Usa la stessa DFS logica DMM 's e ho usato questa soluzione come confronto in fase di test.
public static IEnumerable<T> TopogicalSequenceDFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> deps)
{
HashSet<T> yielded = new HashSet<T>();
HashSet<T> visited = new HashSet<T>();
Stack<Tuple<T, IEnumerator<T>>> stack = new Stack<Tuple<T, IEnumerator<T>>>();
foreach (T t in source)
{
stack.Clear();
if (visited.Add(t))
stack.Push(new Tuple<T, IEnumerator<T>>(t, deps(t).GetEnumerator()));
while (stack.Count > 0)
{
var p = stack.Peek();
bool depPushed = false;
while (p.Item2.MoveNext())
{
var curr = p.Item2.Current;
if (visited.Add(curr))
{
stack.Push(new Tuple<T, IEnumerator<T>>(curr, deps(curr).GetEnumerator()));
depPushed = true;
break;
}
else if (!yielded.Contains(curr))
throw new Exception("cycle");
}
if (!depPushed)
{
p = stack.Pop();
if (!yielded.Add(p.Item1))
throw new Exception("bug");
yield return p.Item1;
}
}
}
}
Anche qui è più semplice stack in base BFS variante.Produrrà risultati diversi da quelli sopra, ma ancora valido.Non so se c'è qualche vantaggio per il DFS utilizzando la variante di cui sopra, ma è stato divertente creazione.
public static IEnumerable<T> TopologicalSequenceBFS<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> dependencies)
{
var yielded = new HashSet<T>();
var visited = new HashSet<T>();
var stack = new Stack<Tuple<T, bool>>(source.Select(s => new Tuple<T, bool>(s, false))); // bool signals Add to sorted
while (stack.Count > 0)
{
var item = stack.Pop();
if (!item.Item2)
{
if (visited.Add(item.Item1))
{
stack.Push(new Tuple<T, bool>(item.Item1, true)); // To be added after processing the dependencies
foreach (var dep in dependencies(item.Item1))
stack.Push(new Tuple<T, bool>(dep, false));
}
else if (!yielded.Contains(item.Item1))
throw new Exception("cyclic");
}
else
{
if (!yielded.Add(item.Item1))
throw new Exception("bug");
yield return item.Item1;
}
}
}
Per .NETTO di 4,7+ suggerisco di sostituire Tupla con ValueTuple per il basso utilizzo della memoria.In più .NET versioni Tupla può essere sostituito con KeyValuePair.
