Discussion :

[mathieu_r]

Bonjour,

J'ai à ma disposition un graphe représentant des rivières dans lequel chaque noeud a, soit la catégorie "croisement", soit "riviere".

J'aimerais pouvoir partir dans toutes les directions à partir d'un noeud de type "croisement" afin de voir quels sont les noeuds "croisement" autour selon une condition.
La condition est que tous les noeuds qui se situent entre mon départ et d'arrivée, soient de type "rivière" et qu'ils soient de degré 2 (ce qui signifie pas d'embranchement à leur niveau).

Voici un petit dessin qui montre ce que je souhaite (avec un cercle, les noeuds croisement) :


Auriez-vous une idée sur la marche à suivre ?

Bien à vous,

Mathieu

[dev_ggy]

Bonjour,

que penses tu des bases de données orientées graph pour résoudre tes problèmes, mais on sort complètement du cadre de langage R.

Bien cordialement

[mathieu_r]

Bonjour,

Je ne connais pas les bases de données graphe.

A la base, je possède des données géographiques desquelles je dérive un graphe. R permet d'effectuer le traitement de la source, de l'intégration des données à leur transformation.

A vrai dire, je travaille ici sur un cas bien précis. Je n'ai jamais eu à travailler avec les réseaux avant et cela risque peu de se représenter plus tard.

J'apprends donc au fur et à mesure avec le langage que je connais, R. Je ne pense pas investir dans une autre technologie d'autant plus que je pense avoir à disposition tous les outils qu'il faut avec R et igraph.

Encore une fois, si vous avez une idée pour le problème cité, je suis preneur

[Emmanuel R]

Bonsoir,

Je pense que tu peux t'inspirer de l'algorithme de parcours en profondeur.
C'est une fonction récursive. Du coup pour marquer les sommets visités, il te faut une variable globale, que tu modifieras avec la syntaxe "x <<- ..."

A côté de ça, tu ajoutes un test lorsque tu arrives sur un sommet. Lorsque le noeud respecte la condition que tu nous a donné, tu le définis comme croisement. Par exemple sur un vecteur de la taille du nombre de sommets, tu mettras "1".

Mais bon, après ce n'est pas trop du R, c'est plus de l'algorithmie...

[mathieu_r]

Bonjour Emmanuel et à tous,

J'ai créé ma fonction récursive de DFS en m'appuyant sur un exemple test basé sur un graphe de 10 noeuds auxquels sont attribués les couleur "rose" et "orange".

Ici, je choisis, à partir d'un noeud, de détecter le premier noeud "rouge" rencontré, et ce, dans toutes les "directions".

Je pense arriver quasiment au bout car mon algo détecte bien les noeuds "rouges". Par contre, j'éprouve des difficultés à stocker dans une variable la liste de ces noeuds.

Voici le code reproductible, si jamais vous avez une idée (on y est presque, je pense )

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
library(igraph)
 
g <- make_tree(10, mode="undirected")
a <- as_adj_list(g)
 
V(g)$color <- "orange"
V(g)$color[c(5,6,7,9)] <- "red"
 
 
dfs.f <- function(a, s, nodes=NULL, okNodes=NULL) {
  nodes <- c(s, nodes)
 
  for (child in a[[s]]) {
    if (!(child %in% nodes)) {
 
      v <- V(g)[child]
      cat(v, v$color, "\n")
 
      if(v$color=="red") {
        okNodes <<- c(as.numeric(v), okNodes)
        return
      } else {
        dfs.f(a, child, nodes, okNodes)
      }
    }
  }
}
 
# dfs.f(adjacency list, root node)
res <- dfs.f(a, 1)
 
okNodes #cette variable globale insérée dans ma boucle ne renvoie qu'un élément au lieu de 4

[mathieu_r]

Par tâtonnements, j'ai abouti à ce code, bien qu'il me paraisse assez peu orthodoxe..

Je pense que je maîtrise finalement peu les rouages de la programmatique avancée, le système des récursions, des variables globales.

Voici donc mon code qui fonctionne pour ce que je veux mais qui fait un peu "bricolage".

En particulier, j'aimerais, plutôt que d'employer une variable globale, avoir une fonction qui me retourne comme résultat la liste des noeuds "rouges" rencontrés.

N'hésitez pas pour toute suggestion !

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
library(igraph)
 
g <- make_tree(10, mode="undirected")
a <- as_adj_list(g)
 
V(g)$color <- "orange"
V(g)$color[c(5,6,7,9)] <- "red"
 
 
okNodes <- NULL
 
dfs.f <- function(a, s, nodes=NULL) {
  nodes <- c(s, nodes)
 
  for (child in a[[s]]) {
    if (!(child %in% nodes)) {
 
      v <- V(g)[child]
 
      if(v$color=="red") {
        okNodes <<- c(okNodes, as.numeric(v))
        return
      } else {
        dfs.f(a, child, nodes)
      }
    }
  }
}
 
# dfs.f(adjacency list, root node)
res <- dfs.f(a, 1)
# res ne renvoie rien puisque return ne renvoie pas de variable : c'est cela que j'aimerais accomplir..
okNodes

[mathieu_r]

Bonjour,

Une solution m'a été donnée sur un autre forum.

La voici :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
findRed <- function(graph,node) {
  paths  <- get.shortest.paths(graph,node,V(graph)[V(graph)$color=="red"])$vpath
  colors <- lapply(paths, function(x) V(graph)$color[x] )
  unique(Map(function(p,c) as.vector(p[seq(1,match("red",c))]), paths, colors))
}

Merci pour vos lumières