我编写了一个算法来查找图的最大独立集。 根据定义,独立集合是“集合S,使得图形的每个边缘具有至少一个不在S中的端点,并且不在S中的每个顶点在S中具有至少一个邻居”
该图是一个无向图,如下所示:
节点:1,2,3,4,5,6,7边缘:1-2,2-3,3-4,4-5,5-6,6-7,1-5
这是我的实施:
FindMIS fms= new FindMIS(network); public class FindMIS { INetwork network; public FindMIS(INetwork network) { this.network = network; ArrayList<INode> nodes = new ArrayList<>(); nodes.addAll(network.getNodesList()); Iterator<INode> iter = nodes.iterator(); ArrayList<INode> IS = new ArrayList<>(); while (iter.hasNext()) { INode node=iter.next(); visitNode(node, IS, nodes); } } private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode> previousCandidates) { ArrayList<INode> IS=new ArrayList<>(); IS.addAll(previousIS); ArrayList<INode> candidates = new ArrayList<>(); candidates.addAll(previousCandidates); //System.out.println(node); ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node); for (INode n : previousCandidates) { if (neighbor.contains(n)) { candidates.remove(n); } } IS.add(node); candidates.remove(node); Iterator<INode> iter = candidates.iterator(); while (iter.hasNext()) { visitNode(iter.next(), IS, candidates); } if (candidates.size()==0){ Iterator<INode> iter2=IS.iterator(); System.out.print("output:{" ); while(iter2.hasNext()){ System.out.print(iter2.next().getid()); } System.out.println("}"); } } }输出如下:
output:{1 3 6 } output:{1 4 6 } output:{1 6 3 } output:{1 6 4 } output:{2 4 6 } output:{2 4 7 } output:{2 5 7 } output:{2 6 4 } output:{2 7 4 } output:{2 7 5 } output:{3 1 6 } output:{3 5 7 } output:{3 6 1 } output:{3 7 5 } output:{4 1 6 } output:{4 2 6 } output:{4 2 7 } output:{4 6 1 } output:{4 6 2 } output:{4 7 2 } output:{5 2 7 } output:{5 3 7 } output:{5 7 2 } output:{5 7 3 } output:{6 1 3 } output:{6 1 4 } output:{6 2 4 } output:{6 3 1 } output:{6 4 1 } output:{6 4 2 } output:{7 2 4 } output:{7 2 5 } output:{7 3 5 } output:{7 4 2 } output:{7 5 2 } output:{7 5 3 } You can realize that there are some redundant sets like {1,3,6} and {1,6,3}. The final result must be: output:{1 3 6} output:{1 4 6} output:{2 4 6} output:{2 4 7} output:{2 5 7} output:{3 5 7} I am trying to figure out a way to avoid unnecessary computation. I appreciate for any idea.更新:1:在Darryl Gerrow的回复之后,我改变了我的visitNode方法如下:它有效。 我的算法仍然存在一些问题,使其更具可读性和可移植性。 每当我完成时,我都会发布最终版本。 感谢所有社区。 如果有人有更好的想法在图表中找到最大的独立集合,而不仅仅是寻找所有节点,我真的很感激阅读。
private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode> previousCandidates) { ArrayList<INode> IS=new ArrayList<>(); IS.addAll(previousIS); ArrayList<INode> candidates = new ArrayList<>(); candidates.addAll(previousCandidates); //System.out.println(node); ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node); for (INode n : previousCandidates) { if (neighbor.contains(n)) { candidates.remove(n); } } IS.add(node); candidates.remove(node); Iterator<INode> iter = candidates.iterator(); while (iter.hasNext()) { INode nextnode=iter.next(); if (node.getid() < nextnode.getid()) visitNode(nextnode, IS, candidates); } if (candidates.size()==0){ Iterator<INode> iter2=IS.iterator(); System.out.print("output:{" ); while(iter2.hasNext()){ System.out.print(iter2.next().getid() +" "); } System.out.println("}"); } }}
I coded an algorithm to find maximal independent sets of a graph. By definition an independent set is "a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S"
The graph is an undirected graph as shown below:
Nodes : 1,2,3,4,5,6,7 Edges : 1-2,2-3,3-4,4-5,5-6,6-7,1-5
And here is my implementation:
FindMIS fms= new FindMIS(network); public class FindMIS { INetwork network; public FindMIS(INetwork network) { this.network = network; ArrayList<INode> nodes = new ArrayList<>(); nodes.addAll(network.getNodesList()); Iterator<INode> iter = nodes.iterator(); ArrayList<INode> IS = new ArrayList<>(); while (iter.hasNext()) { INode node=iter.next(); visitNode(node, IS, nodes); } } private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode> previousCandidates) { ArrayList<INode> IS=new ArrayList<>(); IS.addAll(previousIS); ArrayList<INode> candidates = new ArrayList<>(); candidates.addAll(previousCandidates); //System.out.println(node); ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node); for (INode n : previousCandidates) { if (neighbor.contains(n)) { candidates.remove(n); } } IS.add(node); candidates.remove(node); Iterator<INode> iter = candidates.iterator(); while (iter.hasNext()) { visitNode(iter.next(), IS, candidates); } if (candidates.size()==0){ Iterator<INode> iter2=IS.iterator(); System.out.print("output:{" ); while(iter2.hasNext()){ System.out.print(iter2.next().getid()); } System.out.println("}"); } } }The output is below:
output:{1 3 6 } output:{1 4 6 } output:{1 6 3 } output:{1 6 4 } output:{2 4 6 } output:{2 4 7 } output:{2 5 7 } output:{2 6 4 } output:{2 7 4 } output:{2 7 5 } output:{3 1 6 } output:{3 5 7 } output:{3 6 1 } output:{3 7 5 } output:{4 1 6 } output:{4 2 6 } output:{4 2 7 } output:{4 6 1 } output:{4 6 2 } output:{4 7 2 } output:{5 2 7 } output:{5 3 7 } output:{5 7 2 } output:{5 7 3 } output:{6 1 3 } output:{6 1 4 } output:{6 2 4 } output:{6 3 1 } output:{6 4 1 } output:{6 4 2 } output:{7 2 4 } output:{7 2 5 } output:{7 3 5 } output:{7 4 2 } output:{7 5 2 } output:{7 5 3 } You can realize that there are some redundant sets like {1,3,6} and {1,6,3}. The final result must be: output:{1 3 6} output:{1 4 6} output:{2 4 6} output:{2 4 7} output:{2 5 7} output:{3 5 7} I am trying to figure out a way to avoid unnecessary computation. I appreciate for any idea.UPDATE :1 : After Darryl Gerrow's reply, I changed my visitNode method as follows: It worked. I have still some issues with my algorithm to make it more readable and portable. I will post the final version whenever I finished. Thanks for all community. If anyone have better idea to find maximal independent sets in a graph other than just looking for all nodes, I really appreciate to read about.
private void visitNode(INode node, ArrayList<INode> previousIS, ArrayList<INode> previousCandidates) { ArrayList<INode> IS=new ArrayList<>(); IS.addAll(previousIS); ArrayList<INode> candidates = new ArrayList<>(); candidates.addAll(previousCandidates); //System.out.println(node); ArrayList<INode> neighbor = (ArrayList<INode>) network.getNeighborsof(node); for (INode n : previousCandidates) { if (neighbor.contains(n)) { candidates.remove(n); } } IS.add(node); candidates.remove(node); Iterator<INode> iter = candidates.iterator(); while (iter.hasNext()) { INode nextnode=iter.next(); if (node.getid() < nextnode.getid()) visitNode(nextnode, IS, candidates); } if (candidates.size()==0){ Iterator<INode> iter2=IS.iterator(); System.out.print("output:{" ); while(iter2.hasNext()){ System.out.print(iter2.next().getid() +" "); } System.out.println("}"); } }}
最满意答案
看起来你正在做一个n平方的迭代,这就是为什么你得到{1,3,6},{1,6,3},{3,6,1},......基本上每一个可接受的组合的可能组合。
我认为您需要重新编写迭代,以便只访问比当前节点更大的节点。
即。 你会得到{1,3,6},但是{1,6,3}是不可接受的,因为6> 3。
您可能必须删除Iterator并使用ArrayList的索引方法。
It looks like you're doing an n-squared iteration, so that's why you're getting {1, 3, 6}, {1, 6, 3}, {3, 6, 1}, .... essentially every possible combination of an acceptable set.
I think you need to re-write the iteration so that you only visit larger nodes than the current node.
ie. you would get {1, 3, 6}, but {1, 6, 3} would not be acceptable because 6 > 3.
You may have to drop the Iterator and use the index methods of the ArrayList.
更多推荐
发布评论