Programming/Interesting algorithm to find clusters of nodes in a map of related nodes

Is the set of 5 nodes under the left output of the left child of the root also a cluster?
Is the set of two nodes under the right child of the left child of the root also a cluster?
Is the set of one node under that also a cluster?
If not, why not?

yep, sorry. rushed the diagram.
as per your comment, those should all be clusters. and need toa way to find out how to determine them.


node-map-2.png

#!/usr/bin/perl
use strict;
use warnings;
my %fwd;
my %back;
my %ancestor;
my %descendant;
while( <DATA> ){
    if(  my($from,$to)=split/\W+/ ){
        $fwd{$from}{$to}++;
        $back{$to}{$from}++;
        @{$descendant{$_}}{keys %{$descendant{$to}},$to}=() for $from,keys %{$ancestor{$from}};
        @{$ancestor{$_}}{keys %{$ancestor{$from}},$from}=() for $to,keys %{$descendant{$to}};

    }
}
my @clusters;
for( keys %back ){
      if( !$fwd{$_} ){  #leaf node
          my %set=($_,$_);
          my %new=%set;
          while( my @refs=grep{!exists $set{$_}} map{keys %{$back{$_}}} keys %new ){
              push @clusters,[keys %set] if @refs==1;
              %new=();
              @new{ grep{!exists $set{$_}}map{keys %{$descendant{$_}},$_}@refs}=();
              @set{keys %new}=();
          }
     }
  }
print "[@$_]\n" for @clusters;
__DATA__
A -> B
A -> C
B -> D
E -> D
D -> F
F -> G
E -> H
H -> G
B -> I
I -> J
J -> K
C -> L
C -> M
L -> N
M -> N



Produces the following clusters
[M C N L]
[K]
[J K]
[J K I]
[F E H D G]
[F J K B E H D I G]

thanks for the reply, but sorry to be a pain, could you please explain the code. or the basic principles

I am not familiar with the language,  I know vb, php, java

basically, it traces sets back from leaf nodes noting a cluster whenever there is only one arrow from outside the set to inside the set.

okay, I moderately follow.

trace back references finding the single link, make the start of a cluster.

but how do you approach when the left splits into two?

when I add a node to a set, I also add all descendants of that node

still not following

lets say we are trying to find the right hand side cluster of 4 nodes, please walk me through the steps.

we find the bottom leaf node as it has no outputs.
then I transverse up the left parent node, what tests do I perform? do I continue moving up or then transverse the missed right node?

As I think about it, I think the above program may fail to find some clusters in a more complicated diagram
I assume that
If a node is in a cluster, then all of its descendants are also in that cluster
If a node is in a cluster, and that node has more than one parent, and those parents have a common ancestor,
then there will be a common ancestor in the cluster

I guess bad drawing on my part, but we can also have the following situation.

but your solution got me thinking.

we find the single cluster nodes as it has no inputs or no outputs.
you transverse to any node adjacent node, as soon as it gets to a node with a path choice (ie multiple connections), you stop and go back to the previous missed path choice.
if you reach a node with the single parent connection and no missed paths, then those nodes are considered a cluster.
if you reach a node with no more paths, then go to anymore missed paths or consider everything as 1 cluster.

can you please confirm?

i have been thinking about avoidance of duplication, because you are starting at each single cluster node, a lot of doubling up will occur. to avoid this if each node with > 3 connections will have a processed tick, if it has been processed it will make this tick true. and any other clusters will stop processing it if already processed.

can you also confirm it will work?

Thanks
node-map-3.png

okay, the more i think about it the more complicated it gets, and the method above doesn't work.

here is a new node map.
node-map-4.png

Could you label the nodes either circle or list  the clusters so we can test algorithms against it?
It looks to me like the node in the middle belongs to different clusters that overlap but one is not contained in the other.
(and also to some clusters such that one does contain the other)
In the worst case, testing all possible subsets to see if they are a cluster should work, but may become impractical for large maps

yes, you are correct no more than one cluster per arrow.

i have updated the diagram, added labels and marked the clusters. I realised that each cluster will have an opposite cluster of the remaining nodes, so I have circled only the single side. made the diagram a little messy though.

node-map-5.png

> I realised that each cluster will have an opposite cluster of the remaining nodes
So the arrow directions don't matter?
Then every edge that is not part of a cycle divides the graph into two clusters?

yep, arrow directions don't matter.

Then every edge that is not part of a cycle divides the graph into two clusters?
don't follow.

The edges between
A and D
B and D
C and D
D and E
E and F
F and L
F and K
F and J
F and L
F and M
L and M

Not the edges between
F and G
G and H
H and I
I and J
because
F G H I
form a cycle

ahh, yes, a cluster should be connected via the single arrow only

okay, that makes sense

but what would be the best way to determine if an edge is part of a cycle?

thank you very much for your help.
I have successfully implemented the algorithm.

to summarise,
* looped through all connections (arrows)
* chose either the tail or head node of the arrow (lets say head)
* recursively find all nodes references to the head while populating a cluster set of nodes at the same time
* if any nodes reference the tail node, then stop the iterations, delete the working cluster set and move to the next connection

thanks again for taking the time to answer this relatively complex problem