<br><div class="gmail_quote">On Fri, Oct 28, 2011 at 2:31 AM, Ivan Lazar Miljenovic <span dir="ltr"><<a href="mailto:ivan.miljenovic@gmail.com">ivan.miljenovic@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Well, for arbitrary directed graphs, FGL is probably your best bet, or<br>
roll-your-own.<br>
<br>
_But_ you'll need to write the parser yourself using something like<br>
trifecta, uu-parsinglib, polyparse, parsec, etc.<br>
<br>
It would help if you described the structure of these graphs and what<br>
kind of support you'd want in a data structure.<br></blockquote><div class="h5"><br><br>Thanks for the feedback! <br>As I wrote in first message I need to compare both structure and node contents of two graphs, find
similar sub-graphs, and need some metric to measure distance between two graphs. These graphs are produced by POS (part of speech) sentence tagging. POS tagging is done by Standford statistical parser: <a href="http://nlp.stanford.edu/software/lex-parser.shtml">http://nlp.stanford.edu/software/lex-parser.shtml</a><br>
<br>For example in the graph G1:<br>(ROOT<br> (S<br> (NP (DT The) (NN voice) (NN quality))<br> (VP (VBD was)<br> (ADJP (JJ clear) (RB too)))<br> (. .)))<br><br>G1 has an NP node (lets call this sub-graph SG1) which has three child leaf nodes: (DT The) (NN voice) (NN quality), where<br>
DT, NN - nodes names, and <br>"The", "voice", "quality" - corresponding leaf values of these nodes.<br><br>I need to compare this graph with graph G2:<br>(ROOT<br> (S<br> (SBAR (IN Although)<br>
(S<br> (NP (DT the) (NN battery) (NN life))<br> (VP (VBD was) (RB not)<br> (ADJP (JJ long)))))<br>
(, ,)<br> (NP (DT that))<br> (VP (VBZ is)<br> (VP (VBN ok)<br> (PP (IN for)<br> (NP (PRP me)))))<br> (. .)))<br><br>
G2 also has the NP node (let's call it sub-graph SG2) which also has three child leaf nodes: (DT the) (NN battery) (NN life)) <br>I need to find that G1 and G2 has sub-graphs SG1 and SG2 with the similar structure, but with different values of the leaf nodes.<br>
I also need to devise some general metric that will allow me to estimate distance between any two graphs. This distance should account both for structural and leaf-node values similarity.<br><br>It would be easier to measure distance between vectors then graphs. So I am thinking how to convert directed graph (that results from POS tagging) into vector. Any ideas, links here? <br>
<br>Thanks!<br><br>On 28 October 2011 00:27, dokondr <<a href="mailto:dokondr@gmail.com">dokondr@gmail.com</a>> wrote:<br>
> My mistake: need advice on libraries and data types not for trees but for<br>
> directed graphs.<br>
><br>
> On Thu, Oct 27, 2011 at 4:49 PM, dokondr <<a href="mailto:dokondr@gmail.com">dokondr@gmail.com</a>> wrote:<br>
>><br>
>> Please advise on Haskell libraries to compare trees in textual<br>
>> representation.<br>
>> I need to compare both structure and node contents of two trees, find<br>
>> similar sub-trees, and need some metric to measure distance between two<br>
>> trees.<br>
>> Also need advice on simple parser to convert textual tree representation<br>
>> into a data type convenient for tree manipulation (comparison, matching,<br>
>> etc.) What data type to use for trees with arbitrary structure?<br>
>><br>
>> Example trees:<br>
>><br>
>> *** Tree 1:<br>
>> (ROOT<br>
>> (S<br>
>> (NP (DT The) (NN voice) (NN quality))<br>
>> (VP (VBD was)<br>
>> (ADJP (JJ clear) (RB too)))<br>
>> (. .)))<br>
>><br>
>><br>
>> *** Tree 2:<br>
>> (ROOT<br>
>> (S<br>
>> (SBAR (IN Although)<br>
>> (S<br>
>> (NP (DT the) (NN battery) (NN life))<br>
>> (VP (VBD was) (RB not)<br>
>> (ADJP (JJ long)))))<br>
>> (, ,)<br>
>> (NP (DT that))<br>
>> (VP (VBZ is)<br>
>> (VP (VBN ok)<br>
>> (PP (IN for)<br>
>> (NP (PRP me)))))<br>
>> (. .)))<br>
>><br>
>> Thanks!<br>
>> Dmitri<br>
>><br>
><br>
><br>
><br>
><br>
><br>
</div><br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">> _______________________________________________<br>
> Haskell-Cafe mailing list<br>
> <a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
> <a href="http://www.haskell.org/mailman/listinfo/haskell-cafe" target="_blank">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br>
><br>
><br>
<font color="#888888"><br>
<br>
<br>
--<br>
Ivan Lazar Miljenovic<br>
<a href="mailto:Ivan.Miljenovic@gmail.com">Ivan.Miljenovic@gmail.com</a><br>
<a href="http://IvanMiljenovic.wordpress.com" target="_blank">IvanMiljenovic.wordpress.com</a><br>
</font></blockquote></div><br><br clear="all"><br>-- <br>All the best,<br>Dmitri O. Kondratiev<br><br>"This is what keeps me going: discovery"<br><a href="mailto:dokondr@gmail.com" target="_blank">dokondr@gmail.com</a><br>
<a href="http://sites.google.com/site/dokondr/welcome" target="_blank">http://sites.google.com/site/dokondr/welcome</a><br><br><br>