algorithm - Indirect and direct link in a tree - Stack Overflow

admin管理员组

文章数量:1357682

Suppose 3 sets of nodes, each corresponding to a distinct set in an undirected graph:

    Set-A = {1, 2, 3, 4, 5}
    Set-B = {6, 7, 8, 9, 10}
    Set-C = {11, 12, 13, 14, 15}

The graph is defined by two types of edges:
ss-pairs: Intra-set edges (within the same set).
ts-pairs: Inter-set edges (between different sets).

ss-pairs and ts-pairs are:

    ss-pairs = [(1, 2), (2, 3), (3, 4), (4, 5), (6, 7), (7, 8), (8, 9), (9, 10), (11, 12), 
                (12, 13), (13, 14), (14, 15)]
    ts-pairs = [(1, 6), (2, 7), (3, 8), (4, 9), (6, 11), (7, 12), (8, 13), (9, 14)]

After some manipulations on this graph, several spanning trees are generated in which a particular node belonging to one of the sets is removed. For example, when a node (e.g., node 7 from Set-B) is removed, multiple spanning trees (STs) can be generated. Below are examples of such STs (simplified for clarity): :

    ST 1: (3,4), (9,10), (4,9), (14,15), (4,5), (8,13), (2,3), (1,2), (13,14), (12,13), 
          (11,12), (6,11), (8,9)

This spanning tree is anized according to ss-pairs and ts-pairs, as follows:

    ss-pairs = [(1,2), (2,3), (3,4), (4,5), (8,9), (9,10), (11,12), (12,13), (13,14), 
               (14,15)]

    ts-pairs = [(4,9), (6,11), (8,13)]

An indirect connection is generally identified when:

 - any node from Set-A is connected to any node from Set-B AND  
   simultaneously, any node from Set-B is connected to any node 
   from Set-C;    

 - any node from Set-A is connected to any node from Set-B AND 
   simultaneously, that same node from Set-B is connected to any 
   node from Set-C.

To be more explicit, an indirect connection is detected if all three sets Set-A, Set-B, and Set-C are connected through a node from each of these three sets.

A direct connection is identified when any node from any set Set-A, Set-B, or Set-C is connected only to any other node from one of the sets Set-A or Set-B or Set-C.

To be more explicit, a direct connection is identified if:

• node from Set-A is connected only to a single node from Set-B (or vice versa), Set-C node's excluded.

-node from Set-C is connected only to a single node from Set-B (or vice versa), Set-A node's excluded.

Let's take the example of ts-pairs = [(4,9), (6,11), (8,13)]. In this set, we can see that:

• nodes 6, 8, and 9 belong to Set-B from which node 7 has been removed.

• node 4 belongs to Set-A.

• nodes 11 and 13 belong to Set-C.

Therefore, we can establish that:

• edges (4,9) and (8,13) form an indirect connection.

• edge (6,11) is a direct connection.

The question is: how can we write a CLIPS program to detect direct and indirect connections according to the criteria stated above?

本文标签： algorithmIndirect and direct link in a treeStack Overflow