/*
* (C) Copyright 2015-2017, by Fabian Späh and Contributors.
*
* JGraphT : a free Java graph-theory library
*
* This program and the accompanying materials are dual-licensed under
* either
*
* (a) the terms of the GNU Lesser General Public License version 2.1
* as published by the Free Software Foundation, or (at your option) any
* later version.
*
* or (per the licensee's choosing)
*
* (b) the terms of the Eclipse Public License v1.0 as published by
* the Eclipse Foundation.
*/
package org.jgrapht.alg.isomorphism;
import java.util.*;
import org.jgrapht.*;
import org.jgrapht.graph.*;
/**
* Base implementation of the VF2 algorithm using its feature of detecting
* isomorphism between two graphs
* as described in Cordella et al. A (sub)graph isomorphism algorithm for matching large graphs
* (2004), DOI:10.1109/TPAMI.2004.75,
*
* http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1323804
*
*
* This implementation of the VF2 algorithm does not support graphs with multiple edges.
*
* @param the type of the vertices
* @param the type of the edges
*/
public abstract class VF2AbstractIsomorphismInspector
implements IsomorphismInspector
{
protected Graph graph1, graph2;
protected Comparator vertexComparator;
protected Comparator edgeComparator;
protected GraphOrdering ordering1, ordering2;
/**
* Construct a new base implementation of the VF2 isomorphism inspector.
*
* @param graph1 the first graph
* @param graph2 the second graph
* @param vertexComparator comparator for semantic equivalence of vertices
* @param edgeComparator comparator for semantic equivalence of edges
* @param cacheEdges if true, edges get cached for faster access
*/
public VF2AbstractIsomorphismInspector(
Graph graph1, Graph graph2, Comparator vertexComparator,
Comparator edgeComparator, boolean cacheEdges)
{
if ((graph1 instanceof Multigraph) || (graph2 instanceof Multigraph)
|| (graph1 instanceof Pseudograph) || (graph2 instanceof Pseudograph)
|| (graph1 instanceof DirectedMultigraph) || (graph2 instanceof DirectedMultigraph)
|| (graph1 instanceof DirectedPseudograph) || (graph2 instanceof DirectedPseudograph))
{
throw new UnsupportedOperationException(
"graphs with multiple " + "edges are not supported");
}
if (((graph1 instanceof DirectedGraph) && (graph2 instanceof UndirectedGraph))
|| ((graph1 instanceof UndirectedGraph) && (graph2 instanceof DirectedGraph)))
{
throw new IllegalArgumentException(
"can not match directed with " + "undirected graphs");
}
this.graph1 = graph1;
this.graph2 = graph2;
this.vertexComparator = vertexComparator;
this.edgeComparator = edgeComparator;
this.ordering1 = new GraphOrdering<>(graph1, true, cacheEdges);
this.ordering2 = new GraphOrdering<>(graph2, true, cacheEdges);
}
/**
* Construct a new base implementation of the VF2 isomorphism inspector.
*
* @param graph1 the first graph
* @param graph2 the second graph
* @param vertexComparator comparator for semantic equivalence of vertices
* @param edgeComparator comparator for semantic equivalence of edges
*/
public VF2AbstractIsomorphismInspector(
Graph graph1, Graph graph2, Comparator vertexComparator,
Comparator edgeComparator)
{
this(graph1, graph2, vertexComparator, edgeComparator, true);
}
/**
* Construct a new base implementation of the VF2 isomorphism inspector.
*
* @param graph1 the first graph
* @param graph2 the second graph
* @param cacheEdges if true, edges get cached for faster access
*/
public VF2AbstractIsomorphismInspector(
Graph graph1, Graph graph2, boolean cacheEdges)
{
this(graph1, graph2, null, null, cacheEdges);
}
/**
* Construct a new base implementation of the VF2 isomorphism inspector.
*
* @param graph1 the first graph
* @param graph2 the second graph
*/
public VF2AbstractIsomorphismInspector(Graph graph1, Graph graph2)
{
this(graph1, graph2, true);
}
@Override
public abstract Iterator> getMappings();
@Override
public boolean isomorphismExists()
{
Iterator> iter = getMappings();
return iter.hasNext();
}
}
// End VF2AbstractIsomorphismInspector.java
Ads help maintain this website.