Class GraphMatcher

Implements a Graph Isomorphism Algorithm.

Inheritance
System.Object
GraphMatcher
Inherited Members
object.Equals(object)
object.Equals(object, object)
object.GetHashCode()
object.GetType()
object.MemberwiseClone()
object.ReferenceEquals(object, object)
object.ToString()
Namespace: VDS.RDF
Assembly: dotNetRdf.dll
Syntax
public class GraphMatcher
Remarks

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 but has been expanded upon significantly to use a variety of techniques.

Graph Equality is determined according to the following algorithm, we refer to the first graph as the Source Graph and the second graph as the Target Graph:.

  1. If both graphs are null they are considered equal
  2. If only one of the given graph is null then they are not equal
  3. If the given graphs are reference equal then they are equal
  4. If the given graphs have a different number of Triples they are not equal
  5. If the given graphs have a different number of quoted triples, they are not equal
  6. Declare a list of triples which are the asserted triples of the second graph called TargetTriples
  7. Declare a set of triples which are the quoted triples of the second graph called TargetQuoted
  8. Declare two dictionaries of Nodes to Integers which are called SourceClassification and TargetClassification
  9. For Each Triple asserted in the Source Graph
    1. If it is a ground triple and cannot be found and removed from TargetTriples 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 SourceClassification
  10. For Each Triple quoted in the Source Graph
    1. If it is a ground triple and cannot be found and removed from TargetQuoted then graphs are not equal since the triple is not quoted in both graphs
    2. If it contains blank nodes track the number of usages of this blank node in SourceClassification
  11. If there are any triples remaining in TargetTriples which are ground triples then graphs are not equal since the Source Graph does not contain them
  12. If there are any triples remaining in TargetQuoted which are ground triples then graphs are not equal since the Source Graph does not quote them
  13. If all the triples from both graphs were ground triples (i.e. there were no blank nodes) then the graphs are equal
  14. Iterate over the remaining triples in TargetTriples and TargetQuoted and populate the TargetClassification
  15. 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
  16. Now build two additional dictionaries of Integers to Integers which are called SourceDegreeClassification and TargetDegreeClassification. Iterate over SourceClassification and TargetClassification such that the corresponding degree classifications contain a mapping of the number of blank nodes with a given degree
  17. 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
  18. For All classifications in SourceDegreeClassification there must be a matching classification in TargetDegreeClassification else the graphs are not equal
  19. From this point in the algorithm, we can merge the remaining quoted and asserted triples to be matched into a single set for source and target triples.
  20. Then build a possible mapping using the following rules:
    1. Any blank bode used only once (single-use) in the Source Graph should be mapped to an equivalent blank bode in the Target Graph. If this is not possible then the graphs are not equal
    2. Any blank node with a unique degree in the Source Graph should be mapped to an equivalent blank node in the Target Graph. If this is not possible then the graphs are not equal
    3. Any blank node used with unique constants (two other ground terms in a triple) in the Source Graph should be mapped to an equivalent blank bode in the Target Graph. If this is not possible then the graphs are not equal.
    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 in the Source Graph. These should be mapped to equivalent blank nodes in the Target Graph, if this is not possible the graphs are not equal
    6. Important: Keep a copy of the mapping up to this point as a Base Mapping for use as a fallback in later steps
    7. Use the dependency information and existing mappings to generate a possible mapping
    8. If a complete possible mapping (there is a mapping for each blank node from the Source Graph to the Target Graph) then test this mapping. If it succeeds then the graphs are equal
  21. If we don't yet have a mapping take a divide and conquer approach:
    1. Take the not yet mapped blank nodes for each graph and sub-divide them into their isolated sub-graphs
    2. If there are at least 2 isolated sub-graphs proceed to divide and conquer
    3. For Each Isolated Sub-Graph from the Source Graph
      1. Consider each possible isolated sub-graph of the same size from the target graph, if there are none then graphs are not equal. If there is a single possible equal isolated sub-graph add the mappings for all involved blank nodes.
    4. If we now have a complete possible mapping (there is a mapping for each blank node from the Source Graph to the Target Graph) then test the mapping. Return success/failure depending on whether the mapping is valid.
    5. Important: Keep a copy of the mapping up to this point as a Base Mapping for use as a base for the brute force step
  22. If we still don't have a complete mapping 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

Properties

| Improve this Doc View Source

Mapping

Gets the Blank Node Mapping found between the Graphs (if one was found).

Declaration
public Dictionary<INode, INode> Mapping { get; }
Property Value
Type Description
System.Collections.Generic.Dictionary<TKey, TValue><INode, INode>
Remarks

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 but has been expanded upon significantly to use a variety of techniques.

Graph Equality is determined according to the following algorithm, we refer to the first graph as the Source Graph and the second graph as the Target Graph:.

  1. If both graphs are null they are considered equal
  2. If only one of the given graph is null then they are not equal
  3. If the given graphs are reference equal then they are equal
  4. If the given graphs have a different number of Triples they are not equal
  5. If the given graphs have a different number of quoted triples, they are not equal
  6. Declare a list of triples which are the asserted triples of the second graph called TargetTriples
  7. Declare a set of triples which are the quoted triples of the second graph called TargetQuoted
  8. Declare two dictionaries of Nodes to Integers which are called SourceClassification and TargetClassification
  9. For Each Triple asserted in the Source Graph
    1. If it is a ground triple and cannot be found and removed from TargetTriples 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 SourceClassification
  10. For Each Triple quoted in the Source Graph
    1. If it is a ground triple and cannot be found and removed from TargetQuoted then graphs are not equal since the triple is not quoted in both graphs
    2. If it contains blank nodes track the number of usages of this blank node in SourceClassification
  11. If there are any triples remaining in TargetTriples which are ground triples then graphs are not equal since the Source Graph does not contain them
  12. If there are any triples remaining in TargetQuoted which are ground triples then graphs are not equal since the Source Graph does not quote them
  13. If all the triples from both graphs were ground triples (i.e. there were no blank nodes) then the graphs are equal
  14. Iterate over the remaining triples in TargetTriples and TargetQuoted and populate the TargetClassification
  15. 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
  16. Now build two additional dictionaries of Integers to Integers which are called SourceDegreeClassification and TargetDegreeClassification. Iterate over SourceClassification and TargetClassification such that the corresponding degree classifications contain a mapping of the number of blank nodes with a given degree
  17. 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
  18. For All classifications in SourceDegreeClassification there must be a matching classification in TargetDegreeClassification else the graphs are not equal
  19. From this point in the algorithm, we can merge the remaining quoted and asserted triples to be matched into a single set for source and target triples.
  20. Then build a possible mapping using the following rules:
    1. Any blank bode used only once (single-use) in the Source Graph should be mapped to an equivalent blank bode in the Target Graph. If this is not possible then the graphs are not equal
    2. Any blank node with a unique degree in the Source Graph should be mapped to an equivalent blank node in the Target Graph. If this is not possible then the graphs are not equal
    3. Any blank node used with unique constants (two other ground terms in a triple) in the Source Graph should be mapped to an equivalent blank bode in the Target Graph. If this is not possible then the graphs are not equal.
    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 in the Source Graph. These should be mapped to equivalent blank nodes in the Target Graph, if this is not possible the graphs are not equal
    6. Important: Keep a copy of the mapping up to this point as a Base Mapping for use as a fallback in later steps
    7. Use the dependency information and existing mappings to generate a possible mapping
    8. If a complete possible mapping (there is a mapping for each blank node from the Source Graph to the Target Graph) then test this mapping. If it succeeds then the graphs are equal
  21. If we don't yet have a mapping take a divide and conquer approach:
    1. Take the not yet mapped blank nodes for each graph and sub-divide them into their isolated sub-graphs
    2. If there are at least 2 isolated sub-graphs proceed to divide and conquer
    3. For Each Isolated Sub-Graph from the Source Graph
      1. Consider each possible isolated sub-graph of the same size from the target graph, if there are none then graphs are not equal. If there is a single possible equal isolated sub-graph add the mappings for all involved blank nodes.
    4. If we now have a complete possible mapping (there is a mapping for each blank node from the Source Graph to the Target Graph) then test the mapping. Return success/failure depending on whether the mapping is valid.
    5. Important: Keep a copy of the mapping up to this point as a Base Mapping for use as a base for the brute force step
  22. If we still don't have a complete mapping 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

Methods

| Improve this Doc View Source

Equals(IGraph, IGraph)

Compares two Graphs for equality.

Declaration
public bool Equals(IGraph g, IGraph h)
Parameters
Type Name Description
IGraph g

Graph.
IGraph h

Graph.
Returns
Type Description
System.Boolean
Remarks

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 but has been expanded upon significantly to use a variety of techniques.

Graph Equality is determined according to the following algorithm, we refer to the first graph as the Source Graph and the second graph as the Target Graph:.

  1. If both graphs are null they are considered equal
  2. If only one of the given graph is null then they are not equal
  3. If the given graphs are reference equal then they are equal
  4. If the given graphs have a different number of Triples they are not equal
  5. If the given graphs have a different number of quoted triples, they are not equal
  6. Declare a list of triples which are the asserted triples of the second graph called TargetTriples
  7. Declare a set of triples which are the quoted triples of the second graph called TargetQuoted
  8. Declare two dictionaries of Nodes to Integers which are called SourceClassification and TargetClassification
  9. For Each Triple asserted in the Source Graph
    1. If it is a ground triple and cannot be found and removed from TargetTriples 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 SourceClassification
  10. For Each Triple quoted in the Source Graph
    1. If it is a ground triple and cannot be found and removed from TargetQuoted then graphs are not equal since the triple is not quoted in both graphs
    2. If it contains blank nodes track the number of usages of this blank node in SourceClassification
  11. If there are any triples remaining in TargetTriples which are ground triples then graphs are not equal since the Source Graph does not contain them
  12. If there are any triples remaining in TargetQuoted which are ground triples then graphs are not equal since the Source Graph does not quote them
  13. If all the triples from both graphs were ground triples (i.e. there were no blank nodes) then the graphs are equal
  14. Iterate over the remaining triples in TargetTriples and TargetQuoted and populate the TargetClassification
  15. 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
  16. Now build two additional dictionaries of Integers to Integers which are called SourceDegreeClassification and TargetDegreeClassification. Iterate over SourceClassification and TargetClassification such that the corresponding degree classifications contain a mapping of the number of blank nodes with a given degree
  17. 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
  18. For All classifications in SourceDegreeClassification there must be a matching classification in TargetDegreeClassification else the graphs are not equal
  19. From this point in the algorithm, we can merge the remaining quoted and asserted triples to be matched into a single set for source and target triples.
  20. Then build a possible mapping using the following rules:
    1. Any blank bode used only once (single-use) in the Source Graph should be mapped to an equivalent blank bode in the Target Graph. If this is not possible then the graphs are not equal
    2. Any blank node with a unique degree in the Source Graph should be mapped to an equivalent blank node in the Target Graph. If this is not possible then the graphs are not equal
    3. Any blank node used with unique constants (two other ground terms in a triple) in the Source Graph should be mapped to an equivalent blank bode in the Target Graph. If this is not possible then the graphs are not equal.
    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 in the Source Graph. These should be mapped to equivalent blank nodes in the Target Graph, if this is not possible the graphs are not equal
    6. Important: Keep a copy of the mapping up to this point as a Base Mapping for use as a fallback in later steps
    7. Use the dependency information and existing mappings to generate a possible mapping
    8. If a complete possible mapping (there is a mapping for each blank node from the Source Graph to the Target Graph) then test this mapping. If it succeeds then the graphs are equal
  21. If we don't yet have a mapping take a divide and conquer approach:
    1. Take the not yet mapped blank nodes for each graph and sub-divide them into their isolated sub-graphs
    2. If there are at least 2 isolated sub-graphs proceed to divide and conquer
    3. For Each Isolated Sub-Graph from the Source Graph
      1. Consider each possible isolated sub-graph of the same size from the target graph, if there are none then graphs are not equal. If there is a single possible equal isolated sub-graph add the mappings for all involved blank nodes.
    4. If we now have a complete possible mapping (there is a mapping for each blank node from the Source Graph to the Target Graph) then test the mapping. Return success/failure depending on whether the mapping is valid.
    5. Important: Keep a copy of the mapping up to this point as a Base Mapping for use as a base for the brute force step
  22. If we still don't have a complete mapping 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
| Improve this Doc View Source

GenerateMappings(Dictionary<INode, INode>, Dictionary<INode, List<INode>>)

Helper method for brute forcing the possible mappings.

Declaration
public static IEnumerable<Dictionary<INode, INode>> GenerateMappings(Dictionary<INode, INode> baseMapping, Dictionary<INode, List<INode>> possibleMappings)
Parameters
Type Name Description
System.Collections.Generic.Dictionary<TKey, TValue><INode, INode> baseMapping

Base Mapping.
System.Collections.Generic.Dictionary<TKey, TValue><INode, System.Collections.Generic.List<T><INode>> possibleMappings

Possible Mappings.
Returns
Type Description
System.Collections.Generic.IEnumerable<T><System.Collections.Generic.Dictionary<TKey, TValue><INode, INode>>
Remarks

The base mapping at the time of the initial call should contain known good mappings.

Extension Methods