Visualizzazione dei risultati da 1 a 9 su 9
  1. #1
    Utente di HTML.it
    Registrato dal
    Jun 2003
    Messaggi
    4,826

    [c++]attraversamento grafo xml

    Ciao.
    Devo parsare un xml e creare un grafo per inserire nodi in un controllo ad albero.
    ad es l'xml è:
    <primo>
    <secondo>
    <terzo>
    </terzo>
    </secondo>
    <secondobis>
    <terzobis>
    </terzobis>
    </secondobis>

    </primo>
    e il controllo ad albero
    -primo
    |
    secondo
    | |
    | terzo
    secondobis
    |
    terzobis
    detto cosi' è molto semplice , ma per un xml complesso deve essere sicuro,esiste un algoritmo ?
    possibilmente senza ricorsione.
    grazie.

  2. #2
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,381
    Ci sono librerie apposite per manipolare l'xml.
    Xerces, MSXML, Libxml.
    Quello che ti serve (eventualmente) è fornire un DTD o un XMLSchema per fissare il file xml a cui lavori e validarlo.

  3. #3
    Utente di HTML.it
    Registrato dal
    Jun 2003
    Messaggi
    4,826
    grazie Shodan.
    Il mio problema è generare un grafo che puo' essere un controllo ad albero o una classe Boost::Graph.... o tutte e due insieme.
    Per la classe Boost::graph ho la possibilità di inserire vertici(vengono cosi'chiamati i nodi)e edge (connessione tra due nodi).
    Per la classe treview ho solo una funzione : nodo.insertChild ,che pero' puo essere composta , ad es root.insertChild(nodo1).insertChild(nodo2) ecc.....

    Quindi mi serve per inserire tutti i nodi dell'xml nella posizione corretta del grafo un algoritmo di attraversamento del grafo dell' xml;Partendo dal fatto che ho una funzione che mi legge il nodo corrente dell xml, una funzione che mi restituisce restituisce i figli del nodo corrente e delle funzioni per navigare in "su e in giu"(movetoparent / movetochild) nei nodi.

    Il problema piu' grosso è attraversare il grafo xml e generare le relazioni parent/child tra i nodi.
    Infatti se attraverso e basta il grafo non so come impostare la gerarchia data dall' annidamento dei nodi.
    Su google ho trovato molta roba , solo che volevo una dritta sugli articoli o link da studiare (Attraversamenti e ricerche).
    Grazie.

  4. #4
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,381
    Ancora non mi è chiaro il motivo per cui devi portare i nodi dall'xml in un grafo o in una treeview (l'unico che mi venga in mente è un editor XML), comunque il modo più semplice e facile per attraversare un XML usando API DOM è una procedura ricorsiva (dal momento che un documento XML ha una struttura ad albero.)

    Una cosa del genere insomma (consideralo pseudo codice anche se non lo è)
    codice:
    void check_nodes(const Node& nd) {
    	if (nd.hasChildNodes()) {
    		NodeList ndlist = nd.getChildNodes();
    		for (long sz=0; sz<ndlist.getLength(); ++sz) {
    			Node znd = ndlist.getItem(sz);
    			wcout << znd.getNodeType()<< endl;
    			check_nodes(znd);
    		}
    	}
    }
    Poi per impostare le relazioni all'interno della struttura di destinazione, occorre vedere cosa usi e se ci sono funzioni per effettuare queste relazioni.
    Io mi limito alle funzioni delle librerie XML i cui nodi sanno sempre di chi sono figli o padri.

  5. #5
    Utente di HTML.it
    Registrato dal
    Jun 2003
    Messaggi
    4,826
    scusa shodan se non l'ho detto prima , è una generazione di una visual-scene per collada in cui ogni nodo ha una o piu' trasfomazioni da compiere(rotate,translate,scale) e nella scena gli oggetti si annidano ad es:

    tavolo(RTS trasfomazioneTavolo)--computer sul tavolo RTS(trasformazioneTavolo*trasformazioneComp)-- harddisk su computer su tavolo(RTS trasformazioneTavolo*trasformazioneComp*Trasformaz ioneHardDisk)ecc...

    ma se la scena è una stanza allora avro:

    stanza--tavolo--computer sul tavolo-- harddisk su computer sul tavolo
    |
    sedia--gatto su sedia ecc....


    ogni sottonodo ha la sua trasformazione moltiplicata per le trasfomazioni padre.

  6. #6
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,381
    Mi è venuto in mente dopo che poteva trattarsi di qualcosa di simile (e forse XWolverineX potrà aiutarti meglio di me), però in sostanza non cambia molto la faccenda. Una volta estratti i valori dei nodi (che alla fine sono quelli che ti interessano) dev'essere la libreria di destinazione a consertirti di creare la gerarchia e non conoscendo Boost::Graph non so se abbia funzioni preposte allo scopo.
    Spero almeno ti sia utile lo pseudo codice postato.

  7. #7
    Utente di HTML.it
    Registrato dal
    Jun 2003
    Messaggi
    4,826
    Originariamente inviato da shodan

    Una cosa del genere insomma (consideralo pseudo codice anche se non lo è)
    codice:
    void check_nodes(const Node& nd) {
    	if (nd.hasChildNodes()) {
    		NodeList ndlist = nd.getChildNodes();
    		for (long sz=0; sz<ndlist.getLength(); ++sz) {
    			Node znd = ndlist.getItem(sz);
    			wcout << znd.getNodeType()<< endl;
    			check_nodes(znd);
    		}
    	}
    }
    Ho un problema,si puo' trasformare questa funzione ricorsiva in una funzione non ricorsiva?
    Perchè ho una classe Cimporter e una classe CColladaReader.
    La classe Cimporter è una classe generica di importzione , che non dipende dalla classe ccolladareader , l'ho resa generica per poterla utilizzare su vari tipi di importazione , ad es .3ds(3dstudio) o x.

    Nlla classe Cimporter tutto ha una logica del tipo:

    codice:
    void CImporter::ImportVertex()
    {
    	//chiamo la funzione di reset dei vertici
    	m_pApi->VertexReset();
    	float x,y,z;
    	//finchè il reader mi restituisce true ho un vertice da importare
    	//esco quando non ci sono piu' vertici
    	
    	for(int index = 0;m_pApi->NextVertex();index++)
    	{	
    		if(m_pApi->ImportVertex(&x,&y,&z))
    		{
    			
    			Vertex* v = new Vertex();
    			v->_x = x;
    			v->_y = y;
    			v->_z = z;
    			v->_nx = 0.;
    			v->_ny = 0.;
    			v->_nz = 0.;
    			m_CurrMeshVertexes.push_back(v);			
    		}
    	}
    }
    dove m_pApi è una classe specifica dell'importatore incapsulata che ad es puo' essere Ccolladareader o C3dsreader ed è la classe che fa il lavoro di importazione grezzo dipendente dal tipo di file.Inizializzandp semplicemente la classe m_pApi ad una classe C3dsreader o Ccolladareader cambio il tipo di importazione mentre Cimporter rimane la stessa.

    Ora:
    Nei file 3d bisogna in genere ciclare lo scene graph che descrive l'oggetto e andare ad importare la geometria,il materiale e la posizione per ogni nodo di questo.

    Vorrei utilizzare una struttura del tipo:
    codice:
    m_pApi->VertexReset();
    for(int index = 0;m_pApi->NextVertex();index++)
    {	
    	if(m_pApi->ImportVertex(&x,&y,&z))
    	{
            }
    }
    ma per ciclare i nodi nello scene graph ho una funzione ricorsiva , che non so controlare dalla logica di importazione(Cimporter) , è per questo che chiedo se è possibile rendere la funzione ricorsiva una fuunzione normale.
    Grazie.

    Grazie.

  8. #8
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,381
    Che m_pApi sia solo un'interfaccia istanziata con C3dsreader o Ccolladareader è indice di buon design. Permette di isolare i dettagli implementativi e ragionare a interfaccie e non a implementazioni.

    Detto questo: trasformare una funzione da ricorsiva a iterativa è possibile, ma spesso si rivela poco saggia e contro producente. Lo pseudo codice che ho postato, trasformato in iterativo diventa ingestibile dopo pochi nodi figli che andrebbero analizzati, con la stessa logica del padre, in una lunga catena di if e for annidati.
    Tanto per capirsi:
    codice:
    void check_nodes(const Node& nd) {
    
    	if (nd.hasChildNodes()) {
    		NodeList ndlist = nd.getChildNodes();
    		for (long sz=0; sz<ndlist.getLength(); ++sz) {
    			Node znd = ndlist.getItem(sz);
    
    			if (znd.hasChildNodes()) {
    				NodeList ndlist_a = znd.getChildNodes();
    				for (long sz_a=0; sz_a<ndlist_a.getLength(); ++sz_a) {
    					Node znd_a = ndlist_a.getItem(sz_a);
    
    					if (znd_a.hasChildNodes()) {
    						NodeList ndlist_b = znd_a.getChildNodes();
    						for (long sz_b=0; sz_b<ndlist_b.getLength(); ++sz_b) {
    							Node znd_c = ndlist_b.getItem(sz_a);
    
    							if (znd_c.hasChildNodes()) {
    								// etc.
    							}
    				
    						}
    					}
    		
    				}
    			}
    
    		}
    	}
    }
    e questo supponendo di avere un nodo con almeno un figlio che ha un nodo con almeno un figlio etc.
    Giudica tu se conviene avere una funzione ricorsiva o iterativa.

    ma per ciclare i nodi nello scene graph ho una funzione ricorsiva , che non so controlare dalla logica di importazione(Cimporter)
    Cioè? Che funzione ricorsiva?
    Considera comunque che CImporter::ImportVertex() può richiamare una procedura ricorsiva ad hoc e tramite quella analizzare l'albero di vertex e sotto vertex vari.
    Es.
    codice:
    void CImporter::ImportVertex()
    {
    	//chiamo la funzione di reset dei vertici
    	m_pApi->VertexReset();
            this->privateImportVertex(); 
    }
    //--------------------------------
    void CImporter::privateImportVertex() {
        if ( m_pApi->NextVertex() ) {
            float x,y,z;
            if( m_pApi->ImportVertex(&x,&y,&z) ) {
    			Vertex* v = new Vertex();
    			v->_x = x;
    			v->_y = y;
    			v->_z = z;
    			v->_nx = 0.;
    			v->_ny = 0.;
    			v->_nz = 0.;
    			m_CurrMeshVertexes.push_back(v);			
    	}
            this->privateImportVertex(); 
        }
    }

  9. #9
    Utente di HTML.it
    Registrato dal
    Jun 2003
    Messaggi
    4,826
    grazie shodan,ma ho risolto con una lista FIFO e una funzione non ricorsiva.
    In pratica faccio fare alla lista quello che fa lo stack con le variabili.
    Ho letto qui molte cose interessanti sui grafi , soprattutto il depth-first search.
    Ho adattato questa funzione:
    codice:
    Another version, without the recursion:
    
    dfs(graph G)
    {
      list L = empty
      tree T = empty
      choose a starting vertex x
      search(x)
      while(L is not empty)
      {
        remove edge (v, w) from beginning of L
        if w not yet visited
        {
          add (v, w) to T
          search(w)
        }
      }
    }
       
    search(vertex v)
    {
      visit v
      for each edge (v, w)
        add edge (v, w) to the beginning of L
    }

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.