jena-arq/src/main/java/org/apache/jena/sparql/util/IsoMatcher.java - jena - Git at Google

 /**
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you under the Apache License, Version 2.0 (the
  * "License"); you may not use this file except in compliance
  * with the License.  You may obtain a copy of the License at
  *
  *     http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package org.apache.jena.sparql.util ;

 import static org.apache.jena.atlas.lib.tuple.TupleFactory.tuple ;

 import java.util.ArrayList ;
 import java.util.Collection ;
 import java.util.Iterator ;
 import java.util.List ;

 import org.apache.jena.atlas.lib.tuple.Tuple ;
 import org.apache.jena.graph.Graph ;
 import org.apache.jena.graph.Node ;
 import org.apache.jena.graph.Triple ;
 import org.apache.jena.sparql.core.DatasetGraph ;
 import org.apache.jena.sparql.core.Quad ;
 import org.apache.jena.sparql.util.NodeUtils.EqualityTest ;

 // Needs to be back tracking?

 /** Simple isomorphism testing
  * This code is simple and slow.
  * For graphs, the Graph isomorphism code in Jena is much better (better tested, better performance)
  * This code can work on any tuples of nodes.
  */
 public class IsoMatcher
 {
     // Possible speed ups
     //  A/ Phase 1 - do all non-bNode tuples. / Phase 2 : all tuples with a bNode
     //  B/ turn tuples2 into a map, keyed by (1) constants or (2) first term.

     static boolean DEBUG = false ;
     private final List<Tuple<Node>>        tuples1 ;
     private final List<Tuple<Node>>        tuples2 ;

 //    private final Map<Node, Node>           mapping = new HashMap<>();
 //    private final Queue<Pair<Node, Node>>   causes  = new LinkedList<>() ;
     private final EqualityTest nodeTest ;

     static class Mapping {
         final Node     node1 ;
         final Node     node2 ;
         final Mapping  parent ;

         static Mapping rootMapping = new Mapping(null, null, null) ;

         public Mapping(Mapping parent, Node node1, Node node2) {
             super() ;
             this.parent = parent ;
             this.node1 = node1 ;
             this.node2 = node2 ;
         }

         public boolean mapped(Node node) {
             return map(node) != null ;
         }

         public boolean revmapped(Node node) {
             return revmap(node) != null ;
         }

         public Node map(Node node) {
             Mapping mapping = this ;
             while (mapping != rootMapping) {
                 if ( mapping.node1.equals(node) )
                     return mapping.node2 ;
                 mapping = mapping.parent ;
             }
             return null ;
         }

         // Reverse mapping.
         public Node revmap(Node node) {
             Mapping mapping = this ;
             while (mapping != rootMapping) {
                 if ( mapping.node2.equals(node) )
                     return mapping.node1 ;
                 mapping = mapping.parent ;
             }
             return null ;
         }

         @Override
         public String toString() {
             StringBuilder sbuff = new StringBuilder() ;
             Mapping mapping = this ;
             while (mapping != rootMapping) {
                 sbuff.append("{" + mapping.node1 + " => " + mapping.node2 + "}") ;
                 mapping = mapping.parent ;
             }
             sbuff.append("{}") ;
             return sbuff.toString() ;
         }
     }

     static class Cause {
         final Tuple<Node> tuple ;
         final Mapping     mapping ;

         public Cause(Tuple<Node> tuple, Mapping mapping) {
             super() ;
             this.tuple = tuple ;
             this.mapping = mapping ;
         }
     }

     public static boolean isomorphic(Graph g1, Graph g2) {
         List<Tuple<Node>> x1 = tuplesTriples(g1.find(null, null, null)) ;
         List<Tuple<Node>> x2 = tuplesTriples(g2.find(null, null, null)) ;

         IsoMatcher matcher = new IsoMatcher(x1, x2, NodeUtils.sameTerm) ;
         return matcher.match() ;
     }

     public static boolean isomorphic(DatasetGraph dsg1, DatasetGraph dsg2) {
         List<Tuple<Node>> x1 = tuplesQuads(dsg1.find()) ;
         List<Tuple<Node>> x2 = tuplesQuads(dsg2.find()) ;

         IsoMatcher matcher = new IsoMatcher(x1, x2, NodeUtils.sameTerm) ;
         return matcher.match() ;
     }

     public static boolean isomorphic(List<Tuple<Node>> x1, List<Tuple<Node>> x2) {
         x1 = new ArrayList<>(x1) ;
         x2 = new ArrayList<>(x2) ;
         IsoMatcher matcher = new IsoMatcher(x1, x2, NodeUtils.sameTerm) ;
         return matcher.match() ;
     }

     private static List<Tuple<Node>> tuplesTriples(Iterator<Triple> iter) {
         List<Tuple<Node>> tuples = new ArrayList<>() ;
         for ( ; iter.hasNext() ; ) {
             Triple t = iter.next() ;
             Tuple<Node> tuple = tuple(t.getSubject(), t.getPredicate(), t.getObject()) ;
             tuples.add(tuple) ;
         }
         return tuples ;
     }

     private static List<Tuple<Node>> tuplesQuads(Iterator<Quad> iter) {
         List<Tuple<Node>> tuples = new ArrayList<>() ;
         for ( ; iter.hasNext() ; ) {
             Quad q = iter.next() ;
             Tuple<Node> tuple = tuple(q.getGraph(), q.getSubject(), q.getPredicate(), q.getObject()) ;
             tuples.add(tuple) ;
         }
         return tuples ;
     }

     public IsoMatcher(List<Tuple<Node>> g1, List<Tuple<Node>> g2, EqualityTest nodeTest) {
         this.tuples1 = g1 ;
         this.tuples2 = g2 ;
         this.nodeTest = nodeTest ;
     }

     // May MUTATE tuples1 or tuples2
     public boolean match() {
         return match(tuples1, tuples2, Mapping.rootMapping) ;
     }

     private boolean match(List<Tuple<Node>> tuples1, List<Tuple<Node>> tuples2, Mapping mapping) {
         if ( DEBUG ) {
             System.out.println("match: ") ;
             System.out.println("  "+tuples1) ;
             System.out.println("  "+tuples2) ;
             System.out.println("  "+mapping) ;
         }
         if ( tuples1.size() != tuples2.size() )
             return false;

         List<Tuple<Node>> tuples = new ArrayList<>(tuples1) ;  // Copy, mutate
         for ( Tuple<Node> t1 : tuples1 ) {
             if ( DEBUG )
                 System.out.println("  t1 = "+t1) ;
             tuples.remove(t1) ;
             List<Cause> causes = match(t1, tuples2, mapping) ;
             for ( Cause c : causes ) {
                 if ( DEBUG )
                     System.out.println("  Try: "+c.mapping) ;
                 // Try t1 -> t2
                 Tuple<Node> t2 = c.tuple ;
                 tuples2.remove(t2) ;
                 if ( tuples2.isEmpty() )
                     return true ;
                 if ( match(tuples, tuples2, c.mapping) ) {
                     if ( DEBUG )
                         System.out.println("Yes") ;
                     return true ;
                 }
                 if ( DEBUG )
                     System.out.println("No") ;
                 tuples2.add(t2) ;
             }
             return false ;
         }
         // The empty-empty case
         return true ;
     }

     private List<Cause> match(Tuple<Node> t1, Collection<Tuple<Node>> g2, Mapping mapping) {
         List<Cause> matches = new ArrayList<>() ;
         for ( Tuple<Node> t2 : g2 ) {
             // No - multiple bNodes.
             Mapping step = gen(t1, t2, mapping) ;
             if (step != null) {
                 Cause c = new Cause(t2, step) ;
                 matches.add(c) ;
             }
         }
         return matches ;
     }

     // Maybe several mappings!
     private Mapping gen(Tuple<Node> t1, Tuple<Node> t2, Mapping _mapping) {
         if ( t1.len() != t2.len() )
             return null ;

         Mapping mapping = _mapping ;
         for ( int i = 0 ; i < t1.len() ; i++ ) {
             Node n1 = t1.get(i) ;
             Node n2 = t2.get(i) ;
             if ( ! nodeTest.equal(n1, n2) ) {
                 mapping = gen(n1, n2, mapping) ;
                 if ( mapping == null )
                     return null ;
             }
         }
         return mapping ;
     }

     private Mapping gen(Node x1, Node x2, Mapping mapping) {
         if ( x1.isBlank() && x2.isBlank() ) {
             // Is x1 already mapped?
             Node z = mapping.map(x1) ;
             if ( z != null )
                 // Already mapped
                 return (nodeTest.equal(x2, z)) ? mapping : null ;
             // Check reverse
             if ( mapping.revmapped(x2) )
                 return null ;
             return new Mapping(mapping, x1, x2) ;

         }
         return null ;
     }

 }
	/**
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you under the Apache License, Version 2.0 (the
	* "License"); you may not use this file except in compliance
	* with the License. You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package org.apache.jena.sparql.util ;

	import static org.apache.jena.atlas.lib.tuple.TupleFactory.tuple ;

	import java.util.ArrayList ;
	import java.util.Collection ;
	import java.util.Iterator ;
	import java.util.List ;

	import org.apache.jena.atlas.lib.tuple.Tuple ;
	import org.apache.jena.graph.Graph ;
	import org.apache.jena.graph.Node ;
	import org.apache.jena.graph.Triple ;
	import org.apache.jena.sparql.core.DatasetGraph ;
	import org.apache.jena.sparql.core.Quad ;
	import org.apache.jena.sparql.util.NodeUtils.EqualityTest ;

	// Needs to be back tracking?

	/** Simple isomorphism testing
	* This code is simple and slow.
	* For graphs, the Graph isomorphism code in Jena is much better (better tested, better performance)
	* This code can work on any tuples of nodes.
	*/
	public class IsoMatcher
	{
	// Possible speed ups
	// A/ Phase 1 - do all non-bNode tuples. / Phase 2 : all tuples with a bNode
	// B/ turn tuples2 into a map, keyed by (1) constants or (2) first term.

	static boolean DEBUG = false ;
	private final List<Tuple<Node>> tuples1 ;
	private final List<Tuple<Node>> tuples2 ;

	// private final Map<Node, Node> mapping = new HashMap<>();
	// private final Queue<Pair<Node, Node>> causes = new LinkedList<>() ;
	private final EqualityTest nodeTest ;

	static class Mapping {
	final Node node1 ;
	final Node node2 ;
	final Mapping parent ;

	static Mapping rootMapping = new Mapping(null, null, null) ;

	public Mapping(Mapping parent, Node node1, Node node2) {
	super() ;
	this.parent = parent ;
	this.node1 = node1 ;
	this.node2 = node2 ;
	}

	public boolean mapped(Node node) {
	return map(node) != null ;
	}

	public boolean revmapped(Node node) {
	return revmap(node) != null ;
	}

	public Node map(Node node) {
	Mapping mapping = this ;
	while (mapping != rootMapping) {
	if ( mapping.node1.equals(node) )
	return mapping.node2 ;
	mapping = mapping.parent ;
	}
	return null ;
	}

	// Reverse mapping.
	public Node revmap(Node node) {
	Mapping mapping = this ;
	while (mapping != rootMapping) {
	if ( mapping.node2.equals(node) )
	return mapping.node1 ;
	mapping = mapping.parent ;
	}
	return null ;
	}

	@Override
	public String toString() {
	StringBuilder sbuff = new StringBuilder() ;
	Mapping mapping = this ;
	while (mapping != rootMapping) {
	sbuff.append("{" + mapping.node1 + " => " + mapping.node2 + "}") ;
	mapping = mapping.parent ;
	}
	sbuff.append("{}") ;
	return sbuff.toString() ;
	}
	}

	static class Cause {
	final Tuple<Node> tuple ;
	final Mapping mapping ;

	public Cause(Tuple<Node> tuple, Mapping mapping) {
	super() ;
	this.tuple = tuple ;
	this.mapping = mapping ;
	}
	}

	public static boolean isomorphic(Graph g1, Graph g2) {
	List<Tuple<Node>> x1 = tuplesTriples(g1.find(null, null, null)) ;
	List<Tuple<Node>> x2 = tuplesTriples(g2.find(null, null, null)) ;

	IsoMatcher matcher = new IsoMatcher(x1, x2, NodeUtils.sameTerm) ;
	return matcher.match() ;
	}

	public static boolean isomorphic(DatasetGraph dsg1, DatasetGraph dsg2) {
	List<Tuple<Node>> x1 = tuplesQuads(dsg1.find()) ;
	List<Tuple<Node>> x2 = tuplesQuads(dsg2.find()) ;

	IsoMatcher matcher = new IsoMatcher(x1, x2, NodeUtils.sameTerm) ;
	return matcher.match() ;
	}

	public static boolean isomorphic(List<Tuple<Node>> x1, List<Tuple<Node>> x2) {
	x1 = new ArrayList<>(x1) ;
	x2 = new ArrayList<>(x2) ;
	IsoMatcher matcher = new IsoMatcher(x1, x2, NodeUtils.sameTerm) ;
	return matcher.match() ;
	}

	private static List<Tuple<Node>> tuplesTriples(Iterator<Triple> iter) {
	List<Tuple<Node>> tuples = new ArrayList<>() ;
	for ( ; iter.hasNext() ; ) {
	Triple t = iter.next() ;
	Tuple<Node> tuple = tuple(t.getSubject(), t.getPredicate(), t.getObject()) ;
	tuples.add(tuple) ;
	}
	return tuples ;
	}

	private static List<Tuple<Node>> tuplesQuads(Iterator<Quad> iter) {
	List<Tuple<Node>> tuples = new ArrayList<>() ;
	for ( ; iter.hasNext() ; ) {
	Quad q = iter.next() ;
	Tuple<Node> tuple = tuple(q.getGraph(), q.getSubject(), q.getPredicate(), q.getObject()) ;
	tuples.add(tuple) ;
	}
	return tuples ;
	}

	public IsoMatcher(List<Tuple<Node>> g1, List<Tuple<Node>> g2, EqualityTest nodeTest) {
	this.tuples1 = g1 ;
	this.tuples2 = g2 ;
	this.nodeTest = nodeTest ;
	}

	// May MUTATE tuples1 or tuples2
	public boolean match() {
	return match(tuples1, tuples2, Mapping.rootMapping) ;
	}

	private boolean match(List<Tuple<Node>> tuples1, List<Tuple<Node>> tuples2, Mapping mapping) {
	if ( DEBUG ) {
	System.out.println("match: ") ;
	System.out.println(" "+tuples1) ;
	System.out.println(" "+tuples2) ;
	System.out.println(" "+mapping) ;
	}
	if ( tuples1.size() != tuples2.size() )
	return false;

	List<Tuple<Node>> tuples = new ArrayList<>(tuples1) ; // Copy, mutate
	for ( Tuple<Node> t1 : tuples1 ) {
	if ( DEBUG )
	System.out.println(" t1 = "+t1) ;
	tuples.remove(t1) ;
	List<Cause> causes = match(t1, tuples2, mapping) ;
	for ( Cause c : causes ) {
	if ( DEBUG )
	System.out.println(" Try: "+c.mapping) ;
	// Try t1 -> t2
	Tuple<Node> t2 = c.tuple ;
	tuples2.remove(t2) ;
	if ( tuples2.isEmpty() )
	return true ;
	if ( match(tuples, tuples2, c.mapping) ) {
	if ( DEBUG )
	System.out.println("Yes") ;
	return true ;
	}
	if ( DEBUG )
	System.out.println("No") ;
	tuples2.add(t2) ;
	}
	return false ;
	}
	// The empty-empty case
	return true ;
	}

	private List<Cause> match(Tuple<Node> t1, Collection<Tuple<Node>> g2, Mapping mapping) {
	List<Cause> matches = new ArrayList<>() ;
	for ( Tuple<Node> t2 : g2 ) {
	// No - multiple bNodes.
	Mapping step = gen(t1, t2, mapping) ;
	if (step != null) {
	Cause c = new Cause(t2, step) ;
	matches.add(c) ;
	}
	}
	return matches ;
	}

	// Maybe several mappings!
	private Mapping gen(Tuple<Node> t1, Tuple<Node> t2, Mapping _mapping) {
	if ( t1.len() != t2.len() )
	return null ;

	Mapping mapping = _mapping ;
	for ( int i = 0 ; i < t1.len() ; i++ ) {
	Node n1 = t1.get(i) ;
	Node n2 = t2.get(i) ;
	if ( ! nodeTest.equal(n1, n2) ) {
	mapping = gen(n1, n2, mapping) ;
	if ( mapping == null )
	return null ;
	}
	}
	return mapping ;
	}

	private Mapping gen(Node x1, Node x2, Mapping mapping) {
	if ( x1.isBlank() && x2.isBlank() ) {
	// Is x1 already mapped?
	Node z = mapping.map(x1) ;
	if ( z != null )
	// Already mapped
	return (nodeTest.equal(x2, z)) ? mapping : null ;
	// Check reverse
	if ( mapping.revmapped(x2) )
	return null ;
	return new Mapping(mapping, x1, x2) ;

	}
	return null ;
	}

	}