Gráfico dirigido el isomorfismo en Java -- java campo con algorithm campo con graph camp codereview Relacionados El problema

Directed graph isomorphism in Java


9
vote

problema

Español

Dados dos gráficos dirigidos por entrada $ G_1 = (v_1, A_1) $ y $ G_2 = (v_2, A_2) $, el problema de isomorfismo Pregunta si los dos gráficos dirigidos son isomorfos, o en otras palabras, si los dos gráficos de entrada tienen precisamente la misma estructura. Formalmente, dos gráficos de entrada $ g_1 $ y $ g_2 $ son isomorfos si y solo si existe una biyection $ f colon v_1 a v_2 $ tal que $ (F ​​(u), f (v )) en A_2 $ if y solo si $ (u, v) en A_1 $.

Claramente, si los dos gráficos de entrada tienen una cantidad diferente de nodos o bordes, no pueden ser isomórficos. De lo contrario, si ordenamos los nodos de ambos gráficos por sus títulos de entrada y salida y las secuencias no hacen mucho, los dos gráficos no pueden ser isomórficos. Si dos gráficos de entrada pasarán las pruebas mencionadas anteriormente, se utiliza una fuerza bruta para encontrar un posible isomorfismo. Esto sucede de la siguiente manera:

  1. dividir las listas de nodos de ambos gráficos de entrada en grupos . Un grupo es una lista de nodos con exactamente los mismos títulos de entrada.
  2. Permuta una vez los nodos en un solo grupo. Si produce un isomorfismo, devuélvalo. De lo contrario, permuta algún grupo una vez más.

ahora, vea lo que tengo:

abstractaphnode.java :

  package net.coderodde.graph;  import java.util.Objects; import java.util.Set;  /**  * This class defines the API for a graph node.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  * @param <N> the actual graph node implementation type.  */ public abstract class AbstractGraphNode<N extends AbstractGraphNode<N>> {      private final String name;     private Graph<N> ownerGraph;      public AbstractGraphNode(String name) {         Objects.requireNonNull(name, "The name of the node is null.");         this.name = name;     }      public String getName() {         return name;     }      public void setOwnerGraph(Graph<N> ownerGraph) {         if (this.getOwnerGraph() != null) {             clear();             this.getOwnerGraph().removeNode(this);         }          this.ownerGraph = ownerGraph;     }      public Graph<N> getOwnerGraph() {         return ownerGraph;     }      /**      * Makes {@code child} a child node of this node.      *       * @param child the child node.      */     public abstract void addChild(N child);      /**      * Tests whether {@code node} is a child node of this node.      *       * @param node the node to test.      * @return {@code true} only if {@code node} is the child node of this node.      */     public abstract boolean hasChild(N node);      /**      * Tests whether {@code node} is a parent node of this node.      *       * @param node the node to test.      * @return {@code true} only if {@code node} is the parent node of this       *         node.      */     public abstract boolean hasParent(N node);      /**      * Removes the child from this node.      *       * @param child the node to remove.      */     public abstract void removeChild(N child);      /**      * Returns a set of child nodes of this node.      *       * @return a set of nodes.      */     public abstract Set<N> children();      /**      * Returns a set of parent nodes of this node.      *       * @return a set of nodes.      */     public abstract Set<N> parents();      /**      * Disconnects this node from all its neighbors.      */     public abstract void clear();      /**      * {@inheritDoc }      */     @Override     public int hashCode() {         return name.hashCode();     }      /**      * {@inheritDoc }       */     @Override     public boolean equals(Object obj) {         if (obj == null) {             return false;         }          if (getClass() != obj.getClass()) {             return false;         }          AbstractGraphNode<N> other = (AbstractGraphNode<N>) obj;         return Objects.equals(name, other.name);     }      protected void checkNodeBelongsToGraph() {         if (this.getOwnerGraph() == null) {             throw new IllegalStateException(                     "The node does not belong to any graph.");         }     }      protected void addEdges(int edges) {         ownerGraph.addEdges(edges);     } }   

Directedgnode.java :

  package net.coderodde.graph.support;  import java.util.Collections; import java.util.LinkedHashSet; import java.util.Set; import net.coderodde.graph.AbstractGraphNode;  /**  * This class implements a directed graph node.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  */ public class DirectedGraphNode extends AbstractGraphNode<DirectedGraphNode> {      private final Set<DirectedGraphNode> children = new LinkedHashSet<>();     private final Set<DirectedGraphNode> parents  = new LinkedHashSet<>();      private final Set<DirectedGraphNode> childrenWrapper =              Collections.<DirectedGraphNode>unmodifiableSet(children);      private final Set<DirectedGraphNode> parentsWrapper =              Collections.<DirectedGraphNode>unmodifiableSet(parents);      /**      * Constructs a new directed graph node with given name.      *       * @param name the name of the node.      */     public DirectedGraphNode(String name) {         super(name);     }      @Override     public void addChild(DirectedGraphNode child) {         checkNodeBelongsToGraph();          if (child == null) {             return;         }          children.add(child);         child.parents.add(this);         addEdges(1);     }      @Override     public boolean hasChild(DirectedGraphNode node) {         return children.contains(node);     }      @Override     public boolean hasParent(DirectedGraphNode node) {         return parents.contains(node);     }      @Override     public void removeChild(DirectedGraphNode node) {         if (node == null) {             return;         }          if (node.getOwnerGraph() != this.getOwnerGraph()) {             return;         }          if (!children.contains(node)) {             return;         }          children.remove(node);         node.parents.remove(this);         addEdges(-1);     }      @Override     public Set<DirectedGraphNode> children() {         return childrenWrapper;     }      @Override     public Set<DirectedGraphNode> parents() {         return parentsWrapper;     }      @Override     public void clear() {         for (DirectedGraphNode child : children) {             child.parents.remove(this);         }          for (DirectedGraphNode parent : parents) {             parent.children.remove(this);         }          addEdges(-children.size());         addEdges(-parents.size());         children.clear();         parents.clear();     }      @Override     public String toString() {         return "[DirectedGraphNode "" + getName() + ""]";     } }   

gráfico.java :

  package net.coderodde.graph;  import java.util.Iterator; import java.util.LinkedHashMap; import java.util.Map; import java.util.Objects;  /**  * This class implements the graph data structure.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  * @param <N> the actual graph node implementation type.  */ public class Graph<N extends AbstractGraphNode<N>> implements Iterable<N> {      private final Map<String, N> nameMap = new LinkedHashMap<>();     private int numberOfEdges;      @Override     public Iterator<N> iterator() {         return nameMap.values().iterator();     }      public void addNode(N node) {         Objects.requireNonNull(node, "The input node is null.");          if (!nameMap.containsKey(node.getName())) {             node.setOwnerGraph(this);             nameMap.put(node.getName(), node);         }     }      public void removeNode(AbstractGraphNode<N> node) {         Objects.requireNonNull(node, "The input node is null.");         node.clear();         nameMap.remove(node.getName());     }      public N getNodeByName(String name) {         return nameMap.get(name);     }      public void clear() {         nameMap.clear();         numberOfEdges = 0;     }      public int size() {         return nameMap.size();     }      public int getNumberOfEdges() {         return numberOfEdges;     }      protected void addEdges(int edges) {         numberOfEdges += edges;     } }   

abstracthmaphisomorphismChecker.java :

  package net.coderodde.graph.isomorphism;  import java.util.Map; import net.coderodde.graph.AbstractGraphNode; import net.coderodde.graph.Graph;  /**  * This interface defines the API for checking whether two graphs are   * isomorphic, i.e., whether the two graphs have the same structure.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  * @param <N> the actual graph node implementation type..  */ public interface AbstractGraphIsomorphismChecker <N extends AbstractGraphNode<N>> {      /**      * Performs the isomorphism check and returns an isomorphism in case the two      * input graphs are isomorphic. If the input graphs are not isomorphic,      * {@code null} is returned.      *       * @param graph1 the first graph.      * @param graph2 the second graph.      * @return {@code true} only if the two input graphs are isomorphic.      */     public Map<N, N> getIsomorphism(Graph<N> graph1, Graph<N> graph2); }   

trivialdiredgraphenomorphismChecker.java :

  package net.coderodde.graph.isomorphism;  import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import net.coderodde.graph.Graph; import net.coderodde.graph.support.DirectedGraphNode;  /**  * This class implements a simple graph isomorphism tester for directed graphs.  *   * @author Rodion "rodde" Efremov  * @version 1.6   */ public class TrivialDirectedGraphIsomorphismChecker  implements AbstractGraphIsomorphismChecker<DirectedGraphNode>{      private final Comparator<DirectedGraphNode> permutationComparator =             new PermutationComparator();      /**      * {@inheritDoc }       */     @Override     public Map<DirectedGraphNode, DirectedGraphNode>         getIsomorphism(Graph<DirectedGraphNode> graph1,                         Graph<DirectedGraphNode> graph2) {         Objects.requireNonNull(graph1, "The first input graph is null.");         Objects.requireNonNull(graph2, "The second input graph is null.");          if (graph1.size() != graph2.size()) {             return null;         }          if (graph1.getNumberOfEdges() != graph2.getNumberOfEdges()) {             return null;         }          List<DirectedGraphNode> nodeList1 = graphToList(graph1);         List<DirectedGraphNode> nodeList2 = graphToList(graph2);          Comparator<DirectedGraphNode> comparator =                  new Comparator<DirectedGraphNode>() {                      @Override                     public int compare(DirectedGraphNode o1,                                         DirectedGraphNode o2) {                         int outDegree1 = o1.children().size();                         int outDegree2 = o2.children().size();                          if (outDegree1 != outDegree2) {                             return Integer.compare(outDegree1, outDegree2);                         }                          int inDegree1 = o1.parents().size();                         int inDegree2 = o2.parents().size();                         return Integer.compare(inDegree1, inDegree2);                     }                 };          Collections.sort(nodeList1, comparator);         Collections.sort(nodeList2, comparator);          for (int i = 0; i < nodeList1.size(); ++i) {             if (nodeList1.get(i).children().size() !=                      nodeList2.get(i).children().size()) {                 return null;             }              if (nodeList1.get(i).parents().size() !=                      nodeList2.get(i).parents().size()) {                 return null;             }         }          return bruteForceIsomorphism(nodeList1, nodeList2);     }      private static List<DirectedGraphNode>          graphToList(Graph<DirectedGraphNode> graph) {         List<DirectedGraphNode> ret = new ArrayList<>(graph.size());          for (DirectedGraphNode node : graph) {             ret.add(node);         }          return ret;     }      private static Map<DirectedGraphNode, DirectedGraphNode>                  bruteForceIsomorphism(List<DirectedGraphNode> nodeList1,                                        List<DirectedGraphNode> nodeList2) {         List<List<DirectedGraphNode>> list1 = new ArrayList<>();         List<List<DirectedGraphNode>> list2 = new ArrayList<>();          list1.add(new ArrayList<DirectedGraphNode>());         list1.get(0).add(nodeList1.get(0));          list2.add(new ArrayList<DirectedGraphNode>());         list2.get(0).add(nodeList2.get(0));          int previousInDegree = nodeList1.get(0).parents().size();         int previousOutDegree = nodeList2.get(0).children().size();          for (int i = 1; i < nodeList1.size(); ++i) {             DirectedGraphNode currentNode = nodeList1.get(i);             int currentInDegree = currentNode.parents().size();             int currentOutDegree = currentNode.children().size();              if (previousInDegree != currentInDegree                     || previousOutDegree != currentOutDegree) {                 List<DirectedGraphNode> newSubList1 = new ArrayList<>();                 List<DirectedGraphNode> newSubList2 = new ArrayList<>();                  newSubList1.add(currentNode);                 newSubList2.add(nodeList2.get(i));                  list1.add(newSubList1);                 list2.add(newSubList2);                  previousInDegree = currentInDegree;                 previousOutDegree = currentOutDegree;             } else {                 list1.get(list1.size() - 1).add(currentNode);                 list2.get(list2.size() - 1).add(nodeList2.get(i));             }         }          Map<DirectedGraphNode, DirectedGraphNode> certainMap = new HashMap<>();          for (int i = 0; i < list1.size(); ++i) {             List<DirectedGraphNode> currentSubList = list1.get(i);              if (currentSubList.size() == 1) {                 certainMap.put(currentSubList.get(0), list2.get(i).get(0));             }         }          List<List<DirectedGraphNode>> groupList1 = new ArrayList<>();         List<List<DirectedGraphNode>> groupList2 = new ArrayList<>();          for (int i = 0; i < list1.size(); ++i) {             if (list1.get(i).size() > 1) {                 groupList1.add(new ArrayList<>(list1.get(i)));                 groupList2.add(new ArrayList<>(list2.get(i)));             }         }          if (groupList1.isEmpty()) {             return Utils.isIsomorphism(certainMap) ? certainMap : null;         }          Map<DirectedGraphNode, DirectedGraphNode> isomorphism =                  findIsomorphismPermutation(groupList1,                                             groupList2,                                            new HashMap<>(certainMap));          return isomorphism;     }      private static Map<DirectedGraphNode, DirectedGraphNode>          findIsomorphismPermutation(List<List<DirectedGraphNode>> groupList1,                                    List<List<DirectedGraphNode>> groupList2,                                    Map<DirectedGraphNode,                                         DirectedGraphNode> certainMap) {         List<PermutationEnumerator> permutationEnumeratorList =                  new ArrayList<>(groupList1.size());          for (List<DirectedGraphNode> group : groupList1) {             permutationEnumeratorList                     .add(new PermutationEnumerator(group.size()));         }          do {             Map<DirectedGraphNode, DirectedGraphNode> candidate =                      generateIsomorphismCandidate(groupList1,                                                  groupList2,                                                  permutationEnumeratorList);              candidate.putAll(certainMap);              if (Utils.isIsomorphism(candidate)) {                 return candidate;             }         } while (incrementPermutationEnumeratorList(permutationEnumeratorList));          return null;     }      private static Map<DirectedGraphNode, DirectedGraphNode>             generateIsomorphismCandidate(                     List<List<DirectedGraphNode>> groupList1,                     List<List<DirectedGraphNode>> groupList2,                     List<PermutationEnumerator> permutationEnumeratorList) {         for (int groupIndex = 0; groupIndex < groupList2.size(); ++groupIndex) {             permute(groupList2.get(groupIndex),                     permutationEnumeratorList.get(groupIndex));         }          Map<DirectedGraphNode, DirectedGraphNode> isomorphismCandidate =                  new HashMap<>();          for (int groupIndex = 0; groupIndex < groupList1.size(); ++groupIndex) {             for (int nodeIndex = 0;                       nodeIndex < groupList1.get(groupIndex).size();                       nodeIndex++) {                 isomorphismCandidate                         .put(groupList1.get(groupIndex).get(nodeIndex),                              groupList2.get(groupIndex).get(nodeIndex));             }         }          return isomorphismCandidate;     }      private static void          permute(List<DirectedGraphNode> groupList,                 PermutationEnumerator permutationEnumeratorList) {         int[] indices = permutationEnumeratorList.indices;         List<DirectedGraphNode> tmp = new ArrayList<>(groupList);          for (int i = 0; i < groupList.size(); ++i) {             groupList.set(indices[i], tmp.get(i));         }     }       private static boolean          incrementPermutationEnumeratorList(List<PermutationEnumerator> list) {         for (int i = 0; i < list.size(); ++i) {             if (list.get(i).next() == null) {                 list.get(i).reset();             } else {                 return true;             }         }          return false;     }      private static final class PermutationComparator      implements Comparator<DirectedGraphNode> { ;         @Override         public int compare(DirectedGraphNode o1, DirectedGraphNode o2) {             throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.         }      }      private static final class PermutationEnumerator {          private final int[] indices;         private boolean initial;          PermutationEnumerator(int length) {             this.indices = new int[length];             reset();         }          void reset() {             initial = true;              for (int i = 0; i < indices.length; ++i) {                 indices[i] = i;             }         }          int[] next() {             if (initial) {                 initial = false;                 return indices;             }              int i = indices.length - 2;              while (i >= 0 && indices[i] > indices[i + 1]) {                 --i;             }              if (i == -1) {                 return null;             }              int j = i + 1;             int minValue = indices[j];             int minIndex = j;              while (j < indices.length) {                 if (indices[i] < indices[j] && indices[j] < minValue) {                     minValue = indices[j];                     minIndex = j;                 }                  ++j;             }              int tmp = indices[i];             indices[i] = indices[minIndex];             indices[minIndex] = tmp;              ++i;             j = indices.length - 1;              while (i < j) {                 tmp = indices[i];                 indices[i] = indices[j];                 indices[j] = tmp;                  ++i;                 --j;             }              return indices;         }     } }   

utils.java :

  package net.coderodde.graph.isomorphism;  import java.util.Map; import net.coderodde.graph.support.DirectedGraphNode;  /**  * This class provides some utility methods for working with graph isomorphisms.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  */ public class Utils {      /**      * This method tests that the input mapping is a graph isomorphism.      *       * @param candidate the candidate isomorphism.      * @return {@code true} only if the input map is a graph isomorphism.      */     public static boolean          isIsomorphism(Map<DirectedGraphNode, DirectedGraphNode> candidate) {         for (Map.Entry<DirectedGraphNode,                         DirectedGraphNode> mapping : candidate.entrySet()) {             if (mapping.getKey().children().size() !=                      mapping.getValue().children().size()) {                 return false;             }              if (mapping.getKey().parents().size() !=                      mapping.getValue().parents().size()) {                 return false;             }              for (DirectedGraphNode child : mapping.getKey().children()) {                 if (!candidate.get(child)                               .hasParent(candidate.get(mapping.getKey()))) {                     return false;                 }             }         }          return true;     } }   

grafttest.java :

  package net.coderodde.graph;  import java.util.Iterator; import net.coderodde.graph.support.DirectedGraphNode; import org.junit.Test; import static org.junit.Assert.*; import org.junit.Before;  public class GraphTest {      private final Graph<DirectedGraphNode> graph = new Graph<>();     private final DirectedGraphNode a = new DirectedGraphNode("A");     private final DirectedGraphNode b = new DirectedGraphNode("B");     private final DirectedGraphNode c = new DirectedGraphNode("C");     private final DirectedGraphNode d = new DirectedGraphNode("D");     private final DirectedGraphNode e = new DirectedGraphNode("E");      @Before     public void before() {         graph.clear();     }      @Test     public void test() {         graph.addNode(a);         graph.addNode(e);         graph.addNode(d);          assertEquals(3, graph.size());          Iterator<DirectedGraphNode> iterator = graph.iterator();          assertEquals(a, iterator.next());         assertEquals(e, iterator.next());         assertEquals(d, iterator.next());         assertFalse(iterator.hasNext());          assertTrue(graph.getNodeByName("A").equals(a));         assertTrue(graph.getNodeByName("E").equals(e));         assertTrue(graph.getNodeByName("D").equals(d));         assertTrue(graph.getNodeByName("B") == null);          a.addChild(e);         e.addChild(d);         d.addChild(e);          assertEquals(3, graph.getNumberOfEdges());          Graph<DirectedGraphNode> anotherGraph = new Graph<>();          anotherGraph.addNode(a);          assertEquals(1, anotherGraph.size());         assertEquals(0, anotherGraph.getNumberOfEdges());          assertEquals(anotherGraph, a.getOwnerGraph());         assertEquals(graph, d.getOwnerGraph());         assertEquals(graph, e.getOwnerGraph());          assertEquals(2, graph.size());         assertEquals(2, graph.getNumberOfEdges());          graph.removeNode(e);         d.addChild(d);          assertEquals(1, graph.size());         assertEquals(1, graph.getNumberOfEdges());          assertEquals(d, graph.getNodeByName("D"));     }     }   

trivialdiredGraphisomorphismTest.Java :

  package net.coderodde.graph.isomorphism;  import java.util.Map; import net.coderodde.graph.Graph; import net.coderodde.graph.support.DirectedGraphNode; import org.junit.Test; import static org.junit.Assert.*; import org.junit.Before;  public class TrivialDirectedGraphIsomorphismTesterTest {      private final DirectedGraphNode a1 = new DirectedGraphNode("A1");     private final DirectedGraphNode b1 = new DirectedGraphNode("B1");     private final DirectedGraphNode c1 = new DirectedGraphNode("C1");     private final DirectedGraphNode d1 = new DirectedGraphNode("D1");     private final DirectedGraphNode e1 = new DirectedGraphNode("E1");     private final DirectedGraphNode f1 = new DirectedGraphNode("F1");     private final DirectedGraphNode g1 = new DirectedGraphNode("G1");     private final DirectedGraphNode h1 = new DirectedGraphNode("H1");      private final DirectedGraphNode a2 = new DirectedGraphNode("A2");     private final DirectedGraphNode b2 = new DirectedGraphNode("B2");     private final DirectedGraphNode c2 = new DirectedGraphNode("C2");     private final DirectedGraphNode d2 = new DirectedGraphNode("D2");     private final DirectedGraphNode e2 = new DirectedGraphNode("E2");     private final DirectedGraphNode f2 = new DirectedGraphNode("F2");     private final DirectedGraphNode g2 = new DirectedGraphNode("G2");     private final DirectedGraphNode h2 = new DirectedGraphNode("H2");      private final Graph<DirectedGraphNode> graph1 = new Graph<>();     private final Graph<DirectedGraphNode> graph2 = new Graph<>();      private final AbstractGraphIsomorphismChecker<DirectedGraphNode>             checker = new TrivialDirectedGraphIsomorphismChecker();      @Before     public void before() {         graph1.clear();         graph2.clear();     }      @Test     public void testGetIsomorphism1() {         graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);          graph2.addNode(a2);         graph2.addNode(b2);          a1.addChild(c1);         a2.addChild(c2);          assertNull(checker.getIsomorphism(graph1, graph2));     }      @Test     public void testGetIsomorphism2() {         graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);          graph2.addNode(a2);         graph2.addNode(b2);         graph2.addNode(e2);          a1.addChild(b1);         a2.addChild(e2);          Map<DirectedGraphNode, DirectedGraphNode> isomorphism =                  checker.getIsomorphism(graph1, graph2);          assertNotNull(isomorphism);         assertTrue(Utils.isIsomorphism(isomorphism));     }      @Test     public void testGetIsomorphism3() {         graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);          graph2.addNode(a2);         graph2.addNode(b2);         graph2.addNode(e2);          a1.addChild(b1);         b1.addChild(c1);         a2.addChild(e2);          assertNull(checker.getIsomorphism(graph1, graph2));     }      @Test     public void testGetIsomorphism4() {         //       c - e         //      /   /          // a - b    |  g - h         //        /  /         //       d - f         // Directed edges from nodes with smaller lexicographic name to larger.          graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);         graph1.addNode(d1);         graph1.addNode(e1);         graph1.addNode(f1);         graph1.addNode(g1);         graph1.addNode(h1);          a1.addChild(b1);         b1.addChild(c1);         b1.addChild(d1);         c1.addChild(e1);         d1.addChild(f1);         d1.addChild(e1);         e1.addChild(g1);         f1.addChild(g1);         g1.addChild(h1);          graph2.addNode(h2);         graph2.addNode(b2);         graph2.addNode(c2);         graph2.addNode(d2);         graph2.addNode(e2);         graph2.addNode(f2);         graph2.addNode(g2);         graph2.addNode(a2);          h2.addChild(b2);         b2.addChild(c2);         b2.addChild(d2);         c2.addChild(e2);         d2.addChild(f2);         d2.addChild(e2);         e2.addChild(g2);         f2.addChild(g2);         g2.addChild(a2);          Map<DirectedGraphNode, DirectedGraphNode> isomorphism =                  checker.getIsomorphism(graph1, graph2);          assertNotNull(isomorphism);         assertTrue(Utils.isIsomorphism(isomorphism));     } }   
Original en ingles

Given two input directed graphs \$G_1 = (V_1, A_1)\$ and \$G_2 = (V_2, A_2)\$, the problem of isomorphism asks whether the two directed graphs are isomorphic, or in other words, whether the two input graphs have precisely the same structure. Formally, two input graphs \$G_1\$ and \$G_2\$ are isomorphic if and only if there exists a bijection \$f \colon V_1 \to V_2\$ such that \$(f(u), f(v)) \in A_2\$ if and only if \$(u, v) \in A_1\$.

Clearly, if the two input graphs have different amount of nodes or edges, they cannot be isomorphic. Otherwise, if we sort the nodes of both the graphs by their in-/out-degrees and the sequences do not much, the two graphs cannot be isomorphic. If two input graphs will pass the aforementioned tests, a brute force is used in order to find a possible isomorphism. This happens as follows:

  1. Split the node lists of both the input graphs into groups. A group is a list of nodes with exactly the same in-/out-degrees.
  2. Permute once the nodes in one single group. If it produces an isomorphism, return it. Otherwise, permute some group one more time.

Now, see what I have:

AbstractGraphNode.java:

package net.coderodde.graph;  import java.util.Objects; import java.util.Set;  /**  * This class defines the API for a graph node.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  * @param <N> the actual graph node implementation type.  */ public abstract class AbstractGraphNode<N extends AbstractGraphNode<N>> {      private final String name;     private Graph<N> ownerGraph;      public AbstractGraphNode(String name) {         Objects.requireNonNull(name, "The name of the node is null.");         this.name = name;     }      public String getName() {         return name;     }      public void setOwnerGraph(Graph<N> ownerGraph) {         if (this.getOwnerGraph() != null) {             clear();             this.getOwnerGraph().removeNode(this);         }          this.ownerGraph = ownerGraph;     }      public Graph<N> getOwnerGraph() {         return ownerGraph;     }      /**      * Makes {@code child} a child node of this node.      *       * @param child the child node.      */     public abstract void addChild(N child);      /**      * Tests whether {@code node} is a child node of this node.      *       * @param node the node to test.      * @return {@code true} only if {@code node} is the child node of this node.      */     public abstract boolean hasChild(N node);      /**      * Tests whether {@code node} is a parent node of this node.      *       * @param node the node to test.      * @return {@code true} only if {@code node} is the parent node of this       *         node.      */     public abstract boolean hasParent(N node);      /**      * Removes the child from this node.      *       * @param child the node to remove.      */     public abstract void removeChild(N child);      /**      * Returns a set of child nodes of this node.      *       * @return a set of nodes.      */     public abstract Set<N> children();      /**      * Returns a set of parent nodes of this node.      *       * @return a set of nodes.      */     public abstract Set<N> parents();      /**      * Disconnects this node from all its neighbors.      */     public abstract void clear();      /**      * {@inheritDoc }      */     @Override     public int hashCode() {         return name.hashCode();     }      /**      * {@inheritDoc }       */     @Override     public boolean equals(Object obj) {         if (obj == null) {             return false;         }          if (getClass() != obj.getClass()) {             return false;         }          AbstractGraphNode<N> other = (AbstractGraphNode<N>) obj;         return Objects.equals(name, other.name);     }      protected void checkNodeBelongsToGraph() {         if (this.getOwnerGraph() == null) {             throw new IllegalStateException(                     "The node does not belong to any graph.");         }     }      protected void addEdges(int edges) {         ownerGraph.addEdges(edges);     } } 

DirectedGraphNode.java:

package net.coderodde.graph.support;  import java.util.Collections; import java.util.LinkedHashSet; import java.util.Set; import net.coderodde.graph.AbstractGraphNode;  /**  * This class implements a directed graph node.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  */ public class DirectedGraphNode extends AbstractGraphNode<DirectedGraphNode> {      private final Set<DirectedGraphNode> children = new LinkedHashSet<>();     private final Set<DirectedGraphNode> parents  = new LinkedHashSet<>();      private final Set<DirectedGraphNode> childrenWrapper =              Collections.<DirectedGraphNode>unmodifiableSet(children);      private final Set<DirectedGraphNode> parentsWrapper =              Collections.<DirectedGraphNode>unmodifiableSet(parents);      /**      * Constructs a new directed graph node with given name.      *       * @param name the name of the node.      */     public DirectedGraphNode(String name) {         super(name);     }      @Override     public void addChild(DirectedGraphNode child) {         checkNodeBelongsToGraph();          if (child == null) {             return;         }          children.add(child);         child.parents.add(this);         addEdges(1);     }      @Override     public boolean hasChild(DirectedGraphNode node) {         return children.contains(node);     }      @Override     public boolean hasParent(DirectedGraphNode node) {         return parents.contains(node);     }      @Override     public void removeChild(DirectedGraphNode node) {         if (node == null) {             return;         }          if (node.getOwnerGraph() != this.getOwnerGraph()) {             return;         }          if (!children.contains(node)) {             return;         }          children.remove(node);         node.parents.remove(this);         addEdges(-1);     }      @Override     public Set<DirectedGraphNode> children() {         return childrenWrapper;     }      @Override     public Set<DirectedGraphNode> parents() {         return parentsWrapper;     }      @Override     public void clear() {         for (DirectedGraphNode child : children) {             child.parents.remove(this);         }          for (DirectedGraphNode parent : parents) {             parent.children.remove(this);         }          addEdges(-children.size());         addEdges(-parents.size());         children.clear();         parents.clear();     }      @Override     public String toString() {         return "[DirectedGraphNode \"" + getName() + "\"]";     } } 

Graph.java:

package net.coderodde.graph;  import java.util.Iterator; import java.util.LinkedHashMap; import java.util.Map; import java.util.Objects;  /**  * This class implements the graph data structure.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  * @param <N> the actual graph node implementation type.  */ public class Graph<N extends AbstractGraphNode<N>> implements Iterable<N> {      private final Map<String, N> nameMap = new LinkedHashMap<>();     private int numberOfEdges;      @Override     public Iterator<N> iterator() {         return nameMap.values().iterator();     }      public void addNode(N node) {         Objects.requireNonNull(node, "The input node is null.");          if (!nameMap.containsKey(node.getName())) {             node.setOwnerGraph(this);             nameMap.put(node.getName(), node);         }     }      public void removeNode(AbstractGraphNode<N> node) {         Objects.requireNonNull(node, "The input node is null.");         node.clear();         nameMap.remove(node.getName());     }      public N getNodeByName(String name) {         return nameMap.get(name);     }      public void clear() {         nameMap.clear();         numberOfEdges = 0;     }      public int size() {         return nameMap.size();     }      public int getNumberOfEdges() {         return numberOfEdges;     }      protected void addEdges(int edges) {         numberOfEdges += edges;     } } 

AbstractGraphIsomorphismChecker.java:

package net.coderodde.graph.isomorphism;  import java.util.Map; import net.coderodde.graph.AbstractGraphNode; import net.coderodde.graph.Graph;  /**  * This interface defines the API for checking whether two graphs are   * isomorphic, i.e., whether the two graphs have the same structure.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  * @param <N> the actual graph node implementation type..  */ public interface AbstractGraphIsomorphismChecker <N extends AbstractGraphNode<N>> {      /**      * Performs the isomorphism check and returns an isomorphism in case the two      * input graphs are isomorphic. If the input graphs are not isomorphic,      * {@code null} is returned.      *       * @param graph1 the first graph.      * @param graph2 the second graph.      * @return {@code true} only if the two input graphs are isomorphic.      */     public Map<N, N> getIsomorphism(Graph<N> graph1, Graph<N> graph2); } 

TrivialDirectedGraphIsomorphismChecker.java:

package net.coderodde.graph.isomorphism;  import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.Objects; import net.coderodde.graph.Graph; import net.coderodde.graph.support.DirectedGraphNode;  /**  * This class implements a simple graph isomorphism tester for directed graphs.  *   * @author Rodion "rodde" Efremov  * @version 1.6   */ public class TrivialDirectedGraphIsomorphismChecker  implements AbstractGraphIsomorphismChecker<DirectedGraphNode>{      private final Comparator<DirectedGraphNode> permutationComparator =             new PermutationComparator();      /**      * {@inheritDoc }       */     @Override     public Map<DirectedGraphNode, DirectedGraphNode>         getIsomorphism(Graph<DirectedGraphNode> graph1,                         Graph<DirectedGraphNode> graph2) {         Objects.requireNonNull(graph1, "The first input graph is null.");         Objects.requireNonNull(graph2, "The second input graph is null.");          if (graph1.size() != graph2.size()) {             return null;         }          if (graph1.getNumberOfEdges() != graph2.getNumberOfEdges()) {             return null;         }          List<DirectedGraphNode> nodeList1 = graphToList(graph1);         List<DirectedGraphNode> nodeList2 = graphToList(graph2);          Comparator<DirectedGraphNode> comparator =                  new Comparator<DirectedGraphNode>() {                      @Override                     public int compare(DirectedGraphNode o1,                                         DirectedGraphNode o2) {                         int outDegree1 = o1.children().size();                         int outDegree2 = o2.children().size();                          if (outDegree1 != outDegree2) {                             return Integer.compare(outDegree1, outDegree2);                         }                          int inDegree1 = o1.parents().size();                         int inDegree2 = o2.parents().size();                         return Integer.compare(inDegree1, inDegree2);                     }                 };          Collections.sort(nodeList1, comparator);         Collections.sort(nodeList2, comparator);          for (int i = 0; i < nodeList1.size(); ++i) {             if (nodeList1.get(i).children().size() !=                      nodeList2.get(i).children().size()) {                 return null;             }              if (nodeList1.get(i).parents().size() !=                      nodeList2.get(i).parents().size()) {                 return null;             }         }          return bruteForceIsomorphism(nodeList1, nodeList2);     }      private static List<DirectedGraphNode>          graphToList(Graph<DirectedGraphNode> graph) {         List<DirectedGraphNode> ret = new ArrayList<>(graph.size());          for (DirectedGraphNode node : graph) {             ret.add(node);         }          return ret;     }      private static Map<DirectedGraphNode, DirectedGraphNode>                  bruteForceIsomorphism(List<DirectedGraphNode> nodeList1,                                        List<DirectedGraphNode> nodeList2) {         List<List<DirectedGraphNode>> list1 = new ArrayList<>();         List<List<DirectedGraphNode>> list2 = new ArrayList<>();          list1.add(new ArrayList<DirectedGraphNode>());         list1.get(0).add(nodeList1.get(0));          list2.add(new ArrayList<DirectedGraphNode>());         list2.get(0).add(nodeList2.get(0));          int previousInDegree = nodeList1.get(0).parents().size();         int previousOutDegree = nodeList2.get(0).children().size();          for (int i = 1; i < nodeList1.size(); ++i) {             DirectedGraphNode currentNode = nodeList1.get(i);             int currentInDegree = currentNode.parents().size();             int currentOutDegree = currentNode.children().size();              if (previousInDegree != currentInDegree                     || previousOutDegree != currentOutDegree) {                 List<DirectedGraphNode> newSubList1 = new ArrayList<>();                 List<DirectedGraphNode> newSubList2 = new ArrayList<>();                  newSubList1.add(currentNode);                 newSubList2.add(nodeList2.get(i));                  list1.add(newSubList1);                 list2.add(newSubList2);                  previousInDegree = currentInDegree;                 previousOutDegree = currentOutDegree;             } else {                 list1.get(list1.size() - 1).add(currentNode);                 list2.get(list2.size() - 1).add(nodeList2.get(i));             }         }          Map<DirectedGraphNode, DirectedGraphNode> certainMap = new HashMap<>();          for (int i = 0; i < list1.size(); ++i) {             List<DirectedGraphNode> currentSubList = list1.get(i);              if (currentSubList.size() == 1) {                 certainMap.put(currentSubList.get(0), list2.get(i).get(0));             }         }          List<List<DirectedGraphNode>> groupList1 = new ArrayList<>();         List<List<DirectedGraphNode>> groupList2 = new ArrayList<>();          for (int i = 0; i < list1.size(); ++i) {             if (list1.get(i).size() > 1) {                 groupList1.add(new ArrayList<>(list1.get(i)));                 groupList2.add(new ArrayList<>(list2.get(i)));             }         }          if (groupList1.isEmpty()) {             return Utils.isIsomorphism(certainMap) ? certainMap : null;         }          Map<DirectedGraphNode, DirectedGraphNode> isomorphism =                  findIsomorphismPermutation(groupList1,                                             groupList2,                                            new HashMap<>(certainMap));          return isomorphism;     }      private static Map<DirectedGraphNode, DirectedGraphNode>          findIsomorphismPermutation(List<List<DirectedGraphNode>> groupList1,                                    List<List<DirectedGraphNode>> groupList2,                                    Map<DirectedGraphNode,                                         DirectedGraphNode> certainMap) {         List<PermutationEnumerator> permutationEnumeratorList =                  new ArrayList<>(groupList1.size());          for (List<DirectedGraphNode> group : groupList1) {             permutationEnumeratorList                     .add(new PermutationEnumerator(group.size()));         }          do {             Map<DirectedGraphNode, DirectedGraphNode> candidate =                      generateIsomorphismCandidate(groupList1,                                                  groupList2,                                                  permutationEnumeratorList);              candidate.putAll(certainMap);              if (Utils.isIsomorphism(candidate)) {                 return candidate;             }         } while (incrementPermutationEnumeratorList(permutationEnumeratorList));          return null;     }      private static Map<DirectedGraphNode, DirectedGraphNode>             generateIsomorphismCandidate(                     List<List<DirectedGraphNode>> groupList1,                     List<List<DirectedGraphNode>> groupList2,                     List<PermutationEnumerator> permutationEnumeratorList) {         for (int groupIndex = 0; groupIndex < groupList2.size(); ++groupIndex) {             permute(groupList2.get(groupIndex),                     permutationEnumeratorList.get(groupIndex));         }          Map<DirectedGraphNode, DirectedGraphNode> isomorphismCandidate =                  new HashMap<>();          for (int groupIndex = 0; groupIndex < groupList1.size(); ++groupIndex) {             for (int nodeIndex = 0;                       nodeIndex < groupList1.get(groupIndex).size();                       nodeIndex++) {                 isomorphismCandidate                         .put(groupList1.get(groupIndex).get(nodeIndex),                              groupList2.get(groupIndex).get(nodeIndex));             }         }          return isomorphismCandidate;     }      private static void          permute(List<DirectedGraphNode> groupList,                 PermutationEnumerator permutationEnumeratorList) {         int[] indices = permutationEnumeratorList.indices;         List<DirectedGraphNode> tmp = new ArrayList<>(groupList);          for (int i = 0; i < groupList.size(); ++i) {             groupList.set(indices[i], tmp.get(i));         }     }       private static boolean          incrementPermutationEnumeratorList(List<PermutationEnumerator> list) {         for (int i = 0; i < list.size(); ++i) {             if (list.get(i).next() == null) {                 list.get(i).reset();             } else {                 return true;             }         }          return false;     }      private static final class PermutationComparator      implements Comparator<DirectedGraphNode> { ;         @Override         public int compare(DirectedGraphNode o1, DirectedGraphNode o2) {             throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.         }      }      private static final class PermutationEnumerator {          private final int[] indices;         private boolean initial;          PermutationEnumerator(int length) {             this.indices = new int[length];             reset();         }          void reset() {             initial = true;              for (int i = 0; i < indices.length; ++i) {                 indices[i] = i;             }         }          int[] next() {             if (initial) {                 initial = false;                 return indices;             }              int i = indices.length - 2;              while (i >= 0 && indices[i] > indices[i + 1]) {                 --i;             }              if (i == -1) {                 return null;             }              int j = i + 1;             int minValue = indices[j];             int minIndex = j;              while (j < indices.length) {                 if (indices[i] < indices[j] && indices[j] < minValue) {                     minValue = indices[j];                     minIndex = j;                 }                  ++j;             }              int tmp = indices[i];             indices[i] = indices[minIndex];             indices[minIndex] = tmp;              ++i;             j = indices.length - 1;              while (i < j) {                 tmp = indices[i];                 indices[i] = indices[j];                 indices[j] = tmp;                  ++i;                 --j;             }              return indices;         }     } } 

Utils.java:

package net.coderodde.graph.isomorphism;  import java.util.Map; import net.coderodde.graph.support.DirectedGraphNode;  /**  * This class provides some utility methods for working with graph isomorphisms.  *   * @author Rodion "rodde" Efremov  * @version 1.6 (Oct 11, 2015)  */ public class Utils {      /**      * This method tests that the input mapping is a graph isomorphism.      *       * @param candidate the candidate isomorphism.      * @return {@code true} only if the input map is a graph isomorphism.      */     public static boolean          isIsomorphism(Map<DirectedGraphNode, DirectedGraphNode> candidate) {         for (Map.Entry<DirectedGraphNode,                         DirectedGraphNode> mapping : candidate.entrySet()) {             if (mapping.getKey().children().size() !=                      mapping.getValue().children().size()) {                 return false;             }              if (mapping.getKey().parents().size() !=                      mapping.getValue().parents().size()) {                 return false;             }              for (DirectedGraphNode child : mapping.getKey().children()) {                 if (!candidate.get(child)                               .hasParent(candidate.get(mapping.getKey()))) {                     return false;                 }             }         }          return true;     } } 

GraphTest.java:

package net.coderodde.graph;  import java.util.Iterator; import net.coderodde.graph.support.DirectedGraphNode; import org.junit.Test; import static org.junit.Assert.*; import org.junit.Before;  public class GraphTest {      private final Graph<DirectedGraphNode> graph = new Graph<>();     private final DirectedGraphNode a = new DirectedGraphNode("A");     private final DirectedGraphNode b = new DirectedGraphNode("B");     private final DirectedGraphNode c = new DirectedGraphNode("C");     private final DirectedGraphNode d = new DirectedGraphNode("D");     private final DirectedGraphNode e = new DirectedGraphNode("E");      @Before     public void before() {         graph.clear();     }      @Test     public void test() {         graph.addNode(a);         graph.addNode(e);         graph.addNode(d);          assertEquals(3, graph.size());          Iterator<DirectedGraphNode> iterator = graph.iterator();          assertEquals(a, iterator.next());         assertEquals(e, iterator.next());         assertEquals(d, iterator.next());         assertFalse(iterator.hasNext());          assertTrue(graph.getNodeByName("A").equals(a));         assertTrue(graph.getNodeByName("E").equals(e));         assertTrue(graph.getNodeByName("D").equals(d));         assertTrue(graph.getNodeByName("B") == null);          a.addChild(e);         e.addChild(d);         d.addChild(e);          assertEquals(3, graph.getNumberOfEdges());          Graph<DirectedGraphNode> anotherGraph = new Graph<>();          anotherGraph.addNode(a);          assertEquals(1, anotherGraph.size());         assertEquals(0, anotherGraph.getNumberOfEdges());          assertEquals(anotherGraph, a.getOwnerGraph());         assertEquals(graph, d.getOwnerGraph());         assertEquals(graph, e.getOwnerGraph());          assertEquals(2, graph.size());         assertEquals(2, graph.getNumberOfEdges());          graph.removeNode(e);         d.addChild(d);          assertEquals(1, graph.size());         assertEquals(1, graph.getNumberOfEdges());          assertEquals(d, graph.getNodeByName("D"));     }     } 

TrivialDirectedGraphIsomorphismTesterTest.java:

package net.coderodde.graph.isomorphism;  import java.util.Map; import net.coderodde.graph.Graph; import net.coderodde.graph.support.DirectedGraphNode; import org.junit.Test; import static org.junit.Assert.*; import org.junit.Before;  public class TrivialDirectedGraphIsomorphismTesterTest {      private final DirectedGraphNode a1 = new DirectedGraphNode("A1");     private final DirectedGraphNode b1 = new DirectedGraphNode("B1");     private final DirectedGraphNode c1 = new DirectedGraphNode("C1");     private final DirectedGraphNode d1 = new DirectedGraphNode("D1");     private final DirectedGraphNode e1 = new DirectedGraphNode("E1");     private final DirectedGraphNode f1 = new DirectedGraphNode("F1");     private final DirectedGraphNode g1 = new DirectedGraphNode("G1");     private final DirectedGraphNode h1 = new DirectedGraphNode("H1");      private final DirectedGraphNode a2 = new DirectedGraphNode("A2");     private final DirectedGraphNode b2 = new DirectedGraphNode("B2");     private final DirectedGraphNode c2 = new DirectedGraphNode("C2");     private final DirectedGraphNode d2 = new DirectedGraphNode("D2");     private final DirectedGraphNode e2 = new DirectedGraphNode("E2");     private final DirectedGraphNode f2 = new DirectedGraphNode("F2");     private final DirectedGraphNode g2 = new DirectedGraphNode("G2");     private final DirectedGraphNode h2 = new DirectedGraphNode("H2");      private final Graph<DirectedGraphNode> graph1 = new Graph<>();     private final Graph<DirectedGraphNode> graph2 = new Graph<>();      private final AbstractGraphIsomorphismChecker<DirectedGraphNode>             checker = new TrivialDirectedGraphIsomorphismChecker();      @Before     public void before() {         graph1.clear();         graph2.clear();     }      @Test     public void testGetIsomorphism1() {         graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);          graph2.addNode(a2);         graph2.addNode(b2);          a1.addChild(c1);         a2.addChild(c2);          assertNull(checker.getIsomorphism(graph1, graph2));     }      @Test     public void testGetIsomorphism2() {         graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);          graph2.addNode(a2);         graph2.addNode(b2);         graph2.addNode(e2);          a1.addChild(b1);         a2.addChild(e2);          Map<DirectedGraphNode, DirectedGraphNode> isomorphism =                  checker.getIsomorphism(graph1, graph2);          assertNotNull(isomorphism);         assertTrue(Utils.isIsomorphism(isomorphism));     }      @Test     public void testGetIsomorphism3() {         graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);          graph2.addNode(a2);         graph2.addNode(b2);         graph2.addNode(e2);          a1.addChild(b1);         b1.addChild(c1);         a2.addChild(e2);          assertNull(checker.getIsomorphism(graph1, graph2));     }      @Test     public void testGetIsomorphism4() {         //       c - e         //      /   / \         // a - b    |  g - h         //      \  /  /         //       d - f         // Directed edges from nodes with smaller lexicographic name to larger.          graph1.addNode(a1);         graph1.addNode(b1);         graph1.addNode(c1);         graph1.addNode(d1);         graph1.addNode(e1);         graph1.addNode(f1);         graph1.addNode(g1);         graph1.addNode(h1);          a1.addChild(b1);         b1.addChild(c1);         b1.addChild(d1);         c1.addChild(e1);         d1.addChild(f1);         d1.addChild(e1);         e1.addChild(g1);         f1.addChild(g1);         g1.addChild(h1);          graph2.addNode(h2);         graph2.addNode(b2);         graph2.addNode(c2);         graph2.addNode(d2);         graph2.addNode(e2);         graph2.addNode(f2);         graph2.addNode(g2);         graph2.addNode(a2);          h2.addChild(b2);         b2.addChild(c2);         b2.addChild(d2);         c2.addChild(e2);         d2.addChild(f2);         d2.addChild(e2);         e2.addChild(g2);         f2.addChild(g2);         g2.addChild(a2);          Map<DirectedGraphNode, DirectedGraphNode> isomorphism =                  checker.getIsomorphism(graph1, graph2);          assertNotNull(isomorphism);         assertTrue(Utils.isIsomorphism(isomorphism));     } } 
        

Lista de respuestas

2
 
vote

Sugerencias basadas en Java

  • En getIsomorphism , el comparador que define puede ser un campo final estático. Adicionalmente se puede simplificar para solo:

      Comparator<DirectedGraphNode> comparator = Comparator.comparing(n -> n.children().size())       .thenComparing(n -> n.parents().size());   

    Si está exponiendo inDegree y node *newNode(int data, int node_id) { node *new_node = (node *) malloc(sizeof(node)); // Its quite possible for malloc to fail so you need to check // and only assign if the malloc worked (otherwise segfault probably). if (new_node) { new_node->data = data; new_node->node_id = node_id; new_node->right = new_node->left = NULL; } return new_node; } 0 Puede colocar node *newNode(int data, int node_id) { node *new_node = (node *) malloc(sizeof(node)); // Its quite possible for malloc to fail so you need to check // and only assign if the malloc worked (otherwise segfault probably). if (new_node) { new_node->data = data; new_node->node_id = node_id; new_node->right = new_node->left = NULL; } return new_node; } 1 y node *newNode(int data, int node_id) { node *new_node = (node *) malloc(sizeof(node)); // Its quite possible for malloc to fail so you need to check // and only assign if the malloc worked (otherwise segfault probably). if (new_node) { new_node->data = data; new_node->node_id = node_id; new_node->right = new_node->left = NULL; } return new_node; } 2 como las funciones del extractor de teclas en su lugar.

  • Justo debajo de que está iterando sobre una colección de nodos ordenados, comparando nuevamente su 99887766655443313 y node *newNode(int data, int node_id) { node *new_node = (node *) malloc(sizeof(node)); // Its quite possible for malloc to fail so you need to check // and only assign if the malloc worked (otherwise segfault probably). if (new_node) { new_node->data = data; new_node->node_id = node_id; new_node->right = new_node->left = NULL; } return new_node; } 4 . Si Java fuera un lenguaje más funcional, esto podría expresarse mejor como lo siguiente:

      node *newNode(int data, int node_id) {     node *new_node = (node *) malloc(sizeof(node));      // Its quite possible for malloc to fail so you need to check     // and only assign if the malloc worked (otherwise segfault probably).     if (new_node)     {         new_node->data = data;         new_node->node_id = node_id;         new_node->right = new_node->left = NULL;     }     return new_node; } 5  

    Qué sucede aquí es esencialmente que los elementos ordenados se asocian juntos en una tupla, el comparador los compara y el 998877766555443316 verifica que todos los elementos sean iguales de acuerdo con el comparador.
    No estoy seguro de por qué no estás reutilizando el comparador aquí. Eso simplificaría el código a:

      node *newNode(int data, int node_id) {     node *new_node = (node *) malloc(sizeof(node));      // Its quite possible for malloc to fail so you need to check     // and only assign if the malloc worked (otherwise segfault probably).     if (new_node)     {         new_node->data = data;         new_node->node_id = node_id;         new_node->right = new_node->left = NULL;     }     return new_node; } 7  
  • node *newNode(int data, int node_id) { node *new_node = (node *) malloc(sizeof(node)); // Its quite possible for malloc to fail so you need to check // and only assign if the malloc worked (otherwise segfault probably). if (new_node) { new_node->data = data; new_node->node_id = node_id; new_node->right = new_node->left = NULL; } return new_node; } 8 podría escribirse un poco más sucintamente como:

      node *newNode(int data, int node_id) {     node *new_node = (node *) malloc(sizeof(node));      // Its quite possible for malloc to fail so you need to check     // and only assign if the malloc worked (otherwise segfault probably).     if (new_node)     {         new_node->data = data;         new_node->node_id = node_id;         new_node->right = new_node->left = NULL;     }     return new_node; } 9  
  • En cur0 podría buscar si el llenado de cur1 998877665554433222 podría simplificarse construyendo el sublista explícitamente y manteniendo un referencia a ella. Ya que solo estoy escribiendo esto sin un IDE, tengo problemas para reorganizar esto en una operación de arroyos, pero por lo que puedo decir, estás agrupando estos nodos por sus grados.
    Como punto de partida, echa un vistazo a:

      cur3  
  • No está usando cur4 y cur5 Después de la inicialización del cur6 . No estoy muy seguro de por qué está creando una copia profunda defensiva antes de pasarlos a cur7

  • Puede simplificar la creación de cur8 en cur9 mediante SOUTS SO:

      node *insert_node(node *root, int data, int node_id) {     if (root == NULL) {         return newNode(data, node_id);     }       if (node_id < root->node_id) {         root->left = insert_node(root->left, data, node_id);     } else if (node_id > root->node_id) {         root->right = insert_node(root->right, data, node_id);     }      return root; } 0  

Naming & Amp; Documentación

La documentación para todo el código aquí es bastante escasa. Especialmente la implementación del hallazgo real del isomorfismo es difícil de entender. Lo que también es difícil de entender es la forma en que funciona exactamente funciona exactamente 998877665554433311 El problema es que el código es tan diferente y mucho más verboso en comparación con la formulación matemática.

Aquí hay algunos nombres que realmente necesitan ser mejores:

  • node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 2 es más fácil de entender como node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 3
  • node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 4 y node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 5 son mediocre. Especialmente considerando que en realidad son solo los nodos extraídos de un gráfico, es posible que desee nombrarlos un poco más limpios. node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 6 y node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 7 son también nombres malos. Incluso node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 38 y node *insert_node(node *root, int data, int node_id) { if (root == NULL) { return newNode(data, node_id); } if (node_id < root->node_id) { root->left = insert_node(root->left, data, node_id); } else if (node_id > root->node_id) { root->right = insert_node(root->right, data, node_id); } return root; } 9 sería algo mejor. O newNode()0 y newNode()1 ...
  • En general, parece que le gusta nombrar cosas por lo que son. El newNode()2 sufijo a sus nombres de variables casi siempre puede ser reemplazado por una pluralización. Algo como newNode()3 es mucho más comunicativo que newNode()4 . (Más ejemplos: newNode()5 , newNode()6 )
  • newNode()7 en newNode()8 podría ser o algo así. Es mucho menos general de lo que el nombre implica ...
  • en newNode()0 Los nombres hacen que sea realmente difícil de seguir. newNode()1 y newNode()2 son los nombres menos útiles semánticamente posibles para dos listas ... No tengo ni idea de cuáles se usan las listas para, en realidad. Simplemente me doy cuenta de que estas listas tienen que ver con los grados de los nodos que examinas. Ya que están ordenados, asumo que tiene que ver con qué nodos se pueden asignarse entre sí ...
  • newNode()3 es un buen comienzo, pero podría estar mejor como newNode()4
o algo así? Que también lo haría más claro por qué se pasa ese mapa a newNode()5 .
  • newNode()6 es un nombre que ... no está realmente diciendo nada en absoluto. Tampoco estoy seguro, ¿por qué el cheque 99887766655443357 no se implementa en el newNode()8 ... sería mucho sentido allí, imo.
  • Algori curiosidades HMIC

    newNode()9 sobrescribe el estado actual node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 0 . Eso hace llamadas posteriores a node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 1 Use un estado ya node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 2 . No he comprado si todas las permutaciones de node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 3 están cubiertas, aunque trabajan fuera de la permutación anterior. Podría haber una manera de que todavía cubran todas las permutaciones posibles, solo en un orden diferente. Mi sensación de intestino dice que no ...

    En lugar de permitir el estado node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 4 , podría acceder directamente a la permutación al crear el node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 5 Al permitir el acceso a node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 6 en la llamada a node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 7 , como SO:

      node *insert_node(node *root, int data, int node_id) {     node *item = newNode(data, nodeId);     return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) {     if (!root) {         return item;     }     // I think you get the idea } 8  

    Consideraciones de diseño

    No estoy totalmente convencido de que la representación de los gráficos que eligió hace tanto sentido. Siguiendo las cosas se sienten un poco raras al respecto:

    • Los nodos deben recibir los nodos la gráfica a la que pertenecen. (¿Por qué un nodo lo sabe?)
    • El mecanismo para crear bordes es muy no obvio y, por alguna razón, no es realmente parte de la interfaz node *insert_node(node *root, int data, int node_id) { node *item = newNode(data, nodeId); return item ? insert_node_data(root, item) : root; } node* insert_node_data(node* root, node* item) { if (!root) { return item; } // I think you get the idea } 9 . Se siente raro tener que saber el nodo tanto sobre el resto del gráfico.
    • Estoy casi convencido de que usar una matriz de adyacencia para la representación haría que las verificaciones de permutación sean mucho más fáciles. Debe haber formas similarmente convincente de determinar los grados de un nodo, y los cambios necesarios para admitir gráficos ponderados y / o no dirigidos serían mínimos.

      En lugar de crear permutaciones entre los nodos, un isomorfismo se describiría mediante una matriz de permutación simétrica (gráficos no dirigidos).

    • Es muy poco claro para mí ¿Por qué 99887766555443370 no está en su propia clase? Esa cosa es útil más allá del getIsomorphism1 .

    • La forma en que se realiza ciclismo a través de todas las permutaciones de permutaciones es ... un truco. Un poco de código realmente inteligente que me hizo sonreír, pero es realmente algo que se debe hacer de una manera mejor. Podría considerar encapsular el getIsomorphism2 en su propia clase que maneja la iteración de las permutaciones.

     

    Java based suggestions

    • in getIsomorphism, the comparator you define can be a static final field. It can additionally be simplified to just:

      Comparator<DirectedGraphNode> comparator = Comparator.comparing(n -> n.children().size())       .thenComparing(n -> n.parents().size()); 

      If you were exposing inDegree and outDegree you could put DirectedGraphNode::inDegree and DirectedGraphNode::outDegree as the key-extractor functions instead.

    • Just below that you're iterating over an ordered collection of nodes, again comparing their inDegree and outDegree. If java were a more functional language, this could be better expressed like the following:

      all (== 0) $ map comparator::compare $ zip nodeList1 nodeList2 

      What happens here is essentially that the ordered items are associated together into a tuple, the comparator compares them and the == 0 checks that all elements are equal according to the comparator.
      I'm not quite sure why you're not reusing the comparator here. That would simplify the code to:

      for (int i = 0; i < nodeList1.size(); ++i) {     if (0 != comparator.compare(nodeList1.get(i), nodeList2.get(i))) {         return null;     } } 
    • graphToList could be written a bit more succinctly as:

      return StreamSupport.stream(graph.spliterator(), false).collect(Collectors.toList()); 
    • in bruteForceIsomorphism you could look whether the filling of list1 and list2 could be simplified by constructing the sublist explicitly and keeping a reference to it. Since I'm just writing this down without an IDE, I'm having trouble to reorganize this into a stream operation, but as far as I can tell, you're grouping these nodes by their degrees.
      As starting point, check out:

      List<List<DirectedGraphNode>> list1 = new ArrayList<>(); List<List<DirectedGraphNode>> list2 = new ArrayList<>(); List<DirectedGraphNode> sublist1 = new ArrayList<>(); List<DirectedGraphNode> sublist2 = new ArrayList<>();  sublist1.add(nodeList1.get(0)); sublist2.add(nodeList2.get(0));  int previousInDegree = nodeList1.get(0).parents().size(); int previousOutDegree = nodeList2.get(0).children().size();  for (int i = 1; i < nodeList1.size(); ++i) {     DirectedGraphNode currentNode = nodeList1.get(i);     int currentInDegree = currentNode.parents().size();     int currentOutDegree = currentNode.children().size();      if (previousInDegree != currentInDegree || previousOutDegree != currentOutDegree) {         list1.add(sublist1);         list2.add(sublist2);         sublist1 = new ArrayList<>();         sublist2 = new ArrayList<>();          previousInDegree = currentInDegree;         previousOutdegree = currentOutDegree;     } else {         sublist1.add(currentNode);         sublist2.add(nodeList2.get(i);     } } 
    • You're not using list1 and list2 after the initialization of the certainMap. I'm not quite sure why you're creating a defensive deep copy before passing them to findIsomorphismPermutation

    • You can simplify the creation of permutationEnumeratorList in findIsomorphismPermutation by using streams like so:

      List<PermutationEnumerator> permutationEnumerators = groupList1.stream()   .map(group -> new PermutationEnumerator(group.size())   .collect(Collectors.toList()); 

    Naming & Documentation

    The documentation for all the code here is rather very sparse. Especically the implementation of the actual isomorphism finding is difficult to understand. What's also hard to understand is how the isIsomorphism check works exactly. The problem there is that the code is so different and much more verbose compared to the mathematical formulation.

    Here's some names that really need to be better:

    • addEdges is easier to understand as modifyEdgeCounter
    • nodeList1 and nodeList2 are mediocre. Especially considering that they're actually just the nodes extracted from a graph, you might want to name them somewhat cleaner. graph1 and graph2 are also bad names. Even left and right would be somewhat better. Or source and target...
    • In general you seem to like naming things by what they are. The List suffix to your variable names can nearly always be replaced by a pluralization. Something like sourceNodes is much more communicative than nodeList1. (more examples: groupList1, permutationEnumeratorList)
    • comparator in getIsomorphism could be nodeDegreeComparator or something like that. It's much less general than the name implies...
    • In bruteForceIsomorphism the names make it really hard to follow. list1 and list2 are the least semantically useful names possible for two lists... I have no clue what the lists are used for, actually. I just notice that these lists have to do with the degrees of the nodes you examine. Since they are sorted, I assume it has to do with which nodes could be mapped to one another...
    • certainMap is a good start, but it might be better off as requiredMappings or something like that? That'd also make clearer why that map is passed to findIsomorphismPermutation.
    • Utils is a name that's... not really saying anything at all. I'm also not sure, why the isIsomorphism check is not implemented in the AbstractGraphIsomorphismChecker... It would make a lot of sense there, IMO.

    Algorithmic Curiosities

    permute overwrites the current groupList state. That makes subsequent calls to permute use an already permuted state. I have not check whether all permutations from PermutationEnumerator are actually covered, even though they work off the previous permutation. There could be a way that they still cover all possible permutations, just in a different order. My gut feeling says they don't...

    Instead of permuting the groupList state, you could directly access the permutation when building the isomorphismCandidate by permuting the access to groupList2 in the call to put, like so:

    // generateIsomorphismCandidate // note that I don't permute the groupList2 entries here Map<DirectedGraphNode, DirectedGraphNode> isomorphismCandidate = new HashMap<>();  for (int groupIndex = 0; groupIndex < groupList1.size(); ++groupIndex) {     int[] permutation = permutationEnumeratorList.get(groupIndex).indices;     for (int nodeIndex = 0; nodeIndex < groupList1.get(groupIndex).size(); nodeIndex++) {         isomorphismCandidate.put(           groupList1.get(groupIndex).get(nodeIndex),           groupList2.get(groupIndex).get(permutation[nodeIndex]));     } } 

    Design Considerations

    I'm not fully convinced that the representation of graphs you chose makes that much sense. Following things feel a little weird about it:

    • Nodes need to be told the Graph they belong to. (Why does a node know that?)
    • The mechanism to create edges is very non-obvious and for some reason not actually part of the Graph interface. It feels weird to have the node know so much about the rest of the graph.
    • I'm almost convinced that using an adjacency matrix for representation would make the permutation checks much easier. There should be similarly compelling ways to determine the degrees of a node, and the changes necessary to support weighted and/or undirected graphs would be minimal.

      Instead of creating permutations between nodes, an isomorphism would be described by a symmetric (for undirected graphs) permutation matrix.

    • It's very unclear to me why PermutationEnumerator is not in it's own class. That thing is useful beyond just the TrivialGraphIsomorphismChecker.

    • The way that cycling through all permutations of permutations is done is ... a hack. A really clever bit of code that made me smile, but it's really something that should be done in a better way. You could consider encapsulating the permutationEnumeratorList into it's own class that handles iteration of the permutations.

     
     

    Relacionados problema

    5  "Investigador Hatim es el desafío" correcto o incorrecto "  ( Researcher hatim is right or wrong challenge ) 
    Escribí un programa para resolver un problema, no soy tan bueno en Python, así que quiera ayuda para encontrar áreas donde este programa se pueda mejorar o si...

    0  Código de número de rutas posible de la longitud dada entre 2 nodos dados  ( Code for number of routes possible of the given length between 2 given nodes ) 
    Recientemente me encontré en este problema , aquí hay un extracto de eso, Es bien sabido que el algoritmo de enrutamiento utilizado en Internet es altam...

    2  Pequeño marco de búsqueda de ruta genérica en Java  ( Small generic path search framework in java ) 
    Tengo esta pequeña biblioteca de búsqueda de ruta genérica. No es perfecto en absoluto, así que necesito algunos comentarios para tener la oportunidad de mejo...

    3  Amplitud Primera búsqueda Python Implementación  ( Breadth first search python implementation ) 
    Tengo la siguiente implementación del algoritmo BFS, en el que he usado //C# Syntax here public string Reverse(string s) { char[] arr = s.ToCharArray(); ...

    1  BFS secuencial Java  ( Java sequential bfs ) 
    Actualmente estoy trabajando para optimizar mi código. Para hacerlo, tengo que asegurarme de que mi BFS secuencial funcione perfectamente. Luego, debo aplicar...

    3  Implementación del algoritmo de DIJKSTRA para encontrar el camino más corto en gráfico  ( Implementation of dijkstras algorithm to find the shortest path in graph ) 
    Esta es mi implementación del algoritmo de Dijkstra en C ++. Por favor aclare Si el diseño de la clase es adecuado o si necesita mejorarse. Estoy codif...

    4  Una implementación de gráficos en C ++  ( A graph implementation in c ) 
    Estoy construyendo un gráfico genérico. Quiero saber si el diseño actual está bien. ¿Hay alguna pérdida de memoria? Cualquier sugerencia es profundamente apre...

    31  Un algoritmo de búsqueda  ( A search algorithm ) 
    NodeData8 almacena toda la información del nodo que necesita el AStar algoritmo. Esta información incluye el valor de _cache0 , _cache1 y 998877665...

    4  Algoritmo a gráficos conectados al grupo  ( Algorithm to group connected graphs ) 
    Estoy trabajando en un algoritmo, que debe agrupar arcos conectados. La situación se describe a través de ejemplos de código a continuación. Tengo arcos: ...

    5  Vertiendo agua entre dos jarras para obtener una cierta cantidad en una de las jarras  ( Pouring water between two jugs to get a certain amount in one of the jugs ) 
    Escribí una solución para un problema de jarra (dado que dos jarras de agua de diferentes tamaños encuentran los pasos necesarios para obtener una cantidad es...




    © 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos