Place Graphs

Learn how place graphs represent hierarchical structure through nesting, siblings, and regions, and how sites abstract from unspecified or variable contents.

Exercise 1: Building and Composing Hierarchies

Background

The place graph, which is a forest, describes the structural organization of entities, that is, nodes in the bigraph. It represents a hierarchy in which entities are located relative to one another through nesting, sibling relationships, and regions (roots of the forest).

For example,

Room.Adult

states that an Adult is located inside a Room. The dot "." is called the nesting operator. (This operator will be important again in Exercise 2 when working with abstractions.)

Two entities under the same parent are siblings:

Room.(Adult | Child)

Here, Adult and Child occupy the same Room.

At the outermost level, a bigraph may contain one or more regions, which are the roots of the forest. This distinction becomes important when independently constructed bigraphs are combined.

Two operations (namely products) are particularly useful:

B₁ || B₂

keeps B₁ and B₂ as distinct bigraphs in separate regions, whereas

B₁ | B₂

merges their contents into a common region.

Parallel vs. Merge Product [1]

Use || when modelling distinct bigraphs, and | when combining bigraphs into the same region.

Problem

Consider two rooms:

• one room contains an Adult,
• another room contains a Child.

Start by modelling each room independently:

Room.Adult

and

Room.Child

Tasks

1. Define the controls:

   • Room
   • Adult
   • Child

2. Construct the two independent place graphs:

   Room.Adult

   and

   Room.Child

3. Combine them using the parallel product:

   Room.Adult || Room.Child

   and determine:

   • How many regions does the resulting bigraph have?
   • Are the two Room nodes siblings?

4. Combine the same bigraphs using the merge product:

   Room.Adult | Room.Child

   and determine:

   • How many regions does this bigraph have?
   • Which nodes are siblings?
   • Which nesting relationships remain unchanged?

5. Consider a larger building model. Decide which operation you would use when:

   • Modelling two physically independent buildings,
   • modelling two rooms belonging to the same floor, and
   • explain the modelling difference between | and ||.

---

Download Bigraph Framework Starter Project

Show Java solution

Construct the individual bigraphs

PureBigraph roomWithAdult = pureBuilder(signature)
    .root()
    .child("Room").down()
        .child("Adult")
    .create();

This represents:

Room.Adult

The second room is constructed independently:

PureBigraph roomWithChild = pureBuilder(signature)
    .root()
    .child("Room").down()
        .child("Child")
    .create();

representing:

Room.Child

Parallel product

Combine the two bigraphs using the parallel product:

PureBigraph parallel = ops(roomWithAdult)
    .parallelProduct(roomWithChild)
    .getOuterBigraph();

Conceptually:

Room.Adult || Room.Child

The resulting place graph contains two regions:

r₀                    r₁
│                     │
└── Room              └── Room
    └── Adult             └── Child

The two Room nodes are therefore not siblings. Each belongs to a different root.

Merge product

Now combine the same bigraphs using the merge product:

PureBigraph merged = ops(roomWithAdult)
    .merge(roomWithChild)
    .getOuterBigraph();

Conceptually:

Room.Adult | Room.Child

The result contains one region:

r₀
├── Room
│   └── Adult
│
└── Room
    └── Child

The two Room nodes are now siblings, because they share the same parent root.

The internal nesting relationships remain unchanged:

Adult < Room
Child < Room

Only the relationship between the two independently constructed bigraphs has changed.

Modelling Decision

Use

B₁ || B₂

when the two structures should remain spatially distinct.

Use

B₁ | B₂

when their contents should become part of the same region.

For example:

Building₁ || Building₂

can represent two independent buildings, whereas

Room₁ | Room₂

can represent two rooms belonging to the same spatial region, such as a common floor.

---

Exercise 2: Sites for Abstraction

Background

A site represents an unspecified part of a bigraph's place structure. It acts as a placeholder for zero or more entities that may be supplied later through composition or rewriting.

This gives rise to an important modelling distinction.

Room.1

states that the Room contains no further structure at this position.

By contrast,

Room.id

contains a site and therefore leaves the room's contents unspecified. The site may later represent zero or more entities.

Although both models may initially appear to describe an empty room, they express different assumptions about the system.

Sites as Structural Abstraction [1]

Use 1 when no children are possible, and id when zero or more children may be supplied by the surrounding context.

Problem

Consider two rooms in a building.

The first is a sealed room whose contents are fully known. No additional entities may occur inside it.

The second is a general-purpose room whose current contents are intentionally left unspecified. Depending on the surrounding context, it may later contain people, furniture, devices, or other entities.

Model both situations and compare their place structures.

Tasks

1. Define all the necessary controls of the signature.

2. Construct a bigraph representing:

   Room.1

   Then, construct a second bigraph representing:

   Room.id

   and explain why Room.1 and Room.id are not equivalent, even if both currently appear empty.

3. Consider the following possible room contents:

   Adult
   Child
   Table

   Which room model would you choose if these contents are not yet known at modelling time?

4. Build a place graph containing an Adult, a Child, and a Table. How can this place graph be nested into the empty Room place graph? Construct the resulting bigraph.

---

Download Bigraph Framework Starter Project

Show Java solution

Model Room.1

PureBigraph roomOne = pureBuilder(signature)
    .root()
    .child("Room")
    .create();

Conceptually:

Room.1

Its place graph contains a Room without any nested site:

r₀
└── Room

The absence of a site makes the model structurally complete at this position.

Model Room.id

PureBigraph roomId = pureBuilder(signature)
    .root()
    .child("Room").down()
        .site()
    .create();

Conceptually:

Room.id

Its place graph contains a site:

r₀
└── Room
    └── □

The site abstracts from the concrete contents of the room. It marks a position at which additional place structure may later be inserted.

The modelling distinction is therefore:

Room.1  ≠  Room.id

Use 1 when the model should state that no children are possible at that position.

Use id when the model should leave the contents open and allow zero or more entities to be supplied by the surrounding context.

---

References

• [1] B. Archibald, M. Calder, and M. Sevegnani. Practical Modelling with Bigraphs. Formal Aspects of Computing, 37(3), Article 20, pp. 1–36, 2025. DOI: 10.1145/3721142.