[FEATURE] Provide more basic graph tools

[mgovers]

Describe the feature request

Currently, the graph representation only contains some more global tools (e.g.: get all cycles). However, it would be nice if there would be some tool to step locally through a graph (e.g.: get adjacent nodes/edges). The functionality already exists in the graph implementation, but is not yet exposed over the API and requires one to rebuild the graph from scratch.

[vincentkoppen]

If you have a specific request as an addition to the API then we are definitely open to discuss (and afterwards review) these. The examples you provided sound like useful additions indeed.

The reason we do not (currently) expose the rustworkx graph object itself, is that with the current API based implementation we allow ourself as maintainers to change the underlying dependency (e.g change from rustworkx to igraph) without any breaking change for the user.
We implemented this, since we initially used a different library that became unmaintained, which forced us to a different graph library.

If you see a way for us to expose the graph object, while keeping this flexibility I'm definitely open we are definitely open to that.

[mgovers]

I think these tools should be exposed via the BaseGraphModel interface. In particular, the following operations are supported by (almost) every graph library:

• adjacent(node: int) -> list[int]
  • Get the list of all nodes
• adjacent_edges(node: int) -> list[int]
  • Get the list of all edges connected to the node
• other_node(node: int, edge: int) -> int
  • Step through an edge. This can already be done by accessing the edge in the PGM grid but not via the Graph interface.
• bfs / breath_first_search; I do know you already have get_downstream_nodes so this can probably just be an alias, or vice versa
• dfs / depth_first_search; The current interface does not seem to support this yet

Optionally, we can also expose other useful functionalities like

• adjacent(node: Int, excluding: list[int] = []) -> list[int]
  • Same as adjacent(node: int) -> list[int] but do not return any nodes in the excluded list
  • This is particularly useful when you do a local search but don't want to visit any nodes twice

[vincentkoppen]

Thanks for the examples:

• adjacent(node:int) -> list[int] and adjacent_edges definitely agree and open to PR's or might implement this myself when I have time
  • On: adjacent_edges will return a list[tuple[int,int]] since we don't have branch id's on the graph
  • On: adjacent(node: int, excluding: list[int]) -> list[int]: seems like a nice optional argument indeed. Nit: would change the excluding to either be set[int] (for performance) or Container[int] to support any structure that support the x in excluded_list check.
• Since we don't have branch ids on the graph, currently other_node doesn't seem useful. Since a branch is just a tuple of the two nodes.

The above also shows that we might want to think about supported edge_id (from our branches/three winding transformers) on our graphs.

For bfs / dfs I agree that these are useful, will try to find some time in the upcoming weeks to see if I can get a grasp of what a good interface could look like.

[juliettegiraud-2004]

Hello, I definitely agree with that request (all the functions adjacent, adjacent_edges, other_nodes, bfs, dfs would also be really useful for me)! I would also suggest a couple of other complementary features that would be really useful for me as well :

Context: fault isolation and service restoration

My main use case is distribution network fault isolation and restoration.

In this context, I need to work with the same network at two different levels:

• a full graph for electrical computations (load flow, constraint checks),
• a simplified topological graph, where:
  • nodes represent pockets / zones,
  • edges represent switches (breakers) that can be opened/closed.

Each pocket corresponds to a subgraph of the full network, and the restoration logic is driven by the switches between these pockets.

A typical workflow is:

1. Fault isolation
   • open switches surrounding the faulty pocket
2. Topological decomposition
   • compute connected components on the simplified graph
3. Classification
   • run load flow
   • classify components into:
     • faulted (ignored),
     • energized,
     • non-energized or violating constraints
4. Restoration search
   • identify candidate open switches that connect an energized component to a non-energized one
   • test candidates iteratively:
     • close the switch,
     • recompute components,
     • run load flow,
     • check violations on the merged component
5. Output
   • list of switches to open (isolation) and close (restoration) in the full graph

In this workflow, the local traversal functions discussed here are really key building blocks for:

• navigating between neighboring pockets,
• identifying candidate switches,
• implementing custom search strategies.

Additional suggestion 1: hierarchical / multi-level graph

One feature that would be a real game changer for this use case is the ability to work with a hierarchical (multi-level) graph.

The key need is to manipulate one logical graph object at different abstraction levels:

• detailed level → for electrical computations,
• aggregated level → for topological reasoning.

Today, this typically requires rebuilding a second graph manually maintaining mappings between:

• detailed elements (nodes/branches),
• aggregated elements (pockets),
• switches linking them.

It would be extremely useful to have a library-agnostic way to:

• define node groupings (e.g. pockets),
• obtain a topological view of the two levels of the graph,
• maintain mappings between levels.

Importantly, this would not require exposing the underlying graph library (it is not available in rustworkx ), but could instead live as an abstraction on BaseGraphModel (e.g. graph views or hierarchical node mapping) ?

Additional suggestion 2: minimum spanning tree

Another functionality that would be very helpful is a minimum spanning tree capability (available in rustworkx as rustworkx.minimum_spanning_tree : https://www.rustworkx.org/stable/0.12/apiref/rustworkx.minimum_spanning_tree.html).

One restoration strategy I would like to implement is:

• first identify which components are energizable,
• restrict the problem to the subgraph containing energizable + energized components,
• compute a spanning tree with:
  • cost = 0 for switches already closed,
  • cost = 1 for switches currently open.

This would help derive a restoration plan that minimizes switching operations and could be more efficient than purely local iterative approaches.

[vincentkoppen]

I made a PR for adjacent and two draft PRs for dfs and bfs.

For the drafts, choosing a fixed output format for a dfs/bfs is always tricky. Currently it just returns the nodes in the order they are found, but I can imagine that providing the branch that got you to their might also be useful. Any thoughts?

[mgovers]

I made a PR for adjacent and two draft PRs for dfs and bfs.

Awesome!

For the drafts, choosing a fixed output format for a dfs/bfs is always tricky. Currently it just returns the nodes in the order they are found, but I can imagine that providing the branch that got you to their might also be useful. Any thoughts?

BFS gives you kind of a notion of "upstream" (e.g. a "direction to (closest?) source"), so that is definitely useful.

For DFS, is less useful from an electrical engineering perspective, but it could still be useful when implementing extra functionality that uses the DFS. It is also probably a good idea to homogenize the output of BFS and DFS, so I am definitely leaning towards providing the branch.

[vincentkoppen]

@juliettegiraud-2004 I only now see your comment, apologies. Thanks for the detailed request!

Suggestion 1
My first honest take is that I'm not sure if this use case is generic enough to warrant to possible implication/complexity it will introduce on our side. What are your thoughts @jaapschoutenalliander ?

I'm definitely open to see what an implementation of this could look like, but I'm a bit worried that it might complicate things quite a bit. Also it might not be fully clear to me why the aggregated is necessary to me currently?

• Are the current algorithms (to open/close edges and find connected component) too slow on the full graph?
• What algorithms would be used on the aggregated result?

Suggestion 2
I would definitely be open to support mst on the graph.

• We need to determine how we want to deal with weights in general (get_shortest_path could then also get this parameter)
  rustworkx uses a function, however I would personally think a mapping dict might be clearer? We can easily translate it to a function on our side for rustworkx.

• The output would be a list of edges I guess?

[vincentkoppen]

BFS gives you kind of a notion of "upstream" (e.g. a "direction to (closest?) source"), so that is definitely useful.

For DFS, is less useful from an electrical engineering perspective, but it could still be useful when implementing extra functionality that uses the DFS. It is also probably a good idea to homogenize the output of BFS and DFS, so I am definitely leaning towards providing the branch.

Yeah I agree. Will update one of the PRs with a proposal that includes the branches (probably today)

[vincentkoppen]

@mgovers I have updated the bfs PR: #274

I chose to go for (node, parent), this is almost equivalent to returning the branches but:

• the sources are included in the result (with a None parent unless they are found within the search of another source)
• The order is very explicit in the order of the tuple (which edges aren't necessarily)

Let me know what you think!

[mgovers]

@mgovers I have updated the bfs PR: #274

I chose to go for (node, parent), this is almost equivalent to returning the branches but:

• the sources are included in the result (with a None parent unless they are found within the search of another source)
• The order is very explicit in the order of the tuple (which edges aren't necessarily)

Let me know what you think!

Makes sense! Do you think adding an edge ID would be useful? Or does that not match the existing design?