gonum graph directed. How can I add edges to unexisting nodes?

[Carlos Sobrinho]

HI folks, trying to do something slightly different were I have several nodes with edges.

Some edges might point to a node that is not available (let's call these nodes optional).

What I would like is be able to add all the nodes and edges and then:
 - get a recursive list of nodes that are optional plus all the nodes that are connected to thee optional nodes.

 - remove then from the graph.

 

Right now I'm keeping track of all the nodes and only add them to the graph when all their edges are available. When removing I need to do the same thing were I have to check all nodes to see if they are connected and then remove them from the graph if they lost any of the edges but ultimately I would prefer to have a better solution that just uses the gonum library as much as possible.

Thanks!

[Dan Kortschak]

To clarify, you have O (optional) nodes and N (normal) nodes. When you
have an E O--N or O--O it should not be in the final graph, and any N
that is only connected in O--N node pairs should also not exist in the
graph? Is that correct?

If that's the case then when you are constructing the graph, only add
edges, and only edges that do not contain O nodes. If your N nodes are
all uniquely identified by their ID method, this should give you the
result that you want. (Edge setting implies node addition).

Dan

[Carlos Sobrinho]

Yep, I tried doing something like that but the Remove was trickier so I went with another approach. I add all the nodes and edges info on a map[string]*node and set a dirty flag. I don't expose the graph so it's easy to just recalculate the orphan Nodes during the two ops: Sort (topo.SortStabilized) and Cluster (after sort is done, split the slice into [][]node in a way that they don't depend on each other, so second level depends on first, third on second, etc. Not sure if gonum has something for this but I couldn't find one).

What I do is:

 - when a new node comes, add to the cache, set all the edges to the existing nodes and all the unknown edges to a single unknown (U) node. If any edge was added/changed, return true

 - keep doing this until no other node edge is changed.

 - recursively delete from the graph all nodes that have a link from unknown. The nodes are still on the map cache so they can be re-added if needed if dirty becomes true again.

In your example, it wouldn't work when you have O1-N2-N3 because it would just add all the edges for N2 to N3 and the whole O1-N2-N3 link should not on the graph unless O1 becomes N.

They're probably a few other ways of doing this but this seems to works very well for my needs: a ton of write 100-200 nodes, sort + calculate orphans and cluster.

Thanks!

[Dan Kortschak]

On Sun, 2023-05-07 at 19:36 -0700, Carlos Sobrinho wrote:
> Yep, I tried doing something like that but the Remove was trickier so
> I went with another approach. I add all the nodes and edges info on a
> map[string]*node and set a dirty flag. I don't expose the graph so
> it's easy to just recalculate the orphan Nodes during the two ops:
> Sort (topo.SortStabilized) and Cluster (after sort is done, split the
> slice into [][]node in a way that they don't depend on each other, so
> second level depends on first, third on second, etc. Not sure if
> gonum has something for this but I couldn't find one).
>
> What I do is:
>  - when a new node comes, add to the cache, set all the edges to the
> existing nodes and all the unknown edges to a single unknown (U)
> node. If any edge was added/changed, return true
>  - keep doing this until no other node edge is changed.
>  - recursively delete from the graph all nodes that have a link from
> unknown. The nodes are still on the map cache so they can be re-added
> if needed if dirty becomes true again.
>
> In your example, it wouldn't work when you have O1-N2-N3 because it
> would just add all the edges for N2 to N3 and the whole O1-N2-N3 link
> should not on the graph unless O1 becomes N.
>
> They're probably a few other ways of doing this but this seems to
> works very well for my needs: a ton of write 100-200 nodes, sort +
> calculate orphans and cluster.
> Thanks!

I think it would help if the overall intended behaviour were specified
here.

So what you seem to be wanting is a reachability criterion. Is that
correct? If it is, I'd not bother with removing any nodes and just
instead have a flag in nodes that distinguishes O from N (I take it
that in the example above it's G-O1-N2-N3 and not O1-N2-N3-G, where G
is the rest of the graph). Then you can use DFS from the starting node
(this presumably exists since it's a requirement for the rest to make
sense); here you DFS from the origin node, marking visited nodes and
accessible don't extend past O nodes. I'd make a derived graph that
considers nodes that are O or non-accessible to be non-existent for the
purposes of the graph.Graph API, this allows you to cache the work done
by DFS.

This encapsulates (what I think you are describing as) the behaviour.

Dan