Je ne peux pas comprendre une certaine partie du papier publié par Donald Johnson sur la recherche de cycles (circuits) dans un graphique.
plus spécifique, je ne peux pas comprendre quelle est la matrice ak qui est mentionnée dans la ligne suivante du pseudo code:
ak: = Structure de l'adjacence du composant fort K avec le moins sommet au sous-graphique de g induit par {s, s + 1, .... n};
Pour aggraver les choses, certaines lignes après sont des mentins "pour i in vk do" sans déclarer ce que le VK est ...
Aussi loin que j'ai compris, nous avons ce qui suit: 1) En général, un composant puissant est un sous-graphique d'un graphique, dans lequel, pour chaque noeud de ce sous-graphique, il existe un chemin d'accès à n'importe quel noeud du sous-graphique (en d'autres termes, vous pouvez accéder à n'importe quel nœud de la Sous-graphique à partir de tout autre noeud du sous-graphique)
2) Un sous-graphique induit par une liste de nœuds est Un graphique contenant tous ces nœuds plus tous les bords reliant ces nœuds. Dans le papier, la définition mathématique est "F est un sous-graphique de g induit par W si w est sous-ensemble de v et f = (w, {u, y) | u, y dans w et u, y)}}) où vous, y sont des bords, e est l'ensemble de tous les bords du graphique, w est un ensemble de nœuds.
3) Dans la mise en œuvre du code, les nœuds sont nommés par des numéros d'entier 1 ... n.
4) i suspect que le VK est l'ensemble de nœuds de la composante forte K.
maintenant à la question. Disons que nous avons un graphique g = (v, e) avec v = {1,2,3,4,5,6,7,8,9} qu'il peut être divisé en 3 composants solides de la SC1 = {1, 4,7,8} SC2 = {2,3,9} SC3 = {5,6} (et leurs bords)
Quelqu'un peut-il me donner un exemple pour S = 1, S = 2, S = 5 Et si vous allez être le VK et AK selon le code?
Le pseudo code est dans ma question précédente dans Comprendre le pseudocode dans le Donald L'algorithme de B. Johnson
et le papier peut être trouvé à Comprendre le pseudocode dans le Donald L'algorithme de B. Johnson
Merci d'avance
4 Réponses :
Ça marche! Dans un une itération antérieure du Johnson Algorithm , j'avais supposé que addendum: comme indiqué dans ce proposé Modifier et utile Réponse , l'algorithme spécifie que Sortie de l'échantillon: p> Par défaut, le programme commence par a code> était un Matrice de adjacence . Au lieu de cela, il semble représenter un Liste d'adjacence . Dans cet exemple, implémenté ci-dessous, les sommets {A, B, C} sont numérotés {0 , 1, 2}, cédant les circuits suivants. déblocage () code> doit supprimer l'élément ayant la valeur em> w code>, pas l'élément ayant l'index index em> w code>. p> S = 0 code>; Implémentation S: = moins sommet dans v code> comme une optimisation reste. Une variation qui ne produit que des cycles uniques est montré ici . P> import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
* @see http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
* @see https://stackoverflow.com/questions/2908575
* @see https://stackoverflow.com/questions/2939877
* @see http://en.wikipedia.org/wiki/Adjacency_matrix
* @see http://en.wikipedia.org/wiki/Adjacency_list
*/
public final class CircuitFinding {
final Stack<Integer> stack = new Stack<Integer>();
final List<List<Integer>> a;
final List<List<Integer>> b;
final boolean[] blocked;
final int n;
int s;
public static void main(String[] args) {
List<List<Integer>> a = new ArrayList<List<Integer>>();
a.add(new ArrayList<Integer>(Arrays.asList(1, 2)));
a.add(new ArrayList<Integer>(Arrays.asList(0, 2)));
a.add(new ArrayList<Integer>(Arrays.asList(0, 1)));
CircuitFinding cf = new CircuitFinding(a);
cf.find();
}
/**
* @param a adjacency structure of strong component K with
* least vertex in subgraph of G induced by {s, s + 1, n};
*/
public CircuitFinding(List<List<Integer>> a) {
this.a = a;
n = a.size();
blocked = new boolean[n];
b = new ArrayList<List<Integer>>();
for (int i = 0; i < n; i++) {
b.add(new ArrayList<Integer>());
}
}
private void unblock(int u) {
blocked[u] = false;
List<Integer> list = b.get(u);
for (int w : list) {
//delete w from B(u);
list.remove(Integer.valueOf(w));
if (blocked[w]) {
unblock(w);
}
}
}
private boolean circuit(int v) {
boolean f = false;
stack.push(v);
blocked[v] = true;
L1:
for (int w : a.get(v)) {
if (w == s) {
//output circuit composed of stack followed by s;
for (int i : stack) {
System.out.print(i + " ");
}
System.out.println(s);
f = true;
} else if (!blocked[w]) {
if (circuit(w)) {
f = true;
}
}
}
L2:
if (f) {
unblock(v);
} else {
for (int w : a.get(v)) {
//if (v∉B(w)) put v on B(w);
if (!b.get(w).contains(v)) {
b.get(w).add(v);
}
}
}
v = stack.pop();
return f;
}
public void find() {
while (s < n) {
if (a != null) {
//s := least vertex in V;
L3:
circuit(s);
s++;
} else {
s = n;
}
}
}
}
@Staker: J'espère que non! Paraphrasant Knuth: "Méfiez-vous des bugs dans le code ci-dessus; je n'ai que essayé, non pas prouvé qu'il est correct."
@trashgod Merci de votre gentillesse et de très utile aide @Staker, c'est essentiellement ma petite partie de ma thèse MSC, mais ce n'est pas un problème car j'ai déjà écrit la plupart du code et j'utilise des structures totalement différentes. Je n'ai pas testé votre code mais il y a toujours un problème mineur. L'AK fait référence au sous-graphique des composants forts (dans votre exemple le réseau tout un SCC .. Mais que se passe-t-il s'il peut être divisé en 2 CCC? Comment va être l'AK alors?) QUE STIL reste le gros point d'interrogation. Mon idée est que de manière proprablement (je dois y tester pour vérifier la correction) L'AK est la liste des adjacents
du sous-graphique contenant le S, mais avec les bords de ce SCC à tous les autres SCCS enlevés. Par exemple, laissez {0,1,2} votre exemple de graphique connecté au {3,4} avec un bord de 2 -> 3 puis de l'A0, A1, A2 sera la liste de adjacence (déjà donnée par vous) Plus le nouveau sans le bord de 2-> 3.
Toutes les histoires à propos de la CSC sont parce que vous pouvez diviser le g en plus petit, améliorer ainsi la performance de l'algorithme (comme l'algorithme a une complexité O (E * C) où c = nombre de cycles ..qui c Où n est le nombre de nœuds ...) Quoi qu'il en soit, un million de remerciements pour votre toute votre aide!
@Pitelk: Comme cette réponse ne répond pas vraiment à votre question, je laisserais la question ouverte pendant un certain temps. Je vais mettre à jour si je reçois de nouvelles perspectives.
@Trashgod: J'ai mis en œuvre avec succès l'algorithme (je ne peux toujours pas le croire !!) En Java en utilisant ma structure. J'ai supposé que VK est le réseau fortement connecté contenant le noeud actuel (la variable S dans le cas de votre implémentation). Votre code ne fonctionne pas toujours. Selon le réseau, il peut lancer une exception de pointeur nulle. Quoi qu'il en soit, votre aide était inestimable et l'algorithme m'a vraiment aidé à montrer (plus j'ai appris sur la pile) et j'aimerais vous avoir dans ma liste de remerciement de mon projet de thèse si cela vous convient (j'aurais besoin de votre nom .. :) ) Merci beaucoup
@Pitelk: Excellent; Un vote à la hausse est toujours accueilli. :-) Je pense que vous êtes censé citer la ou les questions relatives à Stackoverflow, mais ma page d'utilisateur est assez transparente. CreativeRecommons.org/licenses/by-sa/2.5
Comme @chitr, @chitr mentionne dans une réponse ci-dessous, la sortie contient des permutations cycliques, par ex. 0-1-0 et 1-0-1. C'est parce que l'étape "Structure de l'adjacence d'un composant fort K avec le moins sommet du sous-graphique de G induite par {S, S + 1, ..., N};" Cela signifie fondamentalement que chaque sommet inférieur à S doit être retiré de la liste de adjacence pour cette course. Cela retirera les cycles, y compris ces sommets, et il suffit donc de garder des cycles distincts.
@Gedde: correct; Comme indiqué ci-dessus, cette "optimisation reste"; un Approche a été supprimé par son propriétaire; S'il vous plaît laissez-moi savoir si vous ajoutez une réponse en expansion sur l'observation de Chitr.
@THashRashGod: Oui, c'est juste que c'était la partie clé de la question et de l'OMHO, ce n'est pas seulement une optimisation, mais une étape très importante de l'algorithme. Sans cette partie, vous ne trouverez pas distincts circuits élémentaires, et il est assez coûteux d'éliminer les doublons après la course. Il dégrade vraiment l'efficacité de l'algorithme. Je vais voir si je vais ajouter une réponse plus tard. Il s'agit fondamentalement en éliminant tous les sommets inférieurs à S à partir du ak
@Gedde: J'ai ajouté un Variation , citant citer ci-dessus; Remarque Code correction dans Révision 7 .
J'avais Sumbitd an Modifier Demande au code de @ TrashGod pour corriger l'exception lancée dans mon Modifier la demande a été rejetée! Je ne sais pas pourquoi, parce que j'ai testé ce qui précède avec ma modification sur un réseau de 20 000 nœuds et 70 000 bords et qu'il ne plante pas. P> J'ai également modifié l'algorithme de Johnson pour être plus adapté aux graphiques non écrits. Si quelqu'un veut ces modifications, veuillez me contacter. P> ci-dessous est mon code pour déblocage ( ) code>. Essentiellement, l'algorithme indique que l'élément w code> (qui est pas em> index) doit être supprimé de la liste. Le code ci-dessus utilisé list.remove (w) code>, qui traite w code> comme index. déblocage () code>. P> private void unblock(int u) {
blocked[u] = false;
List<Integer> list = b.get(u);
int w;
for (int iw=0; iw < list.size(); iw++) {
w = Integer.valueOf(list.get(iw));
//delete w from B(u);
list.remove(iw);
if (blocked[w]) {
unblock(w);
}
}
}
+1 pour avoir repéré cela; J'ai mis à jour mon Répondre De même. La demande d'édition a peut-être ressemblé à une tentative de contourner le seuil de commentaire, mais c'est une bonne réponse.
@trashgod, votre sortie d'échantillon contient du cycle qui sont une permutation cyclique. Par exemple, 0-1-0 et 1-0-1 sont les mêmes En fait, la sortie ne doit contenir que 5 cycle I.e. 0 1 0, 0 2 0, 0 1 2 0, 0 2 1 0, 1 2 1,
Le papier Johnson explique ce qu'un cycle est: «Deux circuits élémentaires sont distincts si l'un n'est pas une permutation cyclique de l'autre. " On peut également vérifier la page Wolfram: cela génère également 5 cycle pour la même entrée.
http://demonstrations.wolfram.com/enumeratingclesclesofadirectedGraph/
La variation suivante produit des cycles uniques. Basé sur ce exemple , il est adapté à partir d'un réponse fourni par @ user1406062 .
code: p> sortie: p> Tous les cycles, pour référence: P> 0 1 0
0 1 2 0
0 2 0
0 2 1 0
1 0 1
1 0 2 1
1 2 0 1
1 2 1
2 0 1 2
2 0 2
2 1 0 2
2 1 2