Ah, it seems I didn’t quite get my point across. I am familiar with the concept, having implemented canonical hypergraph labeling before, but I wasn’t sure whether your question about an “explicit hypergraph” representation was primarily about the “explicit”, about the “hypergraph” part, or both, so I decided it would be easier to describe what I was thinking of instead of guessing
What I was trying to point out, is that we can also add the restriction that every port is connected to at most one directed hyperedge. With that, if we label every incidence with a port name, which we have to do anyway if our vertices are cells, we can split the directed hyperedges into multiple simple edges without losing any information.
Thus, a directed hypergraph is more general than what’s required here, so if we only consider data structures that can represent directed hypergraphs we would miss some useful choices, and we would have an explicit invariant to maintain on top of the general directed hypergraph. Whereas the directed edge-labeled multigraph approach precisely captures what I was writing about without the need for any additional invariant.
I also like to combine a graph perspective with a relational perspective where the difference that I’m talking about becomes even clearer, IMO. With only fixed-arity relations, to represent a hypergraph, you need to assign some form of hyperedge ID (which could correspond to an address in an actual implementation). Assuming we label incidences with port names, you would then have a relation (Vertex, Label, Hyperedge) for the vertex→edge incidences and a relation (Hyperedge, Label, Vertex) for the edge→vertex incidences.
The restriction that you mention is that we have exactly one incoming incidence per hyperedge, so we have the functional dependency Hyperedge → (Vertex, Label). The restriction that I want to add, because it simplifies so many things and is already used by bufnorm and signorm, is that we can’t connect the same cell port to multiple hyperedges, so we also have a functional dependency (Vertex, Label) → Hyperedge. At that point we can identify a Hyperedge by a (Vertex, Label) pair, and substituting that makes the vertex→edge incidences entirely redundant and turns the edge→vertex incidence relation into (Vertex, Label, Label, Vertex). That is also how you’d model an edge-labeled directed multigraph relationally, and the reason why I prefer that as a graph model.
I’ll start a separate thread about removing
IdStringrefcounting.
Makes sense, I want to bring that up also internally to double check that I’m not missing anything, and so that we don’t have to be overly conservative to address hypothetical but unlikely breakage but can focus on not breaking actual and expected use cases. I’ll respond to the new thread afterwards.
Ok, it sounds like I should just go ahead and submit that as a PR then.
[…]
Overall it seems like there’s some hope we can fix RTLIL “in place” so const methods are thread-safe. If we can achieve that, parallel opt_merge becomes a much smaller change. So let’s try pushing in this direction.
I agree, that sounds like a good plan for the next steps.