app/src/main/java/org/jgrapht/alg/ChromaticNumber.java
public static <V, E> Map<Integer, Set<V>> findGreedyColoredGroups(
        UndirectedGraph<V, E> g)
    {
        // A copy of the graph is made, so that elements of the graph may be
        // removed to carry out the algorithm
        UndirectedGraph<V, E> sg = new UndirectedSubgraph<V, E>(g, null, null);

        // The Vertices will be sorted in decreasing order by degree, so that
        // higher degree vertices have priority to be colored first
        VertexDegreeComparator<V, E> comp =
            new VertexDegreeComparator<V, E>(sg);
        List<V> sortedVertices = new LinkedList<V>(sg.vertexSet());
        Collections.sort(sortedVertices, comp);
        Collections.reverse(sortedVertices);

        int color;

        // create a map which will hold color as key and Set<V> as value
        Map<Integer, Set<V>> coloredGroups = new HashMap<Integer, Set<V>>();

        // We'll attempt to color each vertex with a single color each
        // iteration, and these vertices will be removed from the graph at the
        // end of each iteration
        for (color = 0; sg.vertexSet().size() > 0; color++) {
            // This set will contain vertices that are colored with the
            // current color of this iteration
            Set<V> currentColor = new HashSet<V>();
            for (
                Iterator<V> iter = sortedVertices.iterator();
                iter.hasNext();)
            {
                V v = iter.next();

                // Add new vertices to be colored as long as they are not
                // adjacent with any other vertex that has already been colored
                // with the current color
                boolean flag = true;
                for (
                    Iterator<V> innerIter = currentColor.iterator();
                    innerIter.hasNext();)
                {
                    V temp = innerIter.next();
                    if (sg.containsEdge(temp, v)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    currentColor.add(v);
                    iter.remove();
                }
            }

            // Add all these vertices as a group for this color
            coloredGroups.put(color, currentColor);

            // Remove vertices from the graph and then repeat the process for
            // the next iteration
            sg.removeAllVertices(currentColor);
        }
        return coloredGroups;
    }
/**
     * Finds a greedy coloring of the graph.
     *
     * @param g an undirected graph for which to find the coloring
     */
Finds a greedy coloring of the graph.
@param g an undirected graph for which to find the coloring
Finds a greedy coloring of the graph . @param g an undirected graph for which to find the coloring
public static <V, E> Map<Integer, Set<V>> findGreedyColoredGroups(
        UndirectedGraph<V, E> g)
    {
        UndirectedGraph<V, E> sg = new UndirectedSubgraph<V, E>(g, null, null);
        VertexDegreeComparator<V, E> comp =
            new VertexDegreeComparator<V, E>(sg);
        List<V> sortedVertices = new LinkedList<V>(sg.vertexSet());
        Collections.sort(sortedVertices, comp);
        Collections.reverse(sortedVertices);
        int color;
        Map<Integer, Set<V>> coloredGroups = new HashMap<Integer, Set<V>>();
        for (color = 0; sg.vertexSet().size() > 0; color++) {
            Set<V> currentColor = new HashSet<V>();
            for (
                Iterator<V> iter = sortedVertices.iterator();
                iter.hasNext();)
            {
                V v = iter.next();
                boolean flag = true;
                for (
                    Iterator<V> innerIter = currentColor.iterator();
                    innerIter.hasNext();)
                {
                    V temp = innerIter.next();
                    if (sg.containsEdge(temp, v)) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    currentColor.add(v);
                    iter.remove();
                }
            }
            coloredGroups.put(color, currentColor);
            sg.removeAllVertices(currentColor);
        }
        return coloredGroups;
    }
public static < V , E > Map < Integer , Set < V > > findGreedyColoredGroups ( UndirectedGraph < V , E > g ) { UndirectedGraph < V , E > sg = new UndirectedSubgraph < V , E > ( g , null , null ) ; VertexDegreeComparator < V , E > comp = new VertexDegreeComparator < V , E > ( sg ) ; List < V > sortedVertices = new LinkedList < V > ( sg . vertexSet ( ) ) ; Collections . sort ( sortedVertices , comp ) ; Collections . reverse ( sortedVertices ) ; int color ; Map < Integer , Set < V > > coloredGroups = new HashMap < Integer , Set < V > > ( ) ; for ( color = 0 ; sg . vertexSet ( ) . size ( ) > 0 ; color ++ ) { Set < V > currentColor = new HashSet < V > ( ) ; for ( Iterator < V > iter = sortedVertices . iterator ( ) ; iter . hasNext ( ) ; ) { V v = iter . next ( ) ; boolean flag = true ; for ( Iterator < V > innerIter = currentColor . iterator ( ) ; innerIter . hasNext ( ) ; ) { V temp = innerIter . next ( ) ; if ( sg . containsEdge ( temp , v ) ) { flag = false ; break ; } } if ( flag ) { currentColor . add ( v ) ; iter . remove ( ) ; } } coloredGroups . put ( color , currentColor ) ; sg . removeAllVertices ( currentColor ) ; } return coloredGroups ; }
Finds a greedy coloring of the graph.
Finds a greedy coloring of the graph .
// A copy of the graph is made, so that elements of the graph may be // removed to carry out the algorithm // The Vertices will be sorted in decreasing order by degree, so that // higher degree vertices have priority to be colored first // create a map which will hold color as key and Set<V> as value // We'll attempt to color each vertex with a single color each // iteration, and these vertices will be removed from the graph at the // end of each iteration // This set will contain vertices that are colored with the // current color of this iteration // Add new vertices to be colored as long as they are not // adjacent with any other vertex that has already been colored // with the current color // Add all these vertices as a group for this color // Remove vertices from the graph and then repeat the process for // the next iteration