@Test public void testSingleNodeGraph() { final MutableDirectedGraph<String> g = new MutableDirectedGraph<>(); g.addNode("a"); final Map<String, Integer> colors = WelshPowell.colorByWelshPowell(g); assertEquals(1, colors.size()); assertEquals(0, (int) colors.get("a")); }
public static <N> Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph) { final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final Map<N, Integer> colors = new HashMap<>(n); final List<N> sortedNodesToColor = new ArrayList<>(n); sortedNodesToColor.addAll(allNodes .stream() .sorted(Comparator.<N>comparingInt(node -> graph.adjacent(node).size()).reversed()) .collect(Collectors.toList())); int color = 0; while (!sortedNodesToColor.isEmpty()) { final Set<N> thisStepColoredNodes = new LinkedHashSet<>(); final N first = sortedNodesToColor.get(0); thisStepColoredNodes.add(first); sortedNodesToColor .stream() .filter(node -> first != node) .filter(node -> !graph.isAdjacent(first, node)) .forEach(thisStepColoredNodes::add); final int nextColor = color++; thisStepColoredNodes.forEach(node -> colors.put(node, nextColor)); sortedNodesToColor.removeAll(thisStepColoredNodes); } return colors; }
WelshPowell { public static <N> Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph) { final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final Map<N, Integer> colors = new HashMap<>(n); final List<N> sortedNodesToColor = new ArrayList<>(n); sortedNodesToColor.addAll(allNodes .stream() .sorted(Comparator.<N>comparingInt(node -> graph.adjacent(node).size()).reversed()) .collect(Collectors.toList())); int color = 0; while (!sortedNodesToColor.isEmpty()) { final Set<N> thisStepColoredNodes = new LinkedHashSet<>(); final N first = sortedNodesToColor.get(0); thisStepColoredNodes.add(first); sortedNodesToColor .stream() .filter(node -> first != node) .filter(node -> !graph.isAdjacent(first, node)) .forEach(thisStepColoredNodes::add); final int nextColor = color++; thisStepColoredNodes.forEach(node -> colors.put(node, nextColor)); sortedNodesToColor.removeAll(thisStepColoredNodes); } return colors; } }
WelshPowell { public static <N> Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph) { final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final Map<N, Integer> colors = new HashMap<>(n); final List<N> sortedNodesToColor = new ArrayList<>(n); sortedNodesToColor.addAll(allNodes .stream() .sorted(Comparator.<N>comparingInt(node -> graph.adjacent(node).size()).reversed()) .collect(Collectors.toList())); int color = 0; while (!sortedNodesToColor.isEmpty()) { final Set<N> thisStepColoredNodes = new LinkedHashSet<>(); final N first = sortedNodesToColor.get(0); thisStepColoredNodes.add(first); sortedNodesToColor .stream() .filter(node -> first != node) .filter(node -> !graph.isAdjacent(first, node)) .forEach(thisStepColoredNodes::add); final int nextColor = color++; thisStepColoredNodes.forEach(node -> colors.put(node, nextColor)); sortedNodesToColor.removeAll(thisStepColoredNodes); } return colors; }  }
WelshPowell { public static <N> Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph) { final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final Map<N, Integer> colors = new HashMap<>(n); final List<N> sortedNodesToColor = new ArrayList<>(n); sortedNodesToColor.addAll(allNodes .stream() .sorted(Comparator.<N>comparingInt(node -> graph.adjacent(node).size()).reversed()) .collect(Collectors.toList())); int color = 0; while (!sortedNodesToColor.isEmpty()) { final Set<N> thisStepColoredNodes = new LinkedHashSet<>(); final N first = sortedNodesToColor.get(0); thisStepColoredNodes.add(first); sortedNodesToColor .stream() .filter(node -> first != node) .filter(node -> !graph.isAdjacent(first, node)) .forEach(thisStepColoredNodes::add); final int nextColor = color++; thisStepColoredNodes.forEach(node -> colors.put(node, nextColor)); sortedNodesToColor.removeAll(thisStepColoredNodes); } return colors; }  static Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph); }
WelshPowell { public static <N> Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph) { final Set<N> allNodes = graph.nodes(); final int n = allNodes.size(); final Map<N, Integer> colors = new HashMap<>(n); final List<N> sortedNodesToColor = new ArrayList<>(n); sortedNodesToColor.addAll(allNodes .stream() .sorted(Comparator.<N>comparingInt(node -> graph.adjacent(node).size()).reversed()) .collect(Collectors.toList())); int color = 0; while (!sortedNodesToColor.isEmpty()) { final Set<N> thisStepColoredNodes = new LinkedHashSet<>(); final N first = sortedNodesToColor.get(0); thisStepColoredNodes.add(first); sortedNodesToColor .stream() .filter(node -> first != node) .filter(node -> !graph.isAdjacent(first, node)) .forEach(thisStepColoredNodes::add); final int nextColor = color++; thisStepColoredNodes.forEach(node -> colors.put(node, nextColor)); sortedNodesToColor.removeAll(thisStepColoredNodes); } return colors; }  static Map<N, Integer> colorByWelshPowell(final Graph<N, ?> graph);  }