Hi Sean,

Looking at all the implementations of Graph, not of them override equals so two graphs are "equal" only if they are the same object.

There isn't really an support in the module for determining equality based on graph structure or a specific data model. So I am afraid you will have to come up with your own algorithm for iterating over the nodes and edges of the graph to determine equality.

-Justin

Sean McGowan wrote:

Hi Justin,

If that's the case, I might try redesigning what I have. You see my index is a list of Graph objects. The nodes in each Graph are 'FeatureNode' objects. These extend BasicNode but have two variables added, 'featureCode' and 'TOID'. The 'featureCode' is a number representing a type of polygon. TOID is a unique number for a polygon so it'll be unique to its node. The nodes don't contain an object.

So my question is this. If I have two graphs, is there any way of checking that they equal but excluding one factor, that is the TOID. So I'd want to check that graphs G1 and G2 are equal where G1's nodes contain only featureCodes but G2's nodes contain featureCodes and TOIDs. I just want to exclude the TOID from the "equalness". Apologies for the bizarreness of this question By the way, when you check that two Graph objects are equal normally, what are you checking? Did you use the inherited .equals() for this?

Thanks,

SeanFrom: Justin Deoliveira <jdeolive@anonymised.com>

To: Sean McGowan <mcgowansean@anonymised.com>

CC: geotools-gt2-users@lists.sourceforge.net

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

Date: Thu, 15 Dec 2005 13:10:26 -0800Hi 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

Geotools-gt2-users@lists.sourceforge.net

https://lists.sourceforge.net/lists/listinfo/geotools-gt2-users--

Justin Deoliveira

The Open Planning Project

http://topp.openplans.org

--

Justin Deoliveira

The Open Planning Project

http://topp.openplans.org