récursion - en galère

Version imprimable

07/02/2006, 16h05
graphicsxp

récursion - en galère

Bonjour,
Avant toute chose je vais détailler les deux tables SQL utilisées par l'algo:

Query (QueryId, QueryName)

QueryLink (QueryLinkId, QueryId, LinkedQueryId)

Voila rien de bien sorcier,vous l'aurez compris dans la table [QueryLink] on peut associer une Query à une autre.

|-Query1
| |
| |-Query2
| |-Query3
|
|-Query2
| |
| |-Query3
|
|-Query4
| |
| |-Query3
|
|-Query3
| |
| |-Query5
|

donne:

Query1 -> Query2 -> Query3 -> Query5
Query1 -> Query3 -> Query5

Query2 -> Query3 -> Query5

Query4 -> Query3 -> Query5

Query3 -> Query5

Comment écrire une fonction qui va me permettre d'obtenir ce shéma? :?

Merci
07/02/2006, 17h27
PRomu@ld

Pas trop compris ce que tu voulais faire ... C'est du SQL, de l'algo ? Une liste chainée ?

Citation:

Voila rien de bien sorcier

Oui et bien rabaisses ton niveau, ou alors j'ai pas compris l'astuce et l'interet ...

Citation:

[QueryLink] on peut associer une Query à une autre.

Alors d'après ce que je comprend, tu veux associer une table à une autre. Pas sur que ce soit réalisable en SQL Pur.
07/02/2006, 17h39
graphicsxp

Citation:

Pas trop compris ce que tu voulais faire

Désolé de m'etre mal exprimé :oops:
C'est de l'algo en effet.

Citation:

Citation:

Voila rien de bien sorcier

Oui et bien rabaisses ton niveau, ou alors j'ai pas compris l'astuce et l'interet ...

Je parlais du shéma SQL, qui est tout simple. La table [Query] a une clée primaire QueryId. La table [QueryLink] a deux clées étrangères sur [Query], qui sont QueryId et LinkedQueryId.

Citation:

Alors d'après ce que je comprend, tu veux associer une table à une autre. Pas sur que ce soit réalisable en SQL Pur.

heu... non en effet tu n'as rien compris :wink: Mais je me suis mal exprimé donc c'est de ma faute.

Je veux construire un graphe pour chaque query dans la table [Query].
Ce graphe doit représenter la Query ainsi que celles auxquelles elle est liée dans la table [QueryLink] (ces dernieres sont liées également a d'autres Queries d'ou la récursivité).
Est-ce plus clair comme cela ?
07/02/2006, 17h49
PRomu@ld

Ok d'accord, bon il faut repartir des bases de la récursivité :

- trouver un point d'arrêt.
- appeller en diminuant les entrée (enfin il faut diminuer quelque chose).

Cependant, pour ton problème de point d'arrêt, je pense que c'est bon : il faut marquer (un peu comme dans un parcours de graphe) chaque query qui est listé (de façon à ne pas y passer deux fois de suite).

En gros c'est :

- tant qu'il reste une query qui est dans la liste des query liées (et non visitée) alors je la parcours.
07/02/2006, 17h54
graphicsxp

Exactement ce que j'ai fais 8)
Sauf que j'ai une petite erreur dans mon algo qui m'embete mais bon je vais trouver. Je te donnerais bien mon algo mais j'ai fais ca en code directement (vb.net). Mais j'ai vérifié au débuggeur et apparemment le résultat obtenu est bon.
Merci

Bon j'ai terminé. Voici le résultat (je dois me débarasser de la derniere fleche mais bon...) et le code:

Citation:

DataPage1->DataPage2->
DataPage2->DataPage1->
NewPage->DataPage1->DataPage2->
NewPage2->DataPage1->DataPage2->

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Private m_arr As New ArrayList
Private m_str As New StringBuilder
 
Public Sub BuildTree()
        Dim dt As DataTable = m_queryLinks.GetAllQueries()
 
        For Each row As DataRow In dt.Rows
            m_arr = New ArrayList
            m_str.Append(row("QueryName").ToString & "->")
            m_arr.Add(CInt(row("QueryId")))
 
            BuildSubTree(m_queryLinks.GetQueries2(CInt(row("QueryId"))))
 
            m_str.Append(vbCrLf)
        Next
        Me.RichTextBox1.Text = m_str.ToString
 End Sub
 
 Public Sub BuildSubTree(ByVal dt As DataTable)
        Dim stopLoop As Boolean = False
        If dt.Rows.Count > 0 Then
            For Each row As DataRow In dt.Rows
                For Each i As Integer In m_arr
                    If CInt(row("QueryId")) = i Then stopLoop = True
                Next
                If Not stopLoop Then
                    m_str.Append(row("QueryName").ToString & "->")
                    m_arr.Add(CInt(row("QueryId")))
                    BuildSubTree(m_queryLinks.GetQueries2(CInt(row("QueryId"))))
                End If
            Next
        End If
    End Sub

Merci

07/02/2006, 18h43
graphicsxp

argh, j'ai enlevé :resolu: car il y a un besoin que vient de rajouter mon cher boss :cry:

Prenons un exemple:
Query1 -> Query2
Query3 -> Query1 -> Query2
Query4 -> Query1

Dans l'exemple ci-dessus, l'association Query1 -> Query2 est contenue dans Query3 -> Query1 -> Query2 donc elle ne dois pas etre affichée.

Comment modifier mon algorithme afin de ne pas montrer cette association?

Merci

Citation:

Envoyé par graphicsxp

Comment modifier mon algorithme afin de ne pas montrer cette association?

De toute façon, si tu gardes la première partie, tu seras obligé de comparer les éléments deux à deux. Donc rajoutes à la fin de ton algorithme:
Code:

1 2 3 4 5 6 7 8 Soit S une liste vide. Pour chaque élément i de la première partie Pour chaque élément j de la première partie Si i <> j et i est compris dans j alors on arrête la recherche Si tous les éléments ont été parcourus, cela veut dire que l'élément i n'est pas inclu dans un autre élément de j, on l'ajoute à la liste S