tripal_chado.phylotree_newick.inc 7.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331
  1. <?php
  2. /**
  3. * This code parses the grammer for the Newick format as per the following
  4. * grammar:
  5. *
  6. * Tree --> Subtree ";" | Branch ";"
  7. * Subtree --> Leaf | Internal
  8. * Leaf --> Name
  9. * Internal --> "(" BranchSet ")" Name
  10. * BranchSet --> Branch | BranchSet "," Branch
  11. * Branch --> Subtree Length
  12. * Name --> empty | string
  13. * Length --> empty | ":" number
  14. *
  15. */
  16. /**
  17. *
  18. * @param unknown $file_name
  19. */
  20. function tripal_phylogeny_parse_newick_file($file_name) {
  21. // Initialize the bootstrap value and index
  22. global $tripal_phylogeny_bootstrap;
  23. $tripal_phylogeny_bootstrap = 1;
  24. $tripal_phylogeny_index = 1;
  25. $tree = array();
  26. $fp = fopen($file_name, 'r');
  27. if ($fp) {
  28. $tree = tripal_phylogeny_parse_newick_tree($fp);
  29. }
  30. else {
  31. // ERROR
  32. }
  33. return $tree;
  34. }
  35. /**
  36. *
  37. * @param unknown $fp
  38. * @param number $depth
  39. * @return boolean
  40. */
  41. function tripal_phylogeny_parse_newick_tree($fp, $depth = 0) {
  42. $subtree = tripal_phylogeny_parse_newick_subtree($fp, $depth);
  43. $subtree['is_root'] = 1;
  44. // this subtree may also be a branch. A branch is a subtree with a length,
  45. // so see if there is a length
  46. $token = tripal_phylogeny_parse_newick_get_token($fp);
  47. if ($token == ";") {
  48. // we're done!
  49. return $subtree;
  50. }
  51. tripal_phylogeny_parse_newick_replace_token($fp);
  52. // Get the length.
  53. $length = tripal_phylogeny_parse_newick_length($fp, $depth);
  54. $subtree['length'] = $length;
  55. // Now if we're missing the semicolon we have a syntax error.
  56. $token = tripal_phylogeny_parse_newick_get_token($fp);
  57. if ($token != ';') {
  58. print "Syntax Error: missing trailing semicolon.\n";
  59. exit;
  60. }
  61. return $subtree;
  62. }
  63. /**
  64. *
  65. * @param unknown $fp
  66. * @param unknown $depth
  67. * @return Ambigous|unknown
  68. */
  69. function tripal_phylogeny_parse_newick_subtree($fp, $depth) {
  70. $internal = tripal_phylogeny_parse_newick_internal($fp, $depth + 1);
  71. if (!is_array($internal)) {
  72. $leaf_node = tripal_phylogeny_parse_newick_leaf($fp, $depth);
  73. return array(
  74. 'name' => $leaf_node,
  75. 'depth' => $depth,
  76. 'is_leaf' => TRUE,
  77. 'descendents' => 0,
  78. );
  79. }
  80. else {
  81. $internal['depth'] = $depth;
  82. }
  83. return $internal;
  84. }
  85. /**
  86. *
  87. * @param unknown $fp
  88. * @param unknown $depth
  89. * @return boolean|multitype:unknown Ambigous <Ambigous, unknown>
  90. */
  91. function tripal_phylogeny_parse_newick_branch($fp, $depth) {
  92. $subtree = tripal_phylogeny_parse_newick_subtree($fp, $depth);
  93. $length = tripal_phylogeny_parse_newick_length($fp, $depth);
  94. $subtree['length'] = $length;
  95. return $subtree;
  96. }
  97. /**
  98. *
  99. * @param unknown $fp
  100. * @param unknown $parent
  101. * @param unknown $depth
  102. */
  103. function tripal_phylogeny_parse_newick_internal($fp, $depth) {
  104. // If the next character is not an open paren then this is an internal node
  105. if (tripal_phylogeny_parse_newick_get_token($fp) != '(') {
  106. tripal_phylogeny_parse_newick_replace_token($fp);
  107. return FALSE;
  108. }
  109. $branches = tripal_phylogeny_parse_newick_branchset($fp, $depth);
  110. if (!is_array($branches)) {
  111. return FALSE;
  112. }
  113. // If we don't have a closing parent then this is a syntax error.
  114. if (tripal_phylogeny_parse_newick_get_token($fp) != ')') {
  115. tripal_phylogeny_parse_newick_replace_token($fp);
  116. return FALSE;
  117. }
  118. $internal_node = tripal_phylogeny_parse_newick_name($fp, $depth);
  119. $descendent_count = 0;
  120. for ($i = 0; $i < count($branches); $i++) {
  121. $branches[$i]['parent'] = $internal_node;
  122. $descendent_count += 1 + $branches[$i]['descendents'];
  123. }
  124. return array(
  125. 'name' => $internal_node,
  126. 'depth' => $depth,
  127. 'branch_set' => $branches,
  128. 'is_internal' => TRUE,
  129. 'descendents' => $descendent_count,
  130. );
  131. }
  132. /**
  133. *
  134. * @param unknown $fp
  135. * @param unknown $parent
  136. * @param unknown $depth
  137. */
  138. function tripal_phylogeny_parse_newick_branchset($fp, $depth) {
  139. $branches = array();
  140. $num_read = 0;
  141. $branch = tripal_phylogeny_parse_newick_branch($fp, $depth);
  142. $branches[] = $branch;
  143. // If it's not a branch then return false, a branchset will
  144. // always appear as a branch.
  145. if (!is_array($branch)) {
  146. return FALSE;
  147. }
  148. // If we have a comma as the next token then this is
  149. // a branchset and we should recurse.
  150. $token = tripal_phylogeny_parse_newick_get_token($fp);
  151. if ($token == ',') {
  152. $rbranches = tripal_phylogeny_parse_newick_branchset($fp, $depth);
  153. foreach ($rbranches as $branch) {
  154. $branches[] = $branch;
  155. }
  156. }
  157. else {
  158. tripal_phylogeny_parse_newick_replace_token($fp);
  159. }
  160. return $branches;
  161. }
  162. /**
  163. *
  164. * @param unknown $fp
  165. * @param unknown $depth
  166. * @return Ambigous <string, boolean, unknown>
  167. */
  168. function tripal_phylogeny_parse_newick_leaf($fp, $depth) {
  169. return tripal_phylogeny_parse_newick_name($fp, $depth);
  170. }
  171. /**
  172. *
  173. * @param unknown $fp
  174. * @param unknown $depth
  175. * @return string|boolean|Ambigous <string, unknown>
  176. */
  177. function tripal_phylogeny_parse_newick_name($fp, $depth) {
  178. global $tripal_phylogeny_bootstrap;
  179. $token = tripal_phylogeny_parse_newick_get_token($fp);
  180. // If the next token is a colon, semicolon, close paren, or comma
  181. // then the name is empty.
  182. if ($token == ':' or $token == ',' or $token == ';' or $token == ')') {
  183. tripal_phylogeny_parse_newick_replace_token($fp);
  184. // create a bootstrap value
  185. return $tripal_phylogeny_bootstrap++;
  186. }
  187. // If the next token is an open paren then this is a syntax error:
  188. if ($token == '(') {
  189. tripal_phylogeny_parse_newick_replace_token($fp);
  190. return FALSE;
  191. }
  192. return $token;
  193. }
  194. /**
  195. *
  196. * @param unknown $fp
  197. * @param unknown $depth
  198. * @return string|boolean|unknown
  199. */
  200. function tripal_phylogeny_parse_newick_length($fp, $depth) {
  201. $length = '';
  202. $token = tripal_phylogeny_parse_newick_get_token($fp);
  203. // If the next token is a semicolon, close paren, or comma
  204. // then the length is empty.
  205. if ($token == ',' or $token == ';' or $token == ')') {
  206. tripal_phylogeny_parse_newick_replace_token($fp);
  207. return '';
  208. }
  209. // If the next token is a colon then we are parsing the length.
  210. // Otherwise we are not.
  211. if ($token != ':') {
  212. tripal_phylogeny_parse_newick_replace_token($fp);
  213. return FALSE;
  214. }
  215. // Now get the length.
  216. $token = tripal_phylogeny_parse_newick_get_token($fp);
  217. // If the next token is an open paren then this is a syntax error:
  218. if ($token == '(') {
  219. exit();
  220. }
  221. return $token;
  222. }
  223. /**
  224. *
  225. * @param unknown $fp
  226. * @return string
  227. */
  228. function tripal_phylogeny_parse_newick_get_token($fp) {
  229. // Keep track of the file position that we start with
  230. global $tripal_phylogeny_fp_pos;
  231. $tripal_phylogeny_fp_pos = ftell($fp);
  232. $token = '';
  233. $in_quote = FALSE;
  234. $num_read = 0;
  235. $c = fgetc($fp);
  236. while (!feof($fp)) {
  237. $num_read++;
  238. switch ($c) {
  239. // If the first character is a reserved character and we
  240. // we have not encountered any other charcters then return
  241. // it as the token. Otherwise, return the collected token.
  242. case ';':
  243. case '(':
  244. case ')':
  245. case ',':
  246. case ':':
  247. if (!$token) {
  248. return $c;
  249. }
  250. else {
  251. // put the character back and return the token
  252. fseek($fp, $tripal_phylogeny_fp_pos + $num_read - 1);
  253. return $token;
  254. }
  255. break;
  256. // Quotes are allowed around names and if a name is in
  257. // quotes then allow spaces. Otherwise, spaces are ignored.
  258. case '\'':
  259. case '"':
  260. if (!$in_quote) {
  261. $in_quote = TRUE;
  262. }
  263. else {
  264. $in_quote = FALSE;
  265. }
  266. break;
  267. case " ":
  268. case "\t":
  269. case "\r":
  270. case "\n":
  271. if ($in_quote) {
  272. $token .= $c;
  273. }
  274. break;
  275. // All other characters get saved as the token
  276. default:
  277. $token .= $c;
  278. }
  279. $c = fgetc($fp);
  280. }
  281. return $token;
  282. }
  283. /**
  284. *
  285. * @param unknown $fp
  286. */
  287. function tripal_phylogeny_parse_newick_replace_token($fp) {
  288. global $tripal_phylogeny_fp_pos;
  289. fseek($fp, $tripal_phylogeny_fp_pos);
  290. $tripal_phylogeny_fp_pos = ftell($fp);
  291. }