News Technology

Lista Delle Adiacenze Per Implementare Un Grafo Con PHP

19 Agosto 2007 di Daniele Frulla

---

Qui di seguito trovate il codice della classe che costruisce un semplice grafo e ne cancella un nodo:

[php]
<?php // La lista delle adiacenze in php class Nodo { //Classe del Nodo che comprende la lista dei nodi ed il puntatore ai nodi adiacenti     var $key;     var $next;     var $prev;     var $adjprev;     var $adjnext;     function Nodo($key = NULL)     {         $this->key = $key;
        $this->next = NULL;
        $this->prev = NULL;
        $this->adjnext = NULL;
        $this->adjprev = NULL;            
    }
}

class ListaAdj
{
    var $head;
    function ListaAdj()
    { // Costruttore della lista delle  adiacenze
        $this->head = NULL;
    }
    
    function InsertNodo($k)
    {  // Inserisco il nodo. Si suppone che non esista il nuovo nodo
        $item = new Nodo($k);
        $item->next = &$this->head;
        if(!is_null($this->head)) $this->head->prev = &$item; //Se head non Null l’item precedente punta al nuovo elemento
        $this->head = &$item;
        $this->head->prev = NULL;
    }
    
    function InsertAdj($n1, $n2)
    {  // Inserisco l’adiacenza al nodo $n1. Nessun controllo sull’esistenza di $n1
        $cerca_n1 = &$this->CercaNodo($n1);
        $newadj = new Nodo($n2);
        if (!is_null($cerca_n1->adjnext)) $cerca_n1->adjnext->adjprev = &$newadj;
        $newadj->adjnext = &$cerca_n1->adjnext;
        $newadj->adjprev = &$cerca_n1;
        $cerca_n1->adjnext = &$newadj;
    }
        
    function DeleteNodo($n1)
    { // Devo cancellare anche tutte le adiacenze che hanno il nodo $n1
        $x=&$this->head; echo "Cancello Nodo ".$n1."<BR>";
        do
        {
            if(!@is_null($x))
            {
                if ($x->key == $n1)
                {
                    if (!is_null($x->prev)) $x->prev->next=&$x->next;
                    else $this->head=&$x->next;
                }
                else
                { // Cancello le adiacenze se ci sono
                    $nadj = &$this->CercaAdj($x->key, $n1);
                    if (!is_null($nadj))
                    {
                        if (!is_null($nadj->adjprev)) $nadj->adjprev->adjnext = &$nadj->adjnext;
                        else $nadj = &$nadj->adjnext;
                    }
                }
            }
            $x=&$x->next;
        }
        while(!is_null($x));
    }
    
    function ShowNodi()
    {
        echo "la lista contiene:
";
        $x=&$this->head;
        do
        {
            if(!@is_null($x->key))
            {
                echo ‘- NODO:’.$x->key."
";
            //    $this->ShowAdj($x->key);
            }    
            $x=&$x->next;
        }
        while(!is_null($x));
    }
    
    function ShowAdjTot()
    {
        echo "la lista contiene:
";
        $x=&$this->head;
        do
        {
            if(!@is_null($x->key))
            {
                echo " – NODO ".$x->key." : ";
                $a = &$x->adjnext;
                while(!is_null($a))
                {    echo " –>".$a->key."<– ";                     $a = &$a->adjnext;
                }
            }
            echo " <BR>";
            $x = &$x->next;
        }
        while(!is_null($x));
    }
    
    function ShowAdj($n1)
    {
        echo " – NODO ".$n1." adiacente a : ";

        $x = &$this->CercaNodo($n1);
        do
        {
            if(!@is_null($x->adjnext))
            {
                echo "–> ".$x->adjnext->key."<–";             }                 $x=&$x->adjnext;
        }
        while(!is_null($x->adjnext));
        echo " <BR>";
    }
    
    function &CercaAdj($n1, $n2)
    { // Cerca se  il nodo $n1 ha adiacenza $n2 in caso ne restituisce il riferimento
        $x = &$this->CercaNodo($n1);
        while(!@is_null($x) && @$x->key!= $n2)
        {
                $x=&$x->adjnext;
        }    
        return $x;
    }
    function &CercaNodo($k)
    { // Ritorna il puntatore all’elemento $k
        $x=&$this->head;
        while(!is_null($x) && @$x->key!=$k)
        {
            $x=&$x->next;
        }
        return $x;
    }
}

$Grafo= new ListaAdj();

$Grafo->InsertNodo(1);
$Grafo->InsertNodo(2);
$Grafo->InsertNodo(3);
$Grafo->InsertNodo(4);
$Grafo->InsertAdj(3,9);
$Grafo->InsertAdj(3,2);
$Grafo->InsertAdj(1,3);
$Grafo->InsertAdj(2,3);
$Grafo->InsertAdj(2,4);
$Grafo->InsertAdj(1,4);
$Grafo->InsertAdj(1,2);
$Grafo->InsertAdj(4,2);

$Grafo->ShowAdjTot();
$Grafo->DeleteNodo(4);
$Grafo->ShowAdjTot();

?>
[/php]

Questa classe si può migliorare e può essere un punto di partenza per applicazioni più complesse che utilizzano i grafi come struttura base.

Fonte: www.newstechnology.eu