Graph Agent Library

Graph is an abstract structure that can represent different types of relationships between real-world objects, not necessarily networks for graph agents. For example, graph can represent dependencies between tasks of a project. So, Graph class is universal and does not know anything about geometry or agents. This is the simple example of a directed graph with 3 nodes - A, B, C and 3 arcs - AB, BA, AC:

This graph can be created using the following code:

The graph above contains just string labels in both its nodes and arcs. The toString() method of a graph returns a string containing the number of nodes and arcs. For the graph we’ve just created it would be:

The Graph class has two inner classes - Node and Arc. These 3 classes provide the basic API for graphs. The code below illustrates retrieving lists of graph nodes and arcs:

Note that Graph is a generic class with two type parameters that allow to specify types of the content of its nodes and arcs. In the example above, we use String as type of contents of both arcs and nodes. The contents of a node or an arc is called its value.

The getNode method returns the instance of Node containing the specified value. The Node class, in its turn, has getArcsOut method that returns the list of all arcs going out of this node:

The code below uses list returned by the getArcsOut method to access the specific arc and, ultimately, its value:

Similarly to getNode, getArc method returns the instance of Arc containing the specified value. Arc class has getSource and getDest methods that allow to access its source and destination nodes:

containsNode and containsArc methods check if graph contains a node or an arc with some specified value:

As can be seen from the examples above, agents move along the graph over the course of the simulation. This implies some type of spatial layouts to be assigned to graph nodes and arcs. The two most natural choices is using either a 2D or a 3D Euclidean space. We consider using a 2D space as the most practical approach because:

It is important to note that using 2d space as a base has some shortcomings that need to be addressed in some models:

So, the basic space for our graph agents is a Euclidean 2d space. Graph with such 2d representation are called geometric graphs.

Any graph node a of a geometric graph corresponds to a point (x, y) in 2-dimensional space. An arc of such graph, in its turn, corresponds to a polyline, the first point of which is the same with the source node and the last point is the same as the destination node. Polyline has at least 2 points in the 2d space. Polylines consisting of less than two points are considered incorrect. Any polyline can be represented as an ordered list of points and segments, the number of segments always equals to the number of point minus 1.

At this point, we need to make a decision whether we should consider directed and undirected graphs separately. It turns out that for simulation purposes is it convenient to only have directed arcs because:

However, it is important to note that using only directed arcs makes modelers explicitly specify the relations between the two directed arcs constituting a single bi-directional relationship. So, bidirectional arcs are represented with two directed arcs with the source and destination nodes swapped. The two such arcs are reverse arcs for each other. These arcs also require that their polylines are reverse polylines. A reverse polyline is the one that consists of points of the original polyline in the reverse order.

Graph agent is the type of agent that lives in environment consisting of a directed graph with geometric representation in 2D space called graph environment. Graph environment has the following features:

Graph agents can be located either at graph nodes or on graph arcs.

A specific position in either node or arc is called a geometric graph position, or simply a position. Graph agents move between positions only along graph nodes and arcs.

Agents are represented as zero-size points located in the graph and moving along this graph. For brevity, we will say that agents live in the graph.

Geometric size of agents can be both important or not important for the simulation logic depending on the chosen level of modeling abstraction. For example, when modeling intercity delivery network, trucks size is almost always not important. Oppositely, the size of cars does matter for microscopic urban traffic models.

Regardless of whether agent’s size does matter or not, it is convenient to associate every agent with a certain single point in the 2d space so that a modeler always has a simple answer to the question “Where is the agent now?”. If necessary, spatial relationships between agents are considered with the additional calculations that take their geometric characteristics into account.

In the previous section, we have learned how to create simple graphs. But those graphs did not know anything about 2D geometry, neither did they know about agents.

Let us now create a graph that corresponds to the following transportation network:

There are 3 significant points in the network above - these are points A, B, and C. A and C are connected by one-way direct line, whereas A and B are connected by a two-way polyline with one bend point.

Such scheme can represent, for example, a shop floor layout with machines located in points A, B, and C. The polylines represent trajectories of moving between the corresponding points.

Note that the scheme above resembles the graph that we had in the previous section. But this scheme represents the geometric locations of points and trajectories, not their logical connectedness.

In simulations, it is useful to combine the graph representation with geometric representation of our transportation network. Here is the way to do it:

The transportation network that we want to create needs to be suitable for agents to live in it.

The code below creates such graph:

Let us go through the code above line by line. The following line creates an instance of GraphEnvironment with AgentGraphNodeImpl as type of node values and AgentGraphArcImpl as type of arc values:

Next, we add a node of type AgentGraphNodeImpl at point with coordinates of (0, -100):

In the next 2 lines, we add nodes B and C with the similar code:

The following code creates a Polyline from node A to node B with one bend point:

After the trajectory polyline between nodes A and B, and the nodes added to the environment, we can create a bidirectional arc:

There are several aspects to be noted in the code above:

In the last two lines of the code, we add a monodirectional arc using addArc method with 3 parameters:

Code that constructs the graph environment has a lot of generics making type declarations cumbersome. This code can be slightly simplified with var keyword introduced in Java 9:

To describe a agent’s position in a 2d Euclidean space, it is sufficient to use a (x, y) point. Describing a similar position in a graph requires some additional attributes. It is important to note that a graph position can be used to describe not only position of some agent, but also some specific place in a graph without immediate relevance to an agent.

So, what are the possible positions in a graph with 2d representation we described above? There are two main types of positions:

A position in graph is represented with GeometricGraphPosition class. Its key methods are getNode, getArc, and getArcAbsOffset. These methods allow to determine the node or arc of a position. In the case of position being on an arc, getArcAbsOffset method returns the absolute offset of the position on the arc’s polyline.

The following listing shows how to create GeometricGraphPosition instances and use their basic methods:

Any graph position corresponds to some point in the 2D-space. This point can be retrieved by getPoint method of GeometricGraphPosition class.

In one of the previous section we have created a graph environment and set up several nodes and arcs. The environment was created with this code:

Now we can create a graph agent and place it into the environment:

Not how the instance of Engine class is necessary to create an a graph agent. This engine will be used to simulate the agent’s actions.

After creation we must place the agent into an environment by calling its setGraphEnvironment method. Trying to call GraphAgent’s `jumpTo or moveTo methods before placing the agent into an environment will result in an exception.

The agent can then be removed from the graph environment by calling its removeFromGraphEnvironment method and placed to the same or a different environment again.

Although there is no explicit instance of a StateMachine inside a graph agent, its states can be represented by the following state diagram:

Immediately after creation, an agent is not in any graph environment. It can be assigned to a graph environment by calling setGraphEnvironment method. Agent can be removed from the graph environment by calling removeFromGraphEnvironment method. Agent can only belong to a single graph environment, so before assigning a new graph environment to an agent it needs to be removed from its current one.

After having been assigned to some environment, an agent is still not in its environment’s graph. In other words, its position within the graph is not yet determined. jumpTo method places the agent into the specific node or arc of its environments’s graph.

Methods like moveTo, moveAlongPath, and moveToClosest actually assign some path to an agent and start its movement. In case of moveTo and moveToClosest methods, the path is determined automatically by the graph environment, whereas moveAlongPath method allows the user to specify the path directly.

During movement, an agent might need to stop one or several times. This can be done by setting a zero velocity using setVelocity method.

Setting a zero velocity does not result in agent "forgetting" its path: setting a positive velocity value will make it continue moving to its destination.

Now that we created an agent and placed it to the environment, let us place it to some specific position in a graph. This can be done with one of the several overloads of GraphAgent 's jumpTo method. These methods immediately place the agent to the specified position:

Moving agents inside graphs is the most commonly used functionality of the library. The simple code below shows how to make an agent move from one node to another:

The first argument of the moveTo method is destination node, and the second argument is speed in distance units per time units. We can also send an agent to a position inside the graph:

The isMoving method can be used to check if the graph agent is currently moving. The getVelocity method returns the speed at which the agent is moving, or zero if the agent is not moving:

The agent is sent to its destination via the shortest path that is determined automatically by the graph environment. By default, the shortest path is just the one having geometrically shortest distance along the graph between source and destination positions. However, the result of path finding algorithm can be influenced by providing custom weights to GraphEnvironment class.

In the logic of simulation models it is often important to get notified about agent’s arrival to its destination. For example, we may need to start loading a truck when it arrives to a warehouse. To get notifications every time an agent arrives to its destination, we need to override its onDestinationReached method:

Below is the full example of getting arrival notification. In the example, we only print the current simulation time and agent’s current position at the moment of arrival:

The Engine's documentation contains more comprehensive explanation about how to run simulation models synchronously, like we did here.

Agent’s speed can be changed during its movement. The speed is measured in distance units per engine’s time units. For simplicity, the model’s distance units are called pixels, so the speed is expressed in pixels per time units, or px/tu. The velocity can be set using setVelocity method:

It is important too keep in mind the following aspects of this method:

Sometimes it is necessary to know the graph path used by an agent moving from its source to destination. For example, we might want to know which nodes and arcs the agent will be moving through. This can be done using GraphAgent’s getGraphPath method:

The path is represented by GraphPath instance which is a sequence of nodes and arcs such that each pair of subsequent nodes is adjacent. Path returned by getGraphPath is a result of the path-finding algorithm performed by GraphEnvironment inside GraphAgent’s `moveTo method. If the agent is not currently moving, null is returned.

Note that getGraphPath method returns agent’s entire path from its current source to its current destination. so, at the moment of call, the agent might have already passed some part of the path.

Besides agent’s path, it is sometimes useful to know agent’s trajectory. A trajectory is represented with a Polyline and always starts at the agent’s current location. Unlike path, trajectory does not contain information about graph arcs and nodes to be passed by the agent.

Agent’s trajectory can be retrieved by getTrajectory method:

Note that if an agent does not currently have a path, then null will be returned.

Whenever an agent moves and meets some other agent, its onOtherAgentReached callback method is called. This method can be overridden to handle such events:

onOtherAgentReached method is not called is the agent is not moving and was just "passively" reached by another agent. The isMovingInSameDirection parameter indicates if the other agent is moving in the same direction with the current one. If isMovingInSameDirection parameter is false, this means that the other agent is in the reverse position relative to the current agent.

When an agent jumps into a node or enters a node while moving, its afterEnteredNode is called. At the moment of calling this method the agent is already at the node.

When an agent leaves a node in the process of movement or as result of jumping, its beforeExitedNode is called. At the moment of calling this method the agent is still in the node but will leave it immediately after the callback method is executed.

The code below shows how GraphAgent’s afterEnteredNode and beforeExitedNode methods can be overridden to handle the events of entering and leaving nodes:

Similarly to entering and exiting nodes, the events of agents' entering and exiting arcs can be handled by overriding GraphAgent’s afterEnteredArc and beforeExitedArc methods:

Agents can enter and leave arcs in the following cases:

It can happen that an agent is sent to an unreachable position by one of the overloads of moveTo or moveToClosest methods. Such attempt will result in calling GraphAgent’s onPathNotFound method. The default implementation of this method throws a runtime exception. However, this method can be overridden to customize the agent’s behavior in case of not finding a path to any valid destinations it is being sent to:

Path is a sequence of nodes and arcs such that each pair of subsequent nodes is adjacent. Path is a result of all path-finding algorithms, such as Algorithm.getShortestPath. Path is not a subgraph: the same graph node or arc can be included into path several times (e.g. if path contains cycles).

Graph path always starts and ends at a node. In a non-empty path, the number of arcs always equals the number of nodes minus one. Path can be empty (e.g. to represent a non-existent path) or consist of only one node (e.g. path from some node to itself).

Paths are represented with GraphPath class. The code below illustrates the use of its constructors and basic methods:

AgentGraphPath is a class representing a path of a GraphAgent from some GeometricGraphPosition to some other, probably equal or adjacent, GeometricGraphPosition. AgentGraphPath is a subclass of GraphPath class, so it can either be empty, or consist of a single node, or, most commonly, be a sequence of nodes and arcs such that each pair of subsequent nodes is adjacent.

As movement of an agent does not necessarily start at a node, AgentGraphPath contains a reference to the actual source position which can point either to a node or to an arc. getActualSourcePosition method of AgentGraphPath class can be used to get such position. If getActualSourcePosition points to a node, this is always the first node of the path, and agent’s movement actually starts from this node. If getActualSourcePosition points to an arc, this is always the first arc of the path, and agent’s movement actually starts from the corresponding position on this arc.

Symmetrically, getActualDestPosition method of AgentGraphPath class contains a reference to a destination position that is the terminal point of agent’s movement.

getWeight method of AgentGraphPath class returns the weight of the path calculated at the moment of path finding.

Current path of a GraphAgent can be retrieved by its getGraphPath method. This method will return agent’s current path, or null of the agent currently does not have one.

If agent’s movement starts or finishes on a bi-directional arc, an agent might need to turn around in the beginning and/or at the end of its movement. This fact is also reflected in AgentGraphPath class. Its requiresTurnAtSource method checks if the movement requires the agent to turn around at the very beginning of the movement. Symmetrically, requiresTurnAtDest method checks whether turning around is required at the destination position of the movement.

getSourcePosition method returns the position after a possible turning around in the beginning of the movement, from which an agent actually starts moving. The position returned by getSourcePosition method can be either equal to or a reverse of the position returned by getActualSourcePosition method. If these positions are equal, turning around is not required in the beginning of the movement, otherwise it is required.

getDestPosition method returns the position before a possible turning around at the end of the movement, where an agent actually completes its movement. The position returned by getDestPosition method can be either equal to or a reverse of the position returned by getActualDestPosition method. If these positions are equal, turning around is not required at the end of the movement, otherwise it is required.

Trajectory is a Polyline representing the movement track of an agent in the 2D-space. Trajectory does not have any references to nodes and arcs that agent will be moving through. It can consist of a single point, however most commonly it consists of several points and segments.

If an agent at some point in time has a graph path, i.e. its getGraphPath method does not return null, it also has a trajectory. Agent’s current trajectory can be retrieved by calling its getTrajectory method. This method will return the remaining trajectory of this agent, i.e. the Polyline ahead of this agent that it will travel according to its current path. Returned polyline includes the segment the agent is currently moving on, and all segments ahead of this agent that it will move through before it reaches its destination.

AgentGraphPath also has a trajectory which can be retrieved by its getTrajectory method. This trajectory is a Polyline that is a representation of movement track of an agent along this path.

It is important to make difference between agent’s current trajectory and the trajectory of agent’s current path:

The example below shows the use of overriding getArcWeight method of GraphEnvironment class to prevent the agents from moving through the arcs that contain the word "Disabled" in their names:

It is important to node that the arcs with infinite weights in the code above may still be included into agents' paths if there is no other paths between the specified source and destination. To prevent the agents from moving over the disabled arcs, we can check the value returned by the AgentGraphPath.getWeight method and add the special handling logic for the case when the weight is infinite.

Sometimes it is required to close (or de-prioritize) not the whole arcs, but just some fragments of arcs. To do so, we can override getPartialArcWeight of GraphEnvironment class. The example below demonstrates one of possible approaches of implementing this. In this example, we define MyArc type that contains the beginning and end of the disabled arc segment. In the overridden getArcWeight method we return infinity if In the overridden getPartialArcWeight method we return the infinity only if