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

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

↳ Parent: EdgeWeightedGraph

Complexity

Conditions	3
Paths	3

Size

Total Lines	31
Code Lines	13

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	3
eloc	13
nc	3
nop	1
dl	0
loc	31
rs	9.8333
c	0
b	0
f	0

<?php

namespace TemplesOfCode\NodesAndEdges;

use InvalidArgumentException;

/**
 * Class EdgeWeightedGraph
 * @package TemplesOfCode\NodesAndEdges
 */
class EdgeWeightedGraph extends Graph
{
    /**
     * @param Edge $e
     */
    public function addEdge(Edge $e)
    {
        // get one side of edge (a vertex)
        $v = $e->either();
        // get the other side (a vertex)
        $w = $e->other($v);
        // validate the vertex
        Graph::validateVertex($v, $this->vertices);
        // validate the vertex
        Graph::validateVertex($v, $this->vertices);
        // link the edge to v
        $this->adjacencyList[$v][] = $e;
        // link the edge to w
        $this->adjacencyList[$w][] = $e;
        // increment the tracker
        $this->edges++;
    }

    /**
     * Returns all edges in this edge-weighted graph.
     *
     * @return array all edges in this edge-weighted graph, as an iterable
     */
    public function getAllEdges()
    {
        // init
        $allEdges = [];
        // iterate over the set of vertices
        for ($vertex = 0; $vertex < $this->getVertices(); $vertex++) {
            // init
            /** @var array $neighbors */
            $neighbors = $this->adjacencyList[$vertex];
            // iterate over the set of neighbors
            foreach ($neighbors as $neighbor) {
                /** @var Edge $neighbor */
                // get v
                $v = $neighbor->either();
                // get w
                $w = $neighbor->other($v);
                // get weight
                $weight = $neighbor->weight();
                // add to the list
                $allEdges[] = new Edge($v, $w, $weight);
            }
        }
        return $allEdges;
    }

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

    /**
     * Initializes a new graph that is a deep copy of $g
     *
     * @param EdgeWeightedGraph $g
     * @return EdgeWeightedGraph
     */
    public static function fromGraph(EdgeWeightedGraph $g)
    {
        // get the number of vertices
        $vertices = $g->getVertices();
        // init
        $adjacencyList = [];
        // iterate over the vertices
        for ($vertex = 0; $vertex < $vertices; $vertex++) {
            // get the adjacent vertices
            $neighbors = $g->adjacent($vertex);
            // init
            $myAdjacencyList = [];
            // iterate over them
            foreach ($neighbors as $edge) {
                /** @var Edge $e */
                // get one side of edge (a vertex)
                $v = $edge->either();
                // get the other side (a vertex)
                $w = $edge->other($v);
                // get the weight
                $weight = $edge->weight();
                // create a new edge and set it
                $e = new Edge($v, $w, $weight);
                // add the edge to the list
                $myAdjacencyList[] = $e;
            }
            // set this set
            $adjacencyList[$vertex] = $myAdjacencyList;
        }
        // return the new graph
        return new EdgeWeightedGraph($vertices, $adjacencyList);
    }

    /**
     * @param string $graph
     * @return EdgeWeightedGraph
     */
    public static function fromString(string $graph)
    {
        // parse the lines
        $lines = explode("\n", $graph);
        // extract V and E
        list (
            $vertices,
            $edges
        ) = self::parseGraphVEFromString($lines[0], $lines[1]);
        // instantiate a new graph
        $graph = new EdgeWeightedGraph($vertices);
        // remove first two lines
        $lines = array_slice($lines, 2);
        // process it
        self::buildWeightedEdgesFromString($graph, $vertices, $edges, $lines);
        // return the built graph
        return $graph;
    }

    /**
     * Initializes a random edge-weighted graph with $v vertices and $e edges.
     *
     * @param int $vertices the number of vertices
     * @param int $edges the number of edges
     * @return EdgeWeightedGraph
     */
    public static function fromRandom(int $vertices, int $edges)
    {
        // sanity check
        if ($edges < 0) {
            // not acceptable
            throw new InvalidArgumentException(
                'Number of edges must be non-negative'
            );
        }
        // instantiate a new graph
        $graph = new EdgeWeightedGraph($vertices);
        // init
        $taken = [];
        // iterate over the edges
        for ($i = 0; $i <$edges; $i++) {
            // generate an edge
            do {
                // generate
                $v = mt_rand(0, $vertices);
                // generate
                $w = mt_rand(0, $vertices);
                // check
                $pairTaken = in_array(
                    sprintf('%d-%d', $v, $w),
                    $taken
                );
            } while ($v == $w && !$pairTaken);
            // add to the set
            $taken[] = $pairTaken;
            // generate weight
            $weight = ((float)(mt_rand(0, 100)));
            // create the edge
            $edge = new Edge($v, $w, $weight);
            // add it to the graph
            $graph->addEdge($edge);
        }
        // return the graph
        return $graph;
    }

    /**
     * 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 EdgeWeightedGraph
     */
    protected 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 EdgeWeightedGraph($vertices);
        // read in the edges
        for ($i = 0; $i < $edges; $i++) {
            // fet from source
            $raw = fgets($handle);
            // parse data
            list (
                $v,
                $w,
                $weight
            ) = self::parseEdge($raw, $vertices, true);
            // create the edge
            $edge = new Edge($v, $w, $weight);
            // add it to the graph
            $graph->addEdge($edge);
        }
        // rewind the stream
        rewind($handle);
        // return the built graph
        return $graph;
    }
}


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

templesofcode / nodes-and-edges

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

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

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