Facebook Interview Question SDE1s
0of 0 votesTo determine if two graphs have isomorphism or not
Country: United States
Yes, it is well-known (classical) NP-complete problem that in general has solution O(n!) but practically many things can be done to reduce practical big-O for this problem:
- Use invariants as much as possible and it is proven that no matter how complicated invariant computation is, while it is polynomial time - it is still better to use it when graphs size rise to infinity
- Simplest invariant (that I used in my program): just be sure all vertices in both graphs in general have same sets of powers (number of adjacent vertices), and even with such simple invariant it is already a problem to construct example when graphs will be not insomorph but still fall into backtracking part (I put comment below to disable one line to actually test backtracking part)
- More complicated vertices invariants:
= calculate now many vertices adjacent to each vertex
= calculate how many vertex/edges will be in each vertex surrounding of X edges (+more strong - calculate for each value of X independent)
and many others.
For backtracking practically there is heruistic to compare first vertices with higher vertex power and then with lower (if graphs are not insomorph is it not important but if they are - such order will find mapping faster in general). I didn't used this heruistic in my code, just because I sure it is not possible to do during 30 minutes (but of course possible in real projects).
Here is the code. In general it is O(n!) time and O(n) space complexity where N - number of vertices in each graph (those should be equal):
private static class Graph {
private List<List<Integer>> adj=new ArrayList<List<Integer>>(); // Adjacency list
void addVertex(int vIndex, List<Integer> adjacentVertices) {
adj.add(vIndex, adjacentVertices);
}
int vertexPower(int vIndex) { return adj.get(vIndex).size(); }
int getVertexs() { return adj.size(); }
}
private static Map<Integer, Integer> vertexPowers(Graph g) {
Map<Integer, Integer> vertexPowers = new HashMap<Integer, Integer>();
for(int i=0;i<g.getVertexs();i++)
vertexPowers.put(i,g.vertexPower(i));
return vertexPowers;
}
private static boolean isVertexMappingAllowed(Graph a, Graph b,
Map<Integer, Integer> mapping,
int aVIndex, int bVIndex) {
for(Integer bVAdj : b.adj.get(bVIndex))
if(mapping.keySet().contains(bVAdj))
if(!a.adj.get(aVIndex).contains(mapping.get(bVAdj)))
return false;
return true;
}
private static boolean isomorphRecursive(Graph a, Graph b,
Map<Integer, Integer> mapping) {
if(mapping.size()==a.getVertexs()) return true;
int aVIndex = mapping.size();
for(int bVIndex=0;bVIndex<b.getVertexs();bVIndex++)
if(!mapping.keySet().contains(bVIndex))
if(isVertexMappingAllowed(a,b,mapping,aVIndex,bVIndex)) {
mapping.put(bVIndex, aVIndex);
if(isomorphRecursive(a,b,mapping))
return true;
mapping.remove(bVIndex);
}
return false;
}
private static boolean isomorph(Graph a, Graph b) {
// Simplest invariant - number of vertices should be the same
if(a.getVertexs()!=b.getVertexs()) return false;
Map<Integer, Integer> aVP = vertexPowers(a);
Map<Integer, Integer> bVP = vertexPowers(b);
// Also very simple invariant - powers on vertices should be the same
List<Integer> aVPowers = new ArrayList<Integer>(aVP.values());
List<Integer> bVPowers = new ArrayList<Integer>(bVP.values());
Collections.sort(aVPowers);
Collections.sort(bVPowers);
if(!aVPowers.equals(bVPowers)) return false; // disable this to have reason fot test2
Map<Integer, Integer> mapping = new HashMap<Integer, Integer>();
boolean isIsomorph = isomorphRecursive(a,b,mapping);
// here mapping will contains actual mapping if graphs are isomorph
System.out.println(mapping);
return isIsomorph;
}
private static void doTest0Yes() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1));
a.addVertex(1, Arrays.asList(0));
Graph b = new Graph();
b.addVertex(0, Arrays.asList(1));
b.addVertex(1, Arrays.asList(0));
System.out.println(isomorph(a,b)?"YES":"NO");
}
private static void doTest0No() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1));
a.addVertex(1, Arrays.asList(0));
Graph b = new Graph();
System.out.println(isomorph(a,b)?"YES":"NO");
}
private static void doTest1Yes() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1,3));
a.addVertex(1, Arrays.asList(0,2,3,4));
a.addVertex(2, Arrays.asList(1,4));
a.addVertex(3, Arrays.asList(0,1,4));
a.addVertex(4, Arrays.asList(1,2,3));
Graph b = new Graph();
b.addVertex(0, Arrays.asList(1,2,3));
b.addVertex(1, Arrays.asList(0,3,4));
b.addVertex(2, Arrays.asList(0,3));
b.addVertex(3, Arrays.asList(0,1,2,4));
b.addVertex(4, Arrays.asList(1,3));
System.out.println(isomorph(a,b)?"YES":"NO");
}
private static void doTest2No() {
Graph a = new Graph();
a.addVertex(0, Arrays.asList(1,2,3));
a.addVertex(1, Arrays.asList(0,5));
a.addVertex(2, Arrays.asList(0,4));
a.addVertex(3, Arrays.asList(0,1,5));
a.addVertex(4, Arrays.asList(2,5));
a.addVertex(5, Arrays.asList(1,3,4));
Graph b = new Graph();
b.addVertex(0, Arrays.asList(1,2));
b.addVertex(1, Arrays.asList(0,2,3));
b.addVertex(2, Arrays.asList(0,1,3,4));
b.addVertex(3, Arrays.asList(1,2,5));
b.addVertex(4, Arrays.asList(2,5));
b.addVertex(5, Arrays.asList(3,4));
System.out.println(isomorph(a,b)?"YES":"NO");
}
public static void main(String[] args) {
doTest0Yes();
doTest0No();
doTest1Yes();
doTest2No();
}
Assume there are two directed graphs G1, G2 with an adjacency list representation.
The question is, is there a function g1tog2(vg1_i) that will return a vertex of G2 vg2_j
if a vertex vg1_i of G1 is given, such that for all edges (vg1_u, vg1_v) of G1
there is a corresponding edge (vg2_u, vg2_v) of G2 where vg2_u = g1tog2(vg1_u)
and vg2_v = g1tog2(vg1_v).
The problem is known to be NP complete. This means there is a polynomial verification
function.
That's the way I would approach it, knowing it's NP complete:
- create a function that creates all possibles mappings of vg1_i to vg2_j where
out-degree(vg1_i) = out-degree(vg2_j)
- call a verification function that verifies if all edges given by graph g1 have a
corresponding edge in g2 under one given mapping (g1tog2)
example graph's
permutations:
1)a->1: doesn't work, differnt out-degree
2)a->2,b->1,c->3, doesn't work, different out-degree
3)a->2,b->1,c->4,d->3, valid permutations, will fail validation method because
(a,d), (a,b); g1tog2(a) = 2, g1tog2(d) = 3, g1tog2(b) = 1, (2,3), (2,1)
but it's (2,3) (2,4) in g2
3) a->2, b->3: doesn't work, differnt out-degree
5) a->2, b->4, c->1, d->3
obviously this will find for edges in g1 a corresponding edge in g2
- Chris November 11, 2017#include <string> #include <stack> #include <unordered_set> #include <unordered_map> #include <iostream> using namespace std; struct Node { string label_; unordered_set<Node*> adjacents_; Node(const string& label) : label_(label) {} void link(Node* v) { adjacents_.insert(v); } }; // this function verifies if the both graphs g1 and g2 are isomorphic // taking into account the function g1tog2 which has a 1:1 mapping of // each node in g1 to a node in g2 bool are_graphs_isomorphic_verification(unordered_set<Node*>& g1, // graph 1 unordered_set<Node*>& g2, // graph 2 unordered_map<Node*, Node*>& g1tog2) // node g1 -> node g2 { unordered_set<Node*> visited; for (auto start : g1) { // standard DFS, outher loop if (visited.count(start) > 0) continue; stack<Node*> stk; stk.push(start); while (!stk.empty()) { // inner loop, to build a single DFS tree with root=start auto ug1 = stk.top(); stk.pop(); if (visited.count(ug1) > 0) continue; visited.insert(ug1); auto ug2 = g1tog2[ug1]; // I assume ug1, ug2 adjacents.size() are equal, as this is ensured by // permutation method below, // otherwise: if (ug1->adjacents_.size() != ug2->adjacents_.size()) return false; for (auto vg1 : ug1->adjacents_) { if (ug2->adjacents_.count(g1tog2[vg1]) == 0) return false; stk.push(vg1); } } } return true; } // this function crates all possible mappings of any node in g1 to any other node in // g2. It will call the vierifcation method above for all possible mappings. // If with one of those mappings isomorphism is detected, the function returns true bool are_graphs_isomorphic(unordered_set<Node*>& g1, unordered_set<Node*>& g2) { if (g1.size() != g2.size()) return false; if (g1.size() == 0 && g2.size() == 0) return true; unordered_map<Node*, Node*> g1tog2; // node g1 -> node g2 for (auto u1 = g1.begin(), u2 = g2.begin(); u1 != g1.end(); ++u1, ++u2) { g1tog2[*u1] = *u2; } // create all valid mappings between nodes of g1 to nodes of g2 // a primitive first indication if a mapping may be valid or not if the size // of the adjacency lists don't match, it makes no sense to further develop // that permutation or to verify it. struct StackItem { decltype(g1tog2)::iterator i, j; // the two nodes to swap to create permutations bool leave; // mark, if entered that common prefix or if about to leave it }; stack<StackItem> stk; // first step, what node of g2 could be at first position so that adj-list-sizes match for (auto j = g1tog2.begin(); j != g1tog2.end(); ++j) { if (j->second->adjacents_.size() == g1tog2.begin()->first->adjacents_.size()) { stk.push({ g1tog2.begin(), j, false }); } } while (!stk.empty()) { if (stk.top().leave) { swap(stk.top().i->second, stk.top().j->second); // swap back stk.pop(); } else { stk.top().leave = true; // recurse, remove next time swap(stk.top().i->second, stk.top().j->second); // swap auto ni = next(stk.top().i); if (ni == g1tog2.end()) { if (are_graphs_isomorphic_verification(g1, g2, g1tog2)) { return true; } } else { for (auto nj = ni; nj != g1tog2.end(); ++nj) { if (ni->first->adjacents_.size() == nj->second->adjacents_.size()) { stk.push({ ni, nj, false }); } } } } } return false; } int main() { Node a("a"); Node b("b"); Node c("c"); Node d("d"); a.link(&b); a.link(&d); b.link(&c); c.link(&c); unordered_set<Node*> g1{ &a, &b, &c, &d }; Node n1("1"); Node n2("2"); Node n3("3"); Node n4("4"); n1.link(&n1); n2.link(&n3); n2.link(&n4); n4.link(&n1); unordered_set<Node*> g2{&n1, &n2, &n3, &n4}; cout << "g1, g2: " << are_graphs_isomorphic(g1, g2) << endl; cout << "g2, g1: " << are_graphs_isomorphic(g2, g1) << endl; cout << "g1, g1: " << are_graphs_isomorphic(g1, g1) << endl; cout << "g2, g2: " << are_graphs_isomorphic(g2, g2) << endl; n1.adjacents_.clear(); cout << "g1, g2: " << are_graphs_isomorphic(g1, g2) << endl; cout << "g2, g1: " << are_graphs_isomorphic(g2, g1) << endl; }