Dijkstra algorithm in php?

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
jmut
Forum Regular
Posts: 945
Joined: Tue Jul 05, 2005 3:54 am
Location: Sofia, Bulgaria
Contact:

Dijkstra algorithm in php?

Post by jmut »

anyone has this algorithm implemented in php?
searched google, and this forums but no real answer.
Thanks
jmut
Forum Regular
Posts: 945
Joined: Tue Jul 05, 2005 3:54 am
Location: Sofia, Bulgaria
Contact:

Post by jmut »

hm...I am now not sure if this is the algorithm I need.
I found this written in pseudo code but the prerequisites does not quite match my situation.
http://www.devmaster.net/articles/pathfinding/



My case:


I have several sources of data (nodes) - DB, urls, XLS..whatever
- each source has:

Code: Select all

0..*  INS
0...* OUTS    which will be used as INS by other sources(nodes).

- several sources (nodes) may have the same/overlaping INS/OUTS.


so this means:
1. From node to node I can have more than one edge (path between neighbour source).
2. I dont know the edges(paths between source) in advance.

Because of these two, I don't think I can impelment this algorithm (as stated in the link I gave).



Here is more specific exmaple of the problem:

Target is source C from source A to find ips basted on customer_id

Code: Select all

source A
IN(s) - customer_id
OUT(s) - phone_number, server_name


source B
IN(s) - server_name
OUT(s) - network_id

source C
IN(s) - networ_id
OUT(s) - ips
Solution in this case is

Code: Select all

IN  (using customer_id)-> SourceA -> (using server_name) -> source B  -> (using network_id) ->source C-> ips   OUT
so the problem is how to find such possible paths (because they can be more than one apperantly.)


Any ideas :roll:
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

Whoa that looks really complicated. May I ask what you are making and why you need this?

Otherwise there seems to be Pseudocode in Wikipedia so you'll have to work from that yourself unless you can find anyone else who is prepaired to do. Remember if you have any specific difficulties you can always come back here for help.
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

OK yeah I definately need to know why you have this fantasic nodes arrangement and also how they are stored.
jmut
Forum Regular
Posts: 945
Joined: Tue Jul 05, 2005 3:54 am
Location: Sofia, Bulgaria
Contact:

Post by jmut »

ole wrote:OK yeah I definately need to know why you have this fantasic nodes arrangement and also how they are stored.
:)

here is the goal: you search in more than one source of data (different source have different output structure,input requirements and so on) for related information.

So once you describe what INs make sense for the source of data and what OUTs (results you can get from data...results like keys I mean...like to use as other INs) you can search for complex data within various sources of data...and come up with some useful information.

like in the example I gave.... you search for ips but you only have customer_id.

the source with the data that knows about ip have no idea what customer_id is...but it knows network_id....etc.
so different source are combinded dynamically and voalla.
of course, you have to make the assumption that customer_id in data source A means the exact same thing in source X


so you start searching by something....give the program from witch module or whatever you need data...and it looks either directly to get data or through other sources to make the relation.


When I am thinking these sources of data are actually nodes :)

To make this one step further...it is all about making search enginge within a company for example. all data, many systems...and when you need something specific you have to go through several interfaces to get what you need. this what problem this is supposed to solve (ultimately there will be ajax stuff...some boxes you group together or something to specify the data you need gathered.). If you need other sources...you just define what keys (INs) it can search by...and what data it can provide....and it will be automatically integrated to the global picture.

Maybe some more advanced methods are there...I am absolutely sure...but so far this is my approach to the problem :)
User avatar
Ollie Saunders
DevNet Master
Posts: 3179
Joined: Tue May 24, 2005 6:01 pm
Location: UK

Post by Ollie Saunders »

Whilst I understand all that I couldn't begin to help you with it. Good luck.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Post by Weirdan »

From what I understand, once you construct the graph of interconnected sources you can use it in Dijkstra's algorithm. Constructing the graph of sources and all possible connections is the part you need to do before you start implement D alg.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Post by Weirdan »

here is simple framework to experiment on (if you haven't implemented yours already):

Code: Select all

 
<?php
class node {
    private static $_instanceCount = 0;
    private $connections = array();
    private $_nodeID = 0;
    public $ins = array();
    public $outs = array();
    public function connect(node $node) {
        $this->connections[] = $node;
    }
    public function __construct($ins, $outs) {
        $this->_nodeID = ++self::$_instanceCount;
        $this->ins = $ins;
        $this->outs = $outs;
    }
    public function __toString() {
        return 'Node #' . $this->_nodeID;
    }
    public function showConnected() {
        $ret = array();
        foreach($this->connections as $nextNode) {
            $ret[] = (string) $nextNode;
        }
        return $ret;
    }
}
 
function indexIns($listOfNodes) {
    $ret = array();
    foreach($listOfNodes as $node) {
        foreach($node->ins as $in) {
            if(!isset($ret[$in]) || !is_array($ret[$in])) 
                $ret[$in] = array();
            $ret[$in][] = $node;
        }
    }
    return $ret;
}
 
function dumpIndex($index) {
    foreach($index as $in => $nodeList) {
        echo $in . ' => ' . 
            join(', ', array_map(
                        create_function('$q', 'return $q->__toString();'), 
                        $nodeList
                        )
            ) . PHP_EOL;
    }
}
 
function interconnectNodes($nodes, $index) {
    foreach($nodes as $node) {
        foreach($node->outs as $out) {
            if(!isset($index[$out]) || !is_array($index[$out])) // free out
                continue;
            foreach($index[$out] as $nextNode) {
                $node->connect($nextNode);
            }
        }
    }
}
 
function dumpConnections($nodes) {
    foreach($nodes as $node) {
        echo $node, ' is connected to ' . implode(', ', $node->showConnected()) . PHP_EOL;
    }
}
 
$nodes = array();
$nodes[] = new Node($ins = array('network_id'), $outs = array('ip'));
$nodes[] = new Node($ins = array('customer_id'), $outs = array('phone_number', 'server_name'));
$nodes[] = new Node($ins = array('customer_id','server_name'), $outs = array('network_id'));
 
$index = indexIns($nodes);
dumpIndex($index);
interconnectNodes($nodes, $index);
dumpConnections($nodes);
?>
 
things that you can optimise:
  1. index node on its creation
  2. make your algorithm work on index instead of working with actual graph
jmut
Forum Regular
Posts: 945
Joined: Tue Jul 05, 2005 3:54 am
Location: Sofia, Bulgaria
Contact:

Post by jmut »

thank you both for assistance, sorry for late reply.
I will take a look at this snippet.
well, we'll see , generally it is more or less a simple problems, or at least it looks like :)
I am just not very much into algorithms yet :)
jmut
Forum Regular
Posts: 945
Joined: Tue Jul 05, 2005 3:54 am
Location: Sofia, Bulgaria
Contact:

Post by jmut »

Weirdan wrote:here is simple framework to experiment on (if you haven't implemented yours already):

Code: Select all

<?php
class node {
    private static $_instanceCount = 0;
    private $connections = array();
    private $_nodeID = 0;
    public $ins = array();
    public $outs = array();
    public function connect(node $node) {
        $this->connections[] = $node;
    }
    public function __construct($ins, $outs) {
        $this->_nodeID = ++self::$_instanceCount;
        $this->ins = $ins;
        $this->outs = $outs;
    }
    public function __toString() {
        return 'Node #' . $this->_nodeID;
    }
    public function showConnected() {
        $ret = array();
        foreach($this->connections as $nextNode) {
            $ret[] = (string) $nextNode;
        }
        return $ret;
    }
}

function indexIns($listOfNodes) {
    $ret = array();
    foreach($listOfNodes as $node) {
        foreach($node->ins as $in) {
            if(!isset($ret[$in]) || !is_array($ret[$in])) 
                $ret[$in] = array();
            $ret[$in][] = $node;
        }
    }
    return $ret;
}

function dumpIndex($index) {
    foreach($index as $in => $nodeList) {
        echo $in . ' => ' . 
            join(', ', array_map(
                        create_function('$q', 'return $q->__toString();'), 
                        $nodeList
                        )
            ) . PHP_EOL;
    }
}

function interconnectNodes($nodes, $index) {
    foreach($nodes as $node) {
        foreach($node->outs as $out) {
            if(!isset($index[$out]) || !is_array($index[$out])) // free out
                continue;
            foreach($index[$out] as $nextNode) {
                $node->connect($nextNode);
            }
        }
    }
}

function dumpConnections($nodes) {
    foreach($nodes as $node) {
        echo $node, ' is connected to ' . implode(', ', $node->showConnected()) . PHP_EOL;
    }
}

$nodes = array();
$nodes[] = new Node($ins = array('network_id'), $outs = array('ip'));
$nodes[] = new Node($ins = array('customer_id'), $outs = array('phone_number', 'server_name'));
$nodes[] = new Node($ins = array('customer_id','server_name'), $outs = array('network_id'));

$index = indexIns($nodes);
dumpIndex($index);
interconnectNodes($nodes, $index);
dumpConnections($nodes);
?>
things that you can optimise:
  1. index node on its creation
  2. make your algorithm work on index instead of working with actual graph
just wanted to say thanks. gave me a quick start on this one.
User avatar
Weirdan
Moderator
Posts: 5978
Joined: Mon Nov 03, 2003 6:13 pm
Location: Odessa, Ukraine

Post by Weirdan »

just wanted to say thanks. gave me a quick start on this one.
So, how is it going?
jmut
Forum Regular
Posts: 945
Joined: Tue Jul 05, 2005 3:54 am
Location: Sofia, Bulgaria
Contact:

Post by jmut »

Weirdan wrote:
just wanted to say thanks. gave me a quick start on this one.
So, how is it going?
we'll see today :)
I will post code when I have my solution...on how I find routes.
Post Reply