A ramdon generator of living Choice-Free
A marked Choice-Free graph is a subclass of marked petri net where each place has exactly one output as shown in the following figure
The generator converts a living and normalized SDF to a living Choice-Free. That transformation is apply on each transition for the SDF that have more than 1 input as shown below.
Then the generator gathers the places according to random generated partitions. To achieve that goal the SDF is generated from a strongly conected graph where a node is converted into a transition and an edge into a place.
Execute the Makefile inside Algorithme_C. That produces two executables choiceFreeGenerator (the generator itself) and main_py the script used by Python for the graphical interface. The Python graphical interface scripts are saved under Python.
The needed library, choiceFreeGeneratorLib.a, is saved into Library with the header file named choiceFreeGenerator.h. To link that library to another program :
gcc -o example example.c -lm -lglpk /pathToMakeFileFolder/Library/choiceFreeGeneratorLib.a -I/pathToMakeFileFolder/Library
- libglpk-dev (version 4.61-1)
- C99 standard
NAME
choiceFreeGenerator - a random generator of living Choice-Free
SYNOPSIS
freeChoiceGenerator [nb_transition] [density] [vect_norm] -OPTIONS
DESCRIPTION
choiceFreeGenerator allows user to generate random living Choice-Free network given the desired number of transitions [nb_transition] in the final petri network.
The generation of the final network is based uppon the one of a strongly connected graph with a density set to [density] in ]0, 1].
The [vect_norm] is the desired norm of the repetition vector to get during the generation of a random one for the SDF
OPTIONS
-c : resize the petri net after the transformation from SDF to Choice-Free (can be time consuming)
-f : [filename] save the Choice-Free to a file to [filename] as PNML format
--sdf : get an SDF as output of the generator
--help : get help
./choiceFreeGenerator 10 0.5 20 -f output.pnml produces a ramdom Choice-Free with 10 transitions, with a density of 0.5 and in which the norm of the repetiton vector is equal to 20. The output is saved into the file output.pnml
./choiceFreeGenerator 10 0.5 20 -f output.pnml --sdf produces a ramdom SDF with 10 transitions, with a density of 0.5 and in which the norm of the repetiton vector is equal to 20. The output is saved into the file output.pnml
The following example can be found under the direction Examples
#include"choiceFreeGenerator.h"//use header file of the static librarysrand(time(NULL));
unsigned intnb_transition=10;//number of desired transition in the result Choice-Freedoubledensity=0.5;//density of the graphunsigned intvect_norm=10;//norm of the repetition vector to generateintcleanExtraMem=0;//the transformation from SDF to Choice-Free leaves extra empty memory space, the cleaning process is optional because it's time consumingunsigned intreal_vect_norm=0;
intSDF=0;
//create random Choice-Free from its repetition vector normpPetrinet1=generateRandomChoiceFree(&real_vect_norm, nb_transition, density, vect_norm, SDF, cleanExtraMem);
if(net1==NULL)
{
printf("Error during the generation of a random Choice-Free\n");
return1;
}
printf("Real repetition vector norm : %u\n", real_vect_norm);
//write Choice-Free named "net1" to file "net1.pnml"petriToPnmlFile(net1, "net1", "net1.pnml");
petriFree(net1);unsigned int*vect=weightsComputation(&real_vect_norm, nb_transition, vect_norm);
if(vect==NULL)
{
printf("Error during the generation of a random repetition vector\n");
return1;
}
printf("Real repetition vector norm : %u\n", real_vect_norm);
pPetrinet2=generateChoiceFreeWithVector(nb_transition, density, vect, SDF, cleanExtraMem);
if(net2==NULL)
{
printf("Error during the generation of a random Choice-Free\n");
free(vect);
return1;
}
//write Choice-Free named "net2" to file "net2.pnml"petriToPnmlFile(net2, "net2", "net2.pnml");
free(vect);
petriFree(net2);/* The following substructure are not meant to be stand alone one Memory management are made within the global petri structure and not individually */#definePETRI_PLACE_TYPE 1
#definePETRI_TRANSITION_TYPE 0
#definePETRI_PT_LINK 2
#definePETRI_TP_LINK 3
/* Each element of the petri network will be saved under this structure. It contains : - the type of element (place or transition) for which the value is defined by the directives "PETRI_PLACE_TYPE" and "PETRI_TRANSITION_TYPE" - the label of the element which here correspond to the index of the element inside a fixed size array (for exemple, the label 0 represents the position of that element inside an fixed size array as the element 0) - Exclusively for a place its initial marking*/typedefstructPetriElem*pPetriElem;
typedefstructPetriElem
{
inttype;
unsigned intlabel;
intval;//for a place it will be use to store the initial marking
} petriElem;
/* A link represent an oriented edge inside the petri net between two elements, with a weightBoth input and output elements are saved as pointers to the actual element (to update all the referencesof an element once, if a value need to be changed) */typedefstructPetriLink*pPetriLink;
typedefstructPetriLink
{
pPetriEleminput;
pPetriElemoutput;
unsigned intweight;
} petriLink;
/* A node can be a place or a transition inside the petri net for which all the input and output links from and to thatelement are included. Thus, retrieve a relation from a given node is easier.A node contains : - the number of input elements to that one - a linked list of the references of the links in which the current element is contains as an output - the number of output elements from that one - a linked list of the references of the links in which the current element is contains as an input The input links represent the links where the current element is an output (because the other element will be an input inside that link which connect from the input element to the current one) For example the link elem1 ----> elem2 will be store inside the linked list of input links for the node of elem2 and inside the output links for the node of elem1 All the links will be store inside a double linked list (from an element inside the list the previpous and next elements can be retrieve). It's allow to store the reference of a link inside the linked list of a node and if needed remove that link from the double linked list only given that reference to the link*/typedefstructPetriNode*pPetriNode;
typedefstructPetriNode
{
unsigned intnb_inputs;
pArrayinput_links;//linked list of petri links (inputs of the node, then the node is the output inside the link)unsigned intnb_outputs;
pArrayoutput_links;//linked list of petri links (ouputs of the node, then the node is the input inside the link)
} petriNode;
/* The petri strcuture is quite heavy in memory because links are store multiple time (as references) to make the manipulation of each element easier It contains : - the number of places - a fixed size array of all the places as node (with its input and output links), initially set to NULL - the number of transitions - a fixed size array of all the transitions as node (with its input and output links), initially set to NULL - the number of links - a double linked list containing all the links - a fixed size array of all the places (as elements), initially set to NULL - a fixed size array of all the transitions (as elements), initially set to NULL The number of places is the size of the fixed size arrays of places as node and as element (the same for the number of transitions) When a node, or an element as not been set (or has been removed) its value at the index of the element (set as its label) is set to NULL A node cannot be removed inside the petri net : the removal of an element (a place or a transition) implies the removal of the corresponding node and its links The advantage of that structure is to access all the element rapidly. For example if the user want to access all the links of the transitions i, it can access its corresponding node inside the fixed size array of node at the index i and loop through all its links thanks to the linked list of input and output links A change of attribute (for example a label or an initial marking for an element, or a weight for a links) impacts all the node because only the reference are store The double linked list of links, fixed size arrays of place and transitions, all to remove it one to release the memory*/typedefstructPetri*pPetri;
typedefstructPetri
{
unsigned intnb_pl;
pPetriNode*places;
unsigned intnb_tr;
pPetriNode*transitions;
unsigned intnb_links;
pArray2links;//linked list of petri linkspPetriElem*pl_elems;
pPetriElem*tr_elems;
} petri;A simple tutorial to understand how to use the structure for Petri net.
unsigned intnb_place=5;
unsigned intnb_transitions=5;
inti;
//initialize structurepPetrinet3=petriCreate(nb_place, nb_transitions);
//add placespetriAddPlace(net3, 0, 1);//add place 0 with an initial marking of 1petriAddPlace(net3, 3, 2);//add place 3 with an initial marking of 2petriAddPlace(net3, 4, 3);//add place 4 with an initial marking of 3petriAddPlace(net3, 1, 4);//add place 1 with an initial marking of 4//the place 2 will not be set inside the petri structure (it value inside the fixed size array will be set to NULL)//add transitionsfor(i=0; i<nb_transitions; i++)
{
petriAddTransition(net3, i);//add transition i
}
//add linkspetriAddlink(net3, PETRI_PT_LINK, 0, 1, 12);//add link between the place 0 and the transition 1 with a weight of 12petriAddlink(net3, PETRI_PT_LINK, 1, 3, 0);//add link between the place 1 and the transition 3 with a weight of 0petriAddlink(net3, PETRI_TP_LINK, 4, 3, 4);//add link between the transition 4 and the place 3 with a weight of 4petriAddlink(net3, PETRI_TP_LINK, 3, 2, 1);//add link between the transition 3 and the place 2 with a weight of 1petriAddlink(net3, PETRI_TP_LINK, 3, 0, 5);//add link between the transition 3 and the place 0 with a weight of 5petriAddlink(net3, PETRI_PT_LINK, 2, 1, 12);//not possible because place 2 does not existspetriAddlink(net3, PETRI_TP_LINK, 3, 2, 12);//not possible because place 2 does not existspPetriLinklink=petriGetLink(net3, PETRI_PT_LINK, 0, 1);//get link between the place 0 and the transition 1printf("Weight of link between place 0 and transition 1 : %d\n", link->weight);
printf("Weight of link between transition 4 and place 3 : %d\n", petriGetWeightLink(net3, PETRI_TP_LINK, 4, 3));
pPetriElemelem=petriGetPlace(net3, 0);//get place 0printf("Initial marking of place %u : %d\n", elem->label, elem->val);
printf("Initial marking of place 4 : %d\n", petriGetInitialMarking(net3, 4));
printf("Places : { ");
for(i=0; i<net3->nb_pl; i++)
{
displayPetriElem(net3->pl_elems[i]);
printf(" ");
}
printf("}\n");
//get all the link for a nodepPetriNodenode=net3->places[0];
pArrayp=node->input_links; //simple linked listprintf("Inputs of node 0 : \n");
while(p)
{
printf("\t");
link=petriNodeGetLinkFromArrayNode(p);
elem=link->input;
displayPetriElem(elem);
printf("\n");
p=p->next;
}
printf("Outputs of node 0 : \n");
p=node->output_links;
while(p)
{
printf("\t");
link=petriNodeGetLinkFromArrayNode(p);
elem=link->output;
displayPetriElem(elem);
printf("\n");
p=p->next;
}//remove place 3petriRemovePlace(net3, 3);
printf("Places : { ");
for(i=0; i<net3->nb_pl; i++)
{
displayPetriElem(net3->pl_elems[i]);
printf(" ");
}
printf("}\n");
//clear extra memory spacepetriClearPlaces(net3);
printf("Places : { ");
for(i=0; i<net3->nb_pl; i++)
{
displayPetriElem(net3->pl_elems[i]);
printf(" ");
}
printf("}\n");
//free memorypetriFree(net3);In order to visualize the results of C functions we use Python. A simple server socket in C collects python requests, process the request and send back the result to python. All the described process can be visualized on the following figure :
The visualization is usefull to debug code for really small graphs (around 10 nodes).
Version : Python 3.5
Used modules :
- ctypes
- networkx
- graphviz (pay attention that you probably will need to install it for python and for the OS)
The module SocketCommunication contains all the needed classes and functions to communicated with the server side. We can underline :
- Task (class) that store all the values of request. Each request starts with a specific task that help the server to know which result needed to be sent back
- Request (ctypes structure) which is the formatted request to send
- createRequest (function) create a new request while formatting the arguments into the correct ctypes
For example, to create a new request use the command
request = createRequest(task = Task.f_createStronglyConnectedGraph, n=n, D=D)with n, D specific arguments
- createRequest (function) create a new request while formatting the arguments into the correct ctypes
For example, to create a new request use the command
- Server (class) the main class that starts the server at the begining and then sends the needed request and return the response as string
For example, to start the C server side from Python use
src=Server(port=5112, buffersize=512, start=True)orsrc=Server()to fill automatically the arguments. Port is the communication port (which can be found automatically if not specified) and buffersize is the size of the buffer used between the clent and the server to transmit data. To start the C server side from an external terminal, start the server and in Python usesrc=Server(port=5112, buffersize=512, start=False). Be aware of the closing of the server : at the end of the script the server need to be closed. For that purpose,use the command srv.close()
The module GraphDisplay takes the formatted response of the server and convert it into a usable graph.
An example of use :
importCFunctionsascimportGraphDisplayasgd#%%numberNode=5density=0.5NumberOutputNode=2net=c.choiceFree(n=numberNode, density=density, rep_vect_norm=10, cleanExtraMemSpace=False)
f_net=gd.drawPetriNetwork(net.obj, nodeSize=500, widthArraw=1.5)
f_net.show()
c.free(net)
c.exit()#free all the non-free object