/*
 * (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.