Analyzing and Traversing Bigraphs
To analyse a bigraph and its elements, several methods are made available by Bigraph Framework via the interface org.bigraphs.framework.core.Bigraph located in the core module.
These methods are implemented by all concrete bigraph implementations, thus, providing a unified way to handle the traversal for all kind of bigraphs.
In the following, we show some examples on how to inspect, analyse and traverse a bigraph.
Checking Properties of a Bigraph
This part shows some methods that return the status for different properties of a bigraph that one can check.
The presented methods can be directly called on the bigraph instance.
Note that this list is not exhaustive, please refer to the JavaDoc of the Bigraph interface.
Bigraph#isGround()
A bigraph is called ground, if it has no sites and inner names.
Bigraph#isPrime()
A bigraph is called prime, if its place graph only has one root and no inner names.
Bigraph#isEpimorphic()
A bigraph is epimorphic if and only if its place graph has no root that is a barren and its link graph has no idle outer names.
Bigraph#isMonomorphic()
A bigraph is monomorphic if and only if no two sites are siblings and no two inner names are siblings. With other words, every edge has at most one inner name (i.e., no two inner names are peers).
Bigraph#isActive()
A bigraph is active if all its sites are active.
Navigating through a Bigraph
In the following, a subset of basic methods for navigating through a bigraph are presented.
The presented list is not exhaustive, please refer also to the JavaDoc of the Bigraph interface.
Additional explanations are given in Traversing a Bigraph on how to implement more complex traversals, which use the presented methods below.
Place Graph
The first methods show, how to navigate through a bigraph's place graph.
Bigraph#getParent(BigraphEntity node)
Returns a BigraphEntity representing the parent for the given bigraph's place.
Passing a root as argument will always return null.
Bigraph#getChildrenOf(BigraphEntity node)
A Collection<BigraphEntity> is returned that contains the set of children for the given node. This collections includes also sites.
Bigraph#getSiblingsOfNode(BigraphEntity node)
A Collection<BigraphEntity> is returned that contains all siblings of the given node of the current bigraph. The node itself is not included.
Link Graph
Navigation through the bigraph's link graph is also supported. Some interesting methods are listed next.
Bigraph#getLinkOfPoint(BigraphEntity point)
This method returns a link of type BigraphEntity.Link for the given point (i.e., a port or an inner name), or null if no link is connected for this point.
The link can be an edge or outer name.
For example, all existing ports of a node can be acquired through the method Bigraph#getPorts(BigraphEntity node).
Bigraph#getSiblingsOfInnerName(BigraphEntity.InnerName innerName)
A Collection<BigraphEntity.InnerName> is returned containg the siblings of the given inner name.
Siblings of an inner name are connected to the same edge or outer name.
Note that the collection does not contain ports, only inner names.
Bigraph#areConnected(BigraphEntity.NodeEntity place1, BigraphEntity.NodeEntity place2)
This method checks, whether two nodes are connected via an edge or an outer name.
Traversing a Bigraph
The framework includes no specific traversal algorithms for bigraphs itself but provides all necessary methods to implement any graph traversal algorithm. Therefore, also review some of the presented methods above in Navigating through a Bigraph or consulte the JavaDoc API.
A bigraph is a combination of two structures as explained in the Getting Started Guide. That means that both structures can be traversed independently.
Different traversal algorithms for trees and graphs exist such as the top-down and postorder traversal, or breadth-first and depth-first traversal. For a more detailed elaboration on tree and graph algorithms we refer to [1].
The next examples demonstrate how to implement traversal strategies for place and link graphs by employing two different implementation approaches. For the first one, Guava (a Java library that contains graph algorithms) is used for a breadth-first traversal on a place graph. Concerning the second implementation, a naive link graph traversal algorithm without additional libraries is implemented.
Traversing a Place Graph Using Guava
The next listing demonstrates the usage of Guava and a bigraph instance on how to implement a breadth-first traversal for its place graph. This example can be adapted to traverse through a link graph.
DefaultDynamicSignature signature = ...;
PureBigraphBuilder<DefaultDynamicSignature> builder = pureBuilder(signature);
builder
.createRoot()
.addChild("A").down().addChild("D").up()
.addChild("B").down().addChild("D").addChild("D").up()
.addChild("E").down().addChild("D").addChild("D").addChild("D").top()
;
PureBigraph bigraph = builder.createBigraph();
Traverser<BigraphEntity> traverser = Traverser.forTree(x -> {
List<BigraphEntity> children = bigraph.getChildrenOf(x);
System.out.format("%s has %d children\n", x.getType(), children.size());
return children;
});
Iterable<BigraphEntity> bigraphEntities = traverser.breadthFirst(bigraph.getRoots());
bigraphEntities.forEach(x -> {
System.out.println(x);
});
The corresponding output is:
ROOT has 3 children
ROOT has 3 children
BigraphEntity{instance=class org.eclipse.emf.ecore.impl.DynamicEObjectImpl, control=null, type=ROOT}
NODE has 1 children
NodeEntity{v0, control=A, 0}
NODE has 2 children
NodeEntity{v2, control=B, 0}
NODE has 3 children
NodeEntity{v5, control=E, 0}
NODE has 0 children
NodeEntity{v1, control=D, 4}
NODE has 0 children
NodeEntity{v4, control=D, 4}
NODE has 0 children
NodeEntity{v3, control=D, 4}
NODE has 0 children
NodeEntity{v7, control=D, 4}
NODE has 0 children
NodeEntity{v8, control=D, 4}
NODE has 0 children
NodeEntity{v6, control=D, 4}
The function Traverser#forTree() returns a Traverser instance. Then the method breadthFirst() is called accepting one or multiple nodes that indicate the start of the traversal.
Guava's Traverser class contains more methods, for example, depthFirstPreOrder() and depthFirstPostOrder() which shall be self-explanatory.
Traversing a Link Graph Without Additional Libraries
The next listing illustrates how to traverse the link graph in no specific order. A link graph can be regarded as an undirected hypergraph.
A brief outline of this very naive algorithm is as follows: First, all links are returned by calling Bigraph#getAllLinks(). Afterwards, we iterate over this list to get the respective points (i.e., ports and inner names) that are connected to that link.
builder = pureBuilder(signature);
BigraphEntity.OuterName y1 = builder.createOuterName("y1");
BigraphEntity.OuterName y2 = builder.createOuterName("y2");
BigraphEntity.OuterName y3 = builder.createOuterName("y3");
BigraphEntity.InnerName x1 = builder.createInnerName("x1");
builder.createRoot()
.connectByEdge("D", "D", "D").linkToOuter(y1)
.addChild("D").linkToOuter(y1).down()
.addChild("D").linkToOuter(y2).addChild("D").linkToOuter(y3)
.addChild("User").linkToOuter(y1).up()
.addChild("D").linkToInner(x1);
PureBigraph bigraph1 = builder.createBigraph();
bigraph1.getAllLinks().forEach(l -> {
List<BigraphEntity> pointsFromLink = bigraph1.getPointsFromLink(l);
pointsFromLink.forEach(p -> {
if (BigraphEntityType.isPort(p)) {
BigraphEntity.NodeEntity<DefaultDynamicControl> nodeOfPort = bigraph1.getNodeOfPort((BigraphEntity.Port) p);
int ix = bigraph1.getPorts(nodeOfPort).indexOf(p);
System.out.format("Node %s with port at index %d is connected to link %s\n", nodeOfPort.getName(), ix, l.getName());
} else if (BigraphEntityType.isInnerName(p)) {
System.out.format("Inner name %s is connected to link %s\n", ((BigraphEntity.InnerName) p).getName(), l.getName());
}
});
});
The corresponding output in this case is:
Node v2 with port at index 1 is connected to link y1
Node v3 with port at index 0 is connected to link y1
Node v6 with port at index 0 is connected to link y1
Node v4 with port at index 0 is connected to link y2
Node v5 with port at index 0 is connected to link y3
Node v0 with port at index 0 is connected to link e0
Node v1 with port at index 0 is connected to link e0
Node v2 with port at index 0 is connected to link e0
Inner name x1 is connected to link e1
Node v7 with port at index 0 is connected to link e1
Note that idle inner names (i.e., not connected to a link) are not covered by the example above.