From df5d936c9357bec642391c1cd58dd952c67c5e8f Mon Sep 17 00:00:00 2001 From: Mike Becker Date: Thu, 5 Dec 2019 18:48:02 +0100 Subject: [PATCH] basic petri net simulation for a fixed number of steps --- pom.xml | 13 ++ .../java/de/yasc/example/petrinet/Main.java | 20 +++ .../de/yasc/example/petrinet/PetriNet.java | 99 +++++++++++ .../yasc/example/petrinet/PetrinetParser.java | 160 ++++++++++++++++++ 4 files changed, 292 insertions(+) create mode 100644 pom.xml create mode 100644 src/main/java/de/yasc/example/petrinet/Main.java create mode 100644 src/main/java/de/yasc/example/petrinet/PetriNet.java create mode 100644 src/main/java/de/yasc/example/petrinet/PetrinetParser.java diff --git a/pom.xml b/pom.xml new file mode 100644 index 0000000..4c2b205 --- /dev/null +++ b/pom.xml @@ -0,0 +1,13 @@ + + + 4.0.0 + de.yasc.example + petrinet + 1.0-SNAPSHOT + jar + + UTF-8 + 11 + 11 + + \ No newline at end of file diff --git a/src/main/java/de/yasc/example/petrinet/Main.java b/src/main/java/de/yasc/example/petrinet/Main.java new file mode 100644 index 0000000..8788f76 --- /dev/null +++ b/src/main/java/de/yasc/example/petrinet/Main.java @@ -0,0 +1,20 @@ +package de.yasc.example.petrinet; + +import java.io.IOException; +import java.util.Arrays; + +public class Main { + public static void main(String arg[]) { + try { + var parser = new PetrinetParser(System.in); + var net = parser.read(); + + net.step(2); + + System.out.println(Arrays.asList(net.getMarking()).toString()); + } catch (IOException ex) { + System.err.println("Error: "+ex.getMessage()); + System.exit(1); + } + } +} diff --git a/src/main/java/de/yasc/example/petrinet/PetriNet.java b/src/main/java/de/yasc/example/petrinet/PetriNet.java new file mode 100644 index 0000000..010a279 --- /dev/null +++ b/src/main/java/de/yasc/example/petrinet/PetriNet.java @@ -0,0 +1,99 @@ +package de.yasc.example.petrinet; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.List; +import java.util.Random; +import java.util.stream.Collectors; + +public final class PetriNet { + + private static final class Place { + + int tokens; + + boolean empty() { + return tokens <= 0; + } + + void dec() { + assert tokens > 0; + tokens--; + } + + void inc() { + tokens++; + } + } + + private static final class Transition { + + final List preset; + final List postset; + + public Transition(List preset, List postset) { + this.preset = preset; + this.postset = postset; + } + + boolean enabled() { + return preset.stream().noneMatch(Place::empty); + } + + void fire() { + preset.forEach(Place::dec); + postset.forEach(Place::inc); + } + } + + final private Random prng = new Random(); + final private Place[] places; + final private List transitions; + + public PetriNet(int places) { + this.places = new Place[places]; + for (int i = 0 ; i < places ; i++) + this.places[i] = new Place(); + transitions = new ArrayList<>(); + } + + public void addTransistion(Integer[] preset, Integer[] postset) { + transitions.add(new Transition( + Arrays.stream(preset).map((i) -> places[i]).collect(Collectors.toList()), + Arrays.stream(postset).map((i) -> places[i]).collect(Collectors.toList()) + )); + } + + public void addMarking(Integer ... marking) { + Arrays.stream(marking).forEach((i) -> places[i].inc()); + } + + public boolean step() { + var enabledTransitions = transitions.stream().filter(Transition::enabled).collect(Collectors.toList()); + if (enabledTransitions.isEmpty()) { + return false; + } else { + transitions.get(prng.nextInt(enabledTransitions.size())).fire(); + return true; + } + } + + public int step(int k) { + int i = 0; + while (i < k) { + if (!step()) + return i; + ++i; + } + return i; + } + + public Integer[] getMarking() { + final var marking = new ArrayList(); + for (int p = 0 ; p < places.length ; p++) { + Collections.nCopies(places[p].tokens, p).forEach(marking::add); + } + return marking.toArray(new Integer[0]); + } +} diff --git a/src/main/java/de/yasc/example/petrinet/PetrinetParser.java b/src/main/java/de/yasc/example/petrinet/PetrinetParser.java new file mode 100644 index 0000000..9a70a42 --- /dev/null +++ b/src/main/java/de/yasc/example/petrinet/PetrinetParser.java @@ -0,0 +1,160 @@ +package de.yasc.example.petrinet; + +import java.io.BufferedReader; +import java.io.IOException; +import java.io.InputStream; +import java.io.InputStreamReader; +import java.util.ArrayList; + +public final class PetrinetParser implements AutoCloseable { + + private final BufferedReader reader; + + public PetrinetParser(InputStream stream) { + reader = new BufferedReader(new InputStreamReader(stream)); + } + + private static class Line { + + static enum Type { + PLACES, TRANSITION, MARKING, COMMENT, UNKNOWN; + } + + Type type; + Integer val0; + Integer val1[]; + Integer val2[]; + + private Integer parsePositiveInt(String token) throws IOException { + try { + var val = Integer.valueOf(token); + if (val < 0) { + throw new IOException("invalid input - '" + token + "' is not positive"); + } + return val; + } catch (NumberFormatException ex) { + throw new IOException("invalid input - '" + token + "' is not an integer"); + } + } + + private void parsePlaces(String tokens[]) throws IOException { + if (tokens.length != 2) { + throw new IOException("invalid input - syntax of places is 'p <#n>'"); + } + val0 = parsePositiveInt(tokens[1]); + } + + private void parseTransition(String tokens[]) throws IOException { + if (tokens.length < 4) { + throw new IOException("invalid input - syntax of transition is 't ... / ... '"); + } + var vals = new ArrayList<>(); + int i = 1; + for (; i < tokens.length; i++) { + if (tokens[i].equals("/")) { + i++; + break; + } + vals.add(parsePositiveInt(tokens[i])); + } + val1 = vals.toArray(new Integer[0]); + if (i == tokens.length) { + throw new IOException("invalid input - transition has no postset"); + } + if (val1.length == 0) { + throw new IOException("invalid input - transition has no preset"); + } + vals.clear(); + for (; i < tokens.length; i++) { + vals.add(parsePositiveInt(tokens[i])); + } + val2 = vals.toArray(new Integer[0]); + } + + private void parseMarking(String tokens[]) throws IOException { + if (tokens.length < 2) { + throw new IOException("invalid input - syntax of marking is 'm ... "); + } + var vals = new ArrayList<>(); + int i = 1; + for (; i < tokens.length; i++) { + vals.add(parsePositiveInt(tokens[i])); + } + val1 = vals.toArray(new Integer[0]); + } + + Line(String line) throws IOException { + if (line.isBlank()) { + type = Type.COMMENT; + } else { + var tokens = line.split("\\s"); + assert tokens.length > 0; + switch (tokens[0]) { + case "p": + type = Type.PLACES; + parsePlaces(tokens); + break; + case "t": + type = Type.TRANSITION; + parseTransition(tokens); + break; + case "m": + type = Type.MARKING; + parseMarking(tokens); + break; + case "#": + type = Type.COMMENT; + break; + default: + type = Type.UNKNOWN; + } + } + } + } + + public PetriNet read() throws IOException { + PetriNet result = null; + + String input; + int line = 0; + while ((input = reader.readLine()) != null) { + line++; + try { + var parsedLine = new Line(input); + switch (parsedLine.type) { + case COMMENT: break; + case PLACES: + if (result == null) { + result = new PetriNet(parsedLine.val0); + } else { + throw new IOException("places command must occur once"); + } + break; + case TRANSITION: + if (result == null) + throw new IOException("the first command must be 'p' to define the places"); + result.addTransistion(parsedLine.val1, parsedLine.val2); + break; + case MARKING: + if (result == null) + throw new IOException("the first command must be 'p' to define the places"); + result.addMarking(parsedLine.val1); + break; + default: + throw new IOException("unknown command"); + } + } catch (IndexOutOfBoundsException ex) { + throw new IOException(String.format("a place with the specified index does not exist (line %d)", line), ex); + } catch (IOException ex) { + throw new IOException(ex.getMessage() + String.format(" (line %d)", line), ex); + } + } + + return result; + } + + @Override + public void close() throws Exception { + reader.close(); + } +} -- 2.43.5