NYCPHP Meetup

[Kenneth Downs]

Jonathan,

Glad this helped.

If your graphs get big then you must do this in a database, don't attempt
it in scripts.

Many people recommend mySQl because it is free, but PostgreSQL is far more
capable and is also free.

> Hi Kenneth,
>
> Thanks very much. I like what you have posted!
> I think I would add keys to the arrays and add one more dimension so
> that there can be multiple graphs with the same label.
>
> $arcs['likes'][]  = array('a','a');
> $arcs['likes'][]  = array('a','b');
> $arcs['knows'][]  = array('a','b');
>
> $arcs['knows'][]  = array('b','a');
> $arcs['confusedby'][]  = array('b','a');
>
>  I can get the functionality I need from this.
> I wonder how scalable this is. What if there are over 5 million arcs. My
> traversal algorithms would have to be very efficient.
>
> Another package I am looking at for graph manipulation is bundled with
> the PHP RDF package RAP.
>
> http://www.wiwiss.fu-berlin.de/suhl/bizer/rdfapi
> http://www.wiwiss.fu-berlin.de/suhl/bizer/rdfapi/tutorial/usingNamedGraphs.htm#ng-intro
>
> They use quads - where a quad is a labeled graph. In the above data
> structure, a new graph would just be a new set of arcs. So it looks like
> nothing is missing from this array based graph.
>
> Hmm, or why not
>
> $arcs['a']['likes']['b'] = true;
> $arcs['b']['likes']['b'] = false;
> or
> $arcs['b']['likes']['chocolate'][] = '80%';
> $arcs['b']['likes']['chocolate'][] = 'quite significantly';
>
> Then I can have a "triple" with a label and a value.
>
> This could be interesting.
>
>
>
>
>
>
>
>
>
>
> Kenneth Downs wrote:
>
>>Johathan,
>>
>>Have you considered putting the nodes into one array, and the arcs into a
>>second?
>>
>>$nodes = array('a'=>array(..info..),'b'=>array(..info..));
>>
>>$arcs = array(array('a','b'),array('b','a'))
>>
>>This allows each node's info to be stored only once, and allows you to
>>then treat the arcs cleanly, allowing or disallowing any combo you may
>>choose.
>>
>>You may have to write a little of your code to walk through things, but
>>you'll have complete integrity and control.
>>
>>
>>
>>>I'm trying to formulate a question out of this. If there isn't one here,
>>>I hope the read is interesting.
>>>My goal is to create the simplest efficient graph data structures - that
>>>allow for cycles.
>>>
>>>The reason one would want cycles in a graph is the following:
>>>a->b
>>>and
>>>b->a
>>>(or b->a again with another arc (also known as a hypergraph))
>>>or
>>>a->a
>>>
>>> where '->' is an arc
>>>Even if the arcs are labled, the data in 'a' is something I don't want
>>>to duplicate.
>>>
>>>I am using php version 4.3.11
>>>
>>>If I try to do this with a simple php array:
>>>
>>>    $a = array();
>>>    $b = array();
>>>
>>>    $a['b'] = & $b;
>>>    $b['a'] = & $a;
>>>
>>>    print_r($a);
>>>
>>>Array
>>>(
>>>    [a] => Array
>>>        (
>>>            [b] => Array
>>>                (
>>>                    [a] => Array
>>> *RECURSION*
>>>                )
>>>
>>>        )
>>>
>>>)
>>>
>>>
>>>I get this recursion error. Or, perhaps this is not an error at all. But
>>>I can't seem to use this function:
>>>
>>>    function recursive_print($array)
>>>    {
>>>        foreach($array as $key => $value)
>>>        {
>>>            if (is_array($value))
>>>            {
>>>                echo $key .' <hr /> ' .recursive_print($value);
>>>            }
>>>            else
>>>            {
>>>                echo 'end'.$value;
>>>            }
>>>        }
>>>    }
>>>
>>>So I went to the PEAR site -
>>> http://pear.php.net/package/Structures_Graph
>>>This pear package doesn't throw any errors but it also seems to balk  -
>>>although I am not sure the *RECURSION* will affect functionality
>>>
>>>
>>>    include 'Structures/Graph.php';
>>>    $directedGraph =& new Structures_Graph(true);
>>>    $nodeOne =& new Structures_Graph_Node();
>>>    $nodeTwo =& new Structures_Graph_Node();
>>>
>>>
>>>    $directedGraph->addNode(&$nodeOne);
>>>    $directedGraph->addNode(&$nodeTwo);
>>>
>>>
>>>    $nodeOne->connectTo($nodeTwo);
>>>    $nodeTwo->connectTo($nodeOne);
>>>
>>>
>>>Inside the code I found a comment about the Zend engine before the data
>>>structure procedes to iteratively loop through the the nodes to see if
>>>there are duplicates.
>>>            /*
>>>             ZE1 equality operators choke on the recursive cycle
>>>introduced by the _graph field in the Node object.
>>>             So, we'll check references the hard way
>>>            */
>>>
>>>Even so, print_r produces many recursion warnings.
>>>
>>>Maybe I am just trying to use a hammer for a screwdriver. But can anyone
>>>offer any insight here?
>>>
>>>Thanks,
>>>
>>>- Jonathan Hendler
>>>
>>>
>>>
>>>_______________________________________________
>>>New York PHP Talk Mailing List
>>>AMP Technology
>>>Supporting Apache, MySQL and PHP
>>>http://lists.nyphp.org/mailman/listinfo/talk
>>>http://www.nyphp.org
>>>
>>>
>>
>>
>>
>>
>
> _______________________________________________
> New York PHP Talk Mailing List
> AMP Technology
> Supporting Apache, MySQL and PHP
> http://lists.nyphp.org/mailman/listinfo/talk
> http://www.nyphp.org
>


-- 
Kenneth Downs
Secure Data Software
631-379-0010
ken at secdat.com
PO Box 708
East Setauket, NY 11733