Digraph::fromGraph() - Code Metrics - templesofcode/nodes-and-edges - Measure and Improve Code Quality continuously with Scrutinizer

Digraph::fromGraph() A
last analyzed 2020-05-06 14:27 UTC

↳ Parent: Digraph

Complexity

Conditions	3
Paths	3

Size

Total Lines	18
Code Lines	7

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	3
eloc	7
nc	3
nop	1
dl	0
loc	18
rs	10
c	0
b	0
f	0

<?php

namespace TemplesOfCode\NodesAndEdges;

use InvalidArgumentException;

/**
 * Class Digraph
 * @package TemplesOfCode\NodesAndEdges
 */
class Digraph extends Graph
{
    /**
     * @var array
     */
    protected $inDegree;

    /**
     * Digraph constructor.
     *
     * @param int $vertices
     * @param array|null $adjacencyList
     */
    public function __construct(int $vertices, array $adjacencyList = null)
    {
        // delegate to parent tasks
        parent::__construct($vertices, $adjacencyList);
        // init
        $this->inDegree = array_fill(0, $vertices, 0);
    }

    /**
     * @param int $v
     * @param int $w
     */
    public function addEdge(int $v, int $w)
    {
        // validate the vertex
        Graph::validateVertex($v, $this->vertices);
        // validate the vertex
        Graph::validateVertex($w, $this->vertices);
        // link the edge to v
        $this->adjacencyList[$v][] = $w;
        // increment the in-degree
        $this->inDegree[$w]++;
        // increment the tracker
        $this->edges++;
    }

    /**
     * Returns the number of directed edges incident from vertex v
     * This is known as the out-degree of vertex v
     *
     * @param int $v the vertex
     * @return int the out-degree of vertex v
     * @throws InvalidArgumentException unless 0 <= v < V
     */
    public function outDegree(int $v)
    {
        // validate
        Graph::validateVertex($v, $this->getVertices());
        // return the count
        return count($this->adjacencyList[$v]);
    }

    /**
     * Returns the number of directed edges incident to vertex v
     * This is known as the in-degree of vertex v
     *
     * @param int $v the vertex
     * @return int the in-degree of vertex v
     * @throws InvalidArgumentException unless 0 <= v < V
     */
    public function inDegree(int $v)
    {
        // validate it
        Graph::validateVertex($v, $this->getVertices());
        // return the count
        return $this->inDegree[$v];
    }

    /**
     * Returns the reverse of the digraph.
     *
     * @return Graph the reverse of the digraph
     */
    public function reverse()
    {
        // get set
        $vertices = $this->getVertices();
        // init
        $reverse = new Digraph($vertices);
        // iterate over the vertices
        for ($vertex = 0; $vertex < $vertices; $vertex++) {
            // get the neighbors
            $neighbors = $this->adjacent($vertex);
            // iterate over the neighbors
            foreach ($neighbors as $w) {
                // add the reverse
                $reverse->addEdge($w, $vertex);
            }
        }
        // return the new digraph
        return $reverse;
    }

    /**
     * Initializes an edge-weighted graph from an input stream.
     * The format is the number of $vertices,
     * followed by the number of $edges ,
     * followed by $edges pairs of vertices and edge weights,
     * with each entry separated by whitespace.
     *
     * @param resource $handle the input stream
     * @return Digraph
     */
    public static function fromStream($handle)
    {
        // sanity check
        if (!is_resource($handle) || $handle === null) {
            // bad state
            throw new InvalidArgumentException(
                'argument is null'
            );
        }
        // parse V and E
        list(
            $vertices,
            $edges
        ) = self::parseGraphVEFromResource($handle);
        // instantiate a new graph
        $graph = new Digraph($vertices);
        // read in the edges
        for ($i = 0; $i < $edges; $i++) {
            // fet from source
            $raw = fgets($handle);
            // parse data
            list (
                $v,
                $w
            ) = self::parseEdge($raw, $vertices);
            // add it to the graph
            $graph->addEdge($v, $w);
        }
        // rewind the stream
        rewind($handle);
        // return the built graph
        return $graph;
    }

    /**
     * Initializes a new digraph that is a deep copy of $g
     *
     * @param Digraph $g
     * @return Digraph
     */
    public static function fromGraph(Digraph $g)
    {
        // make sure there is a references
        if (is_null($g)) {
            // bad state
            throw new InvalidArgumentException('argument is null');
        }
        // get the number of vertices
        $vertices = $g->getVertices();
        // init
        $adjacencyList = [];
        // iterate over the vertices
        for ($vertex = 0; $vertex < $vertices; $vertex++) {
            // get the adjacent vertices
            $adjacencyList[$vertex] = $g->adjacent($vertex);
        }
        // return the new graph
        return new Digraph($vertices, $adjacencyList);
    }

    /**
     *
     * @param string $file
     * @return Digraph
     */
    public static function fromFile(string $file)
    {
        // open the stream for reading
        if (!$handle = fopen($file, 'r')) {
            throw new InvalidArgumentException('could not open stream');
        }
        // parse V and E
        list(
            $vertices,
            $edges
        ) = self::parseGraphVEFromResource($handle);
        // instantiate a new graph
        $graph = new Digraph($vertices);

        // read in the edges
        for ($i = 0; $i < $edges; $i++) {
            // fet from source
            $raw = fgets($handle);
            // parse data
            list (
                $v,
                $w
            ) = self::parseEdge($raw, $vertices);
            // add to the graph
            $graph->addEdge($v, $w);
        }
        // close the stream
        fclose($handle);
        // return the built graph
        return $graph;
    }

    /**
     *
     * @param string $graph
     * @return Digraph
     */
    public static function fromString(string $graph)
    {
        // parse the lines
        $lines = explode("\n", $graph);
        // parse V and E
        list (
            $vertices,
            $edges
        ) = self::parseGraphVEFromString($lines[0], $lines[1]);
        // instantiate a new graph
        $graph = new Digraph($vertices);
        // read in the edges
        for ($i = 0; $i < $edges; $i++) {
            // fet from source
            $raw = $lines[$i+2];
            // parse data
            list (
                $v,
                $w
            ) = self::parseEdge($raw, $vertices);
            // add to the graph
            $graph->addEdge($v, $w);
        }
        // return the built graph
        return $graph;
    }
}

1			<?php
2
3			namespace TemplesOfCode\NodesAndEdges;
4
5			use InvalidArgumentException;
6
7			/**
8			* Class Digraph
9			* @package TemplesOfCode\NodesAndEdges
10			*/
11			class Digraph extends Graph
12			{
13			/**
14			* @var array
15			*/
16			protected $inDegree;
17
18			/**
19			* Digraph constructor.
20			*
21			* @param int $vertices
22			* @param array\|null $adjacencyList
23			*/
24			public function __construct(int $vertices, array $adjacencyList = null)
25			{
26			// delegate to parent tasks
27			parent::__construct($vertices, $adjacencyList);
28			// init
29			$this->inDegree = array_fill(0, $vertices, 0);
30			}
31
32			/**
33			* @param int $v
34			* @param int $w
35			*/
36			public function addEdge(int $v, int $w)
37			{
38			// validate the vertex
39			Graph::validateVertex($v, $this->vertices);
40			// validate the vertex
41			Graph::validateVertex($w, $this->vertices);
42			// link the edge to v
43			$this->adjacencyList[$v][] = $w;
44			// increment the in-degree
45			$this->inDegree[$w]++;
46			// increment the tracker
47			$this->edges++;
48			}
49
50			/**
51			* Returns the number of directed edges incident from vertex v
52			* This is known as the out-degree of vertex v
53			*
54			* @param int $v the vertex
55			* @return int the out-degree of vertex v
56			* @throws InvalidArgumentException unless 0 <= v < V
57			*/
58			public function outDegree(int $v)
59			{
60			// validate
61			Graph::validateVertex($v, $this->getVertices());
62			// return the count
63			return count($this->adjacencyList[$v]);
64			}
65
66			/**
67			* Returns the number of directed edges incident to vertex v
68			* This is known as the in-degree of vertex v
69			*
70			* @param int $v the vertex
71			* @return int the in-degree of vertex v
72			* @throws InvalidArgumentException unless 0 <= v < V
73			*/
74			public function inDegree(int $v)
75			{
76			// validate it
77			Graph::validateVertex($v, $this->getVertices());
78			// return the count
79			return $this->inDegree[$v];
80			}
81
82			/**
83			* Returns the reverse of the digraph.
84			*
85			* @return Graph the reverse of the digraph
86			*/
87			public function reverse()
88			{
89			// get set
90			$vertices = $this->getVertices();
91			// init
92			$reverse = new Digraph($vertices);
93			// iterate over the vertices
94			for ($vertex = 0; $vertex < $vertices; $vertex++) {
95			// get the neighbors
96			$neighbors = $this->adjacent($vertex);
97			// iterate over the neighbors
98			foreach ($neighbors as $w) {
99			// add the reverse
100			$reverse->addEdge($w, $vertex);
101			}
102			}
103			// return the new digraph
104			return $reverse;
105			}
106
107			/**
108			* Initializes an edge-weighted graph from an input stream.
109			* The format is the number of $vertices,
110			* followed by the number of $edges ,
111			* followed by $edges pairs of vertices and edge weights,
112			* with each entry separated by whitespace.
113			*
114			* @param resource $handle the input stream
115			* @return Digraph
116			*/
117			public static function fromStream($handle)
118			{
119			// sanity check
120			if (!is_resource($handle) \|\| $handle === null) {
121			// bad state
122			throw new InvalidArgumentException(
123			'argument is null'
124			);
125			}
126			// parse V and E
127			list(
128			$vertices,
129			$edges
130			) = self::parseGraphVEFromResource($handle);
131			// instantiate a new graph
132			$graph = new Digraph($vertices);
133			// read in the edges
134			for ($i = 0; $i < $edges; $i++) {
135			// fet from source
136			$raw = fgets($handle);
137			// parse data
138			list (
139			$v,
140			$w
141			) = self::parseEdge($raw, $vertices);
142			// add it to the graph
143			$graph->addEdge($v, $w);
144			}
145			// rewind the stream
146			rewind($handle);
147			// return the built graph
148			return $graph;
149			}
150
151			/**
152			* Initializes a new digraph that is a deep copy of $g
153			*
154			* @param Digraph $g
155			* @return Digraph
156			*/
157			public static function fromGraph(Digraph $g)
158			{
159			// make sure there is a references
160			if (is_null($g)) {
161			// bad state
162			throw new InvalidArgumentException('argument is null');
163			}
164			// get the number of vertices
165			$vertices = $g->getVertices();
166			// init
167			$adjacencyList = [];
168			// iterate over the vertices
169			for ($vertex = 0; $vertex < $vertices; $vertex++) {
170			// get the adjacent vertices
171			$adjacencyList[$vertex] = $g->adjacent($vertex);
172			}
173			// return the new graph
174			return new Digraph($vertices, $adjacencyList);
175			}
176
177			/**
178			*
179			* @param string $file
180			* @return Digraph
181			*/
182			public static function fromFile(string $file)
183			{
184			// open the stream for reading
185			if (!$handle = fopen($file, 'r')) {
186			throw new InvalidArgumentException('could not open stream');
187			}
188			// parse V and E
189			list(
190			$vertices,
191			$edges
192			) = self::parseGraphVEFromResource($handle);
193			// instantiate a new graph
194			$graph = new Digraph($vertices);
195
196			// read in the edges
197			for ($i = 0; $i < $edges; $i++) {
198			// fet from source
199			$raw = fgets($handle);
200			// parse data
201			list (
202			$v,
203			$w
204			) = self::parseEdge($raw, $vertices);
205			// add to the graph
206			$graph->addEdge($v, $w);
207			}
208			// close the stream
209			fclose($handle);
210			// return the built graph
211			return $graph;
212			}
213
214			/**
215			*
216			* @param string $graph
217			* @return Digraph
218			*/
219			public static function fromString(string $graph)
220			{
221			// parse the lines
222			$lines = explode("\n", $graph);
223			// parse V and E
224			list (
225			$vertices,
226			$edges
227			) = self::parseGraphVEFromString($lines[0], $lines[1]);
228			// instantiate a new graph
229			$graph = new Digraph($vertices);
230			// read in the edges
231			for ($i = 0; $i < $edges; $i++) {
232			// fet from source
233			$raw = $lines[$i+2];
234			// parse data
235			list (
236			$v,
237			$w
238			) = self::parseEdge($raw, $vertices);
239			// add to the graph
240			$graph->addEdge($v, $w);
241			}
242			// return the built graph
243			return $graph;
244			}
245			}

templesofcode / nodes-and-edges

Digraph::fromGraph() A last analyzed 2020-05-06 14:27 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

Digraph::fromGraph() A
last analyzed 2020-05-06 14:27 UTC