SNAP Library 2.0, User Reference  2013-05-13 16:33:57
SNAP, a general purpose, high performance system for analysis and manipulation of large networks
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
TUNGraph Class Reference

Undirected graph. More...

#include <graph.h>

List of all members.

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 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.
 TUNGraph (const TUNGraph &Graph)
 TUNGraph (TSIn &SIn)
 Constructor that loads the graph from a (binary) stream SIn.
void Save (TSOut &SOut) const
 Saves the graph to a (binary) stream SOut.
bool HasFlag (const TGraphFlag &Flag) const
 Allows for run-time checking the type of the graph (see the TGraphFlag for flags).
TUNGraphoperator= (const TUNGraph &Graph)
int GetNodes () const
 Returns the number of nodes in the graph.
int AddNode (int NId=-1)
 Adds a node of ID NId to the graph.
int AddNode (const TNodeI &NodeI)
 Adds a node of ID NodeI.GetId() to the graph.
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.
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.
void DelNode (const int &NId)
 Deletes node of ID NId from the graph.
void DelNode (const TNode &NodeI)
 Deletes node of ID NodeI.GetId() from the graph.
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 graph.
TNodeI EndNI () const
 Returns an iterator referring to the past-the-end node in the graph.
TNodeI GetNI (const int &NId) const
 Returns an iterator referring to the node of ID NId in the graph.
int GetMxNId () const
 Returns the maximum id of a any node in the graph.
int GetEdges () const
 Returns the number of edges in the graph.
int AddEdge (const int &SrcNId, const int &DstNId)
 Adds an edge between node IDs SrcNId and DstNId to the graph.
int AddEdge (const TEdgeI &EdgeI)
 Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the graph.
void DelEdge (const int &SrcNId, const int &DstNId)
 Deletes an edge between node IDs SrcNId and DstNId from the graph.
bool IsEdge (const int &SrcNId, const int &DstNId) const
 Tests whether an edge between node IDs SrcNId and DstNId exists in the graph.
TEdgeI BegEI () const
 Returns an iterator referring to the first edge in the graph.
TEdgeI EndEI () const
 Returns an iterator referring to the past-the-end edge in the graph.
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 graph.
int GetRndNId (TRnd &Rnd=TInt::Rnd)
 Returns an ID of a random node in the graph.
TNodeI GetRndNI (TRnd &Rnd=TInt::Rnd)
 Returns an interator referring to a random node in the graph.
void GetNIdV (TIntV &NIdV) const
 Gets a vector IDs of all nodes in the graph.
bool Empty () const
 Tests whether the graph is empty (has zero nodes).
void Clr ()
 Deletes all nodes and edges from the graph.
void Reserve (const int &Nodes, const int &Edges)
 Reserves memory for a graph of Nodes nodes and Edges edges.
void ReserveNIdDeg (const int &NId, const int &Deg)
 Reserves memory for node ID NId having Deg edges.
void Defrag (const bool &OnlyNodeLinks=false)
 Defragments the graph.
bool IsOk (const bool &ThrowExcept=true) const
 Checks the graph data structure for internal consistency.
void Dump (FILE *OutF=stdout) const
 Print the graph in a human readable form to an output stream OutF.

Static Public Member Functions

static PUNGraph New ()
 Static constructor that returns a pointer to the graph. Call: PUNGraph Graph = TUNGraph::New().
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.
static PUNGraph Load (TSIn &SIn)
 Static constructor that loads the graph from a stream SIn and returns a pointer to it.
static PUNGraph GetSmallGraph ()
 Returns a small graph on 5 nodes and 5 edges.

Private Member Functions

TNodeGetNode (const int &NId)
const TNodeGetNode (const int &NId) const

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 140 of file graph.h.

: CRef(), MxNId(0), NEdges(0), NodeH() { }
TUNGraph::TUNGraph ( const int &  Nodes,
const int &  Edges 
) [inline, explicit]

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

Definition at line 142 of file graph.h.

: MxNId(0), NEdges(0) { Reserve(Nodes, Edges); }
TUNGraph::TUNGraph ( const TUNGraph Graph) [inline]

Definition at line 143 of file graph.h.

: MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH) { }
TUNGraph::TUNGraph ( TSIn SIn) [inline]

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

Definition at line 145 of file graph.h.

: MxNId(SIn), NEdges(SIn), NodeH(SIn) { }

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 81 of file graph.cpp.

                                                          {
  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
  if (IsEdge(SrcNId, DstNId)) { return -2; } // edge already exists
  GetNode(SrcNId).NIdV.AddSorted(DstNId);
  if (SrcNId!=DstNId) { // not a self edge
    GetNode(DstNId).NIdV.AddSorted(SrcNId); }
  NEdges++;
  return -1; // edge id
}
int TUNGraph::AddEdge ( const TEdgeI EdgeI) [inline]

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

Definition at line 218 of file graph.h.

{ return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }
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.

                             {
  if (NId == -1) {
    NId = MxNId;  MxNId++;
  } else {
    IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
    MxNId = TMath::Mx(NId+1, MxNId());
  }
  NodeH.AddDat(NId, TNode(NId));
  return NId;
}
int TUNGraph::AddNode ( const TNodeI NodeI) [inline]

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

Definition at line 170 of file graph.h.

{ return AddNode(NodeI.GetId()); }
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 20 of file graph.cpp.

                                                          {
  int NewNId;
  if (NId == -1) {
    NewNId = MxNId;  MxNId++;
  } else {
    IAssertR(! IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
    NewNId = NId;
    MxNId = TMath::Mx(NewNId+1, MxNId());
  }
  TNode& Node = NodeH.AddDat(NewNId);
  Node.Id = NewNId;
  Node.NIdV = NbrNIdV;
  Node.NIdV.Sort();
  NEdges += Node.GetDeg();
  return NewNId;
}
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 38 of file graph.cpp.

                                                                                   {
  int NewNId;
  if (NId == -1) {
    NewNId = MxNId;  MxNId++;
  } else {
    IAssertR(!IsNode(NId), TStr::Fmt("NodeId %d already exists", NId));
    NewNId = NId;
    MxNId = TMath::Mx(NewNId+1, MxNId());
  }
  TNode& Node = NodeH.AddDat(NewNId);
  Node.Id = NewNId;
  Node.NIdV.GenExt(Pool.GetValVPt(NIdVId), Pool.GetVLen(NIdVId));
  Node.NIdV.Sort();
  NEdges += Node.GetDeg();
  return NewNId;
}
TEdgeI TUNGraph::BegEI ( ) const [inline]

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

Definition at line 227 of file graph.h.

{ TNodeI NI = BegNI(); TEdgeI EI(NI, EndNI(), 0); if (GetNodes() != 0 && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { EI++; } return EI; }
TNodeI TUNGraph::BegNI ( ) const [inline]

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

Definition at line 201 of file graph.h.

{ return TNodeI(NodeH.BegI()); }
void TUNGraph::Clr ( ) [inline]

Deletes all nodes and edges from the graph.

Definition at line 247 of file graph.h.

{ MxNId=0; NEdges=0; NodeH.Clr(); }
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 129 of file graph.cpp.

                                               {
  for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
    NodeH[n].NIdV.Pack();
  }
  if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
    NodeH.Defrag();
  }
}
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 92 of file graph.cpp.

                                                           {
  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
  { TNode& N = GetNode(SrcNId);
  const int n = N.NIdV.SearchBin(DstNId);
  if (n!= -1) { N.NIdV.Del(n);  NEdges--; } }
  if (SrcNId != DstNId) { // not a self edge
    TNode& N = GetNode(DstNId);
    const int n = N.NIdV.SearchBin(SrcNId);
    if (n!= -1) { N.NIdV.Del(n); }
  }
}
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 56 of file graph.cpp.

                                     {
  { AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
  TNode& Node = GetNode(NId);
  NEdges -= Node.GetDeg();
  for (int e = 0; e < Node.GetDeg(); e++) {
    const int nbr = Node.GetNbrNId(e);
    if (nbr == NId) { continue; }
    TNode& N = GetNode(nbr);
    const int n = N.NIdV.SearchBin(NId);
    IAssert(n != -1); // if NId points to N, then N also should point back
    if (n!= -1) { N.NIdV.Del(n); }
  } }
  NodeH.DelKey(NId);
}
void TUNGraph::DelNode ( const TNode NodeI) [inline]

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

Definition at line 197 of file graph.h.

{ DelNode(NodeI.GetId()); }
void TUNGraph::Dump ( FILE *  OutF = stdout) const

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

Definition at line 176 of file graph.cpp.

                                    {
  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
  fprintf(OutF, "-------------------------------------------------\nUndirected Node Graph: nodes: %d, edges: %d\n", GetNodes(), GetEdges());
  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    const TNode& Node = NodeH[N];
    fprintf(OutF, "  %*d [%d] ", NodePlaces, Node.GetId(), Node.GetDeg());
    for (int edge = 0; edge < Node.GetDeg(); edge++) {
      fprintf(OutF, " %*d", NodePlaces, Node.GetNbrNId(edge)); }
    fprintf(OutF, "\n");
  }
  fprintf(OutF, "\n");
}
bool TUNGraph::Empty ( ) const [inline]

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

Definition at line 245 of file graph.h.

{ return GetNodes()==0; }
TEdgeI TUNGraph::EndEI ( ) const [inline]

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

Definition at line 229 of file graph.h.

{ return TEdgeI(EndNI(), EndNI()); }
TNodeI TUNGraph::EndNI ( ) const [inline]

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

Definition at line 203 of file graph.h.

{ return TNodeI(NodeH.EndI()); }
int TUNGraph::GetEdges ( ) const

Returns the number of edges in the graph.

Definition at line 71 of file graph.cpp.

                             {
  //int Edges = 0;
  //for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
  //  Edges += NodeH[N].GetDeg();
  //}
  //return Edges/2;
  return NEdges;
}
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 111 of file graph.cpp.

                                                                         {
  const int MnNId = TMath::Mn(SrcNId, DstNId);
  const int MxNId = TMath::Mx(SrcNId, DstNId);
  const TNodeI SrcNI = GetNI(MnNId);
  const int NodeN = SrcNI.NodeHI.GetDat().NIdV.SearchBin(MxNId);
  IAssert(NodeN != -1);
  return TEdgeI(SrcNI, EndNI(), NodeN);
}
int TUNGraph::GetMxNId ( ) const [inline]

Returns the maximum id of a any node in the graph.

Definition at line 207 of file graph.h.

{ return MxNId; }
TNodeI TUNGraph::GetNI ( const int &  NId) const [inline]

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

Definition at line 205 of file graph.h.

{ return TNodeI(NodeH.GetI(NId)); }
void TUNGraph::GetNIdV ( TIntV NIdV) const

Gets a vector IDs of all nodes in the graph.

Definition at line 122 of file graph.cpp.

                                        {
  NIdV.Gen(GetNodes(), 0);
  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    NIdV.Add(NodeH.GetKey(N)); }
}
TNode& TUNGraph::GetNode ( const int &  NId) [inline, private]

Definition at line 137 of file graph.h.

{ return NodeH.GetDat(NId); }
const TNode& TUNGraph::GetNode ( const int &  NId) const [inline, private]

Definition at line 138 of file graph.h.

{ return NodeH.GetDat(NId); }
int TUNGraph::GetNodes ( ) const [inline]

Returns the number of nodes in the graph.

Definition at line 162 of file graph.h.

{ return NodeH.Len(); }
TNodeI TUNGraph::GetRndNI ( TRnd Rnd = TInt::Rnd) [inline]

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

Definition at line 240 of file graph.h.

{ return GetNI(GetRndNId(Rnd)); }
int TUNGraph::GetRndNId ( TRnd Rnd = TInt::Rnd) [inline]

Returns an ID of a random node in the graph.

Definition at line 238 of file graph.h.

{ return NodeH.GetKey(NodeH.GetRndKeyId(Rnd, 0.8)); }

Returns a small graph on 5 nodes and 5 edges.

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

Definition at line 190 of file graph.cpp.

                                 {
  PUNGraph Graph = TUNGraph::New();
  for (int i = 0; i < 5; i++) { Graph->AddNode(i); }
  Graph->AddEdge(0,1);  Graph->AddEdge(0,2);
  Graph->AddEdge(0,3);  Graph->AddEdge(0,4);
  Graph->AddEdge(1,2);
  return Graph;
}
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.

                                                   {
  return HasGraphFlag(TUNGraph::TNet, Flag);
}
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 105 of file graph.cpp.

                                                                {
  if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
  return GetNode(SrcNId).IsNbrNId(DstNId);
}
bool TUNGraph::IsNode ( const int &  NId) const [inline]

Tests whether ID NId is a node.

Definition at line 199 of file graph.h.

{ return NodeH.IsKey(NId); }
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 139 of file graph.cpp.

                                                 {
  bool RetVal = true;
  for (int N = NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    const TNode& Node = NodeH[N];
    if (! Node.NIdV.IsSorted()) {
      const TStr Msg = TStr::Fmt("Neighbor list of node %d is not sorted.", Node.GetId());
      if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
      RetVal=false;
    }
    int prevNId = -1;
    for (int e = 0; e < Node.GetDeg(); e++) {
      if (! IsNode(Node.GetNbrNId(e))) {
        const TStr Msg = TStr::Fmt("Edge %d --> %d: node %d does not exist.",
          Node.GetId(), Node.GetNbrNId(e), Node.GetNbrNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
        RetVal=false;
      }
      if (e > 0 && prevNId == Node.GetNbrNId(e)) {
        const TStr Msg = TStr::Fmt("Node %d has duplicate edge %d --> %d.",
          Node.GetId(), Node.GetId(), Node.GetNbrNId(e));
        if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
        RetVal=false;
      }
      prevNId = Node.GetNbrNId(e);
    }
  }
  int EdgeCnt = 0;
  for (TEdgeI EI = BegEI(); EI < EndEI(); EI++) { EdgeCnt++; }
  if (EdgeCnt != GetEdges()) {
    const TStr Msg = TStr::Fmt("Number of edges counter is corrupted: GetEdges():%d, EdgeCount:%d.", GetEdges(), EdgeCnt);
    if (ThrowExcept) { EAssertR(false, Msg); } else { ErrNotify(Msg.CStr()); }
    RetVal=false;
  }
  return RetVal;
}
static PUNGraph TUNGraph::Load ( TSIn SIn) [inline, static]

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

Definition at line 155 of file graph.h.

{ return PUNGraph(new TUNGraph(SIn)); }
static PUNGraph TUNGraph::New ( ) [inline, static]

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

Definition at line 149 of file graph.h.

{ return new TUNGraph(); }
static PUNGraph TUNGraph::New ( const int &  Nodes,
const int &  Edges 
) [inline, static]

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 153 of file graph.h.

{ return new TUNGraph(Nodes, Edges); }
TUNGraph& TUNGraph::operator= ( const TUNGraph Graph) [inline]

Definition at line 158 of file graph.h.

                                               {
    if (this!=&Graph) { MxNId=Graph.MxNId; NEdges=Graph.NEdges; NodeH=Graph.NodeH; } return *this; }
void TUNGraph::Reserve ( const int &  Nodes,
const int &  Edges 
) [inline]

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

Definition at line 249 of file graph.h.

{ if (Nodes>0) NodeH.Gen(Nodes/2); }
void TUNGraph::ReserveNIdDeg ( const int &  NId,
const int &  Deg 
) [inline]

Reserves memory for node ID NId having Deg edges.

Definition at line 251 of file graph.h.

{ GetNode(NId).NIdV.Reserve(Deg); }
void TUNGraph::Save ( TSOut SOut) const [inline]

Saves the graph to a (binary) stream SOut.

Definition at line 147 of file graph.h.

{ MxNId.Save(SOut); NEdges.Save(SOut); NodeH.Save(SOut); }

Friends And Related Function Documentation

friend class TPt< TUNGraph > [friend]

Definition at line 274 of file graph.h.

friend class TUNGraphMtx [friend]

Definition at line 273 of file graph.h.


Member Data Documentation

TCRef TUNGraph::CRef [private]

Definition at line 133 of file graph.h.

TInt TUNGraph::MxNId [private]

Definition at line 134 of file graph.h.

Definition at line 134 of file graph.h.

Definition at line 135 of file graph.h.


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