SNAP Library 6.0, User Reference  2020-12-09 16:24:20
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
TUNGraph Class Reference

Undirected graph. More...

#include <graph.h>

Classes

class  TEdgeI
 Edge iterator. Only forward iteration (operator++) is supported. More...
 
class  TLoadTNodeInitializer
 
class  TNode
 
class  TNodeI
 Node iterator. Only forward iteration (operator++) is supported. More...
 

Public Types

typedef TUNGraph TNet
 
typedef TPt< TUNGraphPNet
 

Public Member Functions

 TUNGraph ()
 
 TUNGraph (const int &Nodes, const int &Edges)
 Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges. More...
 
 TUNGraph (const TUNGraph &Graph)
 
 TUNGraph (TSIn &SIn)
 Constructor that loads the graph from a (binary) stream SIn. More...
 
void Save (TSOut &SOut) const
 Saves the graph to a (binary) stream SOut. More...
 
bool HasFlag (const TGraphFlag &Flag) const
 Allows for run-time checking the type of the graph (see the TGraphFlag for flags). More...
 
TUNGraphoperator= (const TUNGraph &Graph)
 
int GetNodes () const
 Returns the number of nodes in the graph. More...
 
int AddNode (int NId=-1)
 Adds a node of ID NId to the graph. More...
 
int AddNodeUnchecked (int NId=-1)
 Adds a node of ID NId to the network, noop if the node already exists. More...
 
int AddNode (const TNodeI &NodeI)
 Adds a node of ID NodeI.GetId() to the graph. More...
 
int AddNode (const int &NId, const TIntV &NbrNIdV)
 Adds a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV. More...
 
int AddNode (const int &NId, const TVecPool< TInt > &Pool, const int &NIdVId)
 Adds a node of ID NId to the graph and create edges to all nodes in vector NIdVId in the vector pool Pool. More...
 
void DelNode (const int &NId)
 Deletes node of ID NId from the graph. More...
 
void DelNode (const TNode &NodeI)
 Deletes node of ID NodeI.GetId() from the graph. More...
 
bool IsNode (const int &NId) const
 Tests whether ID NId is a node. More...
 
TNodeI BegNI () const
 Returns an iterator referring to the first node in the graph. More...
 
TNodeI EndNI () const
 Returns an iterator referring to the past-the-end node in the graph. More...
 
TNodeI GetNI (const int &NId) const
 Returns an iterator referring to the node of ID NId in the graph. More...
 
int GetMxNId () const
 Returns an ID that is larger than any node ID in the graph. More...
 
int GetEdges () const
 Returns the number of edges in the graph. More...
 
int AddEdge (const int &SrcNId, const int &DstNId)
 Adds an edge between node IDs SrcNId and DstNId to the graph. More...
 
int AddEdge (const int &SrcNId, const int &DstNId, const int &EId)
 Adds an edge between node IDs SrcNId and DstNId to the graph, ignores EId (for compatibility with TNEANet). More...
 
int AddEdgeUnchecked (const int &SrcNId, const int &DstNId)
 Adds an edge between node IDs SrcNId and DstNId to the graph. More...
 
int AddEdge2 (const int &SrcNId, const int &DstNId)
 Adds an edge between node IDs SrcNId and DstNId to the graph. If nodes do not exists, create them. More...
 
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph. More...
 
void DelEdge (const int &SrcNId, const int &DstNId)
 Deletes an edge between node IDs SrcNId and DstNId from the graph. More...
 
bool IsEdge (const int &SrcNId, const int &DstNId) const
 Tests whether an edge between node IDs SrcNId and DstNId exists in the graph. More...
 
bool IsEdge (const int &EId) const
 Tests whether an edge EId exists in the graph (for compatibility with TNEANet), always returns false. More...
 
TEdgeI BegEI () const
 Returns an iterator referring to the first edge in the graph. More...
 
TEdgeI EndEI () const
 Returns an iterator referring to the past-the-end edge in the graph. More...
 
TEdgeI GetEI (const int &EId) const
 Not supported/implemented! More...
 
TEdgeI GetEI (const int &SrcNId, const int &DstNId) const
 Returns an iterator referring to edge (SrcNId, DstNId) in the graph. More...
 
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random node in the graph. More...
 
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random node in the graph. More...
 
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the graph. More...
 
bool Empty () const
 Tests whether the graph is empty (has zero nodes). More...
 
void Clr ()
 Deletes all nodes and edges from the graph. More...
 
void SortNodeAdjV ()
 Sorts the adjacency lists of each node. More...
 
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a graph of Nodes nodes and Edges edges. More...
 
void ReserveNIdDeg (const int &NId, const int &Deg)
 Reserves memory for node ID NId having Deg edges. More...
 
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the graph. More...
 
bool IsOk (const bool &ThrowExcept=true) const
 Checks the graph data structure for internal consistency. More...
 
void Dump (FILE *OutF=stdout) const
 Print the graph in a human readable form to an output stream OutF. More...
 

Static Public Member Functions

static PUNGraph New ()
 Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New(). More...
 
static PUNGraph New (const int &Nodes, const int &Edges)
 Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges. More...
 
static PUNGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it. More...
 
static PUNGraph LoadShM (TShMIn &ShMIn)
 Static constructor that loads the graph from shared memory. More...
 
static PUNGraph GetSmallGraph ()
 Returns a small graph on 5 nodes and 5 edges. More...
 

Private Member Functions

TNodeGetNode (const int &NId)
 
const TNodeGetNode (const int &NId) const
 
void LoadGraphShM (TShMIn &ShMIn)
 

Private Attributes

TCRef CRef
 
TInt MxNId
 
TInt NEdges
 
THash< TInt, TNodeNodeH
 

Friends

class TUNGraphMtx
 
class TPt< TUNGraph >
 

Detailed Description

Undirected graph.

Node IDs can be arbitrary non-negative integers. Nodes and edges have no attributes/data associated with them. There is at most one undirected edge between a pair of nodes. Self loops (one per node) are allowed but multiple (parallel) edges are not. The undirected graph data structure is implemented using sorted adjacency lists. This means adding a node takes constant time, while adding an edge takes linear time (since adjacency list is kept sorted) in the node degree. Accessing arbitrary node takes constant time and accessing any edge takes logarithmic time in the node degree.

Definition at line 32 of file graph.h.

Member Typedef Documentation

Definition at line 35 of file graph.h.

Definition at line 34 of file graph.h.

Constructor & Destructor Documentation

TUNGraph::TUNGraph ( )
inline

Definition at line 162 of file graph.h.

162 : CRef(), MxNId(0), NEdges(0), NodeH() { }
TInt NEdges
Definition: graph.h:144
TCRef CRef
Definition: graph.h:143
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145
TUNGraph::TUNGraph ( const int &  Nodes,
const int &  Edges 
)
inlineexplicit

Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges.

Definition at line 164 of file graph.h.

164 : MxNId(0), NEdges(0) { Reserve(Nodes, Edges); }
TInt NEdges
Definition: graph.h:144
TInt MxNId
Definition: graph.h:144
void Reserve(const int &Nodes, const int &Edges)
Reserves memory for a graph of Nodes nodes and Edges edges.
Definition: graph.h:302
TUNGraph::TUNGraph ( const TUNGraph Graph)
inline

Definition at line 165 of file graph.h.

165 : MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH) { }
TInt NEdges
Definition: graph.h:144
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145
TUNGraph::TUNGraph ( TSIn SIn)
inline

Constructor that loads the graph from a (binary) stream SIn.

Definition at line 167 of file graph.h.

167 : MxNId(SIn), NEdges(SIn), NodeH(SIn) { }
TInt NEdges
Definition: graph.h:144
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145

Member Function Documentation

int TUNGraph::AddEdge ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge between node IDs SrcNId and DstNId to the graph.

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 TUNGraph have no IDs we return -1. The function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 92 of file graph.cpp.

92  {
93  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
94  if (IsEdge(SrcNId, DstNId)) { return -2; } // edge already exists
95  GetNode(SrcNId).NIdV.AddSorted(DstNId);
96  if (SrcNId!=DstNId) { // not a self edge
97  GetNode(DstNId).NIdV.AddSorted(SrcNId); }
98  NEdges++;
99  return -1; // no edge id
100 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNode & GetNode(const int &NId)
Definition: graph.h:153
TInt NEdges
Definition: graph.h:144
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
TIntV NIdV
Definition: graph.h:40
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
bool IsEdge(const int &SrcNId, const int &DstNId) const
Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
Definition: graph.cpp:137
int TUNGraph::AddEdge ( const int &  SrcNId,
const int &  DstNId,
const int &  EId 
)
inline

Adds an edge between node IDs SrcNId and DstNId to the graph, ignores EId (for compatibility with TNEANet).

Definition at line 254 of file graph.h.

254 { return AddEdge(SrcNId, DstNId); }
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
int TUNGraph::AddEdge ( const TEdgeI EdgeI)
inline

Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.

Definition at line 267 of file graph.h.

267 { return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
int AddEdge(const int &SrcNId, const int &DstNId)
Adds an edge between node IDs SrcNId and DstNId to the graph.
Definition: graph.cpp:92
int TUNGraph::AddEdge2 ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge between node IDs SrcNId and DstNId to the graph. If nodes do not exists, create them.

Definition at line 112 of file graph.cpp.

112  {
113  if (! IsNode(SrcNId)) { AddNode(SrcNId); }
114  if (! IsNode(DstNId)) { AddNode(DstNId); }
115  if (GetNode(SrcNId).IsNbrNId(DstNId)) { return -2; } // edge already exists
116  GetNode(SrcNId).NIdV.AddSorted(DstNId);
117  if (SrcNId!=DstNId) { // not a self edge
118  GetNode(DstNId).NIdV.AddSorted(SrcNId); }
119  NEdges++;
120  return -1; // no edge id
121 }
TNode & GetNode(const int &NId)
Definition: graph.h:153
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
TInt NEdges
Definition: graph.h:144
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
TIntV NIdV
Definition: graph.h:40
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
int TUNGraph::AddEdgeUnchecked ( const int &  SrcNId,
const int &  DstNId 
)

Adds an edge between node IDs SrcNId and DstNId to the graph.

Returns -1. The method assumes that SrcNId and DstNId are existing nodes in the graph and adds new neighbor values at the end of their adjacency vectors. No checks are performed to verify these assumptions. Adjacency vectors must be sorted and have duplicates removed after a sequence of these operations to assure consistency of data structures.

Definition at line 103 of file graph.cpp.

103  {
104  GetNode(SrcNId).NIdV.Add(DstNId);
105  if (SrcNId!=DstNId) { // not a self edge
106  GetNode(DstNId).NIdV.Add(SrcNId); }
107  NEdges++;
108  return -1; // no edge id
109 }
TNode & GetNode(const int &NId)
Definition: graph.h:153
TInt NEdges
Definition: graph.h:144
TIntV NIdV
Definition: graph.h:40
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
int TUNGraph::AddNode ( int  NId = -1)

Adds a node of ID NId to the graph.

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.

Definition at line 8 of file graph.cpp.

8  {
9  if (NId == -1) {
10  NId = MxNId; MxNId++;
11  } else {
12  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
13  MxNId = TMath::Mx(NId+1, MxNId());
14  }
15  NodeH.AddDat(NId, TNode(NId));
16  return NId;
17 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
int TUNGraph::AddNode ( const TNodeI NodeI)
inline

Adds a node of ID NodeI.GetId() to the graph.

Definition at line 206 of file graph.h.

206 { return AddNode(NodeI.GetId()); }
int AddNode(int NId=-1)
Adds a node of ID NId to the graph.
Definition: graph.cpp:8
int TUNGraph::AddNode ( const int &  NId,
const TIntV NbrNIdV 
)

Adds a node of ID NId to the graph and create edges to all nodes in vector NbrNIdV.

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.

The operation can create inconsistent graphs when the neighboring nodes in NbrNIdV vector do not exist. Use TUNGraph::IsOk to check that the resulting graph is consistent after the operation.

Definition at line 28 of file graph.cpp.

28  {
29  int NewNId;
30  if (NId == -1) {
31  NewNId = MxNId; MxNId++;
32  } else {
33  IAssertR(! IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
34  NewNId = NId;
35  MxNId = TMath::Mx(NewNId+1, MxNId());
36  }
37  TNode& Node = NodeH.AddDat(NewNId);
38  Node.Id = NewNId;
39  Node.NIdV = NbrNIdV;
40  Node.NIdV.Sort();
41  NEdges += Node.GetDeg();
42  for (int i = 0; i < NbrNIdV.Len(); i++) {
43  GetNode(NbrNIdV[i]).NIdV.AddSorted(NewNId);
44  }
45  return NewNId;
46 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNode & GetNode(const int &NId)
Definition: graph.h:153
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TSizeTy Len() const
Returns the number of elements in the vector.
Definition: ds.h:575
TInt NEdges
Definition: graph.h:144
TSizeTy AddSorted(const TVal &Val, const bool &Asc=true, const TSizeTy &_MxVals=-1)
Adds element Val to a sorted vector.
Definition: ds.h:1117
void Sort(const bool &Asc=true)
Sorts the elements of the vector.
Definition: ds.h:1318
TInt MxNId
Definition: graph.h:144
TIntV NIdV
Definition: graph.h:40
THash< TInt, TNode > NodeH
Definition: graph.h:145
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
int TUNGraph::AddNode ( const int &  NId,
const TVecPool< TInt > &  Pool,
const int &  NIdVId 
)

Adds a node of ID NId to the graph and create edges to all nodes in vector NIdVId in the vector pool Pool.

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.

The operation can create inconsistent graphs when the neighboring nodes stored in the Pool vector are not explicitly added to the graph. Use TUNGraph::IsOk to check that the resulting graph is consistent.

Definition at line 49 of file graph.cpp.

49  {
50  int NewNId;
51  if (NId == -1) {
52  NewNId = MxNId; MxNId++;
53  } else {
54  IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
55  NewNId = NId;
56  MxNId = TMath::Mx(NewNId+1, MxNId());
57  }
58  TNode& Node = NodeH.AddDat(NewNId);
59  Node.Id = NewNId;
60  Node.NIdV.GenExt(Pool.GetValVPt(NIdVId), Pool.GetVLen(NIdVId));
61  Node.NIdV.Sort();
62  NEdges += Node.GetDeg();
63  return NewNId;
64 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt NEdges
Definition: graph.h:144
TVal * GetValVPt(const int &VId) const
Returns pointer to the first element of the vector with id VId.
Definition: ds.h:1731
TInt MxNId
Definition: graph.h:144
int GetVLen(const int &VId) const
Returns the number of elements in the vector with id VId.
Definition: ds.h:1729
THash< TInt, TNode > NodeH
Definition: graph.h:145
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
int TUNGraph::AddNodeUnchecked ( int  NId = -1)

Adds a node of ID NId to the network, noop if the node already exists.

Returns -1, if the node NId already exists. Otherwise, it returns the ID of the node being added. If NId is -1, node ID is automatically assigned.

Definition at line 20 of file graph.cpp.

20  {
21  if (IsNode(NId)) { return -1;}
22  MxNId = TMath::Mx(NId+1, MxNId());
23  NodeH.AddDat(NId, TNode(NId));
24  return NId;
25 }
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
TDat & AddDat(const TKey &Key)
Definition: hash.h:238
TEdgeI TUNGraph::BegEI ( ) const
inline

Returns an iterator referring to the first edge in the graph.

Definition at line 278 of file graph.h.

278 { TNodeI NI = BegNI(); TEdgeI EI(NI, EndNI(), 0); if (GetNodes() != 0 && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { EI++; } return EI; }
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237
TNodeI TUNGraph::BegNI ( ) const
inline

Returns an iterator referring to the first node in the graph.

Definition at line 237 of file graph.h.

237 { return TNodeI(NodeH.BegI()); }
TIter BegI() const
Definition: hash.h:213
THash< TInt, TNode > NodeH
Definition: graph.h:145
void TUNGraph::Clr ( )
inline

Deletes all nodes and edges from the graph.

Definition at line 298 of file graph.h.

298 { MxNId=0; NEdges=0; NodeH.Clr(); }
TInt NEdges
Definition: graph.h:144
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145
void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)
Definition: hash.h:361
void TUNGraph::Defrag ( const bool &  OnlyNodeLinks = false)

Defragments the graph.

After performing many node and edge insertions and deletions to a graph, the graph data structure will be fragmented in memory. This function compacts down the graph data structure and frees unneeded memory.

Definition at line 160 of file graph.cpp.

160  {
161  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
162  NodeH[n].NIdV.Pack();
163  }
164  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
165  NodeH.Defrag();
166  }
167 }
bool IsKeyIdEqKeyN() const
Definition: hash.h:233
void Defrag()
Definition: hash.h:555
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > NodeH
Definition: graph.h:145
void Pack()
Definition: hash.h:289
void TUNGraph::DelEdge ( const int &  SrcNId,
const int &  DstNId 
)

Deletes an edge between node IDs SrcNId and DstNId from the graph.

If the edge (SrcNId, DstNId) does not exist in the graph function still completes. But the function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 124 of file graph.cpp.

124  {
125  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
126  { TNode& N = GetNode(SrcNId);
127  const int n = N.NIdV.SearchBin(DstNId);
128  if (n!= -1) { N.NIdV.Del(n); NEdges--; } }
129  if (SrcNId != DstNId) { // not a self edge
130  TNode& N = GetNode(DstNId);
131  const int n = N.NIdV.SearchBin(SrcNId);
132  if (n!= -1) { N.NIdV.Del(n); }
133  }
134 }
#define IAssertR(Cond, Reason)
Definition: bd.h:265
TNode & GetNode(const int &NId)
Definition: graph.h:153
TInt NEdges
Definition: graph.h:144
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
void TUNGraph::DelNode ( const int &  NId)

Deletes node of ID NId from the graph.

If the node of ID NId does not exist the function aborts.

Definition at line 67 of file graph.cpp.

67  {
68  { AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
69  TNode& Node = GetNode(NId);
70  NEdges -= Node.GetDeg();
71  for (int e = 0; e < Node.GetDeg(); e++) {
72  const int nbr = Node.GetNbrNId(e);
73  if (nbr == NId) { continue; }
74  TNode& N = GetNode(nbr);
75  const int n = N.NIdV.SearchBin(NId);
76  IAssert(n != -1); // if NId points to N, then N also should point back
77  if (n!= -1) { N.NIdV.Del(n); }
78  } }
79  NodeH.DelKey(NId);
80 }
#define IAssert(Cond)
Definition: bd.h:262
TNode & GetNode(const int &NId)
Definition: graph.h:153
TInt NEdges
Definition: graph.h:144
void DelKey(const TKey &Key)
Definition: hash.h:404
THash< TInt, TNode > NodeH
Definition: graph.h:145
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
#define AssertR(Cond, Reason)
Definition: bd.h:258
void TUNGraph::DelNode ( const TNode NodeI)
inline

Deletes node of ID NodeI.GetId() from the graph.

Definition at line 233 of file graph.h.

233 { DelNode(NodeI.GetId()); }
void DelNode(const int &NId)
Deletes node of ID NId from the graph.
Definition: graph.cpp:67
void TUNGraph::Dump ( FILE *  OutF = stdout) const

Print the graph in a human readable form to an output stream OutF.

Definition at line 207 of file graph.cpp.

207  {
208  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
209  fprintf(OutF, "-------------------------------------------------\nUndirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
210  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
211  const TNode& Node = NodeH[N];
212  fprintf(OutF, " %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
213  for (int edge = 0; edge < Node.GetDeg(); edge++) {
214  fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
215  fprintf(OutF, "\n");
216  }
217  fprintf(OutF, "\n");
218 }
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > NodeH
Definition: graph.h:145
bool TUNGraph::Empty ( ) const
inline

Tests whether the graph is empty (has zero nodes).

Definition at line 296 of file graph.h.

296 { return GetNodes()==0; }
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
TEdgeI TUNGraph::EndEI ( ) const
inline

Returns an iterator referring to the past-the-end edge in the graph.

Definition at line 280 of file graph.h.

280 { return TEdgeI(EndNI(), EndNI()); }
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TNodeI TUNGraph::EndNI ( ) const
inline

Returns an iterator referring to the past-the-end node in the graph.

Definition at line 239 of file graph.h.

239 { return TNodeI(NodeH.EndI()); }
TIter EndI() const
Definition: hash.h:218
THash< TInt, TNode > NodeH
Definition: graph.h:145
int TUNGraph::GetEdges ( ) const

Returns the number of edges in the graph.

Definition at line 82 of file graph.cpp.

82  {
83  //int Edges = 0;
84  //for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
85  // Edges += NodeH[N].GetDeg();
86  //}
87  //return Edges/2;
88  return NEdges;
89 }
TInt NEdges
Definition: graph.h:144
TEdgeI TUNGraph::GetEI ( const int &  EId) const

Not supported/implemented!

TUNGraph::TEdgeI TUNGraph::GetEI ( const int &  SrcNId,
const int &  DstNId 
) const

Returns an iterator referring to edge (SrcNId, DstNId) in the graph.

Note that since this is an undirected graph GetEI(SrcNId, DstNId) has the same effect as GetEI(DstNId, SrcNId).

Definition at line 143 of file graph.cpp.

143  {
144  const int MnNId = TMath::Mn(SrcNId, DstNId);
145  const int MxNId = TMath::Mx(SrcNId, DstNId);
146  const TNodeI SrcNI = GetNI(MnNId);
147  const int NodeN = SrcNI.NodeHI.GetDat().NIdV.SearchBin(MxNId);
148  IAssert(NodeN != -1);
149  return TEdgeI(SrcNI, EndNI(), NodeN);
150 }
#define IAssert(Cond)
Definition: bd.h:262
static const T & Mn(const T &LVal, const T &RVal)
Definition: xmath.h:36
static const T & Mx(const T &LVal, const T &RVal)
Definition: xmath.h:32
TInt MxNId
Definition: graph.h:144
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
int TUNGraph::GetMxNId ( ) const
inline

Returns an ID that is larger than any node ID in the graph.

Definition at line 243 of file graph.h.

243 { return MxNId; }
TInt MxNId
Definition: graph.h:144
TNodeI TUNGraph::GetNI ( const int &  NId) const
inline

Returns an iterator referring to the node of ID NId in the graph.

Definition at line 241 of file graph.h.

241 { return TNodeI(NodeH.GetI(NId)); }
THash< TInt, TNode > NodeH
Definition: graph.h:145
TIter GetI(const TKey &Key) const
Definition: hash.h:220
void TUNGraph::GetNIdV ( TIntV NIdV) const

Gets a vector IDs of all nodes in the graph.

Definition at line 153 of file graph.cpp.

153  {
154  NIdV.Gen(GetNodes(), 0);
155  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
156  NIdV.Add(NodeH.GetKey(N)); }
157 }
int GetNodes() const
Returns the number of nodes in the graph.
Definition: graph.h:192
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
int FFirstKeyId() const
Definition: hash.h:278
THash< TInt, TNode > NodeH
Definition: graph.h:145
void Gen(const TSizeTy &_Vals)
Constructs a vector (an array) of _Vals elements.
Definition: ds.h:523
TSizeTy Add()
Adds a new element at the end of the vector, after its current last element.
Definition: ds.h:602
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
TNode& TUNGraph::GetNode ( const int &  NId)
inlineprivate

Definition at line 153 of file graph.h.

153 { return NodeH.GetDat(NId); }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
THash< TInt, TNode > NodeH
Definition: graph.h:145
const TNode& TUNGraph::GetNode ( const int &  NId) const
inlineprivate

Definition at line 154 of file graph.h.

154 { return NodeH.GetDat(NId); }
const TDat & GetDat(const TKey &Key) const
Definition: hash.h:262
THash< TInt, TNode > NodeH
Definition: graph.h:145
int TUNGraph::GetNodes ( ) const
inline

Returns the number of nodes in the graph.

Definition at line 192 of file graph.h.

192 { return NodeH.Len(); }
THash< TInt, TNode > NodeH
Definition: graph.h:145
int Len() const
Definition: hash.h:228
TNodeI TUNGraph::GetRndNI ( TRnd Rnd = TInt::Rnd)
inline

Returns an interator referring to a random node in the graph.

Definition at line 291 of file graph.h.

291 { return GetNI(GetRndNId(Rnd)); }
int GetRndNId(TRnd &Rnd=TInt::Rnd)
Returns an ID of a random node in the graph.
Definition: graph.h:289
TNodeI GetNI(const int &NId) const
Returns an iterator referring to the node of ID NId in the graph.
Definition: graph.h:241
int TUNGraph::GetRndNId ( TRnd Rnd = TInt::Rnd)
inline

Returns an ID of a random node in the graph.

Definition at line 289 of file graph.h.

289 { return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }
THash< TInt, TNode > NodeH
Definition: graph.h:145
int GetRndKeyId(TRnd &Rnd) const
Get an index of a random element. If the hash table has many deleted keys, this may take a long time...
Definition: hash.h:444
const TKey & GetKey(const int &KeyId) const
Definition: hash.h:252
PUNGraph TUNGraph::GetSmallGraph ( )
static

Returns a small graph on 5 nodes and 5 edges.

/// Graph:   3--0--4
///            /|
///           1-2
/// 

Definition at line 221 of file graph.cpp.

221  {
222  PUNGraph Graph = TUNGraph::New();
223  for (int i = 0; i < 5; i++) { Graph->AddNode(i); }
224  Graph->AddEdge(0,1); Graph->AddEdge(0,2);
225  Graph->AddEdge(0,3); Graph->AddEdge(0,4);
226  Graph->AddEdge(1,2);
227  return Graph;
228 }
static PUNGraph New()
Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
Definition: graph.h:172
Definition: bd.h:196
bool TUNGraph::HasFlag ( const TGraphFlag Flag) const

Allows for run-time checking the type of the graph (see the TGraphFlag for flags).

Definition at line 3 of file graph.cpp.

3  {
4  return HasGraphFlag(TUNGraph::TNet, Flag);
5 }
Undirected graph.
Definition: graph.h:32
#define HasGraphFlag(TGraph, Flag)
For quick testing of the properties of the graph/network object (see TGraphFlag). ...
Definition: gbase.h:41
bool TUNGraph::IsEdge ( const int &  SrcNId,
const int &  DstNId 
) const

Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.

Definition at line 137 of file graph.cpp.

137  {
138  if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
139  return GetNode(SrcNId).IsNbrNId(DstNId);
140 }
TNode & GetNode(const int &NId)
Definition: graph.h:153
bool IsNbrNId(const int &NId) const
Definition: graph.h:58
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
bool TUNGraph::IsEdge ( const int &  EId) const
inline

Tests whether an edge EId exists in the graph (for compatibility with TNEANet), always returns false.

Definition at line 276 of file graph.h.

276 { return false; }
bool TUNGraph::IsNode ( const int &  NId) const
inline

Tests whether ID NId is a node.

Definition at line 235 of file graph.h.

235 { return NodeH.IsKey(NId); }
THash< TInt, TNode > NodeH
Definition: graph.h:145
bool IsKey(const TKey &Key) const
Definition: hash.h:258
bool TUNGraph::IsOk ( const bool &  ThrowExcept = true) const

Checks the graph data structure for internal consistency.

For each node in the graph check that its neighbors are also nodes in the graph.

Definition at line 170 of file graph.cpp.

170  {
171  bool RetVal = true;
172  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
173  const TNode& Node = NodeH[N];
174  if (! Node.NIdV.IsSorted()) {
175  const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", Node.GetId());
176  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
177  RetVal=false;
178  }
179  int prevNId = -1;
180  for (int e = 0; e < Node.GetDeg(); e++) {
181  if (! IsNode(Node.GetNbrNId(e))) {
182  const TStr Msg = TStr::Fmt("Edge %d --> %d: node %d does not exist.",
183  Node.GetId(), Node.GetNbrNId(e), Node.GetNbrNId(e));
184  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
185  RetVal=false;
186  }
187  if (e > 0 && prevNId == Node.GetNbrNId(e)) {
188  const TStr Msg = TStr::Fmt("Node %d has duplicate edge %d --> %d.",
189  Node.GetId(), Node.GetId(), Node.GetNbrNId(e));
190  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
191  RetVal=false;
192  }
193  prevNId = Node.GetNbrNId(e);
194  }
195  }
196  int EdgeCnt = 0;
197  for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { EdgeCnt++; }
198  if (EdgeCnt != GetEdges()) {
199  const TStr Msg = TStr::Fmt("Number of edges counter is corrupted: GetEdges():%d, EdgeCount:%d.", GetEdges(), EdgeCnt);
200  if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
201  RetVal=false;
202  }
203  return RetVal;
204 }
TEdgeI EndEI() const
Returns an iterator referring to the past-the-end edge in the graph.
Definition: graph.h:280
int GetEdges() const
Returns the number of edges in the graph.
Definition: graph.cpp:82
void ErrNotify(const char *NotifyCStr)
Definition: bd.h:74
bool FNextKeyId(int &KeyId) const
Definition: hash.h:478
TEdgeI BegEI() const
Returns an iterator referring to the first edge in the graph.
Definition: graph.h:278
int FFirstKeyId() const
Definition: hash.h:278
Definition: dt.h:412
THash< TInt, TNode > NodeH
Definition: graph.h:145
static TStr Fmt(const char *FmtStr,...)
Definition: dt.cpp:1599
#define EAssertR(Cond, MsgStr)
Definition: bd.h:283
bool IsNode(const int &NId) const
Tests whether ID NId is a node.
Definition: graph.h:235
char * CStr()
Definition: dt.h:479
static PUNGraph TUNGraph::Load ( TSIn SIn)
inlinestatic

Static constructor that loads the graph from a stream SIn and returns a pointer to it.

Definition at line 178 of file graph.h.

178 { return PUNGraph(new TUNGraph(SIn)); }
TUNGraph()
Definition: graph.h:162
TPt< TUNGraph > PUNGraph
Pointer to an undirected graph (TUNGraph)
Definition: graph.h:5
void TUNGraph::LoadGraphShM ( TShMIn ShMIn)
inlineprivate

Definition at line 155 of file graph.h.

155  {
156  MxNId = TInt(ShMIn);
157  NEdges = TInt(ShMIn);
158  TLoadTNodeInitializer Fn;
159  NodeH.LoadShM(ShMIn, Fn);
160  }
TInt NEdges
Definition: graph.h:144
void LoadShM(TShMIn &ShMIn)
Load THash from shared memory file. Copying/Deleting Keys is illegal.
Definition: hash.h:157
TInt MxNId
Definition: graph.h:144
Definition: dt.h:1137
THash< TInt, TNode > NodeH
Definition: graph.h:145
static PUNGraph TUNGraph::LoadShM ( TShMIn ShMIn)
inlinestatic

Static constructor that loads the graph from shared memory.

Cannot perform operations that edit the edge vectors of nodes or perform illegal operations on the NodeH (deletion or swapping keys)

Definition at line 182 of file graph.h.

182  {
183  TUNGraph* Graph = new TUNGraph();
184  Graph->LoadGraphShM(ShMIn);
185  return PUNGraph(Graph);
186  }
void LoadGraphShM(TShMIn &ShMIn)
Definition: graph.h:155
Undirected graph.
Definition: graph.h:32
TUNGraph()
Definition: graph.h:162
TPt< TUNGraph > PUNGraph
Pointer to an undirected graph (TUNGraph)
Definition: graph.h:5
static PUNGraph TUNGraph::New ( )
inlinestatic

Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().

Definition at line 172 of file graph.h.

172 { return new TUNGraph(); }
TUNGraph()
Definition: graph.h:162
static PUNGraph TUNGraph::New ( const int &  Nodes,
const int &  Edges 
)
inlinestatic

Static constructor that returns a pointer to the graph and reserves enough memory for Nodes nodes and Edges edges.

Call: PUNGraph Graph = TUNGraph::New(Nodes, Edges).

Definition at line 176 of file graph.h.

176 { return new TUNGraph(Nodes, Edges); }
TUNGraph()
Definition: graph.h:162
TUNGraph& TUNGraph::operator= ( const TUNGraph Graph)
inline

Definition at line 188 of file graph.h.

188  {
189  if (this!=&Graph) { MxNId=Graph.MxNId; NEdges=Graph.NEdges; NodeH=Graph.NodeH; } return *this; }
TInt NEdges
Definition: graph.h:144
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145
void TUNGraph::Reserve ( const int &  Nodes,
const int &  Edges 
)
inline

Reserves memory for a graph of Nodes nodes and Edges edges.

Definition at line 302 of file graph.h.

302 { if (Nodes>0) NodeH.Gen(Nodes/2); }
void Gen(const int &ExpectVals)
Definition: hash.h:222
THash< TInt, TNode > NodeH
Definition: graph.h:145
void TUNGraph::ReserveNIdDeg ( const int &  NId,
const int &  Deg 
)
inline

Reserves memory for node ID NId having Deg edges.

Definition at line 304 of file graph.h.

304 { GetNode(NId).NIdV.Reserve(Deg); }
TNode & GetNode(const int &NId)
Definition: graph.h:153
TIntV NIdV
Definition: graph.h:40
void Reserve(const TSizeTy &_MxVals)
Reserves enough memory for the vector to store _MxVals elements.
Definition: ds.h:543
void TUNGraph::Save ( TSOut SOut) const
inline

Saves the graph to a (binary) stream SOut.

Definition at line 170 of file graph.h.

170 { MxNId.Save(SOut); NEdges.Save(SOut); NodeH.Save(SOut); }
void Save(TSOut &SOut) const
Definition: dt.h:1153
void Save(TSOut &SOut) const
Definition: hash.h:183
TInt NEdges
Definition: graph.h:144
TInt MxNId
Definition: graph.h:144
THash< TInt, TNode > NodeH
Definition: graph.h:145
void TUNGraph::SortNodeAdjV ( )
inline

Sorts the adjacency lists of each node.

Definition at line 300 of file graph.h.

300 { for (TNodeI NI = BegNI(); NI < EndNI(); NI++) { NI.SortNIdV();} }
TNodeI EndNI() const
Returns an iterator referring to the past-the-end node in the graph.
Definition: graph.h:239
TNodeI BegNI() const
Returns an iterator referring to the first node in the graph.
Definition: graph.h:237

Friends And Related Function Documentation

friend class TPt< TUNGraph >
friend

Definition at line 327 of file graph.h.

friend class TUNGraphMtx
friend

Definition at line 326 of file graph.h.

Member Data Documentation

TCRef TUNGraph::CRef
private

Definition at line 143 of file graph.h.

TInt TUNGraph::MxNId
private

Definition at line 144 of file graph.h.

TInt TUNGraph::NEdges
private

Definition at line 144 of file graph.h.

THash<TInt, TNode> TUNGraph::NodeH
private

Definition at line 145 of file graph.h.


The documentation for this class was generated from the following files: