slang-netlist  0.9.0
Loading...
Searching...
No Matches
slang::netlist::DirectedGraph< NodeType, EdgeType > Class Template Reference

#include <DirectedGraph.hpp>

Public Types

using NodePtrType = std::unique_ptr<NodeType>
using NodeListType = std::vector<NodePtrType>
using iterator = typename NodeListType::iterator
using const_iterator = typename NodeListType::const_iterator
using node_descriptor = size_t
using edge_descriptor = EdgeType *
using DirectedGraphType = DirectedGraph<NodeType, EdgeType>

Public Member Functions

 DirectedGraph ()=default
auto begin () const -> const_iterator
auto end () const -> const_iterator
auto begin () -> iterator
auto end () -> iterator
auto findNode (const NodeType &nodeToFind) const -> node_descriptor
auto getNode (node_descriptor node) const -> NodeType &
 Given a node descriptor, return the node by reference.
auto addNode () -> NodeType &
auto addNode (std::unique_ptr< NodeType > node) -> NodeType &
auto removeNode (NodeType &nodeToRemove) -> bool
auto addEdge (NodeType &sourceNode, NodeType &targetNode) -> EdgeType &
 Add an edge between two existing nodes in the graph.
auto addNewEdge (NodeType &sourceNode, NodeType &targetNode) -> EdgeType &
auto removeEdge (NodeType &sourceNode, NodeType &targetNode) -> bool
auto outDegree (const NodeType &node) const -> size_t
 Return the number of edges outgoing from the specified node.
auto inDegree (const NodeType &node) const -> size_t
 Return the number of edges incident to the specified node.
auto numNodes () const -> size_t
 Return the size of the graph.
auto numEdges () const -> size_t
 Return the number of edges in the graph.

Static Public Attributes

static const size_t null_node = std::numeric_limits<size_t>::max()

Protected Attributes

std::mutex nodesMutex
NodeListType nodes

Detailed Description

template<class NodeType, class EdgeType>
class slang::netlist::DirectedGraph< NodeType, EdgeType >

A directed graph. Nodes and edges are stored in an adjacency list data structure, where the DirectedGraph contains a vector of nodes, and each node contains a vector of directed edges to other nodes. Multi-edges are not permitted.

Member Typedef Documentation

◆ const_iterator

template<class NodeType, class EdgeType>
using slang::netlist::DirectedGraph< NodeType, EdgeType >::const_iterator = typename NodeListType::const_iterator

◆ DirectedGraphType

template<class NodeType, class EdgeType>
using slang::netlist::DirectedGraph< NodeType, EdgeType >::DirectedGraphType = DirectedGraph<NodeType, EdgeType>

◆ edge_descriptor

template<class NodeType, class EdgeType>
using slang::netlist::DirectedGraph< NodeType, EdgeType >::edge_descriptor = EdgeType *

◆ iterator

template<class NodeType, class EdgeType>
using slang::netlist::DirectedGraph< NodeType, EdgeType >::iterator = typename NodeListType::iterator

◆ node_descriptor

template<class NodeType, class EdgeType>
using slang::netlist::DirectedGraph< NodeType, EdgeType >::node_descriptor = size_t

◆ NodeListType

template<class NodeType, class EdgeType>
using slang::netlist::DirectedGraph< NodeType, EdgeType >::NodeListType = std::vector<NodePtrType>

◆ NodePtrType

template<class NodeType, class EdgeType>
using slang::netlist::DirectedGraph< NodeType, EdgeType >::NodePtrType = std::unique_ptr<NodeType>

Constructor & Destructor Documentation

◆ DirectedGraph()

template<class NodeType, class EdgeType>
slang::netlist::DirectedGraph< NodeType, EdgeType >::DirectedGraph ( )
default

Member Function Documentation

◆ addEdge()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::addEdge ( NodeType & sourceNode,
NodeType & targetNode ) -> EdgeType &
inline

Add an edge between two existing nodes in the graph.

◆ addNewEdge()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::addNewEdge ( NodeType & sourceNode,
NodeType & targetNode ) -> EdgeType &
inline

Unconditionally add a new edge between two existing nodes, even if one already exists (creating a parallel edge).

◆ addNode() [1/2]

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::addNode ( ) -> NodeType &
inline

Add a node to the graph and return a reference to it.

Thread safety: safe to call concurrently from multiple threads.

◆ addNode() [2/2]

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::addNode ( std::unique_ptr< NodeType > node) -> NodeType &
inline

Add an existing node to the graph and return a reference to it.

Thread safety: safe to call concurrently from multiple threads.

◆ begin() [1/2]

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::begin ( ) -> iterator
inline

◆ begin() [2/2]

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::begin ( ) const -> const_iterator
inline

◆ end() [1/2]

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::end ( ) -> iterator
inline

◆ end() [2/2]

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::end ( ) const -> const_iterator
inline

◆ findNode()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::findNode ( const NodeType & nodeToFind) const -> node_descriptor
inline

◆ getNode()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::getNode ( node_descriptor node) const -> NodeType &
inline

Given a node descriptor, return the node by reference.

◆ inDegree()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::inDegree ( const NodeType & node) const -> size_t
inline

Return the number of edges incident to the specified node.

◆ numEdges()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::numEdges ( ) const -> size_t
inline

Return the number of edges in the graph.

◆ numNodes()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::numNodes ( ) const -> size_t
inline

Return the size of the graph.

◆ outDegree()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::outDegree ( const NodeType & node) const -> size_t
inline

Return the number of edges outgoing from the specified node.

◆ removeEdge()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::removeEdge ( NodeType & sourceNode,
NodeType & targetNode ) -> bool
inline

Remove an edge between the two specified vertices. Return true if the edge exists and was removed, and false if it didn't exist.

◆ removeNode()

template<class NodeType, class EdgeType>
auto slang::netlist::DirectedGraph< NodeType, EdgeType >::removeNode ( NodeType & nodeToRemove) -> bool
inline

Remove the specified node from the graph, including all edges that are incident upon this node, and all edges that are outgoing from this node. Return true if the node exists and was removed and false if it didn't exist.

Member Data Documentation

◆ nodes

template<class NodeType, class EdgeType>
NodeListType slang::netlist::DirectedGraph< NodeType, EdgeType >::nodes
protected

◆ nodesMutex

template<class NodeType, class EdgeType>
std::mutex slang::netlist::DirectedGraph< NodeType, EdgeType >::nodesMutex
mutableprotected

Mutex protecting the nodes vector. Only addNode() acquires this; iteration and read-only access are safe after build() completes.

◆ null_node

template<class NodeType, class EdgeType>
const size_t slang::netlist::DirectedGraph< NodeType, EdgeType >::null_node = std::numeric_limits<size_t>::max()
static
The documentation for this class was generated from the following file: