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 view
#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
