GraphPersistenceWrapperEquals Method (IGraph, DictionaryINode, INode)

public bool Equals(
	IGraph g,
	out Dictionary<INode, INode> mapping
)

Public Function Equals ( 
	g As IGraph,
	<OutAttribute> ByRef mapping As Dictionary(Of INode, INode)
) As Boolean

Parameters

g

Type: VDS.RDFIGraph
Graph to test for equality.

mapping

Type: System.Collections.GenericDictionaryINode, INode
Mapping of Blank Nodes iff the Graphs are equal and contain some Blank Nodes.

Return Value

[Missing <returns> documentation for "M:VDS.RDF.GraphPersistenceWrapper.Equals(VDS.RDF.IGraph,System.Collections.Generic.Dictionary{VDS.RDF.INode,VDS.RDF.INode}@)"]

Implements

The algorithm used to determine Graph equality is based in part on a Iterative Vertex Classification Algorithm described in a Technical Report from HP by Jeremy J Carroll -. Matching RDF Graphs

Graph Equality is determined according to the following algorithm:.

1. If the given Graph is null Graphs are not equal
2. If the given Graph is this Graph (as determined by Reference Equality) then Graphs are equal
3. If the Graphs have a different number of Triples they are not equal
4. Declare a list of Triples which are the Triples of the given Graph called OtherTriples
5. Declare two dictionaries of Nodes to Integers which are called LocalClassification and OtherClassification
6. For Each Triple in this Graph
   1. If it is a Ground Triple and cannot be found and removed from OtherTriples then Graphs are not equal since the Triple does not exist in both Graphs
   2. If it contains Blank Nodes track the number of usages of this Blank Node in LocalClassification
7. If there are any Triples remaining in OtherTriples which are Ground Triples then Graphs are not equal since this Graph does not contain them
8. If all the Triples from both Graphs were Ground Triples and there were no Blank Nodes then the Graphs are equal
9. Iterate over the remaining Triples in OtherTriples and populate the OtherClassification
10. If the count of the two classifications is different the Graphs are not equal since there are differing numbers of Blank Nodes in the Graph
11. Now build two additional dictionaries of Integers to Integers which are called LocalDegreeClassification and OtherDegreeClassification. Iterate over LocalClassification and OtherClassification such that the corresponding degree classifications contain a mapping of the number of Blank Nodes with a given degree
12. If the count of the two degree classifications is different the Graphs are not equal since there are not the same range of Blank Node degrees in both Graphs
13. For All classifications in LocalDegreeClassification there must be a matching classification in OtherDegreeClassification else the Graphs are not equal
14. Then build a possible mapping using the following rules:
    1. Any Blank Node used only once should be mapped to an equivalent Blank Node in the other Graph. If this is not possible then the Graphs are not equal
    2. Any Blank Node with a unique degree should be mapped to an equivalent Blank Node in the other Graph. If this is not possible then the Graphs are not equal
    3. Keep a copy of the mapping up to this point as a Base Mapping for use as a fallback in later steps
    4. Build up lists of dependent pairs of Blank Nodes for both Graphs
    5. Use these lists to determine if there are any independent nodes not yet mapped. These should be mapped to equivalent Blank Nodes in the other Graph, if this is not possible the Graphs are not equal
    6. Use the Dependencies and existing mappings to generate a possible mapping
    7. If a Complete Possible Mapping (there is a Mapping for each Blank Node from this Graph to the Other Graph) then test this mapping. If it succeeds then the Graphs are equal
    8. Otherwise we now fallback to the Base Mapping and use it as a basis for Brute Forcing the possible solution space and testing every possibility until either a mapping works or we find the Graphs to be non-equal

Reference