Visualization techniques have been used with increasing success to assist users in complex system analyses, providing meaningful insights. Structured Occurrence Nets (SONs) originate from occurrence nets (ONs), which are directed acyclic graphs showing causality and concurrency in system executions. Visualization of SONs in tools such as SonCraft is currently limited, as there is a lack of effective support to visualise complex and large data sets. In this paper, we address challenges resulting from the overlapping and out-of-order placement of ONs, and propose a novel solution to deal with this issue based on a step execution policy. Also, we discuss the development of the resulting algorithm, and SonCraft plug-in implementing it.
Complex and large data sets drive considerable attention from information
science researchers, crime investigators, and decision makers within governments.
Tremendous growth of this kind of data tends to transform its analysis into a
hard process. The existence of such data provides important insights, but also
raises challenges. In particular, visualization techniques have been used with
increasing success to assist users in various analyses, and providing valuable
insights about system structure and behaviour [
Structured occurrence nets (SONs) [
The paper is organised as follows. The next section describes the basic features SONs. Section 3 discusses visualization challenges related to SONs in SonCraft, and proposes a novel solution to deal with them based on maximal concurrency. Section 4 describes implementation and results. The last section contains concluding remarks. 2 2.1
Ocurrence net is an abstract record of a single execution of some computing
system in which only information about causality and concurrency between events
and visited local states is represented. SONs [
SONs are underpinned by causal structures which extend causal partial orders with additional ordering, called weak causality. Two events ordered in this way can be executed in the order given or simultaneously. Moreover, if two events are weakly ordered in both directions(this means, in particular, that weak causality is not assumed to be acyclic), then they can only be executed simultaneously. In SONs, weak causality results from passing tokens through channel places, whereas the non-channel places introduce the standard causality, as in ONs. In Figure 1 (b), (e0) weakly causes (e2), and the events (e1) and (e3) form weak causality cycle.
tured occurrence nets (BSONs) are used [
Although SonCraft allows visualising data in an attractive way, it does so mainly when cases are manually modelled. The main issue which users face while attempting to load data automatically is overlapping and out-of-order placement. As shown in Figure 3, we should expect both problems after inputting data sets into SonCraft. Figure 4 shows a better way of presenting the same data which avoids overlapping, but still places ONs in an unstructured way. The latter problem will be addressed by applying the idea of maximal concurrency to order the events, and so also the ONs.
There are various reasons due to which overlapping occurs. The first one is due to the fact that although data is loaded automatically when it is retrieved, it is loaded randomly. The other reason is given by the fact that the current SonCraft platform is not prepared to deal with data in an automatic way. 3.2
Our approach to solving visualisation problems related to SONs consists in a
careful consideration of the positioning of the ONs within the workplace area.
The method involves the arrangement of ONs in a particular way so as to prevent
and avoid overlapping and out-of-order placement by using maximal concurrency
(a step execution policy in the sense of [
We have taken advantage of the well-known algorithms such as topological
sorting and Tarjan algorithm. The idea behind the algorithm is explained and
explanation is supported by clarifying examples. Our consideration to solve the
visualization challenge led us to use topological sorting which treats a directed
graph as a basis of a linear ordering for that graphs vertices [
The result of applying visualization based on the maximal concurrency policy
discussed above is illustrated in Figure 5. As shown, all events within the various
ONs are maximal and have been manually clustered. However, our approach is
to allow data sets to be retrieved automatically rather than manually. As such,
several algorithms have been considered to assist us in doing so. As Khan [
As a result, initially, our algorithm could not handle such a situation, because if it was to be applied, for instance, in Figure 6, then event (a) had another event connected with it, i.e., event (d). However, our approach to cope with these problems in such situations can be solved, should they occur, by using Tarjan algorithm. This algorithm was adapted so as to allow it to detect this special kind of cycle (i.e. weak causality cycle). The adaptation implied the ability to push every event of a particular cycle in one set as maximal concurrency cluster, should this type of cycle occur. For instance, after applying the algorithm to the graph in Figure 6, the first cycle between the three existing ONs, namely (ON 2, ON 3 and ON 4) was detected. This was made via channel places (q0 and q1) and (q2 and q3). As such, the algorithm will push all events in this cycle, namely events (a, d and f ), to one set. After that, event (b) is pushed in one set. Finally, the second cycle between ON 1 and ON 2 is detected via channel places (q4 and q5) in one set, namely events (g and c). Figure 6 illustrates the result. The other interesting case that we have discovered during our investigation of policy-driven visualization in SonCraft is shown in the next example, depicted in Figure 7 (a). Thus, if we apply our algorithm, that use the topological algorithm, we will push events (e1 and e3) as a set, and then push event (e2) as a set, and finally event (e4) as another set. Figure 7 (b) shows the result. Although events (e2) and (e4) can occur together due to asynchronous communication, this could not be handled by the standard algorithm, because event (e2) will be treated before event (e4). A possible solution is given by an updated algorithm where, after detecting asynchronous communication, one pushes all events within it into the same set. Figure 7 (c) shows the result obtained after applying this solution
Theoutput
to our example. Note that the algorithm always succeeds when applied to a
well-formed SON thanks to the general properties of SONs established in [
The pseudo-code of our algorithm for policy-driven visualisation of SONs: 4
We have implemented the policy-driven visualization algorithm as a Java
plugin in the SonCraft toolkit (based on the Workcraft platform). Workcraft is a
platform that provides a framework for the development and analysis of graph
models [
Fig. 8. Retrieve Big Data menu.
Here is a brief explanation of the functionality of our plug-in. Firstly, our
algorithm finds the starter conditions. These are conditions without pre-events.
For every starter condition, we initialise two arrays. This will track which
conditions will be added or removed for the next loop step. Next, we will find all
cycles in the graph via the Tarjan Algorithm and store them in a list.
Afterwards, we need to find starter events and store them in a list. Starter events
are all events that do not have previous events. Next, we will loop through all
starter conditions. If we catch any starter events (for every event), we will add
them to our temporary array if they have no connections. We will also add them
to our temporary array if they have two connections, and the event does not
follow an existing event in the temporary array. Then we will set the next
condition as a starter and mark it if it is not in a cycle. However, if it is in a cycle,
we will mark the starter condition and treat it separately. Next, we will loop
through all starter conditions again. For every starter condition, we check to see
if the condition is not being marked for removal (the condition has been skipped
because the event following the condition is a part of Trajan’s cycle). If this is
the case, we obtain its post-event and all cycle events. Just after the two loops,
we will decide if a set of maximal concurrency has completed or not. Finally,
after we are sure that there are no more starter conditions, we will display the
maximal concurrency events. [
Figure 11 shows the last test case. It involves asynchronous communications, and the algorithm successfully pushes its events into one set, namely (e2 and e4).
Finally, as displayed in the next figure 12, we provided a figure that shows a larger example of our plug-in. In this paper, the problems of ONs overlapping and out-of-order placement have been looked into, and a novel solution to address them has been proposed. The design and development of the corresponding algorithm has been discussed. We provided test examples showing that our algorithm works properly.
In future work we will address the visualization of behavioural abstraction
through maximal concurrency policy. Another direction for future work is to
implement visualization based on local maximal concurrency [
The authors acknowledge financial support provided by University of Hai’l. Also, we would like to thank the reviewers for their insightful comments on the paper.