Re: [Geotools-gt2-users] Structure Matching with Graph Objects

[Justin D. <jde...@un...>]

Hi Sean,

This problem (and the problem of finding a subgraph within a larger 
graph) are both fomrms of the subgraph isomorphism problem. In 
generality the problem is known to be NP-complete, however they are 
algorithms for solving the problem in planer graphs. Unfortunatley there 
are no such algorithms in the geotools graph module that do this as the 
algorithms are fairly complex.

http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/NODE180.HTM

-Justin

Sean McGowan wrote:
> Hi there,
> 
> Just a general graphing question. I want to compare two Graph objects 
> but I only want to check that their structures are equal, not the nodes 
> themselves.
> 
> For example, the following two graphs would be considered a match:
> 
> V = [1, 2, 3, 4]
> E = [6 (1,3), 8 (1,2), 9 (4,3), 11 (2,4)]
> 
> V = [19, 16, 13, 14]
> E = [21 (19,13), 20 (19,16), 15 (14,13), 18 (16,14)]
> 
> Thanks,
> Sean
> 
> 
> 
> 
> -------------------------------------------------------
> This SF.net email is sponsored by: Splunk Inc. Do you grep through log 
> files
> for problems?  Stop!  Download the new AJAX search engine that makes
> searching your log files as easy as surfing the  web.  DOWNLOAD SPLUNK!
> http://ads.osdn.com/?ad_id=7637&alloc_id=16865&op=click
> _______________________________________________
> Geotools-gt2-users mailing list
> Geo...@li...
> https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users
> 


-- 
Justin Deoliveira
The Open Planning Project
http://topp.openplans.org