Package org.tweetyproject.logics.petri.syntax.reachability_graph

Class ReachabilityGraph

java.lang.Object

org.tweetyproject.logics.petri.syntax.reachability_graph.ReachabilityGraph

All Implemented Interfaces:

Iterable<Marking>, BeliefBase, GeneralGraph<Marking>, Graph<Marking>

public class ReachabilityGraph
extends Object
implements Graph<Marking>, BeliefBase

A class to describe the graph of reachability between possible markings of a Petri net

Author:

Benedikt Knopp

Field Summary

Fields inherited from interface org.tweetyproject.graphs.Graph

IGNORE_SELFLOOPS, INVERT_SELFLOOPS, REMOVE_SELFLOOPS

Constructor Summary

Constructors

Constructor	Description
ReachabilityGraph(PetriNet petriNet)	Create a new instance

Method Summary

Modifier and Type	Method	Description
boolean	add(GeneralEdge<Marking> edge)	Adds the given edge to this graph.
boolean	add(Marking node)	Adds the given node to this graph.
boolean	add(MarkingEdge edge)	add a marking edge to this graph
boolean	areAdjacent(Marking a, Marking b)	Returns "true" iff the two nodes are connected by a directed edge from a to b or an undirected edge.
boolean	checkConsistency()	check if all nodes (markings) of this graph describe the same Petri net, i.e.
boolean	contains(Object obj)	Returns "true" when this graph contains the given node or edge.
boolean	existsDirectedPath(Marking node1, Marking node2)	Checks whether there is a (directed) path from node1 to node2.
Matrix	getAdjacencyMatrix()	Returns the adjacency matrix of this graph (the order of the nodes is the same as returned by "iterator()").
Collection<Marking>	getChildren(Node node)	Returns the set of children (node connected via an undirected edge or a directed edge where the given node is the parent) of the given node.
Graph<Marking>	getComplementGraph(int selfloops)	Returns the complement graph of this graph, i.e.
Matrix	getControlMatrix()	Retrieve a matrix that specifies for each pair of marking and transition how likely that transition is going to occur at that marking, based on the probability function that describes this graph.
Edge<Marking>	getEdge(Marking a, Marking b)	Returns the corresponding edge (a,b) if a and b are adjacent.
List<MarkingEdge>	getEdges()	Returns the edges of this graph.
Set<Marking>	getInitialMarkings()	Retrieve the designated initial markings
Optional<Marking>	getMarking(Marking marking)	Retrieve, if present, the marking in this graph that equals the query marking in the sense that both markings describe the same token distribution over places
List<Marking>	getMarkings()	Retrieve the markings
Signature	getMinimalSignature()	Returns the signature of the language of this knowledge base.
Collection<Marking>	getNeighbors(Marking node)	Returns the set of neighbors of the given node.
List<Marking>	getNodes()	Returns the nodes of this graph.
int	getNumberOfEdges()	the number of edges in this graph
int	getNumberOfNodes()	Returns the number of nodes in this graph.
Set<MarkingEdge>	getOutgoing(Marking marking)	For one particular marking, retrieve all outgoing edges
Collection<Marking>	getParents(Node node)	Returns the set of parents (node connected via an undirected edge or a directed edge where the given node is the child) of the given node.
PetriNet	getPetriNet()	Return the petriNet
ProbabilityFunction<MarkingEdge>	getProbabilityFunction()	the probability function of this graph, which is null for default
Graph<Marking>	getRestriction(Collection<Marking> nodes)	Returns a copy of this graph that contains only the specified nodes and all corresponding edges between them.
Collection<Collection<Marking>>	getStronglyConnectedComponents()	Returns the strongly connected components of this graph.
Collection<Graph<Marking>>	getSubgraphs()	Returns the set of sub graphs of this graph.
Matrix	getTransitionMatrix()	Retrieve a matrix that specifies for each pair of markings how likely a transition between these markings is going to happen, based on the probability function that describes this graph.
boolean	hasMarking(Marking marking)	Determine if the specified marking is present as a node in the graph
boolean	hasSelfLoops()	Returns "true" iff the graph has a self loop (an edge from a node to itself).
boolean	hasValidProbabilityFunction()	specifies if the probability function of this graph is 1.
void	initializeDefaultProbabilityFunction()	initializes a probability function over the edges of this graph according to Random Walk, i.e.
void	initializeIrregularProbabilityFunction()	Initialize a probability function over the edges of this graph according to a stochastic walk.
void	initializeRandomProbabilityFunction()	Initialize a probability function over the edges of this graph according to a stochastic walk.
boolean	isInitial(Marking marking)	Check whether a marking is a designated initial marking
boolean	isWeightedGraph()	Checks whether this graph only contains weighted edges.
Iterator<Marking>	iterator()
void	setPetriNet(PetriNet petriNet)	Setter petriNet
void	setProbabilityFunction(ProbabilityFunction<MarkingEdge> probabilityFunction)	sets the probability function of this graph
void	sortMarkings()	fix the sorting to prepare linear algebra analysis in particular, assert a fixed ordering for index-based matrix/vector-access

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.tweetyproject.commons.BeliefBase

toString

Methods inherited from interface org.tweetyproject.graphs.Graph

toString

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Details

ReachabilityGraph

public ReachabilityGraph(PetriNet petriNet)

Create a new instance

Parameters:

petriNet - the underlying Petri net

Method Details

add

public boolean add(Marking node)

Description copied from interface: Graph

Adds the given node to this graph.

Specified by:

add in interface Graph<Marking>

Parameters:

node - some node.

Returns:

"true" iff the edge has been added successfully.

add

public boolean add(MarkingEdge edge)

add a marking edge to this graph

Parameters:

edge - the edge

Returns:

true iff adding the edge was successful

add

public boolean add(GeneralEdge<Marking> edge)

Description copied from interface: Graph

Adds the given edge to this graph. If at least one of the nodes the given edge connects is not in the graph, an illegal argument exception is thrown.

Specified by:

add in interface Graph<Marking>

Parameters:

edge - some edge.

Returns:

"true" iff the edge has been added successfully.

getNodes

public List<Marking> getNodes()

Description copied from interface: Graph

Returns the nodes of this graph.

Specified by:

getNodes in interface GeneralGraph<Marking>

Specified by:

getNodes in interface Graph<Marking>

Returns:

the nodes of this graph.

getNumberOfNodes

public int getNumberOfNodes()

Description copied from interface: Graph

Returns the number of nodes in this graph.

Specified by:

getNumberOfNodes in interface Graph<Marking>

Returns:

the number of nodes in this graph.

getNumberOfEdges

public int getNumberOfEdges()

the number of edges in this graph

Specified by:

getNumberOfEdges in interface Graph<Marking>

Returns:

the number of edges in this graph

areAdjacent

public boolean areAdjacent(Marking a,
 Marking b)

Description copied from interface: Graph

Returns "true" iff the two nodes are connected by a directed edge from a to b or an undirected edge.

Specified by:

areAdjacent in interface Graph<Marking>

Parameters:

a - some node

b - some node

Returns:

"true" iff the two nodes are connected by a directed edge from a to b or an undirected edge.

getEdge

public Edge<Marking> getEdge(Marking a,
 Marking b)

Description copied from interface: Graph

Returns the corresponding edge (a,b) if a and b are adjacent. Otherwise it returns null.

Specified by:

getEdge in interface Graph<Marking>

Parameters:

a - some node

b - some node

Returns:

the edge (a,b) or null.

getEdges

public List<MarkingEdge> getEdges()

Description copied from interface: Graph

Returns the edges of this graph.

Specified by:

getEdges in interface GeneralGraph<Marking>

Specified by:

getEdges in interface Graph<Marking>

Returns:

the edges of this graph.

getPetriNet

public PetriNet getPetriNet()

Return the petriNet

Returns:

the petriNet

setPetriNet

public void setPetriNet(PetriNet petriNet)

Setter petriNet

Parameters:

petriNet - the petriNet to set

getProbabilityFunction

public ProbabilityFunction<MarkingEdge> getProbabilityFunction()

the probability function of this graph, which is null for default

Returns:

the probabilityFunction

setProbabilityFunction

public void setProbabilityFunction(ProbabilityFunction<MarkingEdge> probabilityFunction)

sets the probability function of this graph

Parameters:

probabilityFunction - the probability function to set

initializeDefaultProbabilityFunction

public void initializeDefaultProbabilityFunction()

initializes a probability function over the edges of this graph according to Random Walk, i.e. all outgoing edges of one particular node are assigned to the same probability and the sum of these probabilities equals to 1.

initializeRandomProbabilityFunction

public void initializeRandomProbabilityFunction()

Initialize a probability function over the edges of this graph according to a stochastic walk. The sum of probabilities of outgoing edges at each node equals to 1, and for multiple outgoing edges, probabilities are randomized.

initializeIrregularProbabilityFunction

public void initializeIrregularProbabilityFunction()

Initialize a probability function over the edges of this graph according to a stochastic walk. For multiple outgoing edges, exactly one edge receives a probability of 1 and all other edges a probability of 0. This may turn some transitions dead.

hasValidProbabilityFunction

public boolean hasValidProbabilityFunction()

specifies if the probability function of this graph is 1. initialized, and 2. assigns for each marking a total (summed up) probability of 1 for all successor edges. This implies that each marking needs to have at least one successor marking.

Returns:

true iff the probability function is valid

sortMarkings

public void sortMarkings()

fix the sorting to prepare linear algebra analysis in particular, assert a fixed ordering for index-based matrix/vector-access

getTransitionMatrix

public Matrix getTransitionMatrix()
                           throws IllegalStateException

Retrieve a matrix that specifies for each pair of markings how likely a transition between these markings is going to happen, based on the probability function that describes this graph.

Returns:

the transition matrix

Throws:

IllegalStateException - iff the probability function of this graph is invalid

getControlMatrix

public Matrix getControlMatrix()

Retrieve a matrix that specifies for each pair of marking and transition how likely that transition is going to occur at that marking, based on the probability function that describes this graph.

Returns:

the control matrix

Throws:

IllegalStateException - iff the probability function of this graph is invalid

iterator

public Iterator<Marking> iterator()

Specified by:

iterator in interface Graph<Marking>

Specified by:

iterator in interface Iterable<Marking>

contains

public boolean contains(Object obj)

Description copied from interface: Graph

Returns "true" when this graph contains the given node or edge.

Specified by:

contains in interface Graph<Marking>

Parameters:

obj - an object

Returns:

"true" if this graph contains the given node or edge.

getChildren

public Collection<Marking> getChildren(Node node)

Description copied from interface: Graph

Returns the set of children (node connected via an undirected edge or a directed edge where the given node is the parent) of the given node.

Specified by:

getChildren in interface Graph<Marking>

Parameters:

node - some node (must be in the graph).

Returns:

the set of children of the given node.

getParents

public Collection<Marking> getParents(Node node)

Description copied from interface: Graph

Returns the set of parents (node connected via an undirected edge or a directed edge where the given node is the child) of the given node.

Specified by:

getParents in interface Graph<Marking>

Parameters:

node - some node (must be in the graph).

Returns:

the set of parents of the given node.

existsDirectedPath

public boolean existsDirectedPath(Marking node1,
 Marking node2)

Description copied from interface: Graph

Checks whether there is a (directed) path from node1 to node2.

Specified by:

existsDirectedPath in interface Graph<Marking>

Parameters:

node1 - some node.

node2 - some node.

Returns:

"true" if there is a directed path from node1 to node2.

getNeighbors

public Collection<Marking> getNeighbors(Marking node)

Description copied from interface: Graph

Returns the set of neighbors of the given node.

Specified by:

getNeighbors in interface Graph<Marking>

Parameters:

node - some node (must be in the graph).

Returns:

the set of neighbors of the given node.

getAdjacencyMatrix

public Matrix getAdjacencyMatrix()

Description copied from interface: Graph

Returns the adjacency matrix of this graph (the order of the nodes is the same as returned by "iterator()").

Specified by:

getAdjacencyMatrix in interface Graph<Marking>

Returns:

the adjacency matrix of this graph

getComplementGraph

public Graph<Marking> getComplementGraph(int selfloops)

Description copied from interface: Graph

Returns the complement graph of this graph, i.e. the graph on the same set of vertices as this graph that connects two vertices v and w with an edge if and only if v and w are not connected in this graph.

Specified by:

getComplementGraph in interface Graph<Marking>

Parameters:

selfloops - Indicates how to deal with selfloops:
IGNORE_SELFLOOPS - ignore self loops (don't add and don't remove)
INVERT_SELFLOOPS - deal with self loops like ordinary edges (add if not present and remove if present)
REMOVE_SELFLOOPS - simple remove self loops, but don't add new ones.

Returns:

the complement graph of this graph.

getStronglyConnectedComponents

public Collection<Collection<Marking>> getStronglyConnectedComponents()

Description copied from interface: Graph

Returns the strongly connected components of this graph. A set of nodes is strongly connected, if there is a path from each node to each other. A set of nodes is called strongly connected component if it is strongly connected and maximal with respect to set inclusion.

Specified by:

getStronglyConnectedComponents in interface Graph<Marking>

Returns:

the strongly connected components of this graph.

getSubgraphs

public Collection<Graph<Marking>> getSubgraphs()

Description copied from interface: Graph

Returns the set of sub graphs of this graph.

Specified by:

getSubgraphs in interface Graph<Marking>

Returns:

the set of sub graphs of this graph.

getRestriction

public Graph<Marking> getRestriction(Collection<Marking> nodes)

Description copied from interface: GeneralGraph

Returns a copy of this graph that contains only the specified nodes and all corresponding edges between them.

This method generates a subgraph (or restricted graph) from the current graph by including only the given nodes and the edges that connect them. The returned graph is a new instance and does not modify the original graph.

Specified by:

getRestriction in interface GeneralGraph<Marking>

Parameters:

nodes - a collection of nodes to be included in the restricted graph.

Returns:

a `GeneralGraph` object representing the restricted graph.

hasSelfLoops

public boolean hasSelfLoops()

Description copied from interface: Graph

Returns "true" iff the graph has a self loop (an edge from a node to itself).

Specified by:

hasSelfLoops in interface Graph<Marking>

Returns:

"true" iff the graph has a self loop (an edge from a node to itself).

isWeightedGraph

public boolean isWeightedGraph()

Description copied from interface: Graph

Checks whether this graph only contains weighted edges.

Specified by:

isWeightedGraph in interface Graph<Marking>

Returns:

"true" if all edges are weighted in this graph.

hasMarking

public boolean hasMarking(Marking marking)

Determine if the specified marking is present as a node in the graph

Parameters:

marking - the marking

Returns:

true if the marking is present

getMarking

public Optional<Marking> getMarking(Marking marking)

Retrieve, if present, the marking in this graph that equals the query marking in the sense that both markings describe the same token distribution over places

Parameters:

marking - the query marking

Returns:

the marking that equals the query marking, or null if not present

getOutgoing

public Set<MarkingEdge> getOutgoing(Marking marking)

For one particular marking, retrieve all outgoing edges

Parameters:

marking - the marking of interest

Returns:

the sequence flow successors

checkConsistency

public boolean checkConsistency()

check if all nodes (markings) of this graph describe the same Petri net, i.e. the same set of places

Returns:

true iff all markings describe the same set of places

getMinimalSignature

public Signature getMinimalSignature()

Description copied from interface: BeliefBase

Returns the signature of the language of this knowledge base.

Specified by:

getMinimalSignature in interface BeliefBase

Returns:

the signature of the language of this knowledge base.

getInitialMarkings

public Set<Marking> getInitialMarkings()

Retrieve the designated initial markings

Returns:

getInitialMarkings

isInitial

public boolean isInitial(Marking marking)

Check whether a marking is a designated initial marking

Parameters:

marking - the marking to check

Returns:

true iff the marking is initial

getMarkings

public List<Marking> getMarkings()

Retrieve the markings

Returns:

markings