Determing valid directed graph selections

[GreyMerchant]

Hello,

There are two things I am hoping to get right:

1. I have the following data below. I want to be able to cut invalid selection columns. Invalid selection columns are those that contain both "a -> b" and "b -> a" as an example, i.e. if the source = target and the target = source for two path combinations then it shouldn't be valid as it can only be directed into a single direction between those nodes. See example data below:

df1 <- data.frame(
  stringsAsFactors = FALSE,
            source = c("a", "b", "c", "d", "e", "c", "a", "e", "a"),
            target = c("b", "c", "d", "e", "a", "b", "d", "d", "e"),
         selection1 = c(1, 0, 1, 0, 0, 1, 1, 0, 0),
         selection2 = c(1, 1, 0, 0, 1, 1, 0, 0, 1),
         selection3 = c(1, 1, 1, 1, 1, 0, 0, 0, 0)
)

2. Then I also have a second problem which I believe to be more complicated and I am hoping there is a package for this. I want to exclude selections that have contradictory self reference i.e. a->b b->c c->a. This combination is essentially a triangle and our start and end point is the same node. This condition shouldn't be true for combinations. So a -> b and c-> a would be fine and b->c with either path 1 or 3 but not the combination of all three. These toy problems are relatively simple but I would want them to work for complicated dataframes too.

df2 <- data.frame(
  stringsAsFactors = FALSE,
            source = c("a", "b", "c", "a", "b"),
            target = c("b", "c", "a", "d", "d"),
        seection1 = c(1, 1, 1, 1, 0),
        seection2 = c(1, 0, 1, 0, 0),
        seection3 = c(1, 0, 0, 0, 1)
)

Any help would be massively appreciated!

[nirgrahamuk]

to start of I would do something like :

df1 <- data.frame(
  stringsAsFactors = FALSE,
  source = c("a", "b", "c", "d", "e", "c", "a", "e", "a"),
  target = c("b", "c", "d", "e", "a", "b", "d", "d", "e"),
  selection1 = c(1, 0, 1, 0, 0, 1, 1, 0, 0),
  selection2 = c(1, 1, 0, 0, 1, 1, 0, 0, 1),
  selection3 = c(1, 1, 1, 1, 1, 0, 0, 0, 0)
)

(identify_possibles <- group_by(
  df1,
  selection1,
  selection2,
  selection3
) %>% group_modify(
  ~  if (nrow(.) > 1) {data.frame(.)}  else { data.frame() }
) )

as some selections are unique and so dont have source-target combinations to assess - best strip them out and focus on those that do. the above code produces a new (grouped) table of the selections worth further investigating.

Then I would try to integrate my solution here:

Create a long name chain using R

First.Name<-c("John", "James", "Jack", "Jill", "Corey", "Callie", "Sofie", "Josie", "Lilly", "Luke", "Jane", "Sara", "Chandler","Flora","Parker","Preston") Last.Name<-c("Smith","Flora","Chandler","Jack","John","Reeves","Preston","Parker","James","Brooks","Johnson","Smith","Krause","Casey","Corey","Lilly") library(tidyverse) library(sqldf) first_df <- data.frame( firstname = First.Name, lastname = Last.Name ) # a function to perform repeated left joins do_next <- function(i){ lefttable <- if(i==1){"first_df"} else {paste0("result_",i-1)} join <- if(i==1){"a.lastname"} else {paste0("nextname",i-1)} assign(x=paste0("result_",i), sqldf::sqldf(paste0( "select a.*,b.lastname as nextname…

conceptually it seems the same its just that first name is source and last name is target.

good luck

[GreyMerchant]

Hello,

I will have a look thanks I have realised I what I am looking for relates to graph theory and is called connected and acyclic. Within the package semPLS they perform these checks as functions on the inserted model but I want to evaluate those combinations before they can even be inserted into the model object (as I intend to run thousands of combinations) and I would like to reduce the set before pushing it to the model. I tried to extract those functions from the package but they are not straightforward to extract and setup