readme.mdown

Automata Graph Editor

Methods to implement a graph editor are described. Based on a graph structure description and on d3-graph-plugin.

Methods

Basic methods for a graph (edges only, no explicit nodes)

add(i, j)			# Add the edge (i, j)
del(i, j)			# Delete the edge (i, j)
out(i)				# Returns a list of j such that (i, j) in edges
in(i)				# Returns a list of j such that (j, i) in edges
set(i, j, value)	# Set value for the edge (i, j)
get(i, j)			# Returns value for the edge (i, j)

Extended methods for automata

add()				# Create a new node
add(i)				# Create a new node (j) and add edge(i, j)
del(i)				# Delete the node (i) from nodes
set(i, value)		# Set value for the node (i)
get(i)				# Returns value for the node (i)

Helper methods

ins(i)			# Insert node i
ins(i)			# Insert edge i

For the above we define a structure for a graph and methods to work with it:

Structures

Structrue of a graph (to be kept on a storage)

g : {
	n : {			# Nodes
		x : []		# X-coordinates
		y : []		# Y-coordinates
		v : []		# Values
	}
	e : {			# Edges
		a : []		# index if i-node
		b : []		# index if j-node
		v : []		# Values
	}
	n0 : []			# Initial nodes
}

Helping structure for a graph

g : {
	n : {			# Nodes
	}
	e : {			# Edges
		curved : []	# True if to be drawn curved
	}
}

Draft of methods for Finite Automata

The prefix "fa" states for Finite Automata.

fa : {
	nodes : {		# Nodes
		add(G)		# Create a new node
		add(G,i)	# Insert node into position (i)
		del(G,i)	# Delete the node (i) from nodes
		set(G,i,v)	# Set value for the node (i)
		get(G,i)	# Returns value for the node (i)
		out(G,i)	# Returns a list of j such that (i, j) in edges
	}
	edges : {		# Edges
		add(i)		# Create a new node (j) and add edge(i, j)
		add(i, j)	# Add the edge (i, j)
		ins(i)		# Insert edge into position i
		del(i, j)	# Delete the edge (i, j)
		set(i, j, v)# Set value for the edge (i, j)
		get(i, j)	# Returns value for the edge (i, j) <-- sure we need it?
		has(i, j)	# Returns true if exists edge (i, j)
		out(i)		# Returns a list of edges such that (i, ?) in edges
		in(i)		# Returns a list of edges such that (?, i) in edges
	}
}

Breadth-first Search

BFS : (G) ->
	stack = [G.start]
	visited = [G.start]
	while stack.length
		a = stack.pop()
		# Get edges going out of the node 'a'
		E = @.edges.out(G, a)
		for e in E
			# Get nodes reachabe by the edge 'e'
			b = G.edges.b[e]
			if b not in visited
				visited.push(b)
				stack.push(b)
			# Do something here
			console.log a,"->", b

Parallel composition

a, b : typeof g
stack1.push(a.n0)
stack2.push(b.n0)
wrt = [] # values with respect which we make the composition to
#
while stack1.length
	n1 = stack1.pop()
	n2 = stack2.pop()
	outs1 = a.e.out(n1)
	outs2 = a.e.out(n1)
	for e in outs1
		if e not in wrt
			...

Graph drawing

http://www2.research.att.com/~yifanhu/PUB/graph_draw_small.pdf