Bon algorithme pour trouver le diamètre d’un graphe (rare)?

J’ai un grand graphique connecté et épars sous forme de liste de contiguïté. Je voudrais trouver deux sumts aussi éloignés que possible, à savoir le diamètre du graphe et les deux sumts qui l’atteignent.

Je suis intéressé par ce problème dans les cas non orientés et dirigés, pour différentes applications. Dans le cas dirigé, je m’occupe bien sûr de la distance dirigée (le chemin le plus court dirigé d’un sumt à l’autre).

Existe-t-il une meilleure approche que le calcul des chemins les plus courts par paires?

Edit : Par “aussi loin que possible”, j’entends bien sûr le “plus long chemin le plus court”, c’est-à-dire le maximum sur toutes les paires de sumts de la plus courte distance de l’un à l’autre.

Eh bien, j’ai un peu réfléchi au problème, et un peu de googler, et je suis désolé, mais je ne trouve aucun algorithme qui ne semble pas être “trouver toutes les paires le plus court chemin” .

Cependant, si vous supposez que Floyd-Warshall est le seul algorithme pour calculer une telle chose (Big-Theta de | V | ^ 3), j’ai une bonne nouvelle pour vous: l’algorithme de Johnson pour les graphiques fragmentés (merci, trusty CLRS!) calcule toutes les paires de chemins les plus courts (Big-Oh (| V | ^ 2 * lgV + VE)), ce qui devrait être asymptotiquement plus rapide pour les graphiques fragmentés.

Wikipedia dit que cela fonctionne pour orienté (pas sûr de ne pas dirigé, mais au moins je ne peux pas penser à une raison pour laquelle pas), voici le lien .

Y a-t-il autre chose sur le graphique qui pourrait être utile? S’il est facile de le mapper sur un plan 2D (donc les poids planaires et les poids des arêtes obéissent à l’inégalité sortingangular [il peut être nécessaire de satisfaire à une exigence plus ssortingcte, je ne suis pas sûr]), vous pourrez peut-être décomposer certains algorithmes géomésortingques (la shell convexe peut fonctionner en nlogn, et il est facile de trouver la paire de points la plus éloignée).

J’espère que cela t’aides! – Agor

Edit: J’espère que le lien fonctionne maintenant. Si ce n’est pas le cas, allez sur Google. 🙂

Je ne connais pas de meilleure méthode pour calculer le diamètre que tous les chemins les plus courts, mais Mathematica utilise l’approximation suivante pour PseudoDiameter:

  • Une géodésique de graphe est le plus court chemin entre deux sumts d’un graphe. Le diamètre du graphe est la plus longue longueur possible de toutes les géodésiques du graphe. PseudoDiameter trouve un diamètre de graphique approximatif. Il fonctionne en partant d’un sumt u et trouve un sumt v le plus éloigné de u. Ce processus est répété en traitant v comme nouveau sumt de départ et se termine lorsque la distance du graphique n’augmente plus. Un sumt du dernier ensemble de niveaux ayant le plus petit degré est choisi comme sumt de départ final u et une traversée est effectuée pour voir si la distance du graphique peut être augmentée. Cette distance graphique est considérée comme étant le pseudo-diamètre.

http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html

Modifier Je ne suis pas encore en train de supprimer, simplement pour pouvoir continuer à commenter. J’ai quelques commentaires sur l’algorithme de Johnson en dessous de cette réponse. – Aaron

Mon commentaire original : Je suis moi aussi curieux de ce problème, mais je n’ai pas de réponse. Il semble lié au Minimum Spanning Tree , le sous-graphe reliant tous les sumts mais ayant le moins d’arêtes (ou le plus faible poids). C’est un vieux problème avec un certain nombre d’algorithmes; certains d’entre eux semblent assez faciles à mettre en œuvre.

J’avais d’abord espéré que le diamètre serait évident une fois le MST trouvé, mais je perds espoir maintenant 🙁 Peut-être que le MST peut être utilisé pour placer une limite supérieure raisonnable sur le diamètre, que vous pouvez utiliser pour accélérer votre recherche du diamètre réel?

Voici quelques idées pour faire mieux que toutes les paires de chemins les plus courts dans un graphique non dirigé, bien que je ne sois pas certain de l’amélioration que cela apporterait.

Voici une sous-routine qui trouvera deux nœuds distants D, s’il en existe. Choisissez un nœud arbitraire x et calculez M [x] = distance maximale de x à tout autre nœud (en utilisant un algorithme de plus court chemin source unique). Si M [x]> = D, alors x est l’un de nos nœuds et l’autre est facile à trouver. Cependant, si M [x]

Il ne rest plus qu’à définir D = diam (G) et exécuter la procédure ci-dessus. Nous ne soaps pas ce que diam (G) est, mais nous pouvons obtenir une plage assez étroite, comme pour tout x, M [x] <= diam (G) <= 2M [x]. Choisissez quelques x pour commencer, calculez M [x] pour chacun, et calculez les limites supérieure et inférieure sur diam (G) en conséquence. Nous pouvons alors effectuer une recherche binaire dans la plage résultante, en utilisant la procédure ci-dessus pour trouver un chemin de la longueur devinée, le cas échéant.

Bien sûr, ceci n’est pas dirigé uniquement. Je pense que vous pourriez faire un schéma similaire avec des graphiques dirigés. Les nœuds incorrects sont ceux qui peuvent atteindre x en moins que DM [x], et la limite supérieure de diam (G) ne fonctionne pas. Vous aurez donc besoin d’une plage de recherche binary plus grande.

Je ne sais pas si cela correspond à la facture, mais intéressant:

HADI: Estimation rapide du diamètre et extraction dans des graphiques massifs avec Hadoop

U. Kang, C. Tsourakakis, AP Appel, C. Faloutsos, J. Leskovec, «HADI: Estimation rapide des diamètres et exploitation minière dans des graphes massifs avec Hadoop», Rapport technique CMU ML CMU-ML-08-117, 2008.

si le graphique est un arbre (et non orienté). vous pouvez simplement exécuter 2 dfs. Commencez par un nœud aléatoire u et dfs pour trouver le nœud le plus éloigné v. Puis commencez à v et trouvez la longueur la plus longue. Cette longueur est optimale

Pardonnez-moi si ma réponse n’est pas correcte en termes de syntaxe, mais mon cours d’algorithme était il y a quelque temps (et non en anglais).

Si je comprends bien votre problème, vous voulez savoir quel est le nombre le plus élevé que vous pouvez compter en partant du nœud A et en atteignant le nœud B sans “retracer” vos étapes. Si tel est le cas, j’imagine que votre graphique est acyclique (l’option cyclique vient plus tard).

Tout d’abord, la limite supérieure est le nombre d’arêtes. Comment je vois la chose est: prenez un nœud, créez un arbre où le nœud est à la racine et chaque nœud suivant que vous pouvez atteindre est au niveau suivant. La hauteur de l’arbre que vous construisez est le diamètre et les feuilles sont les nœuds qui se trouvent à cette distance. Si cette distance = nombre d’arêtes que vous avez fini. Sinon, choisissez un autre nœud et répétez.

Je pense que c’est similaire à la construction d’une recherche complète. Ne sachant pas grand chose d’autre sur le graphique, vous pouvez utiliser des heuristiques pour voir quelle orientation de l’arbre (c.-à-d. Quel nœud doit être sélectionné en premier) serait préférable, mais c’est un autre sujet.

En ce qui concerne la cyclicité du graphique, comme d’autres l’ont souligné, cela peut conduire à des boucles infinies. Une façon de s’en débarrasser pourrait consister à «exclure» les nœuds appartenant à un cycle et à append le plus long chemin entre eux en tant que valeur obtenue en entrant dans le cycle, en touchant chaque nœud une seule fois. .

Maintenant, comme je le disais, cette méthode pourrait très facilement être la même chose que faire tout le chemin le plus court. La complexité du pire des cas est certainement la même et ne pourrait en être autrement.

Je doute vraiment qu’il existe une méthode pour trouver le chemin le plus court sans avoir à utiliser un algorithme de chemin le plus court (trouver le plus court chemin d’une source à une autre fait essentiellement toutes les paires dans le pire des cas).

“Diamètre” devient difficile à définir en termes de “chemin le plus long” si le graphique n’est pas un arbre ou un DAG. Le chemin le plus long peut être infini s’il y a des cycles dans le graphique. Une simple traversée du graphe ne peut donc pas générer le plus long chemin sur tous les nœuds. Comme vous avez déjà indiqué que votre graphique n’est pas nécessairement acyclique et que vous êtes intéressé par le chemin le plus “court”, il ne semble pas y avoir de méthode permettant d’éviter de trouver le chemin le plus court pour tous les nœuds. Comme l’a suggéré Agor, l’utilisation de l’algorithme de Johnson est probablement la meilleure solution.

Vous pouvez bien sûr suivre une approche basée sur l’heuristique. L’algorithme qui utilise le vertex pseudo-périphérique semble être l’approche la plus couramment utilisée.

Une façon d’obtenir une estimation de ce nombre est de commencer à un point aléatoire et de procéder à un algorithme de “feu de brousse” large, marquant la distance la plus courte par rapport à chaque nœud. La distance la plus longue est votre estimation.

En exécutant cet algorithme extrêmement rapide plusieurs fois avec différents points de départ, puis en prenant le maximum, vous augmenterez la précision de l’estimation et, bien sûr, vous aurez une limite inférieure décente. Selon la dissortingbution et la connectivité de votre graphique, cette estimation peut même être exacte!

Si votre graphique est suffisamment volumineux, une parsing asymptotique de la façon dont l’estimation est modifiée à mesure que vous ajoutez plus d’échantillons peut vous permettre de deviner encore mieux.

Si vous êtes intéressé par une réponse exacte, il semble peu probable que vous parveniez à couper les angles, à moins que votre graphique soit facile à diviser en composants faiblement connectés les uns aux autres. chemin entre toutes les paires de sumts des différents composants.

Choisissez un sumt v et faites BFS (v), cela calculera la distance de v pour tous les sumts. Obtenez la plus longue distance. C’est O (V + E)

Exécutez maintenant cet algorithme pour tous les sumts et choisissez le maximum de ces plus longues distances. Complexité globale: O (V * (V + E))

Une méthode sale:

On sait que pour un graphe G (V, E) avec | V | = n et | E | = m, l’algorithme de Dijkstra s’exécute en O(m+nlogn) et ceci pour une source unique. Pour votre problème tout-paires, vous devez lancer Dijkstra pour chaque nœud comme sharepoint départ.

Cependant, si vous avez beaucoup de machines, vous pouvez facilement les mettre en parallèle.

Cette méthode est la plus simple à mettre en œuvre, certainement pas très bonne.

Oui, il existe une meilleure méthode pour trouver le diamètre du graphique. Ici, j’ai fait un cours simple pour le démontrer. Les sumts seraient les points sur votre graphique.

 public class MyTestClass { //Simple Point struct struct Vertex { public float X, Y; public Vertex(float pX, float pY) { X = pX; Y = pY; } } //For getting the bounds of your graph struct BoundingBox { public float Left, Right, Bottom, Top; public BoundingBox(float pLeft, float pRight, float pBottom, float pTop) { Left = pLeft; Right = pRight; Bottom = pBottom; Top = pTop; } } //Properties Vertex[] vertices; BoundingBox bound; float diameter; //Constructor //Here is the fastest way to get the diameter >> public MyTestClass() { //Init objects vertices = new Vertex[100]; for(int i = 0; i != vertices.Length; ++i) vertices[i] = new Vertex(i, i); bound = new BoundingBox(vertices[0].X, vertices[0].X, vertices[0].Y, vertices[0].Y); //Calculate BoundingBox for(int i = 0; i != vertices.Length; ++i) { bound.Left = (vertices[i].X <= bound.Left) ? vertices[i].X:bound.Left; bound.Right = (vertices[i].X >= bound.Right) ? vertices[i].X:bound.Right; bound.Bottom = (vertices[i].Y <= bound.Bottom) ? vertices[i].Y:bound.Bottom;//NOTE: If Y is faces down, then flip bottom & top comparison bound.Top = (vertices[i].Y >= bound.Top) ? vertices[i].Y:bound.Top; } //Messure Size of the BoundingBox float vecX = (bound.Right-bound.Left); float vecY = (bound.Top-bound.Bottom); diameter = (float)System.Math.Sqrt((vecX*vecX) + (vecY*vecY)); } }