Close Browse › Articles › 'A' Longest Common Subsequence (LCS) implementation › History › Revision 18 vs. Revision 19
Hide
Solve a problem – Filter by language, license, keyword, owner, or search text to find code & info fast. Join Siafoo Now or Learn More

'A' Longest Common Subsequence (LCS) implementation

Revision 18 vs. Revision 19

Legend:

Unmodified
Added
Removed

  • Content

    r18 r19  
    152152  
    153153What I am working with and how I do the comparison between the two graphs at the moment is to grab the list of nodes.  For each node, I grab the list of edges and compare them until I fail to find a match.  At that point the whole process stops.  I want to be able to continue to check other nodes and other edges without stopping.  
    154154  
    155155To proceed, the meaning of a node matching is simple:  the characteristics of the node are compared and if they are equal, we proceed with the next step. [Note to self: For optimization I may decide to keep some of this info around as well.  There are many repeated nodes in the graphs I am comparing and if node N1 has been compared to N1 before, there is no need to compare it's characteristics all over again.]  Next compare the edges. I approach this as an LCS problem.  Each edge_list G1(N1)(p1_1, p1_2, p1_3, etc) will be compared to G2(N1)(p1_1, p1_2, p1_3, etc) the same way we approach the longest common sub-sequence problem.  Then we go on to the next node in our node_list and do the same thing.  
    156156  
    157 [Note to self: just try making something at CMS and see what happens.  The LCS there will have to allow for comparator (defaults to operator==).  If I use the template I made, what will I be putting?  LCS<edge_list>.  Does edge_list have operator []?  If not then I need to figure out that too...]  
    158  
     157Update  
     158------  
     159  
     160I am busy with a new job.  When I started this work I was unemployed and keeping busy with this and a number of other things.  Now my efforts are to learn more about the things I need for the new job.  So I'm leaving this where it is and making it public.