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;
    }