FiveTech Software tech support forums

Posted: **Mon Sep 02, 2024 12:00 pm**

Hi,

I have a table like:

Name    Link    Input   
Name1   Name5   1   
Name2   Name1   1
Name3   Name20  1
Name4   Name10  1   
Name5   Name6   2
Name6   Name11  1
Name7   Name2   2   
Name8   Name20  1
Name9   Name1   1
Name10  Name5   3
Name11  Name1   1

…..

Now I want to find for example al the links to name6
So:
Name6 is connected to Name11
Name11 is connected to Name1
Name1 is connected to Name5
Name1 is connected to Name2
….

Wat is the fastest way to to this?
What I did now is:
-First look for al the Names connected to that name and add source and the link+input in an array
-Then look for all names connected to the names in that array add source and the link in an array if the same source+link+input dous not exist.
and so on till the are no more new names

So the result a list of all unique name+links+inputs

Is there a better (faster) way to do this?

Posted: **Mon Sep 02, 2024 3:17 pm**

Dear Marc,

You may try this code. I just asked Claude https://claude.ai/ about your question:

To find all connections efficiently, we can use a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS). Given the nature of your problem, BFS might be more suitable as it explores connections level by level.

This solution offers several advantages:

Efficiency: It uses BFS, which is optimal for finding all connections in an undirected graph.
No redundant checks: It keeps track of visited nodes to avoid revisiting the same connections.
Single pass: It builds all connections in one traversal of the graph.
Flexibility: It can easily be adapted to find connections up to a certain depth or with specific criteria.

Here's a breakdown of the approach:

We first build an adjacency list representation of the graph using a defaultdict. This allows for quick lookups of connections.
The find_all_connections function uses BFS to traverse the graph, starting from the given name.
We use a queue to keep track of nodes to visit, and a set to keep track of visited nodes.
As we traverse, we add each new connection to our results list.

This method should be significantly faster than your current approach, especially for larger datasets, as it avoids repeated searches and redundant checks.

Code: Select all | Expand

#include "hbclass.ch"

FUNCTION Main()
    LOCAL oGraph := GraphBuilder():New()
    LOCAL cStartName := "Name6"
    LOCAL aConnections

    // Agregamos los datos al grafo
    oGraph:AddConnection("Name1", "Name5", "1")
    oGraph:AddConnection("Name2", "Name1", "1")
    oGraph:AddConnection("Name3", "Name20", "1")
    oGraph:AddConnection("Name4", "Name10", "1")
    oGraph:AddConnection("Name5", "Name6", "2")
    oGraph:AddConnection("Name6", "Name11", "1")
    oGraph:AddConnection("Name7", "Name2", "2")
    oGraph:AddConnection("Name8", "Name20", "1")
    oGraph:AddConnection("Name9", "Name1", "1")
    oGraph:AddConnection("Name10", "Name5", "3")
    oGraph:AddConnection("Name11", "Name1", "1")

    // Encontramos todas las conexiones
    aConnections := oGraph:FindAllConnections(cStartName)

    // Imprimimos los resultados
    ? "Todas las conexiones empezando desde", cStartName
    AEval(aConnections, {|aConn| QOut(aConn[1] + " está conectado a " + aConn[2] + " (Input: " + aConn[3] + ")")})

RETURN NIL

CLASS GraphBuilder
    PROTECTED:
        VAR hGraph

    EXPORTED:
        METHOD New()
        METHOD AddConnection(cName1, cName2, cInput)
        METHOD FindAllConnections(cStartName)
END CLASS

METHOD New() CLASS GraphBuilder
    ::hGraph := hb_Hash()
RETURN SELF

METHOD AddConnection(cName1, cName2, cInput) CLASS GraphBuilder
    IF !hb_HHasKey(::hGraph, cName1)
        ::hGraph[cName1] := {}
    ENDIF
    IF !hb_HHasKey(::hGraph, cName2)
        ::hGraph[cName2] := {}
    ENDIF
    AAdd(::hGraph[cName1], {cName2, cInput})
    AAdd(::hGraph[cName2], {cName1, cInput})
RETURN NIL

METHOD FindAllConnections(cStartName) CLASS GraphBuilder
    LOCAL aQueue := {{cStartName, NIL, NIL}}
    LOCAL hVisited := hb_Hash()
    LOCAL aConnections := {}
    LOCAL aCurrentNode, cName, cSource, cInput, aNeighbor

    DO WHILE !Empty(aQueue)
        aCurrentNode := hb_ArrayShift(@aQueue)
        cName := aCurrentNode[1]
        cSource := aCurrentNode[2]
        cInput := aCurrentNode[3]

        IF !hb_HHasKey(hVisited, cName + "_" + hb_ValToStr(cSource) + "_" + hb_ValToStr(cInput))
            hVisited[cName + "_" + hb_ValToStr(cSource) + "_" + hb_ValToStr(cInput)] := .T.
            IF cSource != NIL
                AAdd(aConnections, {cName, cSource, cInput})
            ENDIF

            IF hb_HHasKey(::hGraph, cName)
                FOR EACH aNeighbor IN ::hGraph[cName]
                    IF !hb_HHasKey(hVisited, aNeighbor[1] + "_" + cName + "_" + aNeighbor[2])
                        AAdd(aQueue, {aNeighbor[1], cName, aNeighbor[2]})
                    ENDIF
                NEXT
            ENDIF
        ENDIF
    ENDDO

RETURN aConnections

Posted: **Wed Sep 04, 2024 8:58 pm**

Thank you Antonio, I will try it.

FiveTech Software tech support forums

Looking for links in tables

Looking for links in tables

Re: Looking for links in tables

Re: Looking for links in tables