/*
* (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.*;
/**
* This class represents a GraphMapping between two (subgraph)isomorphic graphs. In the subgraph
* isomorphic case, the second one is assumed to be a subgraph of the first one.
*
* @param the type of the vertices
* @param the type of the edges
*/
public class IsomorphicGraphMapping
implements GraphMapping
{
GraphOrdering g1, g2;
int[] core1, core2;
/**
* Construct a new isomorphic graph mapping
*
* @param g1 the first graph
* @param g2 the second graph which is a possible subgraph of g1
* @param core1 the mapping as array (forwards)
* @param core2 the mapping as array (backwards)
*/
public IsomorphicGraphMapping(
GraphOrdering g1, GraphOrdering g2, int[] core1, int[] core2)
{
this.g1 = g1;
this.g2 = g2;
this.core1 = core1.clone();
this.core2 = core2.clone();
}
@Override
public V getVertexCorrespondence(V v, boolean forward)
{
GraphOrdering firstGraph, secondGraph;
int[] core;
if (forward) {
firstGraph = g1;
secondGraph = g2;
core = core1;
} else {
firstGraph = g2;
secondGraph = g1;
core = core2;
}
int vNumber = firstGraph.getVertexNumber(v), uNumber = core[vNumber];
if (uNumber == VF2State.NULL_NODE) {
return null;
}
return secondGraph.getVertex(uNumber);
}
@Override
public E getEdgeCorrespondence(E e, boolean forward)
{
GraphOrdering firstGraph, secondGraph;
int[] core;
if (forward) {
firstGraph = g1;
secondGraph = g2;
core = core1;
} else {
firstGraph = g2;
secondGraph = g1;
core = core2;
}
int[] eNumbers = firstGraph.getEdgeNumbers(e);
if ((core[eNumbers[0]] == VF2State.NULL_NODE)
|| (core[eNumbers[1]] == VF2State.NULL_NODE))
{
return null;
}
return secondGraph.getEdge(core[eNumbers[0]], core[eNumbers[1]]);
}
/**
* Checks if a vertex v from the first graph has a corresponding vertex in the second graph
*
* @param v the vertex
* @return is there a corresponding vertex to v in the subgraph
*/
public boolean hasVertexCorrespondence(V v)
{
return getVertexCorrespondence(v, true) != null;
}
/**
* Checks if a edge e from the first graph has a corresponding edge in the second graph
*
* @param e the edge
* @return is there a corresponding edge to e in the subgraph
*/
public boolean hasEdgeCorrespondence(E e)
{
return getEdgeCorrespondence(e, true) != null;
}
@Override
public String toString()
{
String str = "[";
Set vertexSet = g1.getGraph().vertexSet();
Map vertexMap = new TreeMap<>();
for (V v : vertexSet) {
vertexMap.put(v.toString(), v);
}
int i = 0;
for (Map.Entry entry : vertexMap.entrySet()) {
V u = getVertexCorrespondence(entry.getValue(), true);
str += ((i++ == 0) ? "" : " ") + entry.getKey() + "=" + ((u == null) ? "~~" : u);
}
return str + "]";
}
/**
* Checks for equality. Assuming both are mappings on the same graphs.
*
* @param rel the corresponding mapping
*
* @return do both relations map to the same vertices
*/
public boolean isEqualMapping(GraphMapping rel)
{
for (V v : g2.getGraph().vertexSet()) {
if (!getVertexCorrespondence(v, false).equals(rel.getVertexCorrespondence(v, false))) {
return false;
}
}
return true;
}
}
// End IsomorphicGraphMapping.java
Ads help maintain this website.