abstractexhaustiveisomorphisminspector.java

使用Java开发的图论算法的包

     *
     * <p>Implementation Notes and considerations: Let's consider a trivial
     * example: graph of strings "A","B","C" with two edges A->B,B->C. Let's
     * assume for this example that the vertex comparator always returns true,
     * meaning String value does not matter, only the graph structure does. So
     * "D" "E" "A" with D->E->A will be isomorphic , but "A","B,"C"with
     * A->B,A->C will not.
     *
     * <p>First let's extract the important info for isomorphism from the graph.
     * We don't care what the vertexes are, we care that there are 3 of them
     * with edges from first to second and from second to third. So the source
     * LabelsGraph will be: vertexes:[1,2,3] edges:[[1->2],[2->3]] Now we will
     * do several permutations of D,E,A. A few examples: D->E , E->A
     * [1,2,3]=[A,D,E] so edges are: 2->3 , 3->1 . does it match the source? NO.
     * [1,2,3]=[D,A,E] so edges are: 1->3 , 3->2 . no match either.
     * [1,2,3]=[D,E,A] so edges are: 1->2 , 2->3 . MATCH FOUND ! Trivial
     * algorithm: We will iterate on all permutations
     * [abc][acb][bac][bca][cab][cba]. (n! of them,3!=6) For each, first compare
     * vertexes using the VertexComparator(always true). Then see that the edges
     * are in the exact order 1st->2nd , 2nd->3rd. If we found a match stop and
     * return true, otherwise return false; we will compare vetices and edges by
     * their order (1st,2nd,3rd,etc) only. Two graphs are the same, by this
     * order, if: 1. for each i, sourceVertexArray[i] is equivalent to
     * targetVertexArray[i] 2. for each vertex, the edges which start in it (it
     * is the source) goes to the same ordered vertex. For multiple ones, count
     * them too.
     *
     * @return IsomorphismRelation for a permutation found, or null if no
     * permutation was isomorphic
     */
    private IsomorphismRelation<V, E> findNextIsomorphicGraph()
    {
        boolean result = false;
        IsomorphismRelation<V, E> resultRelation = null;
        if (this.vertexPermuteIter != null) {
            // System.out.println("Souce  LabelsGraph="+this.lableGraph1);
            while (this.vertexPermuteIter.hasNext()) {
                currVertexPermutation = this.vertexPermuteIter.getNextSet();

                // compare vertexes
                if (!areVertexSetsOfTheSameEqualityGroup(
                        this.graph1VertexSet,
                        currVertexPermutation))
                {
                    continue; // this one is not iso, so try the next one
                }

                // compare edges
                GraphOrdering<V, E> currPermuteGraph =
                    new GraphOrdering<V, E>(
                        this.graph2,
                        currVertexPermutation,
                        this.graph2EdgeSet);

                // System.out.println("target LablesGraph="+currPermuteGraph);
                if (this.lableGraph1.equalsByEdgeOrder(currPermuteGraph)) {
                    // create result object.
                    resultRelation =
                        new IsomorphismRelation<V, E>(
                            new ArrayList<V>(graph1VertexSet),
                            new ArrayList<V>(currVertexPermutation),
                            graph1,
                            graph2);

                    // if the edge comparator exists, check equivalence by it
                    boolean edgeEq =
                        areAllEdgesEquivalent(
                            resultRelation,
                            this.edgeComparator);
                    if (edgeEq) // only if equivalent

                    {
                        result = true;
                        break;
                    }
                }
            }
        }

        if (result == true) {
            return resultRelation;
        } else {
            return null;
        }
    }

    /**
     * Will be called on every two sets of vertexes returned by the permutation
     * iterator. From findNextIsomorphicGraph(). Should make sure that the two
     * sets are euqivalent. Subclasses may decide to implements it as an always
     * true methods only if they make sure that the permutationIterator will
     * always be already equivalent.
     *
     * @param vertexSet1 FIXME Document me
     * @param vertexSet2 FIXME Document me
     */
    protected abstract boolean areVertexSetsOfTheSameEqualityGroup(
        Set<V> vertexSet1,
        Set<V> vertexSet2);

    /**
     * For each edge in g1, get the Correspondence edge and test the pair.
     *
     * @param resultRelation
     * @param edgeComparator if null, always return true.
     */
    protected boolean areAllEdgesEquivalent(
        IsomorphismRelation<V, E> resultRelation,
        EquivalenceComparator<? super E, ? super Graph<V, E>> edgeComparator)
    {
        boolean checkResult = true;

        if (edgeComparator == null) {
            // nothing to check
            return true;
        }

        try {
            Set<E> edgeSet = this.graph1.edgeSet();

            for (E currEdge : edgeSet) {
                E correspondingEdge =
                    resultRelation.getEdgeCorrespondence(currEdge, true);

                // if one edge test fail , fail the whole method
                if (!edgeComparator.equivalenceCompare(
                        currEdge,
                        correspondingEdge,
                        this.graph1,
                        this.graph2))
                {
                    checkResult = false;
                    break;
                }
            }
        } catch (IllegalArgumentException illegal) {
            checkResult = false;
        }

        return checkResult;
    }

    /**
     * return nextElement() casted as IsomorphismRelation
     */
    public IsomorphismRelation nextIsoRelation()
    {
        return next();
    }

    /**
     * Efficiency: The value is known after the first check for isomorphism
     * activated on this class and returned there after in O(1). If called on a
     * new ("virgin") class, it activates 1 iso-check.
     *
     * @return <code>true</code> iff the two graphs are isomorphic
     */
    public boolean isIsomorphic()
    {
        return !(this.nextSupplier.isEnumerationStartedEmpty());
    }

    /* (non-Javadoc)
     * @see java.util.Enumeration#hasMoreElements()
     */
    public boolean hasNext()
    {
        boolean result = this.nextSupplier.hasMoreElements();

        return result;
    }

    /**
     * @see java.util.Iterator#next()
     */
    public IsomorphismRelation next()
    {
        return this.nextSupplier.nextElement();
    }

    /* (non-Javadoc)
     * @see java.util.Iterator#remove()
     */
    public void remove()
    {
        throw new UnsupportedOperationException(
            "remove() method is not supported in AdaptiveIsomorphismInspectorFactory."
            + " There is no meaning to removing an isomorphism result.");
    }

    //~ Inner Classes ----------------------------------------------------------

    private class NextFunctor
        implements PrefetchIterator.NextElementFunctor<IsomorphismRelation>
    {
        public IsomorphismRelation nextElement()
            throws NoSuchElementException
        {
            IsomorphismRelation resultRelation = findNextIsomorphicGraph();
            if (resultRelation != null) {
                return resultRelation;
            } else {
                throw new NoSuchElementException(
                    "IsomorphismInspector does not have any more elements");
            }
        }
    }
}

// End AbstractExhaustiveIsomorphismInspector.java