Extracting subgraphs (cliques) within graph on Netlogo

Question

I have a netlogo question. I have some graph structures of nodes connected with (undirected) links. I need to figure out which is the smallest subgraph within one of these structures. Basically subgraph means which nodes are all connected between each other. So if I have a structure of 5 nodes and node 1 is connected to 2 and 3; node 2 to 3, 1 and 4; and node 3 to 1, 2 and 5 I need to detect the subgraph of nodes 1, 2 and 3 since they're all interconnected.

Is there an easy way to do this or is it basically not computationally possible?

Edit: I figured out that if I use the netlogo extension nw I can use the nw:maximal-cliques method to calculate what I want. Although now I have another problem. I'm trying to fill up a list of the lists of the cliques this way

let lista-cliques [nw:maximal-cliques] of turtles with [guild = g]

lista-cliques is usually of length two but the first element which should be a list of the turtles of the clique is a list like this

[[[nobody] [nobody] [nobody] [nobody]...etc

with a length of 300 when the graphs made by turtles with guild = g are around 2-8 turtles in length. Is the call to nw:maximal-cliques well made?

Any ideas of what am I doing wrong?

Edit 2: I figured how to fix the length of the list by doing this

let lista-cliques (list ([nw:maximal-cliques] of turtles with [guild = g]))

Now the list is not of 300 nodes but equal to the amount of nodes on the graph with nodes with guild = g.

That means that

length item 1 lista-cliques

is equal to

count turtles with [guild = g]

which is also evidently wrong since I can see graphs with nodes connected to only one or two nodes. I think I'm getting closer but I don't know why nw:maximal-cliques is not creating a list of the maximal-cliques but a list of all the nodes on the graph.

Any ideas?

Thanks

Answer 1

Your usage of nw:maximal-cliques is not quite correct.

I think that what you are trying to express by specifying of turtles with [guild = g] is something like "taking into account only the turtles that are part of guild g", but what it actually means to NetLogo is "run the reporter that precedes of for each turtle that are part of guild g and make a list out of that". (Just like, e.g., [color] of turtles will run the [color] reporter block once for each turtle and build a list of colors with the results.)

nw:maximal-cliques is a primitive that operates on the whole network, so you don't want to run it once for each turtle. And just like most primitives in the nw extension, you need to tell it which turtles and links to operate on by using the nw:set-snapshot primitive.

I think you can achieve what you want by simply doing:

nw:set-snapshot (turtles with [guild = g]) links
let lista-cliques nw:maximal-cliques

(Note that nw:set-snapshot takes a static "picture" of your network on which further calls to nw primitives operate. If something changes in your network, you need to call nw:set-snapshot to take a new picture. This will probably change in a future version of the extension.)