Page 1 of 1

Dijkstra algorithm in php?

Posted: Fri Aug 11, 2006 8:55 am
by jmut
anyone has this algorithm implemented in php?
searched google, and this forums but no real answer.
Thanks

Posted: Fri Aug 11, 2006 9:27 am
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:

Posted: Fri Aug 11, 2006 9:33 am
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.

Posted: Fri Aug 11, 2006 9:36 am
by Ollie Saunders
OK yeah I definately need to know why you have this fantasic nodes arrangement and also how they are stored.

Posted: Fri Aug 11, 2006 10:00 am
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 :)

Posted: Fri Aug 11, 2006 10:41 am
by Ollie Saunders
Whilst I understand all that I couldn't begin to help you with it. Good luck.

Posted: Fri Aug 11, 2006 10:56 am
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.

Posted: Fri Aug 11, 2006 11:50 am
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

Posted: Sun Aug 13, 2006 4:02 am
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 :)

Posted: Mon Aug 14, 2006 2:07 am
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.

Posted: Mon Aug 14, 2006 2:38 am
by Weirdan
just wanted to say thanks. gave me a quick start on this one.
So, how is it going?

Posted: Mon Aug 14, 2006 3:02 am
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.