TNGraph Class Reference

Directed 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 TNGraph	TNet
typedef TPt< TNGraph >	PNet

Public Member Functions
	TNGraph ()
	TNGraph (const int &Nodes, const int &Edges)
	Constructor that reserves enough memory for a graph of Nodes nodes and Edges edges. More...
	TNGraph (const TNGraph &Graph)
	TNGraph (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...
TNGraph &	operator= (const TNGraph &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 &NodeId)
	Adds a node of ID NodeI.GetId() to the graph. More...
int	AddNode (const int &NId, const TIntV &InNIdV, const TIntV &OutNIdV)
	Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV, creates edges from the node to all nodes in vector OutNIdV. More...
int	AddNode (const int &NId, const TVecPool< TInt > &Pool, const int &SrcVId, const int &DstVId)
	Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV in the vector pool Pool, creates edges from the node to all nodes in vector OutNIdVin 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 from node SrcNId to node 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 from node SrcNId to node DstNId to the graph. More...
int	AddEdge2 (const int &SrcNId, const int &DstNId)
	Adds an edge from node IDs SrcNId to node DstNId to the graph. If nodes do not exist, create them. More...
int	AddEdge (const TEdgeI &EdgeI)
	Adds an edge from EdgeI.GetSrcNId() to EdgeI.GetDstNId() to the graph. More...
void	DelEdge (const int &SrcNId, const int &DstNId, const bool &IsDir=true)
	Deletes an edge from node IDs SrcNId to DstNId from the graph. More...
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 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	Reserve (const int &Nodes, const int &Edges)
	Reserves memory for a graph of Nodes nodes and Edges edges. More...
void	ReserveNIdInDeg (const int &NId, const int &InDeg)
	Reserves memory for node ID NId having InDeg in-edges. More...
void	ReserveNIdOutDeg (const int &NId, const int &OutDeg)
	Reserves memory for node ID NId having OutDeg out-edges. More...
void	SortNodeAdjV ()
	Sorts the adjacency lists of each node. 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 PNGraph	New ()
	Static constructor that returns a pointer to the graph. Call: PNGraph Graph = TNGraph::New(). More...
static PNGraph	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 PNGraph	Load (TSIn &SIn)
	Static constructor that loads the graph from a stream SIn and returns a pointer to it. More...
static PNGraph	LoadShM (TShMIn &ShMIn)
	Static constructor that loads the graph from a shared memory stream and returns pointer to it. More...
static PNGraph	GetSmallGraph ()
	Returns a small graph on 5 nodes and 6 edges. More...

Private Member Functions
TNode &	GetNode (const int &NId)
const TNode &	GetNode (const int &NId) const
void	LoadGraphShM (TShMIn &ShMIn)

Private Attributes
TCRef	CRef
TInt	MxNId
THash< TInt, TNode >	NodeH

Friends
class	TPt< TNGraph >
class	TNGraphMtx

Detailed Description

Directed graph.

Node IDs can be arbitrary non-negative integers. Nodes and edges have no attributes/data associated with them. There is at most one directed edge from one source node to a destination node. There can be an edge between the same pair of nodes in the opposite direction. Self loops (one per node) are allowed but multiple (parallel) edges are not. The directed 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 346 of file graph.h.

Member Typedef Documentation

typedef TPt<TNGraph> TNGraph::PNet

Definition at line 349 of file graph.h.

typedef TNGraph TNGraph::TNet

Definition at line 348 of file graph.h.

Constructor & Destructor Documentation

TNGraph::TNGraph ( )

inline

Definition at line 472 of file graph.h.

: CRef(), MxNId(0), NodeH() { }

TNGraph::TNGraph ( const int &  Nodes, const int &  Edges  )

inlineexplicit

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

Definition at line 474 of file graph.h.

: MxNId(0) { Reserve(Nodes, Edges); }

TNGraph::TNGraph ( const TNGraph &  Graph )

inline

Definition at line 475 of file graph.h.

: MxNId(Graph.MxNId), NodeH(Graph.NodeH) { }

TNGraph::TNGraph ( TSIn &  SIn )

inline

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

Definition at line 477 of file graph.h.

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

Member Function Documentation

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

Adds an edge from node SrcNId to node 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 TNGraph have no IDs we return -1. Function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 321 of file graph.cpp.

                                                         {
  IAssertR(IsNode(SrcNId) && IsNode(DstNId), TStr::Fmt("%d or %d not a node.", SrcNId, DstNId).CStr());
  //IAssert(! IsEdge(SrcNId, DstNId));
  if (IsEdge(SrcNId, DstNId)) { return -2; }
  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
  return -1; // no edge id
}

int TNGraph::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 569 of file graph.h.

{ return AddEdge(SrcNId, DstNId); }

int TNGraph::AddEdge ( const TEdgeI &  EdgeI )

inline

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

Definition at line 582 of file graph.h.

{ return AddEdge(EdgeI.GetSrcNId(), EdgeI.GetDstNId()); }

int TNGraph::AddEdge2	(	const int &	SrcNId,
		const int &	DstNId
	)

Adds an edge from node IDs SrcNId to node DstNId to the graph. If nodes do not exist, create them.

Definition at line 336 of file graph.cpp.

                                                          {
  if (! IsNode(SrcNId)) { AddNode(SrcNId); }
  if (! IsNode(DstNId)) { AddNode(DstNId); }
  if (GetNode(SrcNId).IsOutNId(DstNId)) { return -2; } // edge already exists
  GetNode(SrcNId).OutNIdV.AddSorted(DstNId);
  GetNode(DstNId).InNIdV.AddSorted(SrcNId);
  return -1; // no edge id
}

int TNGraph::AddEdgeUnchecked	(	const int &	SrcNId,
		const int &	DstNId
	)

Adds an edge from node SrcNId to node 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 330 of file graph.cpp.

                                                                  {
  GetNode(SrcNId).OutNIdV.Add(DstNId);
  GetNode(DstNId).InNIdV.Add(SrcNId);
  return -1; // no edge id
}

int TNGraph::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 236 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 TNGraph::AddNode ( const TNodeI &  NodeId )

inline

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

Definition at line 517 of file graph.h.

{ return AddNode(NodeId.GetId()); }

int TNGraph::AddNode	(	const int &	NId,
		const TIntV &	InNIdV,
		const TIntV &	OutNIdV
	)

Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV, creates edges from the node to all nodes in vector OutNIdV.

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 vectors InNIdV and OutNIdV do not exist. Use TNGraph::IsOk to check that the resulting graph is consistent after the operation.

Definition at line 256 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.InNIdV = InNIdV;
  Node.OutNIdV = OutNIdV;
  Node.InNIdV.Sort();
  Node.OutNIdV.Sort();
  return NewNId;
}

int TNGraph::AddNode	(	const int &	NId,
		const TVecPool< TInt > &	Pool,
		const int &	SrcVId,
		const int &	DstVId
	)

Adds a node of ID NId to the graph, creates edges to the node from all nodes in vector InNIdV in the vector pool Pool, creates edges from the node to all nodes in vector OutNIdVin 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 TNGraph::IsOk to check that the resulting graph is consistent.

Definition at line 276 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.InNIdV.GenExt(Pool.GetValVPt(SrcVId), Pool.GetVLen(SrcVId));
  Node.OutNIdV.GenExt(Pool.GetValVPt(DstVId), Pool.GetVLen(DstVId));
  Node.InNIdV.Sort();
  Node.OutNIdV.Sort();
  return NewNId;
}

int TNGraph::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 247 of file graph.cpp.

                                     {
  if (IsNode(NId)) { return NId;}
  MxNId = TMath::Mx(NId+1, MxNId());
  NodeH.AddDat(NId, TNode(NId));
  return NId;
}

TEdgeI TNGraph::BegEI ( ) const

inline

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

Definition at line 594 of file graph.h.

{ TNodeI NI=BegNI(); while(NI<EndNI() && NI.GetOutDeg()==0){NI++;} return TEdgeI(NI, EndNI()); }

TNodeI TNGraph::BegNI ( ) const

inline

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

Definition at line 548 of file graph.h.

{ return TNodeI(NodeH.BegI()); }

void TNGraph::Clr ( )

inline

Deletes all nodes and edges from the graph.

Definition at line 612 of file graph.h.

{ MxNId=0; NodeH.Clr(); }

void TNGraph::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 382 of file graph.cpp.

                                              {
  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 TNGraph::DelEdge	(	const int &	SrcNId,
		const int &	DstNId,
		const bool &	IsDir = true
	)

Deletes an edge from node IDs SrcNId to 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 345 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.OutNIdV.SearchBin(DstNId);
  if (n!= -1) { N.OutNIdV.Del(n); } }
  { TNode& N = GetNode(DstNId);
  const int n = N.InNIdV.SearchBin(SrcNId);
  if (n!= -1) { N.InNIdV.Del(n); } }
  if (! IsDir) {
    { TNode& N = GetNode(SrcNId);
    const int n = N.InNIdV.SearchBin(DstNId);
    if (n!= -1) { N.InNIdV.Del(n); } }
    { TNode& N = GetNode(DstNId);
    const int n = N.OutNIdV.SearchBin(SrcNId);
    if (n!= -1) { N.OutNIdV.Del(n); } }
  }
}

void TNGraph::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 294 of file graph.cpp.

                                    {
  { 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);
    const 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);
    const int n = N.OutNIdV.SearchBin(NId);
    if (n!= -1) { N.OutNIdV.Del(n); }
  } }
  NodeH.DelKey(NId);
}

void TNGraph::DelNode ( const TNode &  NodeI )

inline

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

Definition at line 544 of file graph.h.

{ DelNode(NodeI.GetId()); }

void TNGraph::Dump

(

FILE *

OutF = stdout

)

const

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

Definition at line 437 of file graph.cpp.

                                   {
  const int NodePlaces = (int) ceil(log10((double) GetNodes()));
  fprintf(OutF, "-------------------------------------------------\nDirected 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]\n", NodePlaces, Node.GetId());
    fprintf(OutF, "    in [%d]", Node.GetInDeg());
    for (int edge = 0; edge < Node.GetInDeg(); edge++) {
      fprintf(OutF, " %*d", NodePlaces, Node.GetInNId(edge)); }
    fprintf(OutF, "\n    out[%d]", Node.GetOutDeg());
    for (int edge = 0; edge < Node.GetOutDeg(); edge++) {
      fprintf(OutF, " %*d", NodePlaces, Node.GetOutNId(edge)); }
    fprintf(OutF, "\n");
  }
  fprintf(OutF, "\n");
}

bool TNGraph::Empty ( ) const

inline

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

Definition at line 610 of file graph.h.

{ return GetNodes()==0; }

TEdgeI TNGraph::EndEI ( ) const

inline

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

Definition at line 596 of file graph.h.

{ return TEdgeI(EndNI(), EndNI()); }

TNodeI TNGraph::EndNI ( ) const

inline

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

Definition at line 550 of file graph.h.

{ return TNodeI(NodeH.EndI()); }

int TNGraph::GetEdges

(

)

const

Returns the number of edges in the graph.

Definition at line 313 of file graph.cpp.

                            {
  int edges=0;
  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    edges+=NodeH[N].GetOutDeg();
  }
  return edges;
}

TEdgeI TNGraph::GetEI

(

const int &

EId

)

const

Not supported/implemented!

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

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

Definition at line 369 of file graph.cpp.

                                                                       {
  const TNodeI SrcNI = GetNI(SrcNId);
  const int NodeN = SrcNI.NodeHI.GetDat().OutNIdV.SearchBin(DstNId);
  IAssert(NodeN != -1);
  return TEdgeI(SrcNI, EndNI(), NodeN);
}

int TNGraph::GetMxNId ( ) const

inline

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

Definition at line 556 of file graph.h.

{ return MxNId; }

TNodeI TNGraph::GetNI ( const int &  NId ) const

inline

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

Definition at line 552 of file graph.h.

{ return TNodeI(NodeH.GetI(NId)); }

void TNGraph::GetNIdV

(

TIntV &

NIdV

)

const

Gets a vector IDs of all nodes in the graph.

Definition at line 376 of file graph.cpp.

                                       {
  NIdV.Gen(GetNodes(), 0);
  for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
    NIdV.Add(NodeH.GetKey(N)); }
}

TNode& TNGraph::GetNode ( const int &  NId )

inlineprivate

Definition at line 463 of file graph.h.

{ return NodeH.GetDat(NId); }

const TNode& TNGraph::GetNode ( const int &  NId ) const

inlineprivate

Definition at line 464 of file graph.h.

{ return NodeH.GetDat(NId); }

int TNGraph::GetNodes ( ) const

inline

Returns the number of nodes in the graph.

Definition at line 503 of file graph.h.

{ return NodeH.Len(); }

TNodeI TNGraph::GetRndNI ( TRnd &  Rnd = TInt::Rnd )

inline

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

Definition at line 605 of file graph.h.

{ return GetNI(GetRndNId(Rnd)); }

int TNGraph::GetRndNId ( TRnd &  Rnd = TInt::Rnd )

inline

Returns an ID of a random node in the graph.

Definition at line 603 of file graph.h.

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

PNGraph TNGraph::GetSmallGraph ( )

static

Returns a small graph on 5 nodes and 6 edges.

/// Edges:  0 -> 1, 1 -> 2, 0 -> 2, 1 -> 3, 3 -> 4, 2 -> 3
/// 

Definition at line 454 of file graph.cpp.

                               {
  PNGraph G = TNGraph::New();
  for (int i = 0; i < 5; i++) { G->AddNode(i); }
  G->AddEdge(0,1); G->AddEdge(1,2); G->AddEdge(0,2);
  G->AddEdge(1,3); G->AddEdge(3,4); G->AddEdge(2,3);
  return G;
}

bool TNGraph::HasFlag

(

const TGraphFlag &

Flag

)

const

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

Definition at line 232 of file graph.cpp.

                                                  {
  return HasGraphFlag(TNGraph::TNet, Flag);
}

bool TNGraph::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 graph.

Definition at line 363 of file graph.cpp.

                                                                                  {
  if (! IsNode(SrcNId) || ! IsNode(DstNId)) { return false; }
  if (IsDir) { return GetNode(SrcNId).IsOutNId(DstNId); }
  else { return GetNode(SrcNId).IsOutNId(DstNId) || GetNode(DstNId).IsOutNId(SrcNId); }
}

bool TNGraph::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 592 of file graph.h.

{ return false; }

bool TNGraph::IsNode ( const int &  NId ) const

inline

Tests whether ID NId is a node.

Definition at line 546 of file graph.h.

{ return NodeH.IsKey(NId); }

bool TNGraph::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 391 of file graph.cpp.

                                                {
  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;
}

static PNGraph TNGraph::Load ( TSIn &  SIn )

inlinestatic

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

Definition at line 487 of file graph.h.

{ return PNGraph(new TNGraph(SIn)); }

void TNGraph::LoadGraphShM ( TShMIn &  ShMIn )

inlineprivate

Definition at line 465 of file graph.h.

                                   {
    MxNId = TInt(ShMIn);
    TLoadTNodeInitializer Fn;
    NodeH.LoadShM(ShMIn, Fn);
  }

static PNGraph TNGraph::LoadShM ( TShMIn &  ShMIn )

inlinestatic

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

static constructor to load the graph from 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 492 of file graph.h.

                                        {
    TNGraph* Graph = new TNGraph();
    Graph->LoadGraphShM(ShMIn);
    return PNGraph(Graph);
  }

static PNGraph TNGraph::New ( )

inlinestatic

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

Definition at line 481 of file graph.h.

{ return new TNGraph(); }

static PNGraph TNGraph::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: PNGraph Graph = TNGraph::New(Nodes, Edges).

Definition at line 485 of file graph.h.

{ return new TNGraph(Nodes, Edges); }

TNGraph& TNGraph::operator= ( const TNGraph &  Graph )

inline

Definition at line 499 of file graph.h.

                                             {
    if (this!=&Graph) { MxNId=Graph.MxNId; NodeH=Graph.NodeH; }  return *this; }

void TNGraph::Reserve ( const int &  Nodes, const int &  Edges  )

inline

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

Definition at line 614 of file graph.h.

{ if (Nodes>0) { NodeH.Gen(Nodes/2); } }

void TNGraph::ReserveNIdInDeg ( const int &  NId, const int &  InDeg  )

inline

Reserves memory for node ID NId having InDeg in-edges.

Definition at line 616 of file graph.h.

{ GetNode(NId).InNIdV.Reserve(InDeg); }

void TNGraph::ReserveNIdOutDeg ( const int &  NId, const int &  OutDeg  )

inline

Reserves memory for node ID NId having OutDeg out-edges.

Definition at line 618 of file graph.h.

{ GetNode(NId).OutNIdV.Reserve(OutDeg); }

void TNGraph::Save ( TSOut &  SOut ) const

inline

Saves the graph to a (binary) stream SOut.

Definition at line 479 of file graph.h.

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

void TNGraph::SortNodeAdjV ( )

inline

Sorts the adjacency lists of each node.

Definition at line 620 of file graph.h.

{ for (TNodeI NI = BegNI(); NI < EndNI(); NI++) { NI.SortNIdV();} }

Friends And Related Function Documentation

friend class TNGraphMtx

friend

Definition at line 642 of file graph.h.

friend class TPt< TNGraph >

friend

Definition at line 641 of file graph.h.

Member Data Documentation

TCRef TNGraph::CRef

private

Definition at line 453 of file graph.h.

TInt TNGraph::MxNId

private

Definition at line 454 of file graph.h.

THash<TInt, TNode> TNGraph::NodeH

private

Definition at line 455 of file graph.h.

---

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

• snap-core/graph.h
• snap-core/graph.cpp