I posted a comment/reply to another stackoverflow post over here : R: Understanding Graph relating to graphs in R.
If you create some data corresponding to movies and actors (in which movies can not be connected to other movies directly, and actors can not be connected to other actors directly), you write some R code to check if your graph is bipartite:
library(igraph)
film_data <- data.frame(
"movie" = c("movie_1", "movie_1", "movie_1", "movie_2", "movie_2", "movie_2", "movie_3", "movie_3", "movie_3", "movie_4", "movie_4", "movie_4", "movie_4", "movie_5", "movie_5", "movie_5", "movie_6", "movie_6"),
"actor" = c("actor_1", "actor_2", "actor_3", "actor_2", "actor_3", "actor_4", "actor_1", "actor_5", "actor_6", "actor_2", "actor_7", "actor_1", "actor_8", "actor_5", "actor_9", "actor_3", "actor_2", "actor_8")
)
#create directed graph
graph <- graph.data.frame(film_data, directed=F)
graph <- simplify(graph)
plot(graph)
V(graph)$type <- V(graph)$name %in% film_data[,1]
is.bipartite(graph)
[1] TRUE
However, you can "purposefully sabotage" this graph by adding a link between two actors (actor_2 and actor_3) so that the graph is no longer bipartite:
film_data <- data.frame(
"movie" = c("movie_1", "movie_1", "movie_1", "movie_2", "movie_2", "movie_2", "movie_3", "movie_3", "movie_3", "movie_4", "movie_4", "movie_4", "movie_4", "movie_5", "movie_5", "movie_5", "movie_6", "movie_6", "actor_2"),
"actor" = c("actor_1", "actor_2", "actor_3", "actor_2", "actor_3", "actor_4", "actor_1", "actor_5", "actor_6", "actor_2", "actor_7", "actor_1", "actor_8", "actor_5", "actor_9", "actor_3", "actor_2", "actor_8", "actor_3")
)
#create directed graph
graph <- graph.data.frame(film_data, directed=F)
graph <- simplify(graph)
plot(graph)
But R will still say that this graph is bipartite:
V(graph)$type <- V(graph)$name %in% film_data[,1]
is.bipartite(graph)
[1] TRUE
You can further sabotage this graph by adding an extra link between two movies:
film_data <- data.frame(
"movie" = c("movie_1", "movie_1", "movie_1", "movie_2", "movie_2", "movie_2", "movie_3", "movie_3", "movie_3", "movie_4", "movie_4", "movie_4", "movie_4", "movie_5", "movie_5", "movie_5", "movie_6", "movie_6", "actor_2", "movie_1"),
"actor" = c("actor_1", "actor_2", "actor_3", "actor_2", "actor_3", "actor_4", "actor_1", "actor_5", "actor_6", "actor_2", "actor_7", "actor_1", "actor_8", "actor_5", "actor_9", "actor_3", "actor_2", "actor_8", "actor_3", "movie_2")
)
#create directed graph
graph <- graph.data.frame(film_data, directed=F)
graph <- simplify(graph)
plot(graph)
But R will still call it bipartite:
V(graph)$type <- V(graph)$name %in% film_data[,1]
is.bipartite(graph)
[1] TRUE
Does anyone know if I am doing something wrong? Are these last two graphs actually bipartite? Or am I applying the code incorrectly?
Just to clarify: Are all undirected graphs cyclic? If you have a undirected graph with just one type of node, it it necessarily bipartite?
Thanks
