Added simple examples

1 files changed, 63 insertions, 0 deletions

diff --git a/war_seq.icl b/war_seq.icl
new file mode 100644
index 0000000..353b184
--- /dev/null
+++ b/war_seq.icl
@@ -0,0 +1,63 @@
+module war_seq
+
+/*
+Sequential version of Warshall's shortest path algorithm
+ 
+Calculates the lenghts of the shortest paths between all nodes of
+a directed graph represented by its adjacency matrix using Warshall's
+algorithm. The result of the program will be a matrix containing the
+length of the shortest path between node i and node j on index (i,j).
+
+Run the program with the Show Constructors option on (Application options)
+*/
+
+import StdClass; // RWS
+import StdInt
+
+::Row :== [Int]	// A row is represented as a list of integers.
+::Mat :== [Row]	// A matrix is represented as a list of rows.
+
+Size :== 6		// The size of the initial matrix.
+
+//	The initial matrix.
+
+InitMat::Mat								//	 Shortest path matrix:
+InitMat =	[[  0,100,100, 13,100,100  ],	// [  0, 16,100, 13, 20, 20 ]
+			[ 100,  0,100,100,  4,  9  ],	// [ 19,  0,100,  5,  4,  9 ]
+			[  11,100,  0,100,100,100  ],	// [ 11, 27,  0, 24, 31, 31 ]
+			[ 100,  3,100,  0,100,  7  ],	// [ 18,  3,100,  0,  7,  7 ]
+			[  15,  5,100,  1,  0,100  ],	// [ 15,  4,100,  1,  0,  8 ]
+			[  11,100,100, 14,100,  0 ]]	// [ 11, 17,100, 14, 21,  0 ]
+
+
+//	Miscellaneous functions.
+
+Min::Int Int -> Int
+Min i j | i>j 	=  j
+				=  i
+
+Select::[x] Int -> x 
+Select [f:r] 1 =  f
+Select [f:r] k =  Select r (k - 1)
+
+//	Warshall's shortest path algorithm.
+
+Warshall::Mat -> Mat
+Warshall mat = 	Iterate 1 mat
+
+Iterate::Int Mat -> Mat
+Iterate i mat	| i>Size 	=  mat
+							=  Iterate (i+1) (WarRows i mat (Select mat i))
+
+WarRows::Int Mat Row -> Mat
+WarRows i [] rowi 			=  []
+WarRows i [rowj:rs] rowi	=  [ UpdateRow (Select rowj i) rowj rowi : WarRows i rs rowi ]
+	
+UpdateRow::Int Row Row -> Row
+UpdateRow ji [] [] 				=  []
+UpdateRow ji [jk:rjs] [ik:ris]	=  [ Min jk (ji + ik) : UpdateRow ji rjs ris ]
+
+//	The Start rule: apply Warshall's algorithm on the initial matrix.
+
+Start::Mat
+Start 	= Warshall InitMat