CODEWITHSUNDEEP
phpalgorithmgraphtree
user1949713
user1949713

Reputation: 101

Heaviest path in special graph (PHP)

I have to search the heaviest path in graph what like:

        1

      2  1

    4  5  8

  2  2  3  4

(1,1,8,4 in this example) The graph like this ever. So it is an element who has two children except lowermosts. Who has children they has a common child e.g. (in above graph) 5 (in 3. row) is a common child to 2 and 1 (in 2. row.). So these are nodes and not edges and them have a value.

I wrote an algorithm in php:

class node{
    public $children = array();
    public $value;
    public $_heavier = null;
    public $_value = null;

    function __construct($value, $children) {
        $this->value = $value;
        $this->children = $children;
    }

    function heavier() {
        if (null !== $this->_value) {
            echo 'b' . $this->value . '<br>';
            return $this->_value;
        }

        $val = $this->value;

        if ($this->children[0]) {
            $c1 = $this->children[0]->heavier();
            $c2 = $this->children[1]->heavier();

            if ($c1 > $c2) {
                $this->_heavier = 0;
                $val += $c1;
            } else {
                $this->_heavier = 1;
                $val += $c2;
            }
        }

        echo 'a' . $this->value . '<br>';
        $this->_value = $val;

        return $val;
    }

    function getPath() {
        if (null !== $this->_heavier) {
            echo $this->children[$this->_heavier]->getPath();
        }
        return $this->value;
    }
}

$exists = array();
function a($row, $item) {
    global $input, $exists;

    $nextRow = $row + 1;
    $child1No = $item;
    $child2No = $item + 1;

    $child1 = null;
    if (isset($input[$nextRow][$child1No])) {
        $child1 = a($nextRow, $child1No);
    }

    $child2 = null;
    if (isset($input[$nextRow][$child2No])) {
        $child2 = a($nextRow, $child2No);
    }

    if (!isset($exists[$row][$item])) {
        $obj = new node($input[$row][$item], array($child1, $child2));
        $exists[$row][$item] = &$obj;
    } else {
        $obj = &$exists[$row][$item];
    }
    return $obj;
}

$nodes = a(0, 0);
$nodes->heavier();
echo $nodes->getPath();
echo '<br>';

It is works, but too much time. How to speed up?

Thx.

Upvotes: 1

Views: 102

Answers (1)

Boris Strandjev
Boris Strandjev

Reputation: 46943

Your algorithm is the most optimal possible - you take O(n) time where n is the number of nodes. It can easily be proved that nothing faster can be done.

I think the slow part of your algorithm is the echo-ing - this is a very heavy operation and might slow your algorithm quite a bit as you echo too much.

PS: By the way on how many nodes you execute your algorithm? Is it really on only 10?

Upvotes: 1

Related Questions