Graph Analysis API Overview

Introduction

A page to discuss implementation choices for a graph walking and analysis api, as described here in issue #395.

---

abstract class Graph

hasNext

public boolean hasNext()

Returns true when their are reachable nodes that have not been visited and false otherwise.

isDepthFirst

public boolean isDepthFirst()

Returns true when the graph walks using depth first search.

nextNode

public abstract Node nextNode()

TODO The code is currently not abstract, but empty. This is a bug from issue $
This should return the next node in the walk according to the implementation.

clearNodes

public void clearNodes()

Reset the Nodes in the graph to unvisited, and the structures that manage the walking. After calling clearNodes(), you should be able to walk the graph as if it were new.

getCyclomaticComplexity

TODO

Return the cyclomatic complexity of the graph.

---

interface Node

TODO potentially a trait in the future to inject the boolean isVisited field

visit()

public void visit()

Mark a node as visited.

clear()

public void clear() Mark a node as unvisited.

---

class StateMachineGraph

Functionality to walk through a given StateMachine through an UmpleModel. We walk the states through the transitions, which are already stored in the States, which behave as nodes. Each state inherits from Node giving it the visit method and has the isVisited field.

StateMachineGraph

public StateMachineGraph(Node startNode, boolean isDepthFirst)

startNode is the state from which the walking begins
isDepthFirst true when depth first search is used to walk, false for breadth first search.

public StateMachineGraph(Node startNode, String stateMachineName, boolean isDepthFirst)

Used to walk a nested state machine, where your transitions can move to other-named machines.
startNode is the state from which the walking begins.
stateMachineName the name of the nested state machine that will be walked
isDepthFirst true when depth first search is used to walk, false for breadth first search.

nextNode()

public Node nextNode()

Returns the next state in the walk. It will walk along the pattern according to Graph.isDepthFirst().
Safe to use while Graph.hasNext() returns true.
The visiting order is done by the order in which transitions are declared in the .ump file. For example, if you had this case with Pause as the start state, push would be the first edge used.

On
{
  turnOff -> Off;
  Play 
  { 
    push -> Pause;
  }
  Pause
  {
    push -> Play;      
    standby -> Sleep;
  }      
  
}

clearNodes()

public void clearNodes()

Clear all visited nodes reachable from the start node. The start node is automatically visited when the graph is created and will not be cleared by this function - this is because we do not track open and closed, or pre and post order visiting, and because a graph is defined by its starting node.

clearNodes will also reset the stack or queue for walking, with only the start node, depending on if it is depth first or breadth first search.

---