J'ai un ensemble de nœuds et une fonction Lorsqu'on me donne un ensemble de nœuds, je peux trouver tous les composants connectés dans le graphique en passant toutes les combinaisons possibles de nœuds à le problème avec cette approche est que je reçois de nombreux contrôles redondants que je voudrais éviter: foo (u, v) qui peut déterminer si deux nœuds sont égaux. Par «égal», j'entends l'équivalence transitive:
Si 1 == 2 et 2 == 3 alors 1 == 3 et aussi: Si 1 == 2 code > et 1! = 4 puis 2!=4 foo (u, v) (qui renvoie des résultats prédéterminés à des fins de présentation uniquement - ce n'est pas la vraie fonction! strong>) fonction et la construction des bords nécessaires. Comme ceci: 1==2 # ok
1==3 # ok
1!=4 # ok
1!=5 # ok
2==3 # redundant check, if 1==2 and 1==3 then 2==3
2!=4 # redundant check, if 1!=4 and 1==2 then 2!=4
2!=5 # redundant check, if 1!=5 and 1==2 then 2!=5
3!=4 # redundant check, if 1!=4 and 1==3 then 3!=4
3!=5 # redundant check, if 1!=5 and 1==3 then 3!=5
4==5 # ok
import networkx as nx
import itertools
from matplotlib import pyplot as plt
def foo(u, v):
# this function is simplified, in reality it will do a complex
# calculation to determine whether nodes are equal.
EQUAL_EDGES = {(1, 2), (2, 3), (1, 3), (4, 5)}
return (u, v) in EQUAL_EDGES
def main():
g = nx.Graph()
g.add_nodes_from(range(1, 5 + 1))
for u, v in itertools.combinations(g.nodes, 2):
are_equal = foo(u, v)
print '{u}{sign}{v}'.format(u=u, v=v, sign='==' if are_equal else '!=')
if are_equal:
g.add_edge(u, v)
conn_comps = nx.connected_components(g)
nx.draw(g, with_labels=True)
plt.show()
return conn_comps
if __name__ == '__main__':
main()
Je veux éviter de courir avec une complexité temporelle O (n ^ 2).
Quelle est la bonne façon (ou peut-être une fonction existante dans n'importe quelle bibliothèque python) pour trouver efficacement tous les composants connectés par une fonction foo (u, v) personnalisée?
3 Réponses :
Ce que vous essayez vraiment de faire n'est pas clair, mais voici une solution qui ne vérifie qu'un seul élément dans chaque groupe équivalent:
nodes2place = range(1, 6)
cclist = []
for u in nodes2place:
node_was_placed=False
for icc in range(len(cclist)):
if foo(u, cclist[icc][0]):
cclist[icc].append(u)
node_was_placed=True
break
# node doesn't fit into existing cc so make a new one
if not node_was_placed:
cclist.append([u])
cette solution est toujours O (n ^ 2) dans le pire des cas lorsqu'il n'y a pas de connexions entre les nœuds
Oui, c'est toujours O (n ^ 2) dans le pire des cas, mais ce n'est pas clair pour moi si vous pouvez éviter cela à cause de la façon dont vous avez formulé le problème de recherche de relation d'équivalence. BTW, avez-vous réellement une structure graphique sous-jacente ou supposez-vous que vous en avez besoin pour trouver vos composants? Lorsque vous avez posé la question, il semble que vous construisez un graphique à partir de la relation, et non l'inverse.
Vous pouvez suivre les arêtes qui sont transitivement égales ou inégales dans deux dictionnaires respectifs. Pour chaque combinaison d'arêtes, vous pouvez effectuer quelques vérifications simples en temps O (1) pour voir si le calcul serait redondant. Sinon, vous faites le calcul à partir des premiers principes, puis, selon que les arêtes sont égales ou inégales, vous mettez à jour les dictionnaires ci-dessus avec les informations nécessaires. Vous devrez toujours faire des vérifications d'égalité C (n, 2) car c'est le nombre de combinaisons que vous parcourez, mais pour un certain nombre d'entre elles, la décision peut être prise instantanément.
Le dictionnaire equal_edges est plus simple à expliquer, alors commençons par cela. La paire d'arêtes 1-2 est égale, mais comme ni 1 ni 2 n'existent en tant que clés (le dict est vide pour l'instant), nous créons l'ensemble {1, 2} et l'attachons aux deux equal_edges [1] et equal_edges [2] . Nous rencontrons alors la paire d'arêtes égales 1-3. Puisque equal_edges [1] existe maintenant, nous ajoutons 3 à ses nœuds transitivement égaux. Mais comme cet ensemble est partagé entre les deux bords 1 et 2, il est mis à jour aux deux endroits. Il faut aussi maintenant attacher ce même ensemble à equal_edges [3] . Les trois arêtes font référence au même ensemble en mémoire, c'est-à-dire {1, 2, 3} , nous ne dupliquons donc aucune donnée. Maintenant, quand il s'agit de vérifier la paire de bords égaux 2-3, soit 3 dans equal_edges [2] ou 2 dans equal_edges [3] nous permet de contourner tous les calculs lourds.
Pour les unequal_edges , la logique est quelque peu similaire, mais nous devons également nous référer au dictionnaire equal_edges pour les arêtes transitivement inégales. Par exemple, la paire d'arêtes 1-4 est inégale. Mais comme 1 est transitivement égal à 2 et 3, nous devons avoir unequal_edges [4] = equal_edges [1] . Il serait redondant de définir unequal_edges [1] = {4} , ou unequal_edges [2] = {4} , etc. En effet, ces informations peuvent être obtenues à partir de unequal_edges [4] . Cela signifie simplement que pour une paire ab transitivement inégale, nous devons faire une double vérification, c'est-à-dire a dans unequal_edges [b] ou b dans unequal_edges [a] .
1==2 # ok 1==3 # ok 1!=4 # ok 1!=5 # ok 2==3 # redundant 2!=4 # redundant 2!=5 # redundant 3!=4 # redundant 3!=5 # redundant 4==5 # ok
Vous pouvez utiliser 0 pour représenter l'égalité et math.inf pour représenter l'inégalité sous forme de poids d'arête. Ensuite, pour chaque paire de nœuds u, v , vous pouvez calculer la longueur du chemin de u à v et en fonction du résultat, décider si le (lourd) La vérification des nœuds doit être invoquée ou non:
g = nx.Graph()
g.add_nodes_from(range(1, 6))
for u, v in it.combinations(g.nodes, 2):
try:
path = nx.shortest_path(g, u, v)
except nx.NetworkXNoPath:
new_weight = 0 if func(u, v) else math.inf
else:
weights = list(x['weight'] for x in it.starmap(g.get_edge_data, zip(path[:-1], path[1:])))
if min(weights) == math.inf:
new_weight = 0 if func(u, v) else math.inf
elif max(weights) == math.inf:
new_weight = math.inf
else:
new_weight = 0
g.add_edge(u, v, weight=new_weight)
Si vous n'aimez pas ces arêtes infinies dans votre graphique, vous pouvez soit:
Vous ne pouvez pas éviter la complexité
O (n ^ 2). Tout ce que vous pouvez faire est d'éviter les comparaisons redondantesSi la fonction
foocalcule l'égalité de deux nœuds en respectant l'égalité transitoire entre tous les nœuds, alors pourquoi ne faites-vous pas en premier lieu cette fonction pour gérer les redondances? Ou l'inverse, comment cette fonction garantit-elle qu'elle respecte l'égalité transitoire entre tous les nœuds?