template class NGraph::tGraph¶
Overview¶
#include <ngraph.hpp> template <typename T> class tGraph { public: // typedefs typedef T vertex; typedef T value_type; typedef std::pair<vertex, vertex> edge; typedef std::set<vertex> vertex_set; typedef std::set<edge> edge_set; typedef std::pair<vertex_set, vertex_set> in_out_edge_sets; typedef std::map<vertex, in_out_edge_sets> adj_graph; typedef edge_set::iterator edge_iterator; typedef edge_set::const_iterator const_edge_iterator; typedef vertex_set::iterator vertex_iterator; typedef vertex_set::const_iterator const_vertex_iterator; typedef vertex_set::iterator vertex_neighbor_iterator; typedef vertex_set::const_iterator vertex_neighbor_const_iterator; typedef adj_graph::iterator iterator; typedef adj_graph::const_iterator const_iterator; typedef iterator node_iterator; typedef const_iterator const_node_iterator; // enums enum line_type; // construction tGraph(); tGraph(std::istream& s); tGraph(const tGraph& B); tGraph(const edge_set& E); // methods unsigned int num_vertices() const; unsigned int num_nodes() const; unsigned int num_edges() const; iterator begin(); const_iterator begin() const; iterator end(); const_iterator end() const; void clear(); vertex_neighbor_iterator out_neighbors_begin(const vertex& a); vertex_neighbor_const_iterator out_neighbors_begin(const vertex& a) const; vertex_neighbor_iterator out_neighbors_end(const vertex& a); vertex_neighbor_const_iterator out_neighbors_end(const vertex& a) const; bool is_undirected() const; bool is_directed() const; void set_undirected(); iterator find(const vertex& a); const_iterator find(const vertex& a) const; const vertex_set& in_neighbors(const vertex& a) const; vertex_set& in_neighbors(const vertex& a); const vertex_set& out_neighbors(const vertex& a) const; vertex_set& out_neighbors(const vertex& a); unsigned int in_degree(const vertex& a) const; unsigned int out_degree(const vertex& a) const; unsigned int degree(const vertex& a) const; bool isolated(const vertex& a) const; void insert_vertex(const vertex& a); void insert_new_vertex_inout_list( const vertex& a, const vertex_set& IN, const vertex_set& OUT ); void insert_edge_noloop(iterator pa, iterator pb); void insert_edge(iterator pa, iterator pb); void insert_edge_noloop(const vertex& a, const vertex& b); void insert_edge(const vertex& a, const vertex& b); void insert_undirected_edge(const vertex& a, const vertex& b); void insert_edge(const edge& E); void insert_undirected_edge(const edge& E); bool remove_edge(iterator pa, iterator pb); void remove_edge(const vertex& a, const vertex& b); void remove_edge(const edge& E); void remove_undirected_edge(const vertex& a, const vertex& b); void remove_undirected_edge(const edge& e); void remove_vertex(iterator pa); void remove_vertex_set(const vertex_set& V); void remove_vertex(const vertex& a); bool includes_vertex(const vertex& a) const; bool includes_edge(const vertex& a, const vertex& b) const; bool includes_edge(const edge& e) const; std::vector<edge> edge_list() const; tGraph& plus_eq(const tGraph& B); tGraph intersect(const tGraph& B) const; tGraph operator * (const tGraph& B) const; tGraph minus(const tGraph& B) const; tGraph operator - (const tGraph& B) const; tGraph plus(const tGraph& B) const; tGraph operator + (const tGraph& B) const; tGraph& operator += (const tGraph& B); tGraph subgraph(const vertex_set& A) const; unsigned int subgraph_size(const vertex_set& A) const; double subgraph_sparsity(const vertex_set& A) const; void print() const; void absorb(iterator pa, iterator pb); iterator smart_absorb(iterator pa, iterator pb); vertex smart_absorb(vertex a, vertex b); void absorb(vertex a, vertex b); static const vertex& node(const_iterator p); static const vertex& node(iterator p); static const vertex& node(const_vertex_iterator p); static const vertex_set& in_neighbors(const_iterator p); static vertex_set& in_neighbors(iterator p); static const_vertex_iterator in_begin(const_iterator p); static const_vertex_iterator in_end(const_iterator p); static const vertex_set& out_neighbors(const_iterator p); static const_vertex_iterator out_begin(const_iterator p); static const_vertex_iterator out_end(const_iterator p); static vertex_set& out_neighbors(iterator p); static vertex_iterator out_begin(iterator p); static unsigned int num_edges(const_iterator p); static unsigned int num_edges(iterator p); static unsigned int out_degree(const_iterator p); static unsigned int out_degree(iterator p); static unsigned int in_degree(const_iterator p); static unsigned int in_degree(iterator p); static unsigned int degree(const_iterator p); static unsigned int degree(iterator p); static bool isolated(const_iterator p); static bool isolated(iterator p); static std::istream& read_line( std::istream& s, T& v1, T& v2, std::string& line, line_type& t ); }; // direct descendants class ComputationalGraph;
Detailed Documentation¶
Typedefs¶
typedef adj_graph::iterator iterator
tGraph::iterator refers to pair<const vertex, in_out_edge_sets> .
:ref:`tGraph::const_iterator <doxid-class_n_graph_1_1t_graph_1a64864813622245ff9412c784232f2f99>` p = G.begin();
:ref:`tGraph::vertex <doxid-class_n_graph_1_1t_graph_1a63a04bf8bfc7cf968be524208f49fdee>` a = node(p);
:ref:`tGraph::vertex_set <doxid-class_n_graph_1_1t_graph_1a9e0a5df1ac9a2e6df94431aeaf610b3e>` &in_edges = in_neighbors(p);
:ref:`tGraph::vertex_set <doxid-class_n_graph_1_1t_graph_1a9e0a5df1ac9a2e6df94431aeaf610b3e>` &out_edges = out_neighbors(p);
Methods¶
bool includes_vertex(const vertex& a) const
Is vertex ‘a’ included in graph?
Returns:
true, if vertex a is present; false, otherwise.
bool includes_edge(const vertex& a, const vertex& b) const
Is edge (a,b) included in graph?
Returns:
true, if edge is present; false, otherwise.
std::vector<edge> edge_list() const
Create a new representation of graph as a list of vertex pairs (a,b).
Returns:
std::vector<edge> a vector (list) of vertex pairs
tGraph subgraph(const vertex_set& A) const
Parameters:
A |
vertex set of nodes (subset of G) |
Returns:
a new subgraph containing all nodes of A
void absorb(iterator pa, iterator pb)
abosrb(a,b): ‘a’ absorbs ‘b’, b gets removed from graph
iterator smart_absorb(iterator pa, iterator pb)
c smart_abosrb(a,b): ‘a’ absorbs ‘b’, or b aborbs a, depending on whichever causes the least amount of graph updates
static const vertex& node(const_iterator p)
Parameters:
p |
static unsigned int out_degree(const_iterator p)
Parameters:
p |
Returns:
number of edges going out (out-degree) at node pointed to by p.
static unsigned int in_degree(const_iterator p)
Parameters:
p |
Returns:
number of edges going out (out-degree) at node pointed to by p.