create new graph clone with only vertices and edges actually in the walk

do not add duplicate vertices and edges for loops and intersections, etc.

@return Graph
@uses Walk::getEdges()
@uses Graph::createGraphCloneEdges()
422992
public function createGraph()
    {
        // create new graph clone with only edges of walk
        $graph = $this->getGraph()->createGraphCloneEdges($this->getEdges());
        $vertices = $this->getVertices()->getMap();
        // get all vertices
        foreach ($graph->getVertices()->getMap() as $vid => $vertex) {
            if (!isset($vertices[$vid])) {
                // remove those not present in the walk (isolated vertices, etc.)
                $vertex->destroy();
            }
        }

        return $graph;
    }
474170
private function getSingleUndirectedRelation()
    {
        $ed = $this->getEdgeDefinitions();
        if (count($ed) > 0) {
            $a = $ed[0];
            $b = $a->getFromCollections();
            $c = $a->getToCollections();
        }
        if (count($ed) > 1 ||
            (
                count($ed) === 1 && (
                    count($a->getFromCollections()) > 1 ||
                    count($a->getToCollections()) > 1 ||
                    $b[0] !== $c[0]

                )
            )
        ) {
            throw new ClientException('This operation only supports graphs with one undirected single collection relation');
        }
        if (count($ed) === 1) {
            $eD                     = $ed[0];
            $this->_edgeDefinitions = [];
        } else {
            $eD = new EdgeDefinition();
        }

        return $eD;
    }
528478
public function getCallGraph()
    {
        $node = $root = new Node(array());
        foreach ($this->getQueries() as $query) {
            foreach (array_reverse($query['trace']) as $trace) {
                $node = $node->push($trace);
            }
            $node->addValue($query);
            $node = $root;
        }

        return $root;
    }
589708
public function createEdge(string $id = null, Node $start, Node $end, array $attrs): Edge
	{
		if ($id === null) {
			$id = '_' . count($this->getRootGraph()->getAllEdges());
		}

		return new Edge($this, $id, $start, $end, $attrs);
	}
903016
public function createGraph($graph)
    {
        // Write the dot source to a temporary file
        $tempDot = tempnam(sys_get_temp_dir(), 'DOT_');
        $this->registerTempFile($tempDot);
        file_put_contents($tempDot, $graph);

        // Create component graph
//        $dotCommand = 'ccomps -x '.CommandUtility::escapeShellArgument($tempDot).' | dot -Nfontname=sans-serif -Efontname=sans-serif | gvpack -array_1 | neato -Tsvg ';
        $dotCommand = 'dot -Tsvg -Nfontname=sans-serif -Efontname=sans-serif '.CommandUtility::escapeShellArgument($tempDot);
        $output     = $returnValue = null;
        CommandUtility::exec($dotCommand, $output, $returnValue);

        return $returnValue ? '' : implode('', (array)$output);
    }
345089
def copy(self):
        
        other = DirectedGraph()
        other._vertices = set(self._vertices)
        other._forwards = {k: set(v) for k, v in self._forwards.items()}
        other._backwards = {k: set(v) for k, v in self._backwards.items()}
        return other
868274
public function isTriangle()
    {
        // exactly 3 (implicitly distinct) edges
        return (count($this->walk->getEdges()) === 3 &&
                // exactly three distinct vertices
                count($this->walk->getVertices()->getVerticesDistinct()) === 3 &&
                // this is actually a cycle
                $this->isCycle());
    }
845880
public Graph<T> reduce() {
        Builder<T> builder = new Builder<>();
        nodes.stream()
                .forEach(u -> {
                    builder.addNode(u);
                    edges.get(u).stream()
                         .filter(v -> !pathExists(u, v, false))
                         .forEach(v -> builder.addEdge(u, v));
                });
        return builder.build();
    }
807814
private Graph<Module> buildGraph(Map<Module, Set<Module>> edges) {
        Graph.Builder<Module> builder = new Graph.Builder<>();
        Set<Module> visited = new HashSet<>();
        Deque<Module> deque = new LinkedList<>();
        edges.entrySet().stream().forEach(e -> {
            Module m = e.getKey();
            deque.add(m);
            e.getValue().stream().forEach(v -> {
                deque.add(v);
                builder.addEdge(m, v);
            });
        });

        // read requires transitive from ModuleDescriptor
        Module source;
        while ((source = deque.poll()) != null) {
            if (visited.contains(source))
                continue;

            visited.add(source);
            builder.addNode(source);
            Module from = source;
            requiresTransitive(from).forEach(m -> {
                deque.add(m);
                builder.addEdge(from, m);
            });
        }
        return builder.build();
    }
889993
public function getAncestryGraph($id)
    {
        $data = $this->getAncestry($id);

        if (count($data) == 0) {
            return [null, null];
        }

        // Create Vertices
        $this->vertices = $this->prepareVertices($data);

        // Create Graph
        $graph = new DirectedGraph();
        foreach ($this->vertices as $vertex) {
            $graph->add_vertex($vertex);
        }

        // Create Relations
        foreach ($data as $content) {
            $graph->create_edge($this->vertices[$content->parent_id], $this->vertices[$content->term_id]);
        }

        return [$this->vertices[$id], $graph];
    }
1290444
public static Graph copyTo(Graph fromGraph, Graph toGraph) {
        AllEdgesIterator eIter = fromGraph.getAllEdges();
        while (eIter.next()) {
            int base = eIter.getBaseNode();
            int adj = eIter.getAdjNode();
            toGraph.edge(base, adj).copyPropertiesFrom(eIter);
        }

        NodeAccess fna = fromGraph.getNodeAccess();
        NodeAccess tna = toGraph.getNodeAccess();
        int nodes = fromGraph.getNodes();
        for (int node = 0; node < nodes; node++) {
            if (tna.is3D())
                tna.setNode(node, fna.getLatitude(node), fna.getLongitude(node), fna.getElevation(node));
            else
                tna.setNode(node, fna.getLatitude(node), fna.getLongitude(node));
        }
        return toGraph;
    }
1316312
public function buildGraph()
    {
        if (!empty($this->connection)) {
            $recoder = new Recorder($this->connection);

            $this->appliedMigrations = $recoder->getApplied();
        }

        $migrations = $this->getMigrations();

        $this->graph = new Graph();

        // first add all the migrations into the graph
        foreach ($migrations as $name => $migration) {
            $this->graph->addNode($migration->getName(), $migration);
        }

        // for each migration set its dependencies
        /** @var $migration Migration */
        foreach ($migrations as $name => $migration) {
            foreach ($migration->getDependency() as $appName => $parent) {
                $this->graph->addDependency(
                    $name,
                    [$appName => $parent],
                    $migration
                );
            }
        }
    }
885053
public function createGraph()
    {
        $graphResult = $this->startVertex->getGraph()->createGraphClone();

        // initialize null flow and check edges
        foreach ($graphResult->getEdges() as $edge) {
            if (!($edge instanceof EdgeDirected)) {
                throw new UnexpectedValueException('Undirected edges not supported for edmonds karp');
            }
            $edge->setFlow(0);
        }

        $idA = $this->startVertex->getId();
        $idB = $this->destinationVertex->getId();

        do {
            // Generate new residual graph and repeat
            $residualAlgorithm = new ResidualGraph($graphResult);
            $graphResidual = $residualAlgorithm->createGraph();

            // 1. Search _shortest_ (number of hops and cheapest) path from s -> t
            $alg = new BreadthFirst($graphResidual->getVertex($idA));
            try {
                $pathFlow = $alg->getWalkTo($graphResidual->getVertex($idB));
            } catch (OutOfBoundsException $e) {
                $pathFlow = NULL;
            }

            // If path exists add the new flow to graph
            if ($pathFlow) {
                // 2. get max flow from path
                $maxFlowValue = $pathFlow->getEdges()->getEdgeOrder(Edges::ORDER_CAPACITY)->getCapacity();

                // 3. add flow to path
                foreach ($pathFlow->getEdges() as $edge) {
                    // try to look for forward edge to increase flow
                    try {
                        $originalEdge = $graphResult->getEdgeClone($edge);
                        $originalEdge->setFlow($originalEdge->getFlow() + $maxFlowValue);
                    // forward edge not found, look for back edge to decrease flow
                    } catch (UnderflowException $e) {
                        $originalEdge = $graphResult->getEdgeCloneInverted($edge);
                        $originalEdge->setFlow($originalEdge->getFlow() - $maxFlowValue);
                    }
                }
            }

        // repeat while we still finds paths with residual capacity to add flow to
        } while ($pathFlow);

        return $graphResult;
    }
443124
public function copy()
    {
        $list = [];
        foreach ($this->getIterator() as $key => $value) {
            $list[$key] = \is_object($value) ? clone $value : $value;
        }

        return $this->createFrom($list);
    }
1085646
def make_subgraph(graph, vertices, edges):
    """"""
    # Copy the entire graph
    local_graph = copy.deepcopy(graph)

    # Remove all the edges that aren't in the list
    edges_to_delete = [x for x in local_graph.get_all_edge_ids() if x not in edges]
    for e in edges_to_delete:
        local_graph.delete_edge_by_id(e)

    # Remove all the vertices that aren't in the list
    nodes_to_delete = [x for x in local_graph.get_all_node_ids() if x not in vertices]
    for n in nodes_to_delete:
        local_graph.delete_node(n)

    return local_graph
229641
public function CloneInstance()
	{
		$result = new ChildNodeIterator();
		$result->AssignFrom( $this );
		$result->excludeComments = $this->excludeComments;
		$result->excludeWhitespace = $this->excludeWhitespace;
		return $result;
	}
478414
public function duplicate()
    {
        if (false === $this->is_duplicated) {
            $this->_duplicate();
            $this->is_duplicated = true;
            $this->node = parent::getNode();
        }
        return $this;
    }