Jak napisać algorytm obliczający relację współbieżności na zbiorze miejsc sieci.
(przez konstruowanie pełnego zbioru osiągalnych znakowań(przeszukiwanie grafu dfs).
class Siec {
Znakowanie znakowaniePoczatkowe;
Przejscie[] przejscia;
Relacja relacjaWspolbieznosci;
public Siec(String s,String s2) {
String p[] = s.split(" *; *");
przejscia = new Przejscie[p.length];
int maxp = 0;
for(int i = 0; i < przejscia.length; i++) {
przejscia[i] = new Przejscie(p[i]);
if(przejscia[i].maksMiejsce() > maxp) maxp = przejscia[i].maksMiejsce();
}
znakowaniePoczatkowe = new Znakowanie(s2, maxp + 1);
}
//public osiagalneZnakowania()
public Relacja relacjaWspolbieznosci() {
Relacja r = new Relacja(znakowaniePoczatkowe.length);
Znakowanie[] zSciezki = new Znakowanie[] { znakowaniePoczatkowe };
return r;
}
}
import java.io.*;
public class Znakowanie implements Cloneable {
public int[] liczbaZetonow;
public int[] kolory;
public int length;
public boolean equals(Znakowanie z) {
return z.liczbaZetonow.equals(this.liczbaZetonow);
}
public Znakowanie(int liczbaMiejsc) {
liczbaZetonow = new int[liczbaMiejsc];
}
public Znakowanie(String s,int liczbaMiejsc) throws NumberFormatException {
String[] sMiejsca = s.split(" *, *");
liczbaZetonow = new int[liczbaMiejsc];
for(int i = 0; i < sMiejsca.length; i++) { liczbaZetonow[Integer.decode(sMiejsca[i])] = 1; }
}
public Znakowanie odpalNowe(Przejscie p) {
Znakowanie z = this.clone();
z.odpal(p);
return z;
}
public Znakowanie clone() {
Znakowanie z = new Znakowanie(liczbaZetonow.length);
z.liczbaZetonow = this.liczbaZetonow.clone();
return z;
}
public void prostaSymulacja(Przejscie[] t, int limitPrzejsc) {
boolean f = true;
int j = 0;
while(f && j++ != limitPrzejsc) {
f = false;
for(int i = 0; i < t.length; i++) if(moznaOdpalic(t[i])) { odpal(t[i]); f = true; }
}
}
public boolean moznaOdpalic(Przejscie p) {
for(int i = 0; i < p.wejscia.length; i++) {
if(liczbaZetonow[p.wejscia[i]] == 0) return false;
}
return true;
}
public Znakowanie[] obliczZnakowania(Przejscie[] przejscia) {
int i = 0;
for(Przejscie p : przejscia){ if(moznaOdpalic(p)) i++; }
Znakowanie[] r = new Znakowanie[i];
i = 0;
for(Przejscie p : przejscia) { if(moznaOdpalic(p)) r[i++] = odpalNowe(p); }
return r;
}
public void odpal(Przejscie p) {
for(int i = 0; i < p.wejscia.length; i++) {
liczbaZetonow[p.wejscia[i]]--;
}
for(int i = 0; i < p.wyjscia.length; i++) {
liczbaZetonow[p.wyjscia[i]]++;
}
}
public String toString() {
return Pomocnicza.IntegerArrayToString(liczbaZetonow);
}
}
class Relacja {
boolean[][] rel;
int rozmiar;
public Relacja(int r) {
rel = new boolean[r][];
for(int i = 0; i < r; i++) {
rel[i] = new boolean[i];
}
rozmiar = r;
}
public void dodaj(int a,int b) {
int ap = a > b ? a : b;
int bp = a > b ? b : a;
rel[a][b] = true;
}
public void dodajZnakowanie(Znakowanie z) {
for(int i = 0; i < z.liczbaZetonow.length; i++) {
if(z.liczbaZetonow[i] > 0) {
for(int j = 0; j < z.liczbaZetonow.length; j++)
if(z.liczbaZetonow[j] > 0) rel[i][j] = true;
}
}
}
public boolean zawiera(int a,int b) {
int ap = a > b ? a : b;
int bp = a > b ? b : a;
return rel[a][b];
}
public String toString() {
String s = "";
if(rel != null) {
for(int i = 0; i < rel.length; i++) {
for(int j = 0; j < rel[i].length; j++) {
if(rel[i][j]) s += "(" + String.valueOf(i) + ", " + String.valueOf(j) + ")";
}
s += "\n";
}
}
return s;
}
}
public class Przejscie {
public int[] wejscia;
public int[] wyjscia;
public Przejscie(String s) throws NumberFormatException {
String[] p = s.split(" *: *");
String[] u = p[0].split(" *, *");
String[] v = p[1].split(" *, *");
int[] we = new int[u.length];
int[] wy = new int[v.length];
for(int i = 0; i < u.length; i++) {
we[i] = Integer.decode(u[i]);
}
for(int i = 0; i < v.length; i++) {
wy[i] = Integer.decode(v[i]);
}
wejscia = we;
wyjscia = wy;
}
public int maksMiejsce() {
int m = 0;
for(int i : wejscia) if(i > m) m = i;
for(int i : wyjscia) if(i > m) m = i;
return m;
}
public Przejscie(int [] we, int[] wy) {
wejscia = we;
wyjscia = wy;
}
public String toString() {
String s = "";
if(wejscia != null) {
for(int i = 0; i < wejscia.length - 1; i++) {
s += String.valueOf(wejscia[i]) + ",";
}
if(wejscia.length > 0) s += String.valueOf(wejscia[wejscia.length-1]);
}
if(wyjscia != null) {
s = s + ":";
for(int i = 0;i < wyjscia.length - 1; i++) {
s += String.valueOf(i) + ",";
}
if(wejscia.length > 0) s += String.valueOf(wejscia[wejscia.length-1]);
}
return s;
}
}
package petri;
public class Petri {
public static void main(String[] args) {
Siec s = new Siec("1:2,3;2,3:4,1,2");
System.out.println(s.znakowanie.toString());
System.out.println(s.przejscia[0].toString());
}
}