Il tuo algoritmo potrebbe assomigliare alla teoria dei grafi. Capisco che gli elenchi gerarchici sopra sono mostrati per semplicità. Date le vostre esigenze, i limiti di una struttura gerarchica sono rivelati!
I nodi devono essere gestiti prima che possano essere elaborati. Il mio approccio a questo problema, non avendo uno sfondo nelle strutture del grafo, sarebbe di rivedere prima il materiale sulle strutture del grafo, ad esempio questo questo e questo e ottenere i miei dati codificati con loro . Fatto ciò, elaborare e analizzare le strutture, ad esempio creare un hash che conta i genitori, ordinare l'elenco in base al conteggio e generare una nuova rappresentazione gerarchica senza modificare il grafico sottostante.
ad esempio, prendendo a prestito dal codice nel primo link , in python3
class Vertex:
def __init__(self, key):
self.id = key
self.connected_to = {}
def add_neighbor(self, nbr, weight=0):
self.connected_to[nbr] = weight
def __str__(self):
return str(self.id) + ' connected_to: ' + str([x.id for x in self.connected_to])
def get_connections(self):
return self.connected_to.keys()
def get_id(self): return self.id
def get_weight(self, nbr): return self.connected_to[nbr]
class Graph:
def __init__(self):
self.vert_list = {}
self.num_vertices = 0
def add_vertex(self, key):
self.num_vertices += 1
new_vertex = Vertex(key)
self.vert_list[key] = new_vertex
return new_vertex
def get_vertex(self, n):
if n in self.vert_list:
return self.vert_list[n]
else:
return None
def __contains__(self, n): return n in self.vert_list
def add_edge(self, f, t, cost=0):
if f not in self.vert_list:
self.add_vertex(f)
if t not in self.vert_list:
self.add_vertex(t)
self.vert_list[f].add_neighbor(self.vert_list[t], cost)
def get_vertices(self): return self.vert_list.keys()
def __iter__(self): return iter(self.vert_list.values())
# the main graph
g = Graph()
# populate the main graph
g.add_vertex('dinner')
g.add_edge('dinner', 'food')
g.add_edge('dinner', 'fork')
g.add_edge('dinner', 'spoon')
g.add_vertex('breakfast')
g.add_edge('breakfast', 'food')
g.add_edge('breakfast', 'fork')
print("\nThe main graph is:")
for v in g:
for c in v.get_connections():
print("( %s , %s )" % (v.get_id(), c.get_id()))
# flip the graph by populating a new one with the main's children
flipped_g = Graph()
for v in g:
for c in v.get_connections():
flipped_g.add_edge(c.get_id(), v.get_id())
print("\nThe main graph inverted is:")
for v in flipped_g:
for c in v.get_connections():
print("( %s , %s )" % (v.get_id(), c.get_id()))
produce il seguente output:
The main graph is:
( breakfast , food )
( breakfast , fork )
( dinner , food )
( dinner , fork )
( dinner , spoon )
The main graph inverted is:
( food , breakfast )
( food , dinner )
( spoon , dinner )
( fork , breakfast )
( fork , dinner )
Questa non è certamente una soluzione completa, ma è un framework che puoi usare per ottenere le informazioni di cui hai bisogno.
Ricorda che il metodo add_vertex() controlla l'elenco delle connessioni e aggiunge un nodo solo se non è già presente. Ad esempio, esiste solo un nodo dinner e un solo nodo fork .
Ecco tutti i vertici recuperati con: flipped_g.get_vertices()
dict_keys(['food', 'spoon', 'fork', 'dinner', 'breakfast'])