#include <graph.hpp>
Public Member Functions | |
| undirected_graph () | |
| constructs an empty graph | |
| undirected_graph (unsigned int n_v) | |
| constructs an graph with n_v vertices but no links | |
| undirected_graph (unsigned int n_v, unsigned int n_l) | |
| constructs an undirected graph with n_v vertices and n_l links | |
| qint | degree (vertex_type v) const |
| return the degree of vertex v | |
| link_type | link (vertex_type v1, vertex_type v2) const |
find the first shared link of vertices v1, v2. | |
| bool | are_linked (vertex_type v1, vertex_type v2) const |
| determine wether two vertices v1 and v2 share at least one link | |
| bool | same_link (link_type l1, link_type l2) const |
return true if both l1 and l2 identify the same undirected link | |
| qint | no_of_links (vertex_type v1, vertex_type v2) const |
| determine the number of undirected links shared by vertices v1 and v2. | |
| unsigned int | nv () const |
| return the current number of vertices in the graph | |
| unsigned int | n_vertices () const |
| return the current number of vertices in the graph | |
| unsigned int | nl () const |
| return the current number of links in the graph | |
| unsigned int | n_links () const |
| return the current number of links in the graph | |
| link_type | linkpool (unsigned int i) const |
| return the nth link identifier. | |
| vertex_type | add_vertex () |
| add a new vertex to the graph and return the vertex index. | |
| void | remove_vertex (vertex_type vertex) |
remove teh given vertex along with all links pointing to that vertex. | |
| link_type | add_link (vertex_type, vertex_type) |
| add a new link between two existing sites | |
| void | remove_link (link_type l) |
| remove the given link and put it to the pool | |
| void | remove_link (vertex_type v1, vertex_type v2) |
find the first link shared between v1 and v2, remove it and put it to the link pool | |
| void | switch_link (link_type link, vertex_type to) |
switch an undirected link to point to a new target vertex to. | |
| void | switch_link (link_type link, link_type link_inverse, vertex_type to) |
switch an undirected link to point to a new target vertex to. | |
| void | cross_links (link_type link1, link_type link2) |
cross the given undirected links, so that link1 connects to the target of link2 and vice versa. | |
| vertex_type | target (link_type link) const |
| return the target vertex of a given link | |
| vertex_type | source (int link) const |
| return the source vertex of the link | |
| link_type | out_link (vertex_type v) const |
return the first link emerging the node v. | |
| link_type | next_out_link (link_type l) const |
| return the next link emerging from the same link. | |
| void | clear () |
| remove all links and vertices from the graph | |
| void | gen_BarabasiAlbert (qint m, vertex_type N0=2) |
| construct a random graph, applying the preferential attachment method described by Barabasi and Albert. | |
| void | gen_ErdosRenyi (double p) |
construct a random simple graph, sampling from the G(N,p) model of Erdos and Renyi. | |
| void | gen_ErdosRenyi_N (unsigned int L) |
constructs a random graph, sampling from the G(N,L) model of Erdos and Renyi. | |
| void | gen_DMS (qint m, double alpha) |
| construct a random graph according to the DMS model by Dorogovtsev, Mendes, Samukhin. | |
| void | gen_CompleteGraph (vertex_type N) |
construct a complete graph with the given number N of vertices. | |
| void | gen_CompleteGraph () |
| construct a complete graph with the set number of vertices. | |
| void | gen_InitialLinks (link_type) |
construct a graph adding L of links. | |
| void | gen_RegularLattice (qint d, int L) |
| construct a d-dimensional square lattice | |
| std::istream & | load_adjacencylist (std::istream &) |
| std::istream & | load_adjacencymatrix (std::istream &) |
| std::istream & | load_linklist (std::istream &) |
Static Public Attributes | |
| static const link_type | null_link = -1 |
Protected Member Functions | |
| void | resize_link_tables (unsigned int n) |
| void | resize_site_tables (unsigned int n) |
| link_type | link_to (link_type l, vertex_type v) const |
find next link in list that points to v | |
Friends | |
| std::istream & | operator>> (std::istream &is, undirected_graph &graph) |
| input operator for use with std::istream. | |
Classes | |
| class | ibreadth |
| Breadth first search iterator. More... | |
| class | idepth |
| Depth first search iterator. More... | |
| class | ilinks |
| Iterator over all undirected links of a graph. More... | |
| class | ineighbors |
| Iterator over the neighbors of a start node. More... | |
| class | isequence |
| Simple node sequence iterator. More... | |
The graph G(V,E), consisting of a set of vertices V and a set of edges E connecting vertices is represented with adjacency lists. For every vertex, a list of emerging edges is maintained via the l_out member, the link target is stored in the field target. The next item pointers of this list are stored in l_next. Only undirected graphs are supported, so there can be made some simplifications, as for every edge there exists an inverse edge connecting the same two vertices in the opposite direction.
Computation of observables might take global properties of the entire graph into account to perform better. Some global properties are tracked and updated according to graph operations (updates).
| link_type graphgen::undirected_graph::link | ( | vertex_type | v1, | |
| vertex_type | v2 | |||
| ) | const [inline] |
find the first shared link of vertices v1, v2.
Return null_link if v1, v2 are not directly connected. The link returned has the direction v1 -> v2.
cost k
References degree(), next_out_link(), out_link(), and target().
Referenced by are_linked(), gen_BarabasiAlbert(), no_of_links(), remove_link(), and remove_vertex().
| bool graphgen::undirected_graph::are_linked | ( | vertex_type | v1, | |
| vertex_type | v2 | |||
| ) | const [inline] |
determine wether two vertices v1 and v2 share at least one link
cost k/2
References link().
Referenced by graphgen::estimate_clustering_coeff_local(), graphgen::estimate_number_triangles(), gen_ErdosRenyi_N(), and graphgen::shape::simple< W >::operator()().
| qint graphgen::undirected_graph::no_of_links | ( | vertex_type | v1, | |
| vertex_type | v2 | |||
| ) | const [inline] |
determine the number of undirected links shared by vertices v1 and v2.
for v1!= v2 the
v1=k, v2=l - for v1=v2=k it is mkkReferences degree(), link(), and link_to().
Referenced by graphgen::Ratio< R >::operator()().
| link_type graphgen::undirected_graph::linkpool | ( | unsigned int | i | ) | const [inline] |
return the nth link identifier.
Index range is [0,2*nl)
Referenced by graphgen::shape::multigraph< W >::operator()(), graphgen::shape::noselflinks< W >::operator()(), and graphgen::shape::simple< W >::operator()().
| vertex_type graphgen::undirected_graph::add_vertex | ( | ) |
add a new vertex to the graph and return the vertex index.
Data structures are initialized for the new vertex.
| void graphgen::undirected_graph::remove_vertex | ( | vertex_type | vertex | ) |
remove teh given vertex along with all links pointing to that vertex.
Data structures are not tidied up after removal.
References link(), next_out_link(), out_link(), and remove_link().
| void graphgen::undirected_graph::switch_link | ( | link_type | link, | |
| vertex_type | to | |||
| ) | [inline] |
switch an undirected link to point to a new target vertex to.
link will afterwards point to this site, while the inverse link will then belong to this site.
cost: <k>
Referenced by cross_links().
| void graphgen::undirected_graph::switch_link | ( | link_type | link, | |
| link_type | link_inverse, | |||
| vertex_type | to | |||
| ) | [inline] |
switch an undirected link to point to a new target vertex to.
link will afterwards point to this site, while link_inverse will then belong to this site.
cost: <k>
References target().
| void graphgen::undirected_graph::cross_links | ( | link_type | link1, | |
| link_type | link2 | |||
| ) | [inline] |
cross the given undirected links, so that link1 connects to the target of link2 and vice versa.
suitable for X-move updates.
References switch_link(), and target().
| link_type graphgen::undirected_graph::out_link | ( | vertex_type | v | ) | const [inline] |
return the first link emerging the node v.
null_link if the given vertex has degree 0
Referenced by link(), graphgen::shape::tree< W >::operator()(), graphgen::undirected_graph::idepth::operator++(), graphgen::undirected_graph::ibreadth::operator++(), and remove_vertex().
| link_type graphgen::undirected_graph::next_out_link | ( | link_type | l | ) | const [inline] |
return the next link emerging from the same link.
null_link if this is the last
Referenced by link(), link_to(), graphgen::undirected_graph::idepth::operator++(), graphgen::undirected_graph::ibreadth::operator++(), graphgen::undirected_graph::ineighbors::operator++(), and remove_vertex().
| void graphgen::undirected_graph::gen_BarabasiAlbert | ( | qint | m, | |
| vertex_type | N0 = 2 | |||
| ) |
construct a random graph, applying the preferential attachment method described by Barabasi and Albert.
Each new vertex will be connected to m vertices in the graph. Before adding vertices, the graph is seeded with a complete graph consisting of N0 sites.
References add_link(), gen_CompleteGraph(), link(), nl(), nv(), and target().
| void graphgen::undirected_graph::gen_ErdosRenyi | ( | double | p | ) |
construct a random simple graph, sampling from the G(N,p) model of Erdos and Renyi.
Graphs are choosen from {G(n,M), M in [0,n*(n-1)/2]} with each graph from G(n,M) having the same probability.
References add_link(), clear(), and nv().
| void graphgen::undirected_graph::gen_ErdosRenyi_N | ( | unsigned int | L | ) |
constructs a random graph, sampling from the G(N,L) model of Erdos and Renyi.
Graphs contain n vertices and M links.
References add_link(), are_linked(), clear(), nl(), and nv().
| void graphgen::undirected_graph::gen_DMS | ( | qint | m, | |
| double | alpha | |||
| ) |
construct a random graph according to the DMS model by Dorogovtsev, Mendes, Samukhin.
The method of generation is similar to that of Barabasi and Albert, but with an initial attractivity alpha > -1 that each vertex has, resulting in a power law degree distribution that can be tuned to an arbitrary exponent larger than 2.
| void graphgen::undirected_graph::gen_InitialLinks | ( | link_type | N | ) |
construct a graph adding L of links.
The first N links are added in a star pattern. When exceeding the complete graph, multiple links are added.
References add_link(), clear(), nl(), and nv().
Referenced by undirected_graph().
| std::istream& operator>> | ( | std::istream & | is, | |
| undirected_graph & | graph | |||
| ) | [friend] |
input operator for use with std::istream.
For the construction of the graph ... is used
1.5.6