Lo pseudo-codice ricorda Algol, Pascal o Ada.
Vuol dire che devo implementare un altro algoritmo che trova la A k matrice?
Un k sembra essere un elenco di array di valori di ingresso aventi le proprietà specificate. Potrebbe essere correlato al corrispondente adjacency matrix, ma non è chiaro per me. Sto indovinando qualcosa di simile:
int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int s;
Cosa logical f significa?
Questo dichiara una variabile locale che rappresenta una true o false valore, simile a Java di boolean.
logical procedure CIRCUIT (integer value v);
Questo dichiara un sottoprogramma nome CIRCUIT avere un unico parametro intero v che viene passato per valore. Il sottoprogramma restituisce un risultato logical di true o false e assegna come risultato il f.In Java,
boolean circuit(int v) {
boolean f;
...
f = false;
...
return f;
}
Le parole chiave begin e end delimitano un ambito blocco che possono essere nidificati, così CIRCUIT è annidato nel blocco principale e UNBLOCK è annidato all'interno di CIRCUIT. := è un incarico; ¬ è not; ∈ è un elemento; ∅ è vuoto; ≠ è !=; stack e unstack suggeriscono push e pop.
È solo un inizio, ma spero che sia d'aiuto.
Addendum: A riflessione, A e B devono essere isomorfi.
Ecco uno schema molto letterale. Non so abbastanza su A, B & V per scegliere una struttura dati migliore degli array.
import java.util.Stack;
public final class CircuitFinding {
static int k, n;
int[][] a = new int[k][n];
int[][] b = new int[k][n];
boolean[] blocked = new boolean[n];
int[] v = new int[k];
int s = 1;
Stack<Integer> stack = new Stack<Integer>();
private void unblock(int u) {
blocked[u] = false;
for (int w : b[u]) {
//delete w from B(u)
if (blocked[w]) {
unblock(w);
}
}
}
private boolean circuit(int v) {
boolean f = false;
stack.push(v);
blocked[v] = true;
L1:
for (int w : a[v]) {
if (w == s) {
//output circuit composed of stack followed by s;
f = true;
} else if (!blocked[w]) {
if (circuit(w)) {
f = true;
}
}
}
L2:
if (f) {
unblock(v);
} else {
for (int w : a[v]) {
//if (v∉B(w)) put v on B(w);
}
}
v = stack.pop();
return f;
}
public void main() {
while (s < n) {
//A:= adjacency structure of strong component K with least
//vertex in subgraph of G induced by {s, s+ 1, n};
if (a[k] != null) {
//s := least vertex in V;
for (int i : v) {
blocked[i] = false;
b[i] = null;
}
L3:
circuit(s);
s++;
} else {
s = n;
}
}
}
}
Hai provato a leggere la carta a cui sei collegato? Sembra avere una spiegazione e una prova di accompagnamento. –
sì, ma ancora non spiega il codice stesso, solo l'idea generale. Quello che non riesco a capire è lo pseudo codice. anche io ho trovato un altro link alla carta nel caso in cui il primo non funziona http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf – Pitelk
Grazie a tutti voi, vi siete presi cura del aspetto della mia domanda (ha fatto sembrare migliore, corretto errori di ortografia e cambiato il codice che ho scritto sull'originale del foglio -per qualche strana ragione non potevo semplicemente copiare e incollare il codice così l'ho digitato da zero.) – Pitelk