|
SNAP Library 2.1, User Reference
2013-09-25 10:47:25
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
|
SNAP Library 2.1, User Reference
2013-09-25 10:47:25
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
|
Node Network (directed graph, TNGraph with data on nodes only). More...
#include <network.h>
Classes | |
| class | TEdgeI |
| Edge iterator. Only forward iteration (operator++) is supported. More... | |
| class | TNode |
| class | TNodeI |
| Node iterator. Only forward iteration (operator++) is supported. More... | |
Public Types | |
| typedef TNodeData | TNodeDat |
| typedef TNodeNet< TNodeData > | TNet |
| typedef TPt< TNet > | PNet |
Public Member Functions | |
| TNodeNet () | |
| TNodeNet (const int &Nodes, const int &Edges) | |
| Constructor that reserves enough memory for a network of Nodes nodes and Edges edges. | |
| TNodeNet (const TNodeNet &NodeNet) | |
| TNodeNet (TSIn &SIn) | |
| Constructor that loads the network from a (binary) stream SIn. | |
| virtual | ~TNodeNet () |
| virtual void | Save (TSOut &SOut) const |
| Saves the network to a (binary) stream SOut. | |
| bool | HasFlag (const TGraphFlag &Flag) const |
| Allows for run-time checking the type of the network (see the TGraphFlag for flags). | |
| TNodeNet & | operator= (const TNodeNet &NodeNet) |
| int | GetNodes () const |
| Returns the number of nodes in the network. | |
| int | AddNode (int NId=-1) |
| Adds a node of ID NId to the network. | |
| int | AddNode (int NId, const TNodeData &NodeDat) |
| Adds a node of ID NId and node data NodeDat to the network. | |
| int | AddNode (const TNodeI &NodeId) |
| Adds a node NodeId and its node data to the network. | |
| void | DelNode (const int &NId) |
| Deletes node of ID NId from the network. | |
| void | DelNode (const TNode &NodeI) |
| Deletes node of ID NodeI.GetId() from the network. | |
| bool | IsNode (const int &NId) const |
| Tests whether ID NId is a node. | |
| TNodeI | BegNI () const |
| Returns an iterator referring to the first node in the network. | |
| TNodeI | EndNI () const |
| Returns an iterator referring to the past-the-end node in the network. | |
| TNodeI | GetNI (const int &NId) const |
| Returns an iterator referring to the node of ID NId in the network. | |
| const TNode & | GetNode (const int &NId) const |
| Returns node element for the node of ID NId in the network. | |
| void | SetNDat (const int &NId, const TNodeData &NodeDat) |
| Sets node data for the node of ID NId in the network. | |
| TNodeData & | GetNDat (const int &NId) |
| Returns node data for the node of ID NId in the network. | |
| const TNodeData & | GetNDat (const int &NId) const |
| Returns node data for the node of ID NId in the network. | |
| int | GetMxNId () const |
| Returns the maximum id of a any node in the network. | |
| int | GetEdges () const |
| Returns the number of edges in the network. | |
| int | AddEdge (const int &SrcNId, const int &DstNId) |
| Adds an edge from node IDs SrcNId to node DstNId to the network. | |
| int | AddEdge (const TEdgeI &EdgeI) |
| Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the network. | |
| void | DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true) |
| Deletes an edge from node IDs SrcNId to DstNId from the network. | |
| bool | IsEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true) const |
| Tests whether an edge from node IDs SrcNId to DstNId exists in the network. | |
| TEdgeI | BegEI () const |
| Returns an iterator referring to the first edge in the network. | |
| TEdgeI | EndEI () const |
| Returns an iterator referring to the past-the-end edge in the network. | |
| TEdgeI | GetEI (const int &EId) const |
| Not supported/implemented! | |
| TEdgeI | GetEI (const int &SrcNId, const int &DstNId) const |
| Returns an iterator referring to edge (SrcNId, DstNId) in the network. | |
| int | GetRndNId (TRnd &Rnd=TInt::Rnd) |
| Returns an ID of a random node in the network. | |
| TNodeI | GetRndNI (TRnd &Rnd=TInt::Rnd) |
| Returns an interator referring to a random node in the network. | |
| void | GetNIdV (TIntV &NIdV) const |
| Gets a vector IDs of all nodes in the network. | |
| bool | Empty () const |
| Tests whether the network is empty (has zero nodes). | |
| void | Clr (const bool &DoDel=true, const bool &ResetDat=true) |
| Deletes all nodes and edges from the network. | |
| void | Reserve (const int &Nodes, const int &Edges) |
| Reserves memory for a network of Nodes nodes and Edges edges. | |
| void | SortNIdById (const bool &Asc=true) |
| Sorts nodes by node IDs. | |
| void | SortNIdByDat (const bool &Asc=true) |
| Sorts nodes by node data. | |
| void | Defrag (const bool &OnlyNodeLinks=false) |
| Defragments the network. | |
| bool | IsOk (const bool &ThrowExcept=true) const |
| Checks the network data structure for internal consistency. | |
Static Public Member Functions | |
| static PNet | New () |
| Static constructor that returns a pointer to the network. Call: TPt <TNodeNet<TNodeData> > Net = TNodeNet<TNodeData>::New(). | |
| static PNet | Load (TSIn &SIn) |
| Static constructor that loads the network from a stream SIn and returns a pointer to it. | |
Protected Member Functions | |
| TNode & | GetNode (const int &NId) |
Protected Attributes | |
| TCRef | CRef |
| TInt | MxNId |
| THash< TInt, TNode > | NodeH |
Friends | |
| class | TPt< TNodeNet< TNodeData > > |
Node Network (directed graph, TNGraph with data on nodes only).
| int TNodeNet< TNodeData >::AddEdge | ( | const int & | SrcNId, |
| const int & | DstNId | ||
| ) |
Adds an edge from node IDs SrcNId to node DstNId to the network.
If the edge already exists return -2. If the edge was successfully added return -1. Normally the function should return an ID of the edge added but since edges in TNodeNet have no IDs we return -1. Function aborts if SrcNId or DstNId are not nodes in the network.
Adds a node of ID NId to the network.
Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.
Adds a node of ID NId and node data NodeDat to the network.
Returns the ID of the node being added. If NId is -1, node ID is automatically assigned. Aborts, if a node with ID NId already exists.
Defragments the network.
After performing many node and edge insertions and deletions to a network, the network data structure will be fragmented in memory. This function compacts down the network data structure and frees unneeded memory.
Definition at line 373 of file network.h.
{
for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
TNode& Node = NodeH[n];
Node.InNIdV.Pack(); Node.OutNIdV.Pack();
}
if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
NodeH.Defrag(); }
}
| void TNodeNet< TNodeData >::DelEdge | ( | const int & | SrcNId, |
| const int & | DstNId, | ||
| const bool & | IsDir = true |
||
| ) |
Deletes an edge from node IDs SrcNId to DstNId from the network.
If the edge (SrcNId, DstNId) does not exist in the network function still completes. But the function aborts if SrcNId or DstNId are not nodes in the network.
Deletes node of ID NId from the network.
If the node of ID NId does not exist the function aborts.
Definition at line 297 of file network.h.
{
{ TNode& Node = GetNode(NId);
for (int e = 0; e < Node.GetOutDeg(); e++) {
const int nbr = Node.GetOutNId(e);
if (nbr == NId) { continue; }
TNode& N = GetNode(nbr);
int n = N.InNIdV.SearchBin(NId);
if (n!= -1) { N.InNIdV.Del(n); }
}
for (int e = 0; e < Node.GetInDeg(); e++) {
const int nbr = Node.GetInNId(e);
if (nbr == NId) { continue; }
TNode& N = GetNode(nbr);
int n = N.OutNIdV.SearchBin(NId);
if (n!= -1) { N.OutNIdV.Del(n); }
} }
NodeH.DelKey(NId);
}
Returns the number of edges in the network.
Definition at line 323 of file network.h.
{
int edges=0;
for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N);) {
edges+=NodeH[N].GetOutDeg(); }
return edges;
}
Not supported/implemented!
| bool TNodeNet< TNodeData >::HasFlag | ( | const TGraphFlag & | Flag | ) | const |
Allows for run-time checking the type of the network (see the TGraphFlag for flags).
Definition at line 268 of file network.h.
{
return HasGraphFlag(typename TNet, Flag);
}
| bool TNodeNet< TNodeData >::IsEdge | ( | const int & | SrcNId, |
| const int & | DstNId, | ||
| const bool & | IsDir = true |
||
| ) | const |
Tests whether an edge from node IDs SrcNId to DstNId exists in the network.
| bool TNodeNet< TNodeData >::IsOk | ( | const bool & | ThrowExcept = true | ) | const |
Checks the network data structure for internal consistency.
For each node in the network check that its neighbors are also nodes in the network.
Definition at line 383 of file network.h.
{
bool RetVal = true;
for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
const TNode& Node = NodeH[N];
if (! Node.OutNIdV.IsSorted()) {
const TStr Msg = TStr::Fmt("Out-neighbor list of node %d is not sorted.", Node.GetId());
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
if (! Node.InNIdV.IsSorted()) {
const TStr Msg = TStr::Fmt("In-neighbor list of node %d is not sorted.", Node.GetId());
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
// check out-edges
int prevNId = -1;
for (int e = 0; e < Node.GetOutDeg(); e++) {
if (! IsNode(Node.GetOutNId(e))) {
const TStr Msg = TStr::Fmt("Out-edge %d --> %d: node %d does not exist.",
Node.GetId(), Node.GetOutNId(e), Node.GetOutNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
if (e > 0 && prevNId == Node.GetOutNId(e)) {
const TStr Msg = TStr::Fmt("Node %d has duplidate out-edge %d --> %d.",
Node.GetId(), Node.GetId(), Node.GetOutNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
prevNId = Node.GetOutNId(e);
}
// check in-edges
prevNId = -1;
for (int e = 0; e < Node.GetInDeg(); e++) {
if (! IsNode(Node.GetInNId(e))) {
const TStr Msg = TStr::Fmt("In-edge %d <-- %d: node %d does not exist.",
Node.GetId(), Node.GetInNId(e), Node.GetInNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
if (e > 0 && prevNId == Node.GetInNId(e)) {
const TStr Msg = TStr::Fmt("Node %d has duplidate in-edge %d <-- %d.",
Node.GetId(), Node.GetId(), Node.GetInNId(e));
if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); } RetVal=false;
}
prevNId = Node.GetInNId(e);
}
}
return RetVal;
}
| void TNodeNet< TNodeData >::SortNIdByDat | ( | const bool & | Asc = true | ) | [inline] |
| void TNodeNet< TNodeData >::SortNIdById | ( | const bool & | Asc = true | ) | [inline] |
1.8.0