Template Class Graph

Page Contents

Inheritance Relationships

Base Type

Derived Type

Template Parameter Order

  1. typename __nodeview_t

  2. typename adjlist_t

Class Documentation

template<typename __nodeview_t, typename adjlist_t = py::set<Value_type<__nodeview_t>>>
class Graph : public xn::object

Subclassed by xn::VertexView< Graph >

Public Types

using nodeview_t = __nodeview_t
using Node = typename nodeview_t::value_type
using dict = py::dict<const char*, boost::any>
using graph_attr_dict_factory = dict
using adjlist_inner_dict_factory = adjlist_t
using adjlist_outer_dict_factory = std::vector<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 Functions

inline explicit Graph(const nodeview_t &Nodes)

Initialize a graph with edges, name, or graph attributes.

Parameters

node_container : input nodes

Examples

v = std::vector{5, 3, 2}; G = xn::Graph(v); // or DiGraph, MultiGraph, MultiDiGraph, etc

r = py::range(100); G = xn::Graph(r); // or DiGraph, MultiGraph, MultiDiGraph, etc

inline explicit Graph(int num_nodes)
Graph(const Graph&) = delete
Graph &operator=(const Graph&) = delete
Graph(Graph&&) noexcept = default
inline auto adj() const

Graph adjacency object holding the neighbors of each node.

This object is a read-only dict-like structure with node keys and neighbor-dict values. The neighbor-dict is keyed by neighbor to the edge-data-dict. So `G.adj[3][2][‘color’] = ‘blue’sets the color of the edge(3, 2)to”blue”`.

Iterating over G.adj behaves like a dict. Useful idioms include for nbr, datadict in G.adj[n].items():.

The neighbor information is also provided by subscripting the graph. So `for nbr, foovalue in G[node].data(‘foo’, default=1):` works.

For directed graphs, G.adj holds outgoing (successor) info.

inline auto adj()
inline auto _nodes_nbrs() const
inline Node null_vertex() const
inline auto get_name()
inline auto set_name(boost::string_view s)
inline auto begin() const

Iterate over the nodes. Use: “for (auto&& n : G)”.

Returns

niter : iterator An iterator over all nodes : the graph.

Examples

G = xn::path_graph(4); // or DiGraph, MultiGraph, MultiDiGraph, etc [n for n : G];

[0, 1, 2, 3];

list(G);

[0, 1, 2, 3];

inline auto end() const
inline bool contains(const Node &n)

Return true if (n is a node, false otherwise. Use: “n : G”.

Examples

G = xn::path_graph(4); // or DiGraph, MultiGraph, MultiDiGraph, etc 1 : G

true

inline const auto &operator[](const Node &n) const

Return a dict of neighbors of node n. Use: “G[n]”.

Parameters

n : node A node in the graph.

Returns

adj_dict : dictionary The adjacency dictionary for nodes connected to n.

Notes

G[n] is the same as G.adj[n] and similar to G.neighbors(n); (which is an iterator over G.adj[n]);

Examples

G = xn::path_graph(4); // or DiGraph, MultiGraph, MultiDiGraph, etc G[0];

AtlasView({1: {}});

inline auto &operator[](const Node &n)
inline auto nodes()
inline auto number_of_nodes() const

Return the number of nodes : the graph.

Returns

nnodes : int The number of nodes : the graph.

See Also

order, len which are identical

Examples

G = xn::path_graph(3); // or DiGraph, MultiGraph, MultiDiGraph, etc len(G);

3

inline auto number_of_edges() const
inline auto order()

Return the number of nodes : the graph.

Returns

nnodes : int The number of nodes : the graph.

See Also

number_of_nodes, len which are identical

inline auto has_node(const Node &n)

Return true if (the graph contains the node n.

Identical to n : G

Parameters

n : node

Examples

G = xn::path_graph(3); // or DiGraph, MultiGraph, MultiDiGraph, etc G.has_node(0);

true

template<typename U = key_type>
inline std::enable_if<std::is_same<U, value_type>::value>::type add_edge(const Node &u, const Node &v)

Add an edge between u and v.

The nodes u and 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

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

See Also

add_edges_from : add a collection of edges

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 G) {

G = xn::Graph() // or DiGraph, MultiGraph, MultiDiGraph, etc e = (1, 2); G.add_edge(1, 2) // explicit two-node form G.add_edges_from([(1, 2)]); // add edges from iterable container

Associate data to edges using keywords) {

G.add_edge(1, 2);

For non-string attribute keys, use subscript notation.

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

template<typename U = key_type>
inline std::enable_if<!std::is_same<U, value_type>::value>::type add_edge(const Node &u, const Node &v)
template<typename T>
inline auto add_edge(const Node &u, const Node &v, const T &data)
template<typename C1, typename C2>
inline auto add_edges_from(const C1 &edges, const C2 &data)
inline auto has_edge(const Node &u, const Node &v) -> bool
inline auto degree(const Node &n) const
inline auto clear()

An EdgeView of the Graph as G.edges().

edges( nbunch=None, data=false, default=None);

The EdgeView provides set-like operations on the edge-tuples as well as edge attribute lookup. When called, it also provides an EdgeDataView object which allows control of access to edge attributes (but does not provide set-like operations). Hence, G.edges[u, v]["color"] provides the value of the color attribute for edge (u, v) while for (auto [u, v, c] : G.edges.data("color", default="red") { iterates through all the edges yielding the color attribute with default "red" if (no color attribute exists.

Parameters

nbunch : single node, container, or all nodes (default= all nodes); The view will only report edges incident to these nodes. data : string or bool, optional (default=false); The edge attribute returned : 3-tuple (u, v, ddict[data]). If true, return edge attribute dict : 3-tuple (u, v, ddict). If false, return 2-tuple (u, v). default : value, optional (default=None); Value used for edges that don”t have the requested attribute. Only relevant if (data is not true or false.

Returns

edges : EdgeView A view of edge attributes, usually it iterates over (u, v); or (u, v, d) tuples of edges, but can also be used for attribute lookup as edges[u, v]["foo"].

Notes

Nodes : nbunch that are not : the graph will be (quietly) ignored. For directed graphs this returns the out-edges.

Examples

G = xn::path_graph(3) // or MultiGraph, etc G.add_edge(2, 3, weight=5); [e for e : G.edges];

[(0, 1), (1, 2), (2, 3)];

G.edges.data(); // default data is {} (empty dict);

EdgeDataView([(0, 1, {}), (1, 2, {}), (2, 3, {“weight”: 5})]);

G.edges.data(“weight”, default=1);

EdgeDataView([(0, 1, 1), (1, 2, 1), (2, 3, 5)]);

G.edges([0, 3]); // only edges incident to these nodes

EdgeDataView([(0, 1), (3, 2)]);

G.edges(0); // only edges incident to a single node (use

G.adj[0]?); EdgeDataView([(0, 1)]); 
           A DegreeView for the Graph as G.degree or G.degree().

The node degree is the number of edges adjacent to the node. The weighted node degree is the sum of the edge weights for edges incident to that node.

This object provides an iterator for (node, degree) as well as lookup for the degree for a single node.

Parameters

nbunch : single node, container, or all nodes (default= all nodes); The view will only report edges incident to these nodes.

weight : string or None, optional (default=None); The name of an edge attribute that holds the numerical value used as a weight. If None, then each edge has weight 1. The degree is the sum of the edge weights adjacent to the node.

Returns

If a single node is requested deg : int Degree of the node

OR if (multiple nodes are requested nd_view : A DegreeView object capable of iterating (node, degree) pairs

Examples

G = xn::path_graph(4); // or DiGraph, MultiGraph, MultiDiGraph,

etc

G.degree[0]; // node 0 has degree 1

1

list(G.degree([0, 1, 2]));

[(0, 1), (1, 2), (2, 2)];

inline auto is_multigraph()

Return true if (graph is a multigraph, false otherwise.

inline auto is_directed()

Return true if (graph is directed, false otherwise.

Public Members

size_t _num_of_edges = 0
nodeview_t _node
graph_attr_dict_factory graph = {}
adjlist_outer_dict_factory _adj

Public Static Functions

static inline edge_t &end_points(edge_t &e)

For compatible with BGL adaptor.

Parameters

e – [in]

Returns

edge_t&

static inline const edge_t &end_points(const edge_t &e)

For compatible with BGL adaptor.

Parameters

e – [in]

Returns

edge_t&