This project has moved. For the latest updates, please go here.

Yttrium Demo Package: Petri Net

 
Petrinetz2_wikipedia.png Yttrium tries to handle whole system graphs instead of just expression trees. Hence it should be able to deal with simple network structures like petri nets. I've written a sample package that shows how you could implement such networks in yttrium: The PetriNet package.

Petri nets are bipartite directed graphs, composed of places and transitions. Places can take any number of tokens (thus have a value), and are connected by transitions, which fire nondeterministically (= remove a token from each input and add one to every output). Have a look at the Wikipedia article linked above for more details.

1 - Petri Net Requirements and Representation

  • Places: perfectly fit into the Signal scheme.
  • Transitions: perfectly fit into the Port scheme, but we'll have to provide an architecture.
  • Tokens: The value assigned to the signals. We'll have to write a YttriumCustomDataStructures value structure, or simply use an existing one.
  • nondeterminism: The default yttrium scheduler is deterministic, so we'll have to inject randomness in some way.

2 - Custom Value Structure: TokenValue

TokenValue derives from ValueStructureBase of the packages helper module, so we get some parts of the implementation for free.

First, we'll name the structure as PetriNet.Token and store the actual number of tokens in a local variable:

private static readonly MathIdentifier _customTypeId = new MathIdentifier("Token", "PetriNet");
private readonly long _dataValue;


To add some convenience, we want to be able to convert our structure to and from integers, so we add direct (not required to be direct, the YttriumConversionModule also finds indirect conversion path automatically, but it's trivial in this case) conversion routes from and to the integer structure of the standard package:

public static void Register(ILibrary library)
{
    library.AddCustomDataType<TokenValue>();
    ValueConverter<TokenValue>.AddConverterFrom<IntegerValue>(true, ConvertFrom);
    ValueConverter<TokenValue>.AddConverterTo(ValueConverter<IntegerValue>.Router, true,
    delegate(ICustomData value)
    {
        return new IntegerValue(((TokenValue)value).Value);
    });
}
public static TokenValue ConvertFrom(ICustomData value)
{
    return (TokenValue)ValueConverter<TokenValue>.ConvertFrom(value);
}
public static TokenValue ConvertFrom(IntegerValue value) { return new TokenValue(value.Value); }
public static explicit operator TokenValue(IntegerValue value) { return new TokenValue(value.Value); }


We also need to be able to increment or decrement it, so we add the following two methods:

public TokenValue Increment()
{
    return new TokenValue(_dataValue + 1);
}
public TokenValue Decrement()
{
    return new TokenValue(_dataValue - 1);
}


Finally, to be able to serialize our petri nets, we have to add the following serializer code, that simply writes the number of tokens to an XML node:

public override void Serialize(XmlWriter writer, IDictionary<Guid, Guid> signalMappings,
    IDictionary<Guid, Guid> busMappings)
{
    writer.WriteString(_dataValue.ToString(Config.InternalNumberFormat));
}
private static TokenValue Deserialize(XmlReader reader, IDictionary<Guid, Signal> signals,
    IDictionary<Guid, Bus> buses)
{
    return new TokenValue(long.Parse(reader.ReadString(), Config.InternalNumberFormat));
}

3 - Custom Architecture: TransitionArchitecture

 
Einfaches_petrinetz_wikipedia.png We also have to provide an architecture, that will be loaded into the ports at runtime. Again we derive from a base class provided in the package helper assembly, but there are several quite different ways to implement an architecture. We'll take the most simple case without any processes: we inherit from GenericSimpleArchitecture. There's actually only one interesting method of our class, and that's the one that actually implements the transition firing. We first check that every input signal has at least one token (else we do nothing - Action is called whenever any of the input signal changes its value), and then remove one token from every input and add one to each output

protected override void Action(IList<Signal> inputSignals,
    IList<Signal> outputSignals, IList<Signal> internalSignals, IList<Bus> buses)
{
    foreach(Signal input in inputSignals)
    {
        TokenValue token = input.Value as TokenValue;
        if(token == null || token.Value < 1)
            return;
    }

    // apparently all nodes ok, so we fire:

    foreach(Signal input in inputSignals)
        input.PostNewValue(((TokenValue)input.Value).Decrement());
    foreach(Signal output in outputSignals)
        output.PostNewValue(((output.Value as TokenValue) ?? TokenValue.Zero).Increment());
}

4 - Nondeterminism: PetriNetScheduler

To implement the scheduler randomness we slightly modify the default scheduler to process only a single random event of the so called delta event list in the signal assignment phase, instead of processing the whole list at once:

Original Code (ImmediateScheduler):
while(_deltaEvents.Count > 0)
{
    SchedulerEventItem item = _deltaEvents.Pop();
    ISchedulable subject = item.Subject;
    if(subject.CurrentValue == null || !subject.CurrentValue.Equals(item.Value))
    {
        item.Subject.CurrentValue = item.Value;
        _schedulablesWithEvent.Add(item.Subject);
    }
}


New Code (PetriNetScheduler):
if(_deltaEvents.Count > 0)
{
    int index = _random.Next(_deltaEvents.Count);
    SchedulerEventItem item = _deltaEvents[index];
    _deltaEvents.RemoveAt(index);
    ISchedulable subject = item.Subject;
    if(subject.CurrentValue == null || !subject.CurrentValue.Equals(item.Value))
    {
        item.Subject.CurrentValue = item.Value;
        _schedulablesWithEvent.Add(item.Subject);
    }
}

5 - Providing a Package Manager

That's basically it. Now the only additional thing we need if we want to use this code as a real package is a PackageManager, a class responsible to register load all the data structures to the library. In our case that's trivial:

public class PetriNetPackageManager : IPackageManager
{
    public string Domain
    {
        get { return "PetriNet"; }
    }

    public void Register(ILibrary library)
    {
        if(library == null)
            throw new ArgumentNullException("library");

        library.AddEntity(new ArbitraryGenericEntity("|", "Transition", "PetriNet"));

        library.AddArchitecture(new TransitionArchitectures());

        TokenValue.Register(library);
    }
}

Last edited Jul 29, 2012 at 1:26 PM by cdrnet, version 3

Comments

No comments yet.