- Generated by
1.16.1
|
slang-netlist
0.12.0
|
#include <DirectedGraph.hpp>
Public Types | |
| using | OutEdgePtrType = std::unique_ptr<EdgeType> |
| using | OutEdgeListType = std::vector<OutEdgePtrType> |
| using | InEdgeListType = std::vector<EdgeType *> |
| using | iterator = typename OutEdgeListType::iterator |
| using | const_iterator = typename OutEdgeListType::const_iterator |
| using | in_iterator = typename InEdgeListType::iterator |
| using | const_in_iterator = typename InEdgeListType::const_iterator |
| using | edge_descriptor = EdgeType * |
Public Member Functions | |
| Node ()=default | |
| virtual | ~Node ()=default |
| Node (const Node &)=delete | |
| Node (Node &&)=delete | |
| auto | operator= (const Node &) -> Node &=delete |
| auto | operator= (Node &&) -> Node &=delete |
| auto | begin () const -> const_iterator |
| auto | end () const -> const_iterator |
| auto | begin () -> iterator |
| auto | end () -> iterator |
| auto | inBegin () -> in_iterator |
| auto | inEnd () -> in_iterator |
| auto | inBegin () const -> const_in_iterator |
| auto | inEnd () const -> const_in_iterator |
| auto | operator== (const NodeType &N) const -> bool |
| auto | findEdgeFrom (const NodeType &sourceNode) -> in_iterator |
| Return an iterator to the edge connecting the source node. | |
| auto | findEdgeFrom (const NodeType &sourceNode) const -> const_in_iterator |
| Return an iterator to the edge connecting the source node. | |
| auto | findEdgeTo (const NodeType &targetNode) -> iterator |
| Return an iterator to the edge connecting the target node. | |
| auto | findEdgeTo (const NodeType &targetNode) const -> const_iterator |
| Return an iterator to the edge connecting the target node. | |
| auto | addEdge (NodeType &targetNode) -> EdgeType & |
| auto | getOrAddEdge (NodeType &targetNode) -> EdgeType & |
| auto | removeEdge (NodeType &targetNode) -> bool |
| auto | mayHaveParallelOutEdges () const -> bool |
| template<typename Predicate> | |
| void | removeOutEdgesIf (Predicate pred) |
| void | clearAllEdges () |
| Remove all edges to/from this node. | |
| auto | getEdgesTo (const NodeType &targetNode, std::vector< EdgeType * > &result) -> bool |
| auto | getInEdges () const -> const InEdgeListType & |
| Return the list of outgoing edges from this node. | |
| auto | getOutEdges () const -> const OutEdgeListType & |
| auto | inDegree () const -> size_t |
| Return the total number of edges incoming to this node. | |
| auto | outDegree () const -> size_t |
| Return the total number of edges outgoing from this node. | |
Protected Types | |
| using | OutEdgeIndex = flat_hash_map<NodeType const *, EdgeType *> |
Protected Member Functions | |
| auto | isEqualTo (const NodeType &node) const -> bool |
| auto | getDerived () -> NodeType & |
| auto | getDerived () const -> const NodeType & |
Protected Attributes | |
| std::mutex | edgeMutex |
| InEdgeListType | inEdges |
| OutEdgeListType | outEdges |
| std::unique_ptr< OutEdgeIndex > | outEdgeIndex |
| bool | parallelOutEdges {false} |
Static Protected Attributes | |
| static constexpr size_t | outEdgeIndexThreshold = 16 |
Friends | |
| auto | operator== (NodeType const &A, NodeType const &B) noexcept -> bool |
A class to represent a node in a directed graph.
Edges are owned by their source node via std::unique_ptr in outEdges. The target node stores a raw pointer in inEdges; lifetime is bounded by the source's outEdges entry.
| using slang::netlist::Node< NodeType, EdgeType >::const_in_iterator = typename InEdgeListType::const_iterator |
| using slang::netlist::Node< NodeType, EdgeType >::const_iterator = typename OutEdgeListType::const_iterator |
| using slang::netlist::Node< NodeType, EdgeType >::edge_descriptor = EdgeType * |
| using slang::netlist::Node< NodeType, EdgeType >::in_iterator = typename InEdgeListType::iterator |
| using slang::netlist::Node< NodeType, EdgeType >::InEdgeListType = std::vector<EdgeType *> |
| using slang::netlist::Node< NodeType, EdgeType >::iterator = typename OutEdgeListType::iterator |
|
protected |
Index from target-node pointer to the first edge in outEdges with that target. Allocated lazily once outEdges grows past outEdgeIndexThreshold so low-fanout nodes pay no per-node map overhead. Above the threshold the map keeps getOrAddEdge O(1) amortized regardless of out-degree. Protected by edgeMutex.
| using slang::netlist::Node< NodeType, EdgeType >::OutEdgeListType = std::vector<OutEdgePtrType> |
| using slang::netlist::Node< NodeType, EdgeType >::OutEdgePtrType = std::unique_ptr<EdgeType> |
|
default |
|
virtualdefault |
|
delete |
|
delete |
|
inline |
Add a new edge between this node and a target node, even if one already exists (creating a parallel edge).
Thread safety: safe to call concurrently, including between the same pair of nodes in both directions.
|
inline |
|
inline |
|
inline |
Remove all edges to/from this node.
|
inline |
|
inline |
|
inline |
Return an iterator to the edge connecting the source node.
|
inline |
Return an iterator to the edge connecting the source node.
|
inline |
Return an iterator to the edge connecting the target node.
|
inline |
Return an iterator to the edge connecting the target node.
|
inlineprotected |
|
inlineprotected |
|
inline |
Populate a result vector of edges from this node to the specified target node. Return true if at least one edge was found.
|
inline |
Return the list of outgoing edges from this node.
|
inline |
Return the edge from this node to a target node, adding one if none exists yet. Where parallel edges exist the first is returned, so the others are invisible here.
The returned edge may already be annotated by an earlier caller, and anything written to it replaces that annotation. Use addEdge when the new relation needs an edge of its own.
O(1) amortized: outEdgeIndex memoizes the first edge to each target, avoiding the linear outEdges scan that becomes quadratic on high-fan-out nodes (e.g. shared clocks driving every instance after non-canonical-instance resolution). The index is allocated lazily once outEdges grows past outEdgeIndexThreshold; below that, a linear scan over the few outEdges is faster and avoids the map's empty-control-byte overhead per node.
Thread safety: safe to call concurrently, including between the same pair of nodes in both directions.
|
inline |
|
inline |
|
inline |
|
inline |
Return the total number of edges incoming to this node.
|
inline |
|
inline |
|
inlineprotected |
|
inline |
True if a parallel edge has been added to this node, so it may hold more than one edge to the same target. Conservative: never false for a node that does carry parallel edges.
|
delete |
|
delete |
|
inline |
|
inline |
Return the total number of edges outgoing from this node.
|
inline |
Remove an edge between this node and a target node. Return true if the edge existed and was removed, and false otherwise.
|
inline |
Remove every outgoing edge for which pred returns true, keeping the target nodes' incoming-edge lists and the out-edge index consistent. pred is evaluated more than once per edge, so it must be free of side effects.
Not thread safe: intended for single-threaded use once construction has completed.
|
friend |
Static polymorphism: delegate implementation (via isEqualTo) to the derived class. Add friend operator to resolve ambiguity between operand ordering with C++20.
|
mutableprotected |
Per-node mutex protecting inEdges and outEdges. Adding an edge needs both endpoints' mutexes, which are always acquired together rather than in a fixed source-then-target order.
|
protected |
|
protected |
|
staticconstexprprotected |
Out-degree at which we switch from linear scans of outEdges to the lazily-allocated outEdgeIndex map.
|
protected |
|
protected |
Set whenever addEdge is used, whether or not an edge to the target already existed, since that is the only way a second edge to the same target can appear. Written under edgeMutex, so only safe to read once construction has completed.
1.16.1