public ColoredVertices applyingGreedyAlgorithm()

in src/main/java/org/apache/commons/graph/coloring/DefaultColoringAlgorithmsSelector.java [55:112]
42 lines of code
8 McCabe index (conditional complexity)

    public ColoredVertices<V, C> applyingGreedyAlgorithm()
    {
        final ColoredVertices<V, C> coloredVertices = new ColoredVertices<V, C>();

        // decreasing sorting all vertices by degree.
        final UncoloredOrderedVertices<V> uncoloredOrderedVertices = new UncoloredOrderedVertices<V>();

        for ( V v : g.getVertices() )
        {
            uncoloredOrderedVertices.addVertexDegree( v, g.getDegree( v ) );
        }

        // search coloring
        Iterator<V> it = uncoloredOrderedVertices.iterator();
        Iterator<C> colorsIt = colors.iterator();
        while ( it.hasNext() )
        {
            if ( !colorsIt.hasNext() )
            {
                throw new NotEnoughColorsException( colors );
            }
            C color = colorsIt.next();

            // this list contains all vertex colors with the current color.
            List<V> currentColorVertices = new ArrayList<V>();
            Iterator<V> uncoloredVtxIterator = uncoloredOrderedVertices.iterator();
            while ( uncoloredVtxIterator.hasNext() )
            {
                V uncoloredVtx = uncoloredVtxIterator.next();

                boolean foundAnAdjacentVertex = false;
                for ( V currentColoredVtx : currentColorVertices )
                {
                    if ( g.getEdge( currentColoredVtx, uncoloredVtx ) != null )
                    {
                        // we've found that 'uncoloredVtx' is adiacent to
                        // 'currentColoredVtx'
                        foundAnAdjacentVertex = true;
                        break;
                    }
                }

                if ( !foundAnAdjacentVertex )
                {
                    // It's possible to color the vertex 'uncoloredVtx', it has
                    // no connected vertex into
                    // 'currentcoloredvtx'
                    uncoloredVtxIterator.remove();
                    coloredVertices.addColor( uncoloredVtx, color );
                    currentColorVertices.add( uncoloredVtx );
                }
            }

            it = uncoloredOrderedVertices.iterator();
        }

        return coloredVertices;
    }