public function getColors()
    {
        $colors = array();

        // get color for each vertex
        foreach ($this->graph->getVertices()->getMap() as $vid => $startVertex) {
            if (!isset($colors[$vid])) {
                $queue = array($startVertex);
                // initialize each components color
                $colors[$vid] = 0;

                // breadth search all vertices in same component
                do {
                    // next vertex in color
                    $vertex = array_shift($queue);
                    $color = $colors[$vertex->getId()];
                    $nextColor = 1-$color;

                    // scan all vertices connected to this vertex
                    foreach ($vertex->getVerticesEdge()->getMap() as $vid => $nextVertex) {
                        // color unknown, so expect next color for this vertex
                        if (!isset($colors[$vid])) {
                            $colors[$vid] = $nextColor;
                            $queue []= $nextVertex;
                        // color is known but differs => can not be bipartit
                        } elseif ($colors[$vid] !== $nextColor) {
                            throw new UnexpectedValueException('Graph is not bipartit');
                        }
                    }
                } while ($queue);
            }
        }

        return $colors;
    }
public function getColors()
    {
        $colors = array();

        // get color for each vertex
        foreach ($this->graph->getVertices()->getMap() as $vid => $startVertex) {
            if (!isset($colors[$vid])) {
                $queue = array($startVertex);
                // initialize each components color
                $colors[$vid] = 0;

                // breadth search all vertices in same component
                do {
                    // next vertex in color
                    $vertex = array_shift($queue);
                    $color = $colors[$vertex->getId()];
                    $nextColor = 1-$color;

                    // scan all vertices connected to this vertex
                    foreach ($vertex->getVerticesEdge()->getMap() as $vid => $nextVertex) {
                        // color unknown, so expect next color for this vertex
                        if (!isset($colors[$vid])) {
                            $colors[$vid] = $nextColor;
                            $queue []= $nextVertex;
                        // color is known but differs => can not be bipartit
                        } elseif ($colors[$vid] !== $nextColor) {
                            throw new UnexpectedValueException('Graph is not bipartit');
                        }
                    }
                } while ($queue);
            }
        }

        return $colors;
    }
public function getColors ( ) { $ colors = array ( ) ; // get color for each vertex foreach ( $ this -> graph -> getVertices ( ) -> getMap ( ) as $ vid => $ startVertex ) { if ( ! isset ( $ colors [ $ vid ] ) ) { $ queue = array ( $ startVertex ) ; // initialize each components color $ colors [ $ vid ] = 0 ; // breadth search all vertices in same component do { // next vertex in color $ vertex = array_shift ( $ queue ) ; $ color = $ colors [ $ vertex -> getId ( ) ] ; $ nextColor = 1 - $ color ; // scan all vertices connected to this vertex foreach ( $ vertex -> getVerticesEdge ( ) -> getMap ( ) as $ vid => $ nextVertex ) { // color unknown, so expect next color for this vertex if ( ! isset ( $ colors [ $ vid ] ) ) { $ colors [ $ vid ] = $ nextColor ; $ queue [ ] = $ nextVertex ; // color is known but differs => can not be bipartit } elseif ( $ colors [ $ vid ] !== $ nextColor ) { throw new UnexpectedValueException ( 'Graph is not bipartit' ) ; } } } while ( $ queue ) ; } } return $ colors ; }
get map of vertex ID to vertex color

@return int[]
@throws UnexpectedValueException if graph is not bipartit
@uses AlgorithmBipartit::checkVertex() for every vertex not already colored
get map of vertex ID to vertex color