1 25 42 package org.jgrapht.alg; 43 44 import java.util.*; 45 46 import org.jgrapht.*; 47 import org.jgrapht.alg.util.*; 48 import org.jgrapht.graph.*; 49 50 51 63 public abstract class VertexCovers 64 { 65 66 68 84 public static <V, E> Set<V> find2ApproximationCover(Graph<V, E> g) 85 { 86 Set<V> cover = new HashSet<V>(); 88 89 Subgraph<V, E> sg = new Subgraph<V, E>(g, null, null); 91 92 while (sg.edgeSet().size() > 0) { 94 E e = sg.edgeSet().iterator().next(); 96 97 V u = g.getEdgeSource(e); 99 V v = g.getEdgeTarget(e); 100 cover.add(u); 101 cover.add(v); 102 103 sg.removeVertex(u); 105 sg.removeVertex(v); 106 } 107 108 return cover; } 110 111 126 public static <V, E> Set<V> findGreedyCover(UndirectedGraph<V, E> g) 127 { 128 Set<V> cover = new HashSet<V>(); 130 131 UndirectedGraph<V, E> sg = new UndirectedSubgraph<V, E>(g, null, null); 133 134 VertexDegreeComparator<V, E> comp = 136 new VertexDegreeComparator<V, E>(sg); 137 138 while (sg.edgeSet().size() > 0) { 140 V v = Collections.max(sg.vertexSet(), comp); 142 143 cover.add(v); 145 146 sg.removeVertex(v); 148 } 149 150 return cover; 151 } 152 } 153 | Popular Tags |