Directed graph with arbitrary node types. More...

#include <digraphs.hpp>

Inheritance diagram for xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >:

Collaboration diagram for xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >:

Public Types
using	Node = typename _Base::Node

using	edge_t = std::pair< Node, Node >

using	key_type = typename _Base::key_type

using	value_type = typename _Base::value_type

Public Types inherited from xnetwork::Graph< _nodeview_t, adjlist_t, adjlist_outer_dict_factory >
using	nodeview_t = _nodeview_t

using	Node = typename nodeview_t::value_type

using	adjlist_inner_dict_factory = adjlist_t

using	key_type = typename adjlist_t::key_type

using	value_type = typename adjlist_t::value_type

using	edge_t = std::pair< Node, Node >

using	node_t = Node

Public Member Functions
	DiGraphS (const nodeview_t &Nodes)
	Construct a directed graph from a node container.

	DiGraphS (uint32_t num_nodes)
	Construct a directed graph with a given number of integer nodes.

auto	adj () const
	Get adjacency mapping (successors) of the directed graph (const version)

auto	succ () const
	Get the successors mapping (same as adj)

template<typename U = key_type>
auto	add_edge (const Node &node_u, const Node &node_v) -> typename std::enable_if< std::is_same< U, value_type >::value >::type
	Add a directed edge between two nodes (for simple key type, SFINAE)

template<typename U = key_type>
auto	add_edge (const Node &node_u, const Node &node_v) -> typename std::enable_if<!std::is_same< U, value_type >::value >::type
	Add an edge between two nodes (for complex key type)

template<typename T >
auto	add_edge (const Node &node_u, const Node &node_v, const T &data)
	Add an edge between two nodes with data.

template<typename C1 , typename C2 >
auto	add_edges_from (const C1 &edges, const C2 &data)
	Add edges from a container with associated data.

auto	has_successor (const Node &node_u, const Node &node_v) const -> bool
	Check if a node has a specific successor.

auto	successors (const Node &node) -> auto &
	Get iterator over successors of a node (non-const)

auto	successors (const Node &node) const -> const auto &
	Get iterator over successors of a node (const)

auto	degree (const Node &node) const
	Get the out-degree of a node in the directed graph.

auto	number_of_edges () const -> size_t
	Get the number of edges in the directed graph.

auto	clear ()
	Remove all nodes and edges from the graph.

auto	is_multigraph () const
	Check if the graph is a multigraph.

auto	is_directed () const
	Check if the graph is directed.

Public Member Functions inherited from xnetwork::Graph< _nodeview_t, adjlist_t, adjlist_outer_dict_factory >
	Graph (const nodeview_t &Nodes)
	Construct a graph from a node container.

	Graph (uint32_t num_nodes)
	Construct a graph with a given number of integer nodes.

auto	adj () const
	Get the adjacency mapping of the graph (const version)

auto	adj ()
	Get the adjacency mapping of the graph (non-const version)

auto	_nodes_nbrs () const
	Iterate over nodes and their neighbors.

auto	begin () const
	Begin iterator over nodes.

auto	end () const
	End iterator over nodes.

auto	contains (const Node &node) const -> bool
	Check if a node is in the graph.

auto	operator[] (const Node &node) const -> const auto &
	Access adjacency dict of a node (const version)

auto	at (const Node &node) const -> const auto &
	Access adjacency dict of a node with bounds check (const version)

auto	operator[] (const Node &node) -> auto &
	Access adjacency dict of a node (non-const version)

auto	nodes ()
	Get a NodeView of the graph.

auto	number_of_nodes () const -> size_t
	Get the number of nodes in the graph.

auto	order () const
	Get the number of nodes (same as number_of_nodes)

auto	size () const -> size_t
	Get the number of nodes (same as number_of_nodes)

auto	number_of_edges () const -> size_t
	Get the number of edges in the graph.

auto	edges () const -> std::vector< edge_t >
	Return a vector of all edges as (u, v) pairs.

auto	has_node (const Node &node) const -> bool
	Check if the graph contains a node.

template<typename U = key_type>
auto	add_edge (const Node &node_u, const Node &node_v) -> typename std::enable_if< std::is_same< U, value_type >::value >::type
	Add an edge between two nodes (for simple key type, SFINAE)

template<typename U = key_type>
auto	add_edge (const Node &node_u, const Node &node_v) -> typename std::enable_if<!std::is_same< U, value_type >::value >::type
	Add an edge between two nodes (for complex key type, SFINAE)

template<typename T >
auto	add_edge (const Node &node_u, const Node &node_v, const T &data)
	Add an edge with attached data.

template<typename C1 >
auto	add_edges_from (const C1 &edges)
	Add edges from a container of edge pairs.

template<typename C1 , typename C2 >
auto	add_edges_from (const C1 &edges, const C2 &data)
	Add edges from a container with associated data.

auto	has_edge (const Node &node_u, const Node &node_v) const -> bool
	Check if an edge exists between two nodes.

auto	degree (const Node &node) const
	Get the degree of a node.

auto	clear ()
	Remove all nodes and edges from the graph.

template<typename F >
auto	for_each_edge (F &&func) const -> void
	Apply a callable to each edge without materializing a vector.

auto	is_multigraph () const
	Check if the graph is a multigraph.

auto	is_directed () const
	Check if the graph is directed.

Additional Inherited Members
Static Public Member Functions inherited from xnetwork::Graph< _nodeview_t, adjlist_t, adjlist_outer_dict_factory >
static auto	end_points (edge_t &e) -> edge_t &
	For compatible with BGL adaptor.

static auto	end_points (const edge_t &e) -> const edge_t &
	For compatible with BGL adaptor.

Public Attributes inherited from xnetwork::Graph< _nodeview_t, adjlist_t, adjlist_outer_dict_factory >
size_t	_num_of_edges = 0
	Number of edges in the graph (cached)

nodeview_t	_node
	Container holding all nodes in the graph.

adjlist_outer_dict_factory	_adj
	Adjacency dictionary keyed by node.

Detailed Description

template<typename nodeview_t, typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>
class xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >

Directed graph with arbitrary node types.

A DiGraphS stores nodes and edges with optional data or attributes. Directed edges are stored. Self loops are allowed but multiple (parallel) edges are not. Inherits from the undirected Graph base class.

Template Parameters

nodeview_t	The node container type
adjlist_t	The adjacency list type
adjlist_outer_dict_factory	The outer dict factory

Member Typedef Documentation

◆ edge_t

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

using xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::edge_t = std::pair<Node, Node>

◆ key_type

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

using xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::key_type = typename _Base::key_type

◆ Node

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

using xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::Node = typename _Base::Node

◆ value_type

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

using xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::value_type = typename _Base::value_type

Constructor & Destructor Documentation

◆ DiGraphS() [1/2]

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::DiGraphS ( const nodeview_t & Nodes )

inlineexplicit

Construct a directed graph from a node container.

Parameters

[in] Nodes Container of nodes

◆ DiGraphS() [2/2]

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::DiGraphS ( uint32_t num_nodes )

inlineexplicit

Construct a directed graph with a given number of integer nodes.

Parameters

[in] num_nodes Number of nodes (0 to num_nodes-1)

Member Function Documentation

◆ add_edge() [1/3]

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

template<typename U = key_type>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::add_edge	(	const Node &	node_u,
		const Node &	node_v
	)		-> typename std::enable_if<std::is_same<U, value_type>::value>::type

inline

Add a directed edge between two nodes (for simple key type, SFINAE)

Add an edge between node_u and node_v.

The nodes node_u and node_v will be automatically added if (they are not already : the graph.

Edge attributes can be specified with keywords or by directly accessing the edge"s attribute dictionary. See examples below.

Parameters

node_u, node_v : nodes Nodes can be, for example, strings or numbers. Nodes must be hashable (and not None) C++ objects.

Notes

Adding an edge that already exists updates the edge data.

Many XNetwork algorithms designed for weighted graphs use an edge attribute (by default weight) to hold a numerical value.

Examples

The following all add the edge e=(1, 2) to graph gra) {

> gra = xnetwork::DiGraphS()   // or DiGraph, MultiGraph,

MultiDiGraph, etc > e = (1, 2); > gra.add_edge(1, 2) // explicit two-node form > gra.add_edges_from([(1, 2)]); // add edges from iterable container

Associate data to edges using keywords) {

> gra.add_edge(1, 2);

For non-string attribute keys, use subscript notation.

> gra.add_edge(1, 2);
> gra[1][2].update({0: 5});
> gra.edges()[1, 2].update({0: 5});

Template Parameters

U	Key type parameter for SFINAE dispatch

Parameters

[in]	node_u	Source node
[in]	node_v	Target node

◆ add_edge() [2/3]

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

template<typename U = key_type>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::add_edge	(	const Node &	node_u,
		const Node &	node_v
	)		-> typename std::enable_if<!std::is_same<U, value_type>::value>::type

inline

Add an edge between two nodes (for complex key type)

Template Parameters

U	Key type parameter for SFINAE

Parameters

node_u	Source node
node_v	Target node

◆ add_edge() [3/3]

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

template<typename T >

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::add_edge	(	const Node &	node_u,
		const Node &	node_v,
		const T &	data
	)

inline

Add an edge between two nodes with data.

Template Parameters

T	Type of edge data

Parameters

node_u	Source node
node_v	Target node
data	Edge data to associate with the edge

◆ add_edges_from()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

template<typename C1 , typename C2 >

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::add_edges_from	(	const C1 &	edges,
		const C2 &	data
	)

inline

Add edges from a container with associated data.

Template Parameters

C1	Container type for edges
C2	Container type for edge data

Parameters

edges	Container of edge pairs
data	Container of edge data corresponding to each edge

◆ adj()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::adj ( ) const

inline

Get adjacency mapping (successors) of the directed graph (const version)

◆ clear()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::clear ( )

inline

Remove all nodes and edges from the graph.

◆ degree()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::degree ( const Node & node ) const

inline

Get the out-degree of a node in the directed graph.

Parameters

[in] node The node to get the degree for

Returns: The number of outgoing edges from the node

◆ has_successor()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::has_successor	(	const Node &	node_u,
		const Node &	node_v
	)		const -> bool

inline

Check if a node has a specific successor.

Parameters

[in]	node_u	Source node
[in]	node_v	Potential successor node

Returns: true if the edge u->v exists

◆ is_directed()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::is_directed ( ) const

inline

Check if the graph is directed.

Returns: true (this is a directed graph)

◆ is_multigraph()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::is_multigraph ( ) const

inline

Check if the graph is a multigraph.

Returns: false (this is a simple directed graph)

◆ number_of_edges()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::number_of_edges ( ) const -> size_t

inline

Get the number of edges in the directed graph.

Iterates through the adjacency structure to count edges.

Returns: Number of edges

◆ succ()

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::succ ( ) const

inline

Get the successors mapping (same as adj)

Returns: AdjacencyView of the successor structure

◆ successors() [1/2]

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::successors ( const Node & node ) -> auto&

inline

Get iterator over successors of a node (non-const)

Parameters

[in] node The node to get successors for

Returns: Reference to the adjacency list of the node

◆ successors() [2/2]

template<typename nodeview_t , typename adjlist_t = py::dict<Value_type<nodeview_t>, int>, typename adjlist_outer_dict_factory = py::dict<Value_type<nodeview_t>, adjlist_t>>

auto xnetwork::DiGraphS< nodeview_t, adjlist_t, adjlist_outer_dict_factory >::successors ( const Node & node ) const -> const auto&

inline

Get iterator over successors of a node (const)

Parameters

[in] node The node to get successors for

Returns: Const reference to the adjacency list of the node

The documentation for this class was generated from the following file:

xnetwork/classes/digraphs.hpp

Public Types

Public Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ edge_t

◆ key_type

◆ Node

◆ value_type

Constructor & Destructor Documentation

◆ DiGraphS() [1/2]

◆ DiGraphS() [2/2]

Member Function Documentation

◆ add_edge() [1/3]

Parameters

See Also

Notes

Examples

◆ add_edge() [2/3]

◆ add_edge() [3/3]

◆ add_edges_from()

◆ adj()

◆ clear()

◆ degree()

◆ has_successor()

◆ is_directed()

◆ is_multigraph()

◆ number_of_edges()

◆ succ()

◆ successors() [1/2]

◆ successors() [2/2]