|
libDAI
|
Represents the neighborhood structure of nodes in an undirected, bipartite graph. More...
#include <dai/bipgraph.h>
Classes | |
| struct | levelType |
| Used internally by isTree() More... | |
Public Member Functions | |
Constructors and destructors | |
| BipartiteGraph () | |
| Default constructor (creates an empty bipartite graph) | |
| BipartiteGraph (size_t nr1, size_t nr2) | |
| Constructs BipartiteGraph with nr1 nodes of type 1, nr2 nodes of type 2 and no edges. | |
| template<typename EdgeInputIterator > | |
| BipartiteGraph (size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true) | |
| Constructs BipartiteGraph from a range of edges. | |
Accessors and mutators | |
| const Neighbor & | nb1 (size_t i1, size_t _i2) const |
| Returns constant reference to the _i2 'th neighbor of node i1 of type 1. | |
| Neighbor & | nb1 (size_t i1, size_t _i2) |
| Returns reference to the _i2 'th neighbor of node i1 of type 1. | |
| const Neighbor & | nb2 (size_t i2, size_t _i1) const |
| Returns constant reference to the _i1 'th neighbor of node i2 of type 2. | |
| Neighbor & | nb2 (size_t i2, size_t _i1) |
| Returns reference to the _i1 'th neighbor of node i2 of type 2. | |
| const Neighbors & | nb1 (size_t i1) const |
| Returns constant reference to all neighbors of node i1 of type 1. | |
| Neighbors & | nb1 (size_t i1) |
| Returns reference to all neighbors of node i1 of type 1. | |
| const Neighbors & | nb2 (size_t i2) const |
| Returns constant reference to all neighbors of node i2 of type 2. | |
| Neighbors & | nb2 (size_t i2) |
| Returns reference to all neighbors of node i2 of type 2. | |
Adding nodes and edges | |
| template<typename EdgeInputIterator > | |
| void | construct (size_t nrNodes1, size_t nrNodes2, EdgeInputIterator begin, EdgeInputIterator end, bool check=true) |
| (Re)constructs BipartiteGraph from a range of edges. | |
| size_t | addNode1 () |
| Adds a node of type 1 without neighbors and returns the index of the added node. | |
| size_t | addNode2 () |
| Adds a node of type 2 without neighbors and returns the index of the added node. | |
| template<typename NodeInputIterator > | |
| size_t | addNode1 (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0) |
| Adds a node of type 1, with neighbors specified by a range of nodes of type 2. | |
| template<typename NodeInputIterator > | |
| size_t | addNode2 (NodeInputIterator begin, NodeInputIterator end, size_t sizeHint=0) |
| Adds a node of type 2, with neighbors specified by a range of nodes of type 1. | |
| BipartiteGraph & | addEdge (size_t n1, size_t n2, bool check=true) |
| Adds an edge between node n1 of type 1 and node n2 of type 2. | |
Erasing nodes and edges | |
| void | eraseNode1 (size_t n1) |
| Removes node n1 of type 1 and all incident edges; indices of other nodes are changed accordingly. | |
| void | eraseNode2 (size_t n2) |
| Removes node n2 of type 2 and all incident edges; indices of other nodes are changed accordingly. | |
| void | eraseEdge (size_t n1, size_t n2) |
| Removes edge between node n1 of type 1 and node n2 of type 2. | |
Queries | |
| size_t | nrNodes1 () const |
| Returns number of nodes of type 1. | |
| size_t | nrNodes2 () const |
| Returns number of nodes of type 2. | |
| size_t | nrEdges () const |
| Calculates the number of edges, time complexity: O(nrNodes1()) | |
| bool | hasEdge (size_t n1, size_t n2) const |
| Returns true if the graph contains an edge between node n1 of type 1 and node n2 of type 2. | |
| size_t | findNb1 (size_t n1, size_t n2) |
| Returns the index of a given node n2 of type 2 amongst the neighbors of node n1 of type 1. | |
| size_t | findNb2 (size_t n1, size_t n2) |
| Returns the index of a given node n1 of type 1 amongst the neighbors of node n2 of type 2. | |
| SmallSet< size_t > | nb1Set (size_t n1) const |
| Returns neighbors of node n1 of type 1 as a SmallSet<size_t>. | |
| SmallSet< size_t > | nb2Set (size_t n2) const |
| Returns neighbors of node n2 of type 2 as a SmallSet<size_t>. | |
| SmallSet< size_t > | delta1 (size_t n1, bool include=false) const |
| Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1. | |
| SmallSet< size_t > | delta2 (size_t n2, bool include=false) const |
| Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2. | |
| bool | isConnected () const |
| Returns true if the graph is connected. | |
| bool | isTree () const |
| Returns true if the graph is a tree, i.e., if it is singly connected and connected. | |
| bool | operator== (const BipartiteGraph &x) const |
| Comparison operator which returns true if two graphs are identical. | |
| void | checkConsistency () const |
| Asserts internal consistency. | |
Private Attributes | |
| std::vector< Neighbors > | _nb1 |
| Contains for each node of type 1 a vector of its neighbors. | |
| std::vector< Neighbors > | _nb2 |
| Contains for each node of type 2 a vector of its neighbors. | |
Input and output | |
| void | printDot (std::ostream &os) const |
| Writes this BipartiteGraph to an output stream in GraphViz .dot syntax. | |
| std::ostream & | operator<< (std::ostream &os, const BipartiteGraph &g) |
| Writes this BipartiteGraph to an output stream. | |
Represents the neighborhood structure of nodes in an undirected, bipartite graph.
A bipartite graph has two types of nodes: type 1 and type 2. Edges can occur only between nodes of different type. Nodes are indexed by an unsigned integer. If there are nrNodes1() nodes of type 1 and nrNodes2() nodes of type 2, the nodes of type 1 are numbered 0,1,2,...,nrNodes1()-1 and the nodes of type 2 are numbered 0,1,2,...,nrNodes2()-1. An edge between node n1 of type 1 and node n2 of type 2 is represented by a Edge(n1,n2).
A BipartiteGraph is implemented as a sparse adjacency list, i.e., it stores for each node a list of its neighboring nodes. More precisely: it stores for each node of type 1 a vector of Neighbor structures (accessible by the nb1() method) describing the neighboring nodes of type 2; similarly, for each node of type 2 it stores a vector of Neighbor structures (accessibly by the nb2() method) describing the neighboring nodes of type 1. Thus, each node has an associated variable of type BipartiteGraph::Neighbors, which is a vector of Neighbor structures, describing its neighboring nodes of the other type.
| dai::BipartiteGraph::BipartiteGraph | ( | ) | [inline] |
Default constructor (creates an empty bipartite graph)
| dai::BipartiteGraph::BipartiteGraph | ( | size_t | nr1, |
| size_t | nr2 | ||
| ) | [inline] |
Constructs BipartiteGraph with nr1 nodes of type 1, nr2 nodes of type 2 and no edges.
| dai::BipartiteGraph::BipartiteGraph | ( | size_t | nrNodes1, |
| size_t | nrNodes2, | ||
| EdgeInputIterator | begin, | ||
| EdgeInputIterator | end, | ||
| bool | check = true |
||
| ) | [inline] |
Constructs BipartiteGraph from a range of edges.
| EdgeInputIterator | Iterator that iterates over instances of Edge. |
| nrNodes1 | The number of nodes of type 1. |
| nrNodes2 | The number of nodes of type 2. |
| begin | Points to the first edge. |
| end | Points just beyond the last edge. |
| check | Whether to only add an edge if it does not exist already. |
| const Neighbor& dai::BipartiteGraph::nb1 | ( | size_t | i1, |
| size_t | _i2 | ||
| ) | const [inline] |
Returns constant reference to the _i2 'th neighbor of node i1 of type 1.
| Neighbor& dai::BipartiteGraph::nb1 | ( | size_t | i1, |
| size_t | _i2 | ||
| ) | [inline] |
Returns reference to the _i2 'th neighbor of node i1 of type 1.
| const Neighbor& dai::BipartiteGraph::nb2 | ( | size_t | i2, |
| size_t | _i1 | ||
| ) | const [inline] |
Returns constant reference to the _i1 'th neighbor of node i2 of type 2.
| Neighbor& dai::BipartiteGraph::nb2 | ( | size_t | i2, |
| size_t | _i1 | ||
| ) | [inline] |
Returns reference to the _i1 'th neighbor of node i2 of type 2.
| const Neighbors& dai::BipartiteGraph::nb1 | ( | size_t | i1 | ) | const [inline] |
Returns constant reference to all neighbors of node i1 of type 1.
| Neighbors& dai::BipartiteGraph::nb1 | ( | size_t | i1 | ) | [inline] |
Returns reference to all neighbors of node i1 of type 1.
| const Neighbors& dai::BipartiteGraph::nb2 | ( | size_t | i2 | ) | const [inline] |
Returns constant reference to all neighbors of node i2 of type 2.
| Neighbors& dai::BipartiteGraph::nb2 | ( | size_t | i2 | ) | [inline] |
Returns reference to all neighbors of node i2 of type 2.
| void dai::BipartiteGraph::construct | ( | size_t | nrNodes1, |
| size_t | nrNodes2, | ||
| EdgeInputIterator | begin, | ||
| EdgeInputIterator | end, | ||
| bool | check = true |
||
| ) |
(Re)constructs BipartiteGraph from a range of edges.
| EdgeInputIterator | Iterator that iterates over instances of Edge. |
| nrNodes1 | The number of nodes of type 1. |
| nrNodes2 | The number of nodes of type 2. |
| begin | Points to the first edge. |
| end | Points just beyond the last edge. |
| check | Whether to only add an edge if it does not exist already. |
| size_t dai::BipartiteGraph::addNode1 | ( | ) | [inline] |
Adds a node of type 1 without neighbors and returns the index of the added node.
| size_t dai::BipartiteGraph::addNode2 | ( | ) | [inline] |
Adds a node of type 2 without neighbors and returns the index of the added node.
| size_t dai::BipartiteGraph::addNode1 | ( | NodeInputIterator | begin, |
| NodeInputIterator | end, | ||
| size_t | sizeHint = 0 |
||
| ) | [inline] |
Adds a node of type 1, with neighbors specified by a range of nodes of type 2.
| NodeInputIterator | Iterator that iterates over instances of size_t. |
| begin | Points to the first index of the nodes of type 2 that should become neighbors of the added node. |
| end | Points just beyond the last index of the nodes of type 2 that should become neighbors of the added node. |
| sizeHint | For improved efficiency, the size of the range may be specified by sizeHint. |
| size_t dai::BipartiteGraph::addNode2 | ( | NodeInputIterator | begin, |
| NodeInputIterator | end, | ||
| size_t | sizeHint = 0 |
||
| ) | [inline] |
Adds a node of type 2, with neighbors specified by a range of nodes of type 1.
| NodeInputIterator | Iterator that iterates over instances of size_t. |
| begin | Points to the first index of the nodes of type 1 that should become neighbors of the added node. |
| end | Points just beyond the last index of the nodes of type 1 that should become neighbors of the added node. |
| sizeHint | For improved efficiency, the size of the range may be specified by sizeHint. |
| BipartiteGraph & dai::BipartiteGraph::addEdge | ( | size_t | n1, |
| size_t | n2, | ||
| bool | check = true |
||
| ) |
Adds an edge between node n1 of type 1 and node n2 of type 2.
If check == true, only adds the edge if it does not exist already.
| void dai::BipartiteGraph::eraseNode1 | ( | size_t | n1 | ) |
Removes node n1 of type 1 and all incident edges; indices of other nodes are changed accordingly.
| void dai::BipartiteGraph::eraseNode2 | ( | size_t | n2 | ) |
Removes node n2 of type 2 and all incident edges; indices of other nodes are changed accordingly.
| void dai::BipartiteGraph::eraseEdge | ( | size_t | n1, |
| size_t | n2 | ||
| ) |
Removes edge between node n1 of type 1 and node n2 of type 2.
| size_t dai::BipartiteGraph::nrNodes1 | ( | ) | const [inline] |
Returns number of nodes of type 1.
| size_t dai::BipartiteGraph::nrNodes2 | ( | ) | const [inline] |
Returns number of nodes of type 2.
| size_t dai::BipartiteGraph::nrEdges | ( | ) | const [inline] |
Calculates the number of edges, time complexity: O(nrNodes1())
| bool dai::BipartiteGraph::hasEdge | ( | size_t | n1, |
| size_t | n2 | ||
| ) | const [inline] |
Returns true if the graph contains an edge between node n1 of type 1 and node n2 of type 2.
| size_t dai::BipartiteGraph::findNb1 | ( | size_t | n1, |
| size_t | n2 | ||
| ) | [inline] |
Returns the index of a given node n2 of type 2 amongst the neighbors of node n1 of type 1.
| OBJECT_NOT_FOUND | if n2 is not a neighbor of n1 |
| size_t dai::BipartiteGraph::findNb2 | ( | size_t | n1, |
| size_t | n2 | ||
| ) | [inline] |
Returns the index of a given node n1 of type 1 amongst the neighbors of node n2 of type 2.
| OBJECT_NOT_FOUND | if n1 is not a neighbor of n2 |
| SmallSet< size_t > dai::BipartiteGraph::nb1Set | ( | size_t | n1 | ) | const |
Returns neighbors of node n1 of type 1 as a SmallSet<size_t>.
| SmallSet< size_t > dai::BipartiteGraph::nb2Set | ( | size_t | n2 | ) | const |
Returns neighbors of node n2 of type 2 as a SmallSet<size_t>.
| SmallSet< size_t > dai::BipartiteGraph::delta1 | ( | size_t | n1, |
| bool | include = false |
||
| ) | const |
Calculates second-order neighbors (i.e., neighbors of neighbors) of node n1 of type 1.
If include == true, includes n1 itself, otherwise excludes n1.
| SmallSet< size_t > dai::BipartiteGraph::delta2 | ( | size_t | n2, |
| bool | include = false |
||
| ) | const |
Calculates second-order neighbors (i.e., neighbors of neighbors) of node n2 of type 2.
If include == true, includes n2 itself, otherwise excludes n2.
| bool dai::BipartiteGraph::isConnected | ( | ) | const |
Returns true if the graph is connected.
| bool dai::BipartiteGraph::isTree | ( | ) | const |
Returns true if the graph is a tree, i.e., if it is singly connected and connected.
| bool dai::BipartiteGraph::operator== | ( | const BipartiteGraph & | x | ) | const [inline] |
Comparison operator which returns true if two graphs are identical.
*this has an edge between nodes n1 and n2). | void dai::BipartiteGraph::checkConsistency | ( | ) | const |
Asserts internal consistency.
| void dai::BipartiteGraph::printDot | ( | std::ostream & | os | ) | const |
Writes this BipartiteGraph to an output stream in GraphViz .dot syntax.
| std::ostream& operator<< | ( | std::ostream & | os, |
| const BipartiteGraph & | g | ||
| ) | [friend] |
Writes this BipartiteGraph to an output stream.
std::vector<Neighbors> dai::BipartiteGraph::_nb1 [private] |
Contains for each node of type 1 a vector of its neighbors.
std::vector<Neighbors> dai::BipartiteGraph::_nb2 [private] |
Contains for each node of type 2 a vector of its neighbors.
1.7.4