GraphUtils::predecessorsOf() - Code Metrics - bingo-soft/graphp - Measure and Improve Code Quality continuously with Scrutinizer

GraphUtils::predecessorsOf() A
last analyzed 2019-11-25 13:29 UTC

↳ Parent: GraphUtils

Complexity

Conditions	2
Paths	2

Size

Total Lines	8
Code Lines	5

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	6
CRAP Score	2

Importance

Changes

Metric	Value
cc	2
eloc	5
nc	2
nop	2
dl	0
loc	8
rs	10
c	0
b	0
f	0
ccs	6
cts	6
cp	1
crap	2

<?php

namespace Graphp;

use Exception;
use InvalidArgumentException;
use Graphp\Edge\EdgeInterface;
use Graphp\Edge\EdgeSet;
use Graphp\Vertex\VertexInterface;
use Graphp\Vertex\VertexSet;

/**
 * Class GraphUtils
 *
 * @package Graphp
 */
class GraphUtils
{
    /**
     * Create a new edge and add it to the specified graph
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $sourceVertex - the source vertex
     * @param VertexInterface $targetVertex - the target vertex
     * @param float $weight - the weight of the edge being added
     *
     * @return EdgeInterface
     */
    public static function addEdge(
        GraphInterface $graph,
        VertexInterface $sourceVertex,
        VertexInterface $targetVertex,
        ?float $weight = null
    ): ?EdgeInterface {
        $edgeSupplier = $graph->getEdgeSupplier();
        if (is_null($edgeSupplier)) {
            throw new Exception("Graph contains no edge supplier");
        }
        $edge = $edgeSupplier->get();

        if ($graph->addEdge($sourceVertex, $targetVertex, $edge)) {
            if ($graph->getType()->isWeighted()) {
                $graph->setEdgeWeight($edge, $weight);
            }
            return $edge;
        }
        return null;
    }

    /**
     * Add the speficied source and target vertices to the graph
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $sourceVertex - the source vertex
     * @param VertexInterface $targetVertex - the target vertex
     * @param float $weight - the weight of the edge being added
     *
     * @return EdgeInterface
     */
    public static function addEdgeWithVertices(
        GraphInterface $graph,
        VertexInterface $sourceVertex,
        VertexInterface $targetVertex,
        ?float $weight = null
    ): EdgeInterface {
        $graph->addVertex($sourceVertex);
        $graph->addVertex($targetVertex);
        return self::addEdge($graph, $sourceVertex, $targetVertex, $weight);

    }

    /**
     * Add all the vertices and all the edges of the source graph to the target graph.
     * Return true, if the target graph was changed
     *
     * @param GraphInterface $targetGraph - the target graph
     * @param GraphInterface $sourceGraph - the source graph
     *
     * @return bool
     */
    public static function addGraph(GraphInterface $targetGraph, GraphInterface $sourceGraph): bool
    {
        $modified = self::addAllVertices($targetGraph, $sourceGraph->vertexSet());
        return self::addAllEdges($targetGraph, $sourceGraph, $sourceGraph->edgeSet()) || $modified;
    }

    /**
     * Add all vertices to the specified graph.
     * Return true, if the graph was modified
     *
     * @param GraphInterface $graph - the target graph
     * @param VertexSet $vertices - the vertices
     *
     * @return bool
     */
    public static function addAllVertices(GraphInterface $graph, VertexSet $vertices): bool
    {
        $modified = false;
        foreach ($vertices as $vertex) {
            $modified = $graph->addVertex($vertex) || $modified;
        }
        return $modified;
    }

    /**
     * Add all edges of the source graph to the target graph.
     * Return true, if the graph was modified
     *
     * @param GraphInterface $targetGraph - the target graph
     * @param GraphInterface $sourceGraph - the source graph
     * @param EdgeSet $edges - the edges to add
     *
     * @return bool
     */
    public static function addAllEdges(
        GraphInterface $targetGraph,
        GraphInterface $sourceGraph,
        EdgeSet $edges
    ): bool {
        $modified = false;
        foreach ($edges as $edge) {
            $sourceVertex = $sourceGraph->getEdgeSource($edge);
            $targetVertex = $sourceGraph->getEdgeTarget($edge);
            $targetGraph->addVertex($sourceVertex);
            $targetGraph->addVertex($targetVertex);
            $modified = $targetGraph->addEdge($sourceVertex, $targetVertex, $edge) || $modified;
        }
        return $modified;
    }

    /**
     * Add all the vertices and all the edges of the source graph to the target graph in the reversed order
     *
     * @param GraphInterface $targetGraph - the target graph
     * @param GraphInterface $sourceGraph - the source graph
     */
    public static function addGraphReversed(GraphInterface $targetGraph, GraphInterface $sourceGraph): void
    {
        if (!$sourceGraph->getType()->isDirected() || !$targetGraph->getType()->isDirected()) {
            throw new InvalidArgumentException("graph must be directed");
        }

        self::addAllVertices($targetGraph, $sourceGraph->vertexSet());

        $edges = $sourceGraph->edgeSet();
        foreach ($edges as $edge) {
            $targetGraph->addEdge($sourceGraph->getEdgeTarget($edge), $sourceGraph->getEdgeSource($edge));
        }
    }

    /**
     * Get a list of vertices that are the neighbors of a specified vertex.
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the vertex
     *
     * @return array
     */
    public static function neighborsOf(GraphInterface $graph, VertexInterface $vertex): array
    {
        $neighbors = [];
        $edges = $graph->edgesOf($vertex);
        foreach ($edges as $edge) {
            $neighbors[] = self::getOppositeVertex($graph, $edge, $vertex);
        }
        return $neighbors;
    }

    /**
     * Get a list of vertices that are the direct predecessors of a specified vertex.
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the vertex
     *
     * @return array
     */
    public static function predecessorsOf(GraphInterface $graph, VertexInterface $vertex): array
    {
        $neighbors = [];
        $edges = $graph->incomingEdgesOf($vertex);
        foreach ($edges as $edge) {
            $neighbors[] = self::getOppositeVertex($graph, $edge, $vertex);
        }
        return $neighbors;
    }

    /**
     * Get a list of vertices that are the direct successors of a specified vertex.
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the vertex
     *
     * @return array
     */
    public static function successorsOf(GraphInterface $graph, VertexInterface $vertex): array
    {
        $neighbors = [];
        $edges = $graph->outgoingEdgesOf($vertex);
        foreach ($edges as $edge) {
            $neighbors[] = self::getOppositeVertex($graph, $edge, $vertex);
        }
        return $neighbors;
    }

    /**
     * Test whether an edge is incident to a vertex.
     *
     * @param GraphInterface $graph - the graph
     * @param EdgeInterface $edge - the edge
     * @param VertexInterface $vertex - the vertex
     *
     * @return bool
     */
    public static function testIncidence(GraphInterface $graph, EdgeInterface $edge, VertexInterface $vertex): bool
    {
        return $graph->getEdgeSource($edge)->equals($vertex)
               || $graph->getEdgeTarget($edge)->equals($vertex);
    }

    /**
     * Get the vertex opposite another vertex across an edge.
     *
     * @param GraphInterface $graph - the graph
     * @param EdgeInterface $edge - the edge
     * @param VertexInterface $vertex - the vertex
     *
     * @return VertexInterface
     */
    public static function getOppositeVertex(
        GraphInterface $graph,
        EdgeInterface $edge,
        VertexInterface $vertex
    ): VertexInterface {
        $source = $graph->getEdgeSource($edge);
        $target = $graph->getEdgeTarget($edge);
        if ($vertex->equals($source)) {
            return $target;
        } elseif ($vertex->equals($target)) {
            return $source;
        } else {
            throw new InvalidArgumentException("no such vertex: " . (string) $vertex);
        }
    }

    /**
     * Remove the given vertices from the given graph. If the vertex to be removed has one or more
     * predecessors, the predecessors will be connected directly to the successors of the vertex to
     * be removed.
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the vertex to be removed
     * @param mixed $vertices - the remaining vertices
     *
     * @return bool
     */
    public static function removeVertexAndPreserveConnectivity(
        GraphInterface $graph,
        VertexInterface $vertex,
        ...$vertices
    ): bool {
        if (!$graph->containsVertex($vertex)) {
            return false;
        }

        $vertices[] = $vertex;
        foreach ($vertices as $vertex) {
            if (self::vertexHasPredecessors($graph, $vertex)) {
                $predecessors = self::predecessorsOf($graph, $vertex);
                $successors = self::successorsOf($graph, $vertex);

                foreach ($predecessors as $predecessor) {
                    self::addOutgoingEdges($graph, $predecessor, ...$successors);
                }
            }
            $graph->removeVertex($vertex);
        }

        return true;
    }

    /**
     * Add edges from one source vertex to multiple target vertices
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the source vertex
     * @param mixed $vertices - the target vertices
     */
    public static function addOutgoingEdges(GraphInterface $graph, VertexInterface $vertex, ...$vertices): void
    {
        if (!$graph->containsVertex($vertex)) {
            $graph->addVertex($vertex);
        }
        foreach ($vertices as $target) {
            if (!$graph->containsVertex($target)) {
                $graph->addVertex($target);
            }
            $graph->addEdge($vertex, $target);
        }
    }

    /**
     * Add edges from multiple source vertices to one target vertex
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the target vertex
     * @param mixed $vertices - the source vertices
     */
    public static function addIncomingEdges(GraphInterface $graph, VertexInterface $vertex, ...$vertices): void
    {
        if (!$graph->containsVertex($vertex)) {
            $graph->addVertex($vertex);
        }
        foreach ($vertices as $source) {
            if (!$graph->containsVertex($source)) {
                $graph->addVertex($source);
            }
            $graph->addEdge($source, $vertex);
        }
    }

    /**
     * Check if the vertex has direct successors
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the vertex
     *
     * @return bool
     */
    public static function vertexHasSuccessors(GraphInterface $graph, VertexInterface $vertex): bool
    {
        return count($graph->outgoingEdgesOf($vertex)) > 0;
    }

    /**
     * Check if the vertex has direct predecessors
     *
     * @param GraphInterface $graph - the graph
     * @param VertexInterface $vertex - the vertex
     *
     * @return bool
     */
    public static function vertexHasPredecessors(GraphInterface $graph, VertexInterface $vertex): bool
    {
        return count($graph->incomingEdgesOf($vertex)) > 0;
    }
}


1		<?php
2
3		namespace Graphp;
4
5		use Exception;
6		use InvalidArgumentException;
7		use Graphp\Edge\EdgeInterface;
8		use Graphp\Edge\EdgeSet;
9		use Graphp\Vertex\VertexInterface;
10		use Graphp\Vertex\VertexSet;
11
12		/**
13		* Class GraphUtils
14		*
15		* @package Graphp
16		*/
17		class GraphUtils
18		{
19		/**
20		* Create a new edge and add it to the specified graph
21		*
22		* @param GraphInterface $graph - the graph
23		* @param VertexInterface $sourceVertex - the source vertex
24		* @param VertexInterface $targetVertex - the target vertex
25		* @param float $weight - the weight of the edge being added
26		*
27		* @return EdgeInterface
28		*/
29	9	public static function addEdge(
30		GraphInterface $graph,
31		VertexInterface $sourceVertex,
32		VertexInterface $targetVertex,
33		?float $weight = null
34		): ?EdgeInterface {
35	9	$edgeSupplier = $graph->getEdgeSupplier();
36	9	if (is_null($edgeSupplier)) {
37		throw new Exception("Graph contains no edge supplier");
38		}
39	9	$edge = $edgeSupplier->get();
40
41	9	if ($graph->addEdge($sourceVertex, $targetVertex, $edge)) {
42	9	if ($graph->getType()->isWeighted()) {
43	4	$graph->setEdgeWeight($edge, $weight);
44		}
45	9	return $edge;
46		}
47	1	return null;
48		}
49
50		/**
51		* Add the speficied source and target vertices to the graph
52		*
53		* @param GraphInterface $graph - the graph
54		* @param VertexInterface $sourceVertex - the source vertex
55		* @param VertexInterface $targetVertex - the target vertex
56		* @param float $weight - the weight of the edge being added
57		*
58		* @return EdgeInterface
59		*/
60	5	public static function addEdgeWithVertices(
61		GraphInterface $graph,
62		VertexInterface $sourceVertex,
63		VertexInterface $targetVertex,
64		?float $weight = null
65		): EdgeInterface {
66	5	$graph->addVertex($sourceVertex);
67	5	$graph->addVertex($targetVertex);
68	5	return self::addEdge($graph, $sourceVertex, $targetVertex, $weight);
		0 ignored issues – show Bug Best Practice introduced 2019-11-25 12:19 UTC by Report Bug Copy Issue Report The expression `return self::addEdge($gr...$targetVertex, $weight)` could return the type `null` which is incompatible with the type-hinted return `Graphp\Edge\EdgeInterface`. Consider adding an additional type-check to rule them out. Loading history...
69		}
70
71		/**
72		* Add all the vertices and all the edges of the source graph to the target graph.
73		* Return true, if the target graph was changed
74		*
75		* @param GraphInterface $targetGraph - the target graph
76		* @param GraphInterface $sourceGraph - the source graph
77		*
78		* @return bool
79		*/
80	2	public static function addGraph(GraphInterface $targetGraph, GraphInterface $sourceGraph): bool
81		{
82	2	$modified = self::addAllVertices($targetGraph, $sourceGraph->vertexSet());
83	2	return self::addAllEdges($targetGraph, $sourceGraph, $sourceGraph->edgeSet()) \|\| $modified;
84		}
85
86		/**
87		* Add all vertices to the specified graph.
88		* Return true, if the graph was modified
89		*
90		* @param GraphInterface $graph - the target graph
91		* @param VertexSet $vertices - the vertices
92		*
93		* @return bool
94		*/
95	15	public static function addAllVertices(GraphInterface $graph, VertexSet $vertices): bool
96		{
97	15	$modified = false;
98	15	foreach ($vertices as $vertex) {
99	15	$modified = $graph->addVertex($vertex) \|\| $modified;
100		}
101	15	return $modified;
102		}
103
104		/**
105		* Add all edges of the source graph to the target graph.
106		* Return true, if the graph was modified
107		*
108		* @param GraphInterface $targetGraph - the target graph
109		* @param GraphInterface $sourceGraph - the source graph
110		* @param EdgeSet $edges - the edges to add
111		*
112		* @return bool
113		*/
114	2	public static function addAllEdges(
115		GraphInterface $targetGraph,
116		GraphInterface $sourceGraph,
117		EdgeSet $edges
118		): bool {
119	2	$modified = false;
120	2	foreach ($edges as $edge) {
121	2	$sourceVertex = $sourceGraph->getEdgeSource($edge);
122	2	$targetVertex = $sourceGraph->getEdgeTarget($edge);
123	2	$targetGraph->addVertex($sourceVertex);
124	2	$targetGraph->addVertex($targetVertex);
125	2	$modified = $targetGraph->addEdge($sourceVertex, $targetVertex, $edge) \|\| $modified;
126		}
127	2	return $modified;
128		}
129
130		/**
131		* Add all the vertices and all the edges of the source graph to the target graph in the reversed order
132		*
133		* @param GraphInterface $targetGraph - the target graph
134		* @param GraphInterface $sourceGraph - the source graph
135		*/
136	1	public static function addGraphReversed(GraphInterface $targetGraph, GraphInterface $sourceGraph): void
137		{
138	1	if (!$sourceGraph->getType()->isDirected() \|\| !$targetGraph->getType()->isDirected()) {
139		throw new InvalidArgumentException("graph must be directed");
140		}
141
142	1	self::addAllVertices($targetGraph, $sourceGraph->vertexSet());
143
144	1	$edges = $sourceGraph->edgeSet();
145	1	foreach ($edges as $edge) {
146	1	$targetGraph->addEdge($sourceGraph->getEdgeTarget($edge), $sourceGraph->getEdgeSource($edge));
147		}
148	1	}
149
150		/**
151		* Get a list of vertices that are the neighbors of a specified vertex.
152		*
153		* @param GraphInterface $graph - the graph
154		* @param VertexInterface $vertex - the vertex
155		*
156		* @return array
157		*/
158	3	public static function neighborsOf(GraphInterface $graph, VertexInterface $vertex): array
159		{
160	3	$neighbors = [];
161	3	$edges = $graph->edgesOf($vertex);
162	3	foreach ($edges as $edge) {
163	3	$neighbors[] = self::getOppositeVertex($graph, $edge, $vertex);
164		}
165	3	return $neighbors;
166		}
167
168		/**
169		* Get a list of vertices that are the direct predecessors of a specified vertex.
170		*
171		* @param GraphInterface $graph - the graph
172		* @param VertexInterface $vertex - the vertex
173		*
174		* @return array
175		*/
176	2	public static function predecessorsOf(GraphInterface $graph, VertexInterface $vertex): array
177		{
178	2	$neighbors = [];
179	2	$edges = $graph->incomingEdgesOf($vertex);
180	2	foreach ($edges as $edge) {
181	2	$neighbors[] = self::getOppositeVertex($graph, $edge, $vertex);
182		}
183	2	return $neighbors;
184		}
185
186		/**
187		* Get a list of vertices that are the direct successors of a specified vertex.
188		*
189		* @param GraphInterface $graph - the graph
190		* @param VertexInterface $vertex - the vertex
191		*
192		* @return array
193		*/
194	1	public static function successorsOf(GraphInterface $graph, VertexInterface $vertex): array
195		{
196	1	$neighbors = [];
197	1	$edges = $graph->outgoingEdgesOf($vertex);
198	1	foreach ($edges as $edge) {
199	1	$neighbors[] = self::getOppositeVertex($graph, $edge, $vertex);
200		}
201	1	return $neighbors;
202		}
203
204		/**
205		* Test whether an edge is incident to a vertex.
206		*
207		* @param GraphInterface $graph - the graph
208		* @param EdgeInterface $edge - the edge
209		* @param VertexInterface $vertex - the vertex
210		*
211		* @return bool
212		*/
213	3	public static function testIncidence(GraphInterface $graph, EdgeInterface $edge, VertexInterface $vertex): bool
214		{
215	3	return $graph->getEdgeSource($edge)->equals($vertex)
216	3	\|\| $graph->getEdgeTarget($edge)->equals($vertex);
217		}
218
219		/**
220		* Get the vertex opposite another vertex across an edge.
221		*
222		* @param GraphInterface $graph - the graph
223		* @param EdgeInterface $edge - the edge
224		* @param VertexInterface $vertex - the vertex
225		*
226		* @return VertexInterface
227		*/
228	15	public static function getOppositeVertex(
229		GraphInterface $graph,
230		EdgeInterface $edge,
231		VertexInterface $vertex
232		): VertexInterface {
233	15	$source = $graph->getEdgeSource($edge);
234	15	$target = $graph->getEdgeTarget($edge);
235	15	if ($vertex->equals($source)) {
236	12	return $target;
237	12	} elseif ($vertex->equals($target)) {
238	12	return $source;
239		} else {
240		throw new InvalidArgumentException("no such vertex: " . (string) $vertex);
241		}
242		}
243
244		/**
245		* Remove the given vertices from the given graph. If the vertex to be removed has one or more
246		* predecessors, the predecessors will be connected directly to the successors of the vertex to
247		* be removed.
248		*
249		* @param GraphInterface $graph - the graph
250		* @param VertexInterface $vertex - the vertex to be removed
251		* @param mixed $vertices - the remaining vertices
252		*
253		* @return bool
254		*/
255	1	public static function removeVertexAndPreserveConnectivity(
256		GraphInterface $graph,
257		VertexInterface $vertex,
258		...$vertices
259		): bool {
260	1	if (!$graph->containsVertex($vertex)) {
261		return false;
262		}
263
264	1	$vertices[] = $vertex;
265	1	foreach ($vertices as $vertex) {
266	1	if (self::vertexHasPredecessors($graph, $vertex)) {
267	1	$predecessors = self::predecessorsOf($graph, $vertex);
268	1	$successors = self::successorsOf($graph, $vertex);
269
270	1	foreach ($predecessors as $predecessor) {
271	1	self::addOutgoingEdges($graph, $predecessor, ...$successors);
272		}
273		}
274	1	$graph->removeVertex($vertex);
275		}
276
277	1	return true;
278		}
279
280		/**
281		* Add edges from one source vertex to multiple target vertices
282		*
283		* @param GraphInterface $graph - the graph
284		* @param VertexInterface $vertex - the source vertex
285		* @param mixed $vertices - the target vertices
286		*/
287	2	public static function addOutgoingEdges(GraphInterface $graph, VertexInterface $vertex, ...$vertices): void
288		{
289	2	if (!$graph->containsVertex($vertex)) {
290		$graph->addVertex($vertex);
291		}
292	2	foreach ($vertices as $target) {
293	2	if (!$graph->containsVertex($target)) {
294	1	$graph->addVertex($target);
295		}
296	2	$graph->addEdge($vertex, $target);
297		}
298	2	}
299
300		/**
301		* Add edges from multiple source vertices to one target vertex
302		*
303		* @param GraphInterface $graph - the graph
304		* @param VertexInterface $vertex - the target vertex
305		* @param mixed $vertices - the source vertices
306		*/
307	1	public static function addIncomingEdges(GraphInterface $graph, VertexInterface $vertex, ...$vertices): void
308		{
309	1	if (!$graph->containsVertex($vertex)) {
310		$graph->addVertex($vertex);
311		}
312	1	foreach ($vertices as $source) {
313	1	if (!$graph->containsVertex($source)) {
314	1	$graph->addVertex($source);
315		}
316	1	$graph->addEdge($source, $vertex);
317		}
318	1	}
319
320		/**
321		* Check if the vertex has direct successors
322		*
323		* @param GraphInterface $graph - the graph
324		* @param VertexInterface $vertex - the vertex
325		*
326		* @return bool
327		*/
328	1	public static function vertexHasSuccessors(GraphInterface $graph, VertexInterface $vertex): bool
329		{
330	1	return count($graph->outgoingEdgesOf($vertex)) > 0;
331		}
332
333		/**
334		* Check if the vertex has direct predecessors
335		*
336		* @param GraphInterface $graph - the graph
337		* @param VertexInterface $vertex - the vertex
338		*
339		* @return bool
340		*/
341	2	public static function vertexHasPredecessors(GraphInterface $graph, VertexInterface $vertex): bool
342		{
343	2	return count($graph->incomingEdgesOf($vertex)) > 0;
344		}
345		}
346

bingo-soft / graphp

GraphUtils::predecessorsOf() A last analyzed 2019-11-25 13:29 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

GraphUtils::predecessorsOf() A
last analyzed 2019-11-25 13:29 UTC