Undirected network. 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 TUndirNet	TNet

typedef TPt< TUndirNet >	PNet

Public Member Functions
	TUndirNet ()

	TUndirNet (const int &Nodes, const int &Edges)
	Constructor that reserves enough memory for a network of Nodes nodes and Edges edges. More...

	TUndirNet (const TUndirNet &Graph)

	TUndirNet (TSIn &SIn)
	Constructor that loads the network from a (binary) stream SIn. More...

void	Save (TSOut &SOut) const
	Saves the network to a (binary) stream SOut. Expects data structures for sparse attributes. More...

void	Save_V1 (TSOut &SOut) const
	Saves the network to a (binary) stream SOut. Available for backwards compatibility. More...

bool	HasFlag (const TGraphFlag &Flag) const
	Allows for run-time checking the type of the network (see the TGraphFlag for flags). More...

TUndirNet &	operator= (const TUndirNet &Graph)

int	GetNodes () const
	Returns the number of nodes in the network. More...

int	AddNode (int NId=-1)
	Adds a node of ID NId to the network. More...

int	AddNode (const TNodeI &NodeI)
	Adds a node of ID NodeI.GetId() to the network. More...

int	AddNode (const int &NId, const TIntV &NbrNIdV)
	Adds a node of ID NId to the network 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 network 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 network. More...

void	DelNode (const TNode &NodeI)
	Deletes node of ID NodeI.GetId() from the network. 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 network. More...

TNodeI	EndNI () const
	Returns an iterator referring to the past-the-end node in the network. More...

TNodeI	GetNI (const int &NId) const
	Returns an iterator referring to the node of ID NId in the network. More...

int	GetMxNId () const
	Returns an ID that is larger than any node ID in the network. More...

int	GetEdges () const
	Returns the number of edges in the network. More...

int	AddEdge (const int &SrcNId, const int &DstNId)
	Adds an edge between node IDs SrcNId and DstNId to the network. More...

int	AddEdge (const TEdgeI &EdgeI)
	Adds an edge between EdgeI.GetSrcNId() and EdgeI.GetDstNId() to the network. More...

void	DelEdge (const int &SrcNId, const int &DstNId)
	Deletes an edge between node IDs SrcNId and DstNId from the network. More...

bool	IsEdge (const int &SrcNId, const int &DstNId) const
	Tests whether an edge between node IDs SrcNId and DstNId exists in the network. More...

TEdgeI	BegEI () const
	Returns an iterator referring to the first edge in the network. More...

TEdgeI	EndEI () const
	Returns an iterator referring to the past-the-end edge in the network. 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 network. More...

int	GetRndNId (TRnd &Rnd=TInt::Rnd)
	Returns an ID of a random node in the network. More...

TNodeI	GetRndNI (TRnd &Rnd=TInt::Rnd)
	Returns an interator referring to a random node in the network. More...

void	GetNIdV (TIntV &NIdV) const
	Gets a vector IDs of all nodes in the network. More...

bool	Empty () const
	Tests whether the network is empty (has zero nodes). More...

void	Clr ()
	Deletes all nodes and edges from the network. More...

void	Reserve (const int &Nodes, const int &Edges)
	Reserves memory for a network 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 network. More...

bool	IsOk (const bool &ThrowExcept=true) const
	Checks the network data structure for internal consistency. More...

void	Dump (FILE *OutF=stdout) const
	Print the network in a human readable form to an output stream OutF. More...

int	AddSAttrDatN (const TInt &NId, const TStr &AttrName, const TInt &Val)
	Adds Int sparse attribute with name `AttrName` to the given node with id `NId`. More...

int	AddSAttrDatN (const TInt &NId, const TInt &AttrId, const TInt &Val)
	Adds Int sparse attribute with id `AttrId` to the given node with id `NId`. More...

int	AddSAttrDatN (const TNodeI &NodeI, const TStr &AttrName, const TInt &Val)
	Adds Int sparse attribute with name `AttrName` to `NodeI`. More...

int	AddSAttrDatN (const TNodeI &NodeI, const TInt &AttrId, const TInt &Val)
	Adds Int sparse attribute with id `AttrId` to `NodeI`. More...

int	AddSAttrDatN (const TInt &NId, const TStr &AttrName, const TFlt &Val)
	Adds Flt sparse attribute with name `AttrName` to the given node with id `NId`. More...

int	AddSAttrDatN (const TInt &NId, const TInt &AttrId, const TFlt &Val)
	Adds Flt sparse attribute with id `AttrId` to the given node with id `NId`. More...

int	AddSAttrDatN (const TNodeI &NodeI, const TStr &AttrName, const TFlt &Val)
	Adds Flt sparse attribute with name `AttrName` to `NodeI`. More...

int	AddSAttrDatN (const TNodeI &NodeI, const TInt &AttrId, const TFlt &Val)
	Adds Flt sparse attribute with id `AttrId` to `NodeI`. More...

int	AddSAttrDatN (const TInt &NId, const TStr &AttrName, const TStr &Val)
	Adds Str sparse attribute with name `AttrName` to the given node with id `NId`. More...

int	AddSAttrDatN (const TInt &NId, const TInt &AttrId, const TStr &Val)
	Adds Str sparse attribute with id `AttrId` to the given node with id `NId`. More...

int	AddSAttrDatN (const TNodeI &NodeI, const TStr &AttrName, const TStr &Val)
	Adds Str sparse attribute with name `AttrName` to `NodeI`. More...

int	AddSAttrDatN (const TNodeI &NodeI, const TInt &AttrId, const TStr &Val)
	Adds Str sparse attribute with id `AttrId` to `NodeI`. More...

int	GetSAttrDatN (const TInt &NId, const TStr &AttrName, TInt &ValX) const
	Gets Int sparse attribute with name `AttrName` from node with id `NId`. More...

int	GetSAttrDatN (const TInt &NId, const TInt &AttrId, TInt &ValX) const
	Gets Int sparse attribute with id `AttrId` from node with id `NId`. More...

int	GetSAttrDatN (const TNodeI &NodeI, const TStr &AttrName, TInt &ValX) const
	Gets Int sparse attribute with name `AttrName` from `NodeI`. More...

int	GetSAttrDatN (const TNodeI &NodeI, const TInt &AttrId, TInt &ValX) const
	Gets Int sparse attribute with id `AttrId` from `NodeI`. More...

int	GetSAttrDatN (const TInt &NId, const TStr &AttrName, TFlt &ValX) const
	Gets Flt sparse attribute with name `AttrName` from node with id `NId`. More...

int	GetSAttrDatN (const TInt &NId, const TInt &AttrId, TFlt &ValX) const
	Gets Flt sparse attribute with id `AttrId` from node with id `NId`. More...

int	GetSAttrDatN (const TNodeI &NodeI, const TStr &AttrName, TFlt &ValX) const
	Gets Flt sparse attribute with name `AttrName` from `NodeI`. More...

int	GetSAttrDatN (const TNodeI &NodeI, const TInt &AttrId, TFlt &ValX) const
	Gets Flt sparse attribute with id `AttrId` from `NodeI`. More...

int	GetSAttrDatN (const TInt &NId, const TStr &AttrName, TStr &ValX) const
	Gets Str sparse attribute with name `AttrName` from node with id `NId`. More...

int	GetSAttrDatN (const TInt &NId, const TInt &AttrId, TStr &ValX) const
	Gets Str sparse attribute with id `AttrId` from node with id `NId`. More...

int	GetSAttrDatN (const TNodeI &NodeI, const TStr &AttrName, TStr &ValX) const
	Gets Str sparse attribute with name `AttrName` from `NodeI`. More...

int	GetSAttrDatN (const TNodeI &NodeI, const TInt &AttrId, TStr &ValX) const
	Gets Str sparse attribute with id `AttrId` from `NodeI`. More...

int	DelSAttrDatN (const TInt &NId, const TStr &AttrName)
	Deletes sparse attribute with name `AttrName` from node with id `NId`. More...

int	DelSAttrDatN (const TInt &NId, const TInt &AttrId)
	Deletes sparse attribute with id `AttrId` from node with id `NId`. More...

int	DelSAttrDatN (const TNodeI &NodeI, const TStr &AttrName)
	Deletes sparse attribute with name `AttrName` from `NodeI`. More...

int	DelSAttrDatN (const TNodeI &NodeI, const TInt &AttrId)
	Deletes sparse attribute with id `AttrId` from `NodeI`. More...

int	GetSAttrVN (const TInt &NId, const TAttrType AttrType, TAttrPrV &AttrV) const
	Gets a list of all sparse attributes of type `AttrType` for node with id `NId`. More...

int	GetSAttrVN (const TNodeI &NodeI, const TAttrType AttrType, TAttrPrV &AttrV) const
	Gets a list of all sparse attributes of type `AttrType` for `NodeI`. More...

int	GetIdVSAttrN (const TStr &AttrName, TIntV &IdV) const
	Gets a list of all nodes that have a sparse attribute with name `AttrName`. More...

int	GetIdVSAttrN (const TInt &AttrId, TIntV &IdV) const
	Gets a list of all nodes that have a sparse attribute with id `AttrId`. More...

int	AddSAttrN (const TStr &Name, const TAttrType &AttrType, TInt &AttrId)
	Adds mapping for sparse attribute with name `Name` and type `AttrType`. More...

int	GetSAttrIdN (const TStr &Name, TInt &AttrIdX, TAttrType &AttrTypeX) const
	Gets id and type for attribute with name `Name`. More...

int	GetSAttrNameN (const TInt &AttrId, TStr &NameX, TAttrType &AttrTypeX) const
	Gets name and type for attribute with id `AttrId`. More...

int	AddSAttrDatE (const int &SrcNId, const int &DstNId, const TStr &AttrName, const TInt &Val)
	Adds Int sparse attribute with name `AttrName` to the given edge with ids `SrcId` and `DstId`. More...

int	AddSAttrDatE (const int &SrcNId, const int &DstNId, const TInt &AttrId, const TInt &Val)
	Adds Int sparse attribute with id `AttrId` to the given edge with ids `SrcId` and `DstId`. More...

int	AddSAttrDatE (const TEdgeI &EdgeI, const TStr &AttrName, const TInt &Val)
	Adds Int sparse attribute with name `AttrName` to `EdgeI`. More...

int	AddSAttrDatE (const TEdgeI &EdgeI, const TInt &AttrId, const TInt &Val)
	Adds Int sparse attribute with id `AttrId` to `EdgeI`. More...

int	AddSAttrDatE (const int &SrcNId, const int &DstNId, const TStr &AttrName, const TFlt &Val)
	Adds Flt sparse attribute with name `AttrName` to the given edge with ids `SrcId` and `DstId`. More...

int	AddSAttrDatE (const int &SrcNId, const int &DstNId, const TInt &AttrId, const TFlt &Val)
	Adds Flt sparse attribute with id `AttrId` to the given edge with ids `SrcId` and `DstId`. More...

int	AddSAttrDatE (const TEdgeI &EdgeI, const TStr &AttrName, const TFlt &Val)
	Adds Flt sparse attribute with name `AttrName` to `EdgeI`. More...

int	AddSAttrDatE (const TEdgeI &EdgeI, const TInt &AttrId, const TFlt &Val)
	Adds Flt sparse attribute with id `AttrId` to `EdgeI`. More...

int	AddSAttrDatE (const int &SrcNId, const int &DstNId, const TStr &AttrName, const TStr &Val)
	Adds Str sparse attribute with name `AttrName` to the given edge with ids `SrcId` and `DstId`. More...

int	AddSAttrDatE (const int &SrcNId, const int &DstNId, const TInt &AttrId, const TStr &Val)
	Adds Str sparse attribute with id `AttrId` to the given edge with ids `SrcId` and `DstId`. More...

int	AddSAttrDatE (const TEdgeI &EdgeI, const TStr &AttrName, const TStr &Val)
	Adds Str sparse attribute with name `AttrName` to `EdgeI`. More...

int	AddSAttrDatE (const TEdgeI &EdgeI, const TInt &AttrId, const TStr &Val)
	Adds Str sparse attribute with id `AttrId` to `EdgeI`. More...

int	GetSAttrDatE (const int &SrcNId, const int &DstNId, const TStr &AttrName, TInt &ValX) const
	Gets Int sparse attribute with name `AttrName` from edge with ids `SrcId` and `DstId`. More...

int	GetSAttrDatE (const int &SrcNId, const int &DstNId, const TInt &AttrId, TInt &ValX) const
	Gets Int sparse attribute with id `AttrId` from edge with ids `SrcId` and `DstId`. More...

int	GetSAttrDatE (const TEdgeI &EdgeI, const TStr &AttrName, TInt &ValX) const
	Gets Int sparse attribute with name `AttrName` from `EdgeI`. More...

int	GetSAttrDatE (const TEdgeI &EdgeI, const TInt &AttrId, TInt &ValX) const
	Gets Int sparse attribute with id `AttrId` from `EdgeI`. More...

int	GetSAttrDatE (const int &SrcNId, const int &DstNId, const TStr &AttrName, TFlt &ValX) const
	Gets Flt sparse attribute with name `AttrName` from edge with ids `SrcId` and `DstId`. More...

int	GetSAttrDatE (const int &SrcNId, const int &DstNId, const TInt &AttrId, TFlt &ValX) const
	Gets Flt sparse attribute with id `AttrId` from edge with ids `SrcId` and `DstId`. More...

int	GetSAttrDatE (const TEdgeI &EdgeI, const TStr &AttrName, TFlt &ValX) const
	Gets Flt sparse attribute with name `AttrName` from `EdgeI`. More...

int	GetSAttrDatE (const TEdgeI &EdgeI, const TInt &AttrId, TFlt &ValX) const
	Gets Flt sparse attribute with id `AttrId` from `EdgeI`. More...

int	GetSAttrDatE (const int &SrcNId, const int &DstNId, const TStr &AttrName, TStr &ValX) const
	Gets Str sparse attribute with name `AttrName` from edge with ids `SrcId` and `DstId`. More...

int	GetSAttrDatE (const int &SrcNId, const int &DstNId, const TInt &AttrId, TStr &ValX) const
	Gets Str sparse attribute with id `AttrId` from edge with ids `SrcId` and `DstId`. More...

int	GetSAttrDatE (const TEdgeI &EdgeI, const TStr &AttrName, TStr &ValX) const
	Gets Str sparse attribute with name `AttrName` from `EdgeI`. More...

int	GetSAttrDatE (const TEdgeI &EdgeI, const TInt &AttrId, TStr &ValX) const
	Gets Str sparse attribute with id `AttrId` from `EdgeI`. More...

int	DelSAttrDatE (const int &SrcNId, const int &DstNId, const TStr &AttrName)
	Deletes sparse attribute with name `AttrName` from edge with ids `SrcId` and `DstId`. More...

int	DelSAttrDatE (const int &SrcNId, const int &DstNId, const TInt &AttrId)
	Deletes sparse attribute with id `AttrId` from edge with ids `SrcId` and `DstId`. More...

int	DelSAttrDatE (const TEdgeI &EdgeI, const TStr &AttrName)
	Deletes sparse attribute with name `AttrName` from `EdgeI`. More...

int	DelSAttrDatE (const TEdgeI &EdgeI, const TInt &AttrId)
	Deletes sparse attribute with id `AttrId` from `EdgeI`. More...

int	GetSAttrVE (const int &SrcNId, const int &DstNId, const TAttrType AttrType, TAttrPrV &AttrV) const
	Gets a list of all sparse attributes of type `AttrType` for edge with ids `SrcId` and `DstId`. More...

int	GetSAttrVE (const TEdgeI &EdgeI, const TAttrType AttrType, TAttrPrV &AttrV) const
	Gets a list of all sparse attributes of type `AttrType` for `EdgeI`. More...

int	GetIdVSAttrE (const TStr &AttrName, TIntPrV &IdV) const
	Gets a list of all edges that have a sparse attribute with name `AttrName`. More...

int	GetIdVSAttrE (const TInt &AttrId, TIntPrV &IdV) const
	Gets a list of all edges that have a sparse attribute with id `AttrId`. More...

int	AddSAttrE (const TStr &Name, const TAttrType &AttrType, TInt &AttrId)
	Adds mapping for sparse attribute with name `Name` and type `AttrType`. More...

int	GetSAttrIdE (const TStr &Name, TInt &AttrIdX, TAttrType &AttrTypeX) const
	Gets id and type for attribute with name `Name`. More...

int	GetSAttrNameE (const TInt &AttrId, TStr &NameX, TAttrType &AttrTypeX) const
	Gets name and type for attribute with id `AttrId`. More...

Static Public Member Functions
static PUndirNet	New ()
	Static constructor that returns a pointer to the network. Call: PUndirNet Graph = TUndirNet::New(). More...

static PUndirNet	New (const int &Nodes, const int &Edges)
	Static constructor that returns a pointer to the network and reserves enough memory for Nodes nodes and Edges edges. More...

static PUndirNet	Load (TSIn &SIn)
	Static constructor that loads the network from a stream SIn and returns a pointer to it. More...

static PUndirNet	Load_V1 (TSIn &SIn)
	Static constructor that loads the network from a stream SIn and returns a pointer to it. Backwards compatible. More...

static PUndirNet	GetSmallGraph ()
	Returns a small network on 5 nodes and 5 edges. More...

Private Member Functions
TNode &	GetNode (const int &NId)

const TNode &	GetNode (const int &NId) const

TIntPr	OrderEdgeNodes (const int &SrcNId, const int &DstNId) const

Private Attributes
TCRef	CRef

TInt	MxNId

TInt	NEdges

THash< TInt, TNode >	NodeH

TAttr	SAttrN

TAttrPair	SAttrE

Friends
class	TUndirNetMtx

class	TPt< TUndirNet >

Detailed Description

Undirected network.

Node IDs can be arbitrary non-negative integers. Nodes and edges can have sparse 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 2748 of file network.h.

Member Typedef Documentation

typedef TPt<TUndirNet> TUndirNet::PNet

Definition at line 2751 of file network.h.

typedef TUndirNet TUndirNet::TNet

Definition at line 2750 of file network.h.

Constructor & Destructor Documentation

TUndirNet::TUndirNet ( )

inline

Definition at line 2863 of file network.h.

2863 : CRef(), MxNId(0), NEdges(0), NodeH(), SAttrN(), SAttrE() { }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

TUndirNet::MxNId

TInt MxNId

Definition: network.h:2853

TUndirNet::SAttrE

TAttrPair SAttrE

Definition: network.h:2857

TUndirNet::SAttrN

TAttr SAttrN

Definition: network.h:2856

TUndirNet::CRef

TCRef CRef

Definition: network.h:2852

TUndirNet::NEdges

TInt NEdges

Definition: network.h:2853

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

inlineexplicit

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

Definition at line 2865 of file network.h.

2865 : MxNId(0), NEdges(0), SAttrN(), SAttrE() { Reserve(Nodes, Edges); }

TUndirNet::Reserve

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

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

Definition: network.h:2986

TUndirNet::MxNId

TInt MxNId

Definition: network.h:2853

TUndirNet::SAttrE

TAttrPair SAttrE

Definition: network.h:2857

TUndirNet::SAttrN

TAttr SAttrN

Definition: network.h:2856

TUndirNet::NEdges

TInt NEdges

Definition: network.h:2853

TUndirNet::TUndirNet ( const TUndirNet & Graph )

inline

Definition at line 2866 of file network.h.

2866 : MxNId(Graph.MxNId), NEdges(Graph.NEdges), NodeH(Graph.NodeH),

2867 SAttrN(), SAttrE() { }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

TUndirNet::MxNId

TInt MxNId

Definition: network.h:2853

TUndirNet::SAttrE

TAttrPair SAttrE

Definition: network.h:2857

TUndirNet::SAttrN

TAttr SAttrN

Definition: network.h:2856

TUndirNet::NEdges

TInt NEdges

Definition: network.h:2853

TUndirNet::TUndirNet ( TSIn & SIn )

inline

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

Definition at line 2869 of file network.h.

2869 : MxNId(SIn), NEdges(SIn), NodeH(SIn), SAttrN(SIn), SAttrE(SIn) { }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

TUndirNet::MxNId

TInt MxNId

Definition: network.h:2853

TUndirNet::SAttrE

TAttrPair SAttrE

Definition: network.h:2857

TUndirNet::SAttrN

TAttr SAttrN

Definition: network.h:2856

TUndirNet::NEdges

TInt NEdges

Definition: network.h:2853

Member Function Documentation

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

Adds an edge between node IDs SrcNId and 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 TUndirNet have no IDs we return -1. The function aborts if SrcNId or DstNId are not nodes in the graph.

Definition at line 1742 of file network.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 TUndirNet::AddEdge ( const TEdgeI & EdgeI )

inline

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

Definition at line 2953 of file network.h.

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

TUndirNet::AddEdge

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

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

Definition: network.cpp:1742

int TUndirNet::AddNode ( int NId = -1 )

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.

Definition at line 1664 of file network.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 TUndirNet::AddNode ( const TNodeI & NodeI )

inline

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

Definition at line 2902 of file network.h.

2902 { return AddNode(NodeI.GetId()); }

TUndirNet::AddNode

int AddNode(int NId=-1)

Adds a node of ID NId to the network.

Definition: network.cpp:1664

int TUndirNet::AddNode	(	const int &	NId,
		const TIntV &	NbrNIdV
	)

Adds a node of ID NId to the network 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 TUndirNet::IsOk to check that the resulting graph is consistent after the operation.

Definition at line 1676 of file network.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();
   for (int i = 0; i < NbrNIdV.Len(); i++) {
     GetNode(NbrNIdV[i]).NIdV.AddSorted(NewNId);
   }
   return NewNId;
 }

int TUndirNet::AddNode	(	const int &	NId,
		const TVecPool< TInt > &	Pool,
		const int &	NIdVId
	)

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

//int& NIdVId) 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 TUndirNet::IsOk to check that the resulting graph is consistent.

Definition at line 1697 of file network.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;
 }

int TUndirNet::AddSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TStr &	AttrName,
		const TInt &	Val
	)

Adds Int sparse attribute with name AttrName to the given edge with ids SrcId and DstId.

Definition at line 1995 of file network.cpp.

                                                                                                        {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.AddSAttrDat(EId, AttrName, Val);
 }

int TUndirNet::AddSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TInt &	AttrId,
		const TInt &	Val
	)

Adds Int sparse attribute with id AttrId to the given edge with ids SrcId and DstId.

Definition at line 2003 of file network.cpp.

                                                                                                      {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.AddSAttrDat(EId, AttrId, Val);
 }

int TUndirNet::AddSAttrDatE	(	const TEdgeI &	EdgeI,
		const TStr &	AttrName,
		const TInt &	Val
	)

inline

Adds Int sparse attribute with name AttrName to EdgeI.

Definition at line 3136 of file network.h.

                                                                                {
     return AddSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrName, Val);
   }

int TUndirNet::AddSAttrDatE	(	const TEdgeI &	EdgeI,
		const TInt &	AttrId,
		const TInt &	Val
	)

inline

Adds Int sparse attribute with id AttrId to EdgeI.

Definition at line 3140 of file network.h.

                                                                              {
     return AddSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrId, Val);
   }

int TUndirNet::AddSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TStr &	AttrName,
		const TFlt &	Val
	)

Adds Flt sparse attribute with name AttrName to the given edge with ids SrcId and DstId.

Definition at line 2011 of file network.cpp.

                                                                                                        {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.AddSAttrDat(EId, AttrName, Val);
 }

int TUndirNet::AddSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TInt &	AttrId,
		const TFlt &	Val
	)

Adds Flt sparse attribute with id AttrId to the given edge with ids SrcId and DstId.

Definition at line 2019 of file network.cpp.

                                                                                                      {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.AddSAttrDat(EId, AttrId, Val);
 }

int TUndirNet::AddSAttrDatE	(	const TEdgeI &	EdgeI,
		const TStr &	AttrName,
		const TFlt &	Val
	)

inline

Adds Flt sparse attribute with name AttrName to EdgeI.

Definition at line 3150 of file network.h.

                                                                                {
     return AddSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrName, Val);
   }

int TUndirNet::AddSAttrDatE	(	const TEdgeI &	EdgeI,
		const TInt &	AttrId,
		const TFlt &	Val
	)

inline

Adds Flt sparse attribute with id AttrId to EdgeI.

Definition at line 3154 of file network.h.

                                                                             {
     return AddSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrId, Val);
   }

int TUndirNet::AddSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TStr &	AttrName,
		const TStr &	Val
	)

Adds Str sparse attribute with name AttrName to the given edge with ids SrcId and DstId.

Definition at line 2027 of file network.cpp.

                                                                                                        {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.AddSAttrDat(EId, AttrName, Val);
 }

int TUndirNet::AddSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TInt &	AttrId,
		const TStr &	Val
	)

Adds Str sparse attribute with id AttrId to the given edge with ids SrcId and DstId.

Definition at line 2035 of file network.cpp.

                                                                                                      {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.AddSAttrDat(EId, AttrId, Val);
 }

int TUndirNet::AddSAttrDatE	(	const TEdgeI &	EdgeI,
		const TStr &	AttrName,
		const TStr &	Val
	)

inline

Adds Str sparse attribute with name AttrName to EdgeI.

Definition at line 3164 of file network.h.

                                                                                {
     return AddSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrName, Val);
   }

int TUndirNet::AddSAttrDatE	(	const TEdgeI &	EdgeI,
		const TInt &	AttrId,
		const TStr &	Val
	)

inline

Adds Str sparse attribute with id AttrId to EdgeI.

Definition at line 3168 of file network.h.

                                                                              {
     return AddSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrId, Val);
   }

int TUndirNet::AddSAttrDatN	(	const TInt &	NId,
		const TStr &	AttrName,
		const TInt &	Val
	)

Adds Int sparse attribute with name AttrName to the given node with id NId.

Definition at line 1862 of file network.cpp.

                                                                                   {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.AddSAttrDat(NId, AttrName, Val);
 }

int TUndirNet::AddSAttrDatN	(	const TInt &	NId,
		const TInt &	AttrId,
		const TInt &	Val
	)

Adds Int sparse attribute with id AttrId to the given node with id NId.

Definition at line 1869 of file network.cpp.

                                                                                 {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.AddSAttrDat(NId, AttrId, Val);
 }

int TUndirNet::AddSAttrDatN	(	const TNodeI &	NodeI,
		const TStr &	AttrName,
		const TInt &	Val
	)

inline

Adds Int sparse attribute with name AttrName to NodeI.

Definition at line 3018 of file network.h.

                                                                                {
     return AddSAttrDatN(NodeI.GetId(), AttrName, Val);
   }

int TUndirNet::AddSAttrDatN	(	const TNodeI &	NodeI,
		const TInt &	AttrId,
		const TInt &	Val
	)

inline

Adds Int sparse attribute with id AttrId to NodeI.

Definition at line 3022 of file network.h.

                                                                              {
     return AddSAttrDatN(NodeI.GetId(), AttrId, Val);
   }

int TUndirNet::AddSAttrDatN	(	const TInt &	NId,
		const TStr &	AttrName,
		const TFlt &	Val
	)

Adds Flt sparse attribute with name AttrName to the given node with id NId.

Definition at line 1876 of file network.cpp.

                                                                                   {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.AddSAttrDat(NId, AttrName, Val);
 }

int TUndirNet::AddSAttrDatN	(	const TInt &	NId,
		const TInt &	AttrId,
		const TFlt &	Val
	)

Adds Flt sparse attribute with id AttrId to the given node with id NId.

Definition at line 1883 of file network.cpp.

                                                                                 {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.AddSAttrDat(NId, AttrId, Val);
 }

int TUndirNet::AddSAttrDatN	(	const TNodeI &	NodeI,
		const TStr &	AttrName,
		const TFlt &	Val
	)

inline

Adds Flt sparse attribute with name AttrName to NodeI.

Definition at line 3032 of file network.h.

                                                                                {
     return AddSAttrDatN(NodeI.GetId(), AttrName, Val);
   }

int TUndirNet::AddSAttrDatN	(	const TNodeI &	NodeI,
		const TInt &	AttrId,
		const TFlt &	Val
	)

inline

Adds Flt sparse attribute with id AttrId to NodeI.

Definition at line 3036 of file network.h.

                                                                              {
     return AddSAttrDatN(NodeI.GetId(), AttrId, Val);
   }

int TUndirNet::AddSAttrDatN	(	const TInt &	NId,
		const TStr &	AttrName,
		const TStr &	Val
	)

Adds Str sparse attribute with name AttrName to the given node with id NId.

Definition at line 1890 of file network.cpp.

                                                                                   {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.AddSAttrDat(NId, AttrName, Val);
 }

int TUndirNet::AddSAttrDatN	(	const TInt &	NId,
		const TInt &	AttrId,
		const TStr &	Val
	)

Adds Str sparse attribute with id AttrId to the given node with id NId.

Definition at line 1897 of file network.cpp.

                                                                                 {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.AddSAttrDat(NId, AttrId, Val);
 }

int TUndirNet::AddSAttrDatN	(	const TNodeI &	NodeI,
		const TStr &	AttrName,
		const TStr &	Val
	)

inline

Adds Str sparse attribute with name AttrName to NodeI.

Definition at line 3046 of file network.h.

                                                                                {
     return AddSAttrDatN(NodeI.GetId(), AttrName, Val);
   }

int TUndirNet::AddSAttrDatN	(	const TNodeI &	NodeI,
		const TInt &	AttrId,
		const TStr &	Val
	)

inline

Adds Str sparse attribute with id AttrId to NodeI.

Definition at line 3050 of file network.h.

                                                                              {
     return AddSAttrDatN(NodeI.GetId(), AttrId, Val);
   }

int TUndirNet::AddSAttrE	(	const TStr &	Name,
		const TAttrType &	AttrType,
		TInt &	AttrId
	)

Adds mapping for sparse attribute with name Name and type AttrType.

Definition at line 2124 of file network.cpp.

                                                                                   {
   return SAttrE.AddSAttr(Name, AttrType, AttrId);
 }

int TUndirNet::AddSAttrN	(	const TStr &	Name,
		const TAttrType &	AttrType,
		TInt &	AttrId
	)

Adds mapping for sparse attribute with name Name and type AttrType.

Definition at line 1976 of file network.cpp.

                                                                                   {
   return SAttrN.AddSAttr(Name, AttrType, AttrId);
 }

TEdgeI TUndirNet::BegEI ( ) const

inline

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

Definition at line 2963 of file network.h.

2963 { TNodeI NI = BegNI(); TEdgeI EI(NI, EndNI(), 0); if (GetNodes() != 0 && (NI.GetOutDeg()==0 || NI.GetId()>NI.GetOutNId(0))) { EI++; } return EI; }

TUndirNet::BegNI

TNodeI BegNI() const

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

Definition: network.h:2934

TUndirNet::EndNI

TNodeI EndNI() const

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

Definition: network.h:2936

TUndirNet::GetNodes

int GetNodes() const

Returns the number of nodes in the network.

Definition: network.h:2894

TNodeI TUndirNet::BegNI ( ) const

inline

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

Definition at line 2934 of file network.h.

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

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::BegI

TIter BegI() const

Definition: hash.h:171

void TUndirNet::Clr ( )

inline

Deletes all nodes and edges from the network.

Definition at line 2984 of file network.h.

2984 { MxNId=0; NEdges=0; NodeH.Clr(); SAttrN.Clr(); SAttrE.Clr(); }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

TUndirNet::MxNId

TInt MxNId

Definition: network.h:2853

TAttrPair::Clr

void Clr()

Clears the contents of the attribute map.

Definition: attr.h:114

TUndirNet::SAttrE

TAttrPair SAttrE

Definition: network.h:2857

TUndirNet::SAttrN

TAttr SAttrN

Definition: network.h:2856

THash::Clr

void Clr(const bool &DoDel=true, const int &NoDelLim=-1, const bool &ResetDat=true)

Definition: hash.h:319

TUndirNet::NEdges

TInt NEdges

Definition: network.h:2853

TAttr::Clr

void Clr()

Clears the contents of the attribute map.

Definition: attr.h:29

void TUndirNet::Defrag ( const bool & OnlyNodeLinks = false )

Defragments the network.

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 1792 of file network.cpp.

                                                 {
   for (int n = NodeH.FFirstKeyId(); NodeH.FNextKeyId(n); ) {
     NodeH[n].NIdV.Pack();
   }
   if (! OnlyNodeLinks && ! NodeH.IsKeyIdEqKeyN()) {
     NodeH.Defrag();
   }
 }

void TUndirNet::DelEdge	(	const int &	SrcNId,
		const int &	DstNId
	)

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

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 1753 of file network.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);
   TIntPr Id(SrcNId, DstNId);
   SAttrE.DelSAttrId(Id);
   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 TUndirNet::DelNode ( const int & NId )

Deletes node of ID NId from the network.

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

Definition at line 1715 of file network.cpp.

                                       {
   { AssertR(IsNode(NId), TStr::Fmt("NodeId %d does not exist", NId));
   TInt Id(NId);
   SAttrN.DelSAttrId(Id);
   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 TUndirNet::DelNode ( const TNode & NodeI )

inline

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

Definition at line 2930 of file network.h.

2930 { DelNode(NodeI.GetId()); }

TUndirNet::DelNode

void DelNode(const int &NId)

Deletes node of ID NId from the network.

Definition: network.cpp:1715

int TUndirNet::DelSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TStr &	AttrName
	)

Deletes sparse attribute with name AttrName from edge with ids SrcId and DstId.

Definition at line 2091 of file network.cpp.

                                                                                       {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.DelSAttrDat(EId, AttrName);
 }

int TUndirNet::DelSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TInt &	AttrId
	)

Deletes sparse attribute with id AttrId from edge with ids SrcId and DstId.

Definition at line 2099 of file network.cpp.

                                                                                     {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.DelSAttrDat(EId, AttrId);
 }

int TUndirNet::DelSAttrDatE	(	const TEdgeI &	EdgeI,
		const TStr &	AttrName
	)

inline

Deletes sparse attribute with name AttrName from EdgeI.

Definition at line 3220 of file network.h.

                                                               {
     return DelSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrName);
   }

int TUndirNet::DelSAttrDatE	(	const TEdgeI &	EdgeI,
		const TInt &	AttrId
	)

inline

Deletes sparse attribute with id AttrId from EdgeI.

Definition at line 3224 of file network.h.

                                                             {
     return DelSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrId);
   } 

int TUndirNet::DelSAttrDatN	(	const TInt &	NId,
		const TStr &	AttrName
	)

Deletes sparse attribute with name AttrName from node with id NId.

Definition at line 1946 of file network.cpp.

                                                                  {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.DelSAttrDat(NId, AttrName);
 }

int TUndirNet::DelSAttrDatN	(	const TInt &	NId,
		const TInt &	AttrId
	)

Deletes sparse attribute with id AttrId from node with id NId.

Definition at line 1953 of file network.cpp.

                                                                {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.DelSAttrDat(NId, AttrId);
 }

int TUndirNet::DelSAttrDatN	(	const TNodeI &	NodeI,
		const TStr &	AttrName
	)

inline

Deletes sparse attribute with name AttrName from NodeI.

Definition at line 3102 of file network.h.

                                                               {
     return DelSAttrDatN(NodeI.GetId(), AttrName);
   }

int TUndirNet::DelSAttrDatN	(	const TNodeI &	NodeI,
		const TInt &	AttrId
	)

inline

Deletes sparse attribute with id AttrId from NodeI.

Definition at line 3106 of file network.h.

                                                             {
     return DelSAttrDatN(NodeI.GetId(), AttrId);
   }

void TUndirNet::Dump ( FILE * OutF = stdout ) const

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

Definition at line 1839 of file network.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 TUndirNet::Empty ( ) const

inline

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

Definition at line 2982 of file network.h.

2982 { return GetNodes()==0; }

TUndirNet::GetNodes

int GetNodes() const

Returns the number of nodes in the network.

Definition: network.h:2894

TEdgeI TUndirNet::EndEI ( ) const

inline

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

Definition at line 2965 of file network.h.

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

TUndirNet::EndNI

TNodeI EndNI() const

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

Definition: network.h:2936

TNodeI TUndirNet::EndNI ( ) const

inline

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

Definition at line 2936 of file network.h.

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

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::EndI

TIter EndI() const

Definition: hash.h:176

int TUndirNet::GetEdges ( ) const

Returns the number of edges in the network.

Definition at line 1732 of file network.cpp.

                               {
   //int Edges = 0;
   //for (int N=NodeH.FFirstKeyId(); NodeH.FNextKeyId(N); ) {
   //  Edges += NodeH[N].GetDeg();
   //}
   //return Edges/2;
   return NEdges;
 }

TEdgeI TUndirNet::GetEI ( const int & EId ) const

Not supported/implemented!

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

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

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

Definition at line 1774 of file network.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 TUndirNet::GetIdVSAttrE	(	const TStr &	AttrName,
		TIntPrV &	IdV
	)		const

Gets a list of all edges that have a sparse attribute with name AttrName.

Definition at line 2116 of file network.cpp.

                                                                     {
   return SAttrE.GetIdVSAttr(AttrName, IdV);
 }

int TUndirNet::GetIdVSAttrE	(	const TInt &	AttrId,
		TIntPrV &	IdV
	)		const

Gets a list of all edges that have a sparse attribute with id AttrId.

Definition at line 2120 of file network.cpp.

                                                                   {
   return SAttrE.GetIdVSAttr(AttrId, IdV);
 }

int TUndirNet::GetIdVSAttrN	(	const TStr &	AttrName,
		TIntV &	IdV
	)		const

Gets a list of all nodes that have a sparse attribute with name AttrName.

Definition at line 1968 of file network.cpp.

                                                                   {
   return SAttrN.GetIdVSAttr(AttrName, IdV);
 }

int TUndirNet::GetIdVSAttrN	(	const TInt &	AttrId,
		TIntV &	IdV
	)		const

Gets a list of all nodes that have a sparse attribute with id AttrId.

Definition at line 1972 of file network.cpp.

                                                                 {
   return SAttrN.GetIdVSAttr(AttrId, IdV);
 }

int TUndirNet::GetMxNId ( ) const

inline

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

Definition at line 2940 of file network.h.

2940 { return MxNId; }

TUndirNet::MxNId

TInt MxNId

Definition: network.h:2853

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

inline

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

Definition at line 2938 of file network.h.

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

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::GetI

TIter GetI(const TKey &Key) const

Definition: hash.h:178

void TUndirNet::GetNIdV ( TIntV & NIdV ) const

Gets a vector IDs of all nodes in the network.

Definition at line 1785 of file network.cpp.

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

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

inlineprivate

Definition at line 2859 of file network.h.

2859 { return NodeH.GetDat(NId); }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:220

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

inlineprivate

Definition at line 2860 of file network.h.

2860 { return NodeH.GetDat(NId); }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::GetDat

const TDat & GetDat(const TKey &Key) const

Definition: hash.h:220

int TUndirNet::GetNodes ( ) const

inline

Returns the number of nodes in the network.

Definition at line 2894 of file network.h.

2894 { return NodeH.Len(); }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::Len

int Len() const

Definition: hash.h:186

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

inline

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

Definition at line 2977 of file network.h.

2977 { return GetNI(GetRndNId(Rnd)); }

TUndirNet::GetRndNId

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

Returns an ID of a random node in the network.

Definition: network.h:2975

TUndirNet::GetNI

TNodeI GetNI(const int &NId) const

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

Definition: network.h:2938

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

inline

Returns an ID of a random node in the network.

Definition at line 2975 of file network.h.

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

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::GetRndKeyId

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:402

THash::GetKey

const TKey & GetKey(const int &KeyId) const

Definition: hash.h:210

int TUndirNet::GetSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TStr &	AttrName,
		TInt &	ValX
	)		const

Gets Int sparse attribute with name AttrName from edge with ids SrcId and DstId.

Definition at line 2043 of file network.cpp.

                                                                                                        {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.GetSAttrDat(EId, AttrName, Val);
 }

int TUndirNet::GetSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TInt &	AttrId,
		TInt &	ValX
	)		const

Gets Int sparse attribute with id AttrId from edge with ids SrcId and DstId.

Definition at line 2051 of file network.cpp.

                                                                                                      {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.GetSAttrDat(EId, AttrId, Val);
 }

int TUndirNet::GetSAttrDatE	(	const TEdgeI &	EdgeI,
		const TStr &	AttrName,
		TInt &	ValX
	)		const

inline

Gets Int sparse attribute with name AttrName from EdgeI.

Definition at line 3178 of file network.h.

                                                                                 {
     return GetSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrName, ValX);
   }

int TUndirNet::GetSAttrDatE	(	const TEdgeI &	EdgeI,
		const TInt &	AttrId,
		TInt &	ValX
	)		const

inline

Gets Int sparse attribute with id AttrId from EdgeI.

Definition at line 3182 of file network.h.

                                                                               {
     return GetSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrId, ValX);
   } 

int TUndirNet::GetSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TStr &	AttrName,
		TFlt &	ValX
	)		const

Gets Flt sparse attribute with name AttrName from edge with ids SrcId and DstId.

Definition at line 2059 of file network.cpp.

                                                                                                        {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.GetSAttrDat(EId, AttrName, Val);
 }

int TUndirNet::GetSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TInt &	AttrId,
		TFlt &	ValX
	)		const

Gets Flt sparse attribute with id AttrId from edge with ids SrcId and DstId.

Definition at line 2067 of file network.cpp.

                                                                                                      {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.GetSAttrDat(EId, AttrId, Val);
 }

int TUndirNet::GetSAttrDatE	(	const TEdgeI &	EdgeI,
		const TStr &	AttrName,
		TFlt &	ValX
	)		const

inline

Gets Flt sparse attribute with name AttrName from EdgeI.

Definition at line 3192 of file network.h.

                                                                                 {
     return GetSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrName, ValX);
   }

int TUndirNet::GetSAttrDatE	(	const TEdgeI &	EdgeI,
		const TInt &	AttrId,
		TFlt &	ValX
	)		const

inline

Gets Flt sparse attribute with id AttrId from EdgeI.

Definition at line 3196 of file network.h.

                                                                               {
     return GetSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrId, ValX);
   } 

int TUndirNet::GetSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TStr &	AttrName,
		TStr &	ValX
	)		const

Gets Str sparse attribute with name AttrName from edge with ids SrcId and DstId.

Definition at line 2075 of file network.cpp.

                                                                                                        {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.GetSAttrDat(EId, AttrName, Val);
 }

int TUndirNet::GetSAttrDatE	(	const int &	SrcNId,
		const int &	DstNId,
		const TInt &	AttrId,
		TStr &	ValX
	)		const

Gets Str sparse attribute with id AttrId from edge with ids SrcId and DstId.

Definition at line 2083 of file network.cpp.

                                                                                                      {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   return SAttrE.GetSAttrDat(EId, AttrId, Val);
 }

int TUndirNet::GetSAttrDatE	(	const TEdgeI &	EdgeI,
		const TStr &	AttrName,
		TStr &	ValX
	)		const

inline

Gets Str sparse attribute with name AttrName from EdgeI.

Definition at line 3206 of file network.h.

                                                                                 {
     return GetSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrName, ValX);
   }

int TUndirNet::GetSAttrDatE	(	const TEdgeI &	EdgeI,
		const TInt &	AttrId,
		TStr &	ValX
	)		const

inline

Gets Str sparse attribute with id AttrId from EdgeI.

Definition at line 3210 of file network.h.

                                                                               {
     return GetSAttrDatE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrId, ValX);
   }

int TUndirNet::GetSAttrDatN	(	const TInt &	NId,
		const TStr &	AttrName,
		TInt &	ValX
	)		const

Gets Int sparse attribute with name AttrName from node with id NId.

Definition at line 1904 of file network.cpp.

                                                                                   {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.GetSAttrDat(NId, AttrName, Val);
 }

int TUndirNet::GetSAttrDatN	(	const TInt &	NId,
		const TInt &	AttrId,
		TInt &	ValX
	)		const

Gets Int sparse attribute with id AttrId from node with id NId.

Definition at line 1911 of file network.cpp.

                                                                                 {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.GetSAttrDat(NId, AttrId, Val);
 }

int TUndirNet::GetSAttrDatN	(	const TNodeI &	NodeI,
		const TStr &	AttrName,
		TInt &	ValX
	)		const

inline

Gets Int sparse attribute with name AttrName from NodeI.

Definition at line 3060 of file network.h.

                                                                                 {
     return GetSAttrDatN(NodeI.GetId(), AttrName, ValX);
   }

int TUndirNet::GetSAttrDatN	(	const TNodeI &	NodeI,
		const TInt &	AttrId,
		TInt &	ValX
	)		const

inline

Gets Int sparse attribute with id AttrId from NodeI.

Definition at line 3064 of file network.h.

                                                                               {
     return GetSAttrDatN(NodeI.GetId(), AttrId, ValX);
   }

int TUndirNet::GetSAttrDatN	(	const TInt &	NId,
		const TStr &	AttrName,
		TFlt &	ValX
	)		const

Gets Flt sparse attribute with name AttrName from node with id NId.

Definition at line 1918 of file network.cpp.

                                                                                   {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.GetSAttrDat(NId, AttrName, Val);
 }

int TUndirNet::GetSAttrDatN	(	const TInt &	NId,
		const TInt &	AttrId,
		TFlt &	ValX
	)		const

Gets Flt sparse attribute with id AttrId from node with id NId.

Definition at line 1925 of file network.cpp.

                                                                                 {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.GetSAttrDat(NId, AttrId, Val);
 }

int TUndirNet::GetSAttrDatN	(	const TNodeI &	NodeI,
		const TStr &	AttrName,
		TFlt &	ValX
	)		const

inline

Gets Flt sparse attribute with name AttrName from NodeI.

Definition at line 3074 of file network.h.

                                                                                 {
     return GetSAttrDatN(NodeI.GetId(), AttrName, ValX);
   } 

int TUndirNet::GetSAttrDatN	(	const TNodeI &	NodeI,
		const TInt &	AttrId,
		TFlt &	ValX
	)		const

inline

Gets Flt sparse attribute with id AttrId from NodeI.

Definition at line 3078 of file network.h.

                                                                               {
     return GetSAttrDatN(NodeI.GetId(), AttrId, ValX);
   }

int TUndirNet::GetSAttrDatN	(	const TInt &	NId,
		const TStr &	AttrName,
		TStr &	ValX
	)		const

Gets Str sparse attribute with name AttrName from node with id NId.

Definition at line 1932 of file network.cpp.

                                                                                   {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.GetSAttrDat(NId, AttrName, Val);
 }

int TUndirNet::GetSAttrDatN	(	const TInt &	NId,
		const TInt &	AttrId,
		TStr &	ValX
	)		const

Gets Str sparse attribute with id AttrId from node with id NId.

Definition at line 1939 of file network.cpp.

                                                                                 {
   if (!IsNode(NId)) {
     return -1;
   }
   return SAttrN.GetSAttrDat(NId, AttrId, Val);
 }

int TUndirNet::GetSAttrDatN	(	const TNodeI &	NodeI,
		const TStr &	AttrName,
		TStr &	ValX
	)		const

inline

Gets Str sparse attribute with name AttrName from NodeI.

Definition at line 3088 of file network.h.

                                                                                 {
     return GetSAttrDatN(NodeI.GetId(), AttrName, ValX);
   }

int TUndirNet::GetSAttrDatN	(	const TNodeI &	NodeI,
		const TInt &	AttrId,
		TStr &	ValX
	)		const

inline

Gets Str sparse attribute with id AttrId from NodeI.

Definition at line 3092 of file network.h.

                                                                               {
     return GetSAttrDatN(NodeI.GetId(), AttrId, ValX);
   }

int TUndirNet::GetSAttrIdE	(	const TStr &	Name,
		TInt &	AttrIdX,
		TAttrType &	AttrTypeX
	)		const

Gets id and type for attribute with name Name.

Definition at line 2128 of file network.cpp.

                                                                                     {
   return SAttrE.GetSAttrId(Name, AttrId, AttrType);
 }

int TUndirNet::GetSAttrIdN	(	const TStr &	Name,
		TInt &	AttrIdX,
		TAttrType &	AttrTypeX
	)		const

Gets id and type for attribute with name Name.

Definition at line 1980 of file network.cpp.

                                                                                     {
   return SAttrN.GetSAttrId(Name, AttrId, AttrType);
 }

int TUndirNet::GetSAttrNameE	(	const TInt &	AttrId,
		TStr &	NameX,
		TAttrType &	AttrTypeX
	)		const

Gets name and type for attribute with id AttrId.

Definition at line 2132 of file network.cpp.

                                                                                       {
   return SAttrE.GetSAttrName(AttrId, Name, AttrType);
 }

int TUndirNet::GetSAttrNameN	(	const TInt &	AttrId,
		TStr &	NameX,
		TAttrType &	AttrTypeX
	)		const

Gets name and type for attribute with id AttrId.

Definition at line 1984 of file network.cpp.

                                                                                       {
   return SAttrN.GetSAttrName(AttrId, Name, AttrType);
 }

int TUndirNet::GetSAttrVE	(	const int &	SrcNId,
		const int &	DstNId,
		const TAttrType	AttrType,
		TAttrPrV &	AttrV
	)		const

Gets a list of all sparse attributes of type AttrType for edge with ids SrcId and DstId.

Definition at line 2107 of file network.cpp.

                                                                                                                {
   if (!IsEdge(SrcNId, DstNId)) {
     return -1;
   }
   TIntPr EId = OrderEdgeNodes(SrcNId, DstNId);
   SAttrE.GetSAttrV(EId, AttrType, AttrV);
   return 0;
 }

int TUndirNet::GetSAttrVE	(	const TEdgeI &	EdgeI,
		const TAttrType	AttrType,
		TAttrPrV &	AttrV
	)		const

inline

Gets a list of all sparse attributes of type AttrType for EdgeI.

Definition at line 3230 of file network.h.

                                                                                        {
     return GetSAttrVE(EdgeI.GetSrcNId(), EdgeI.GetDstNId(), AttrType, AttrV);
   }

int TUndirNet::GetSAttrVN	(	const TInt &	NId,
		const TAttrType	AttrType,
		TAttrPrV &	AttrV
	)		const

Gets a list of all sparse attributes of type AttrType for node with id NId.

Definition at line 1960 of file network.cpp.

                                                                                           {
   if (!IsNode(NId)) {
     return -1;
   }
   SAttrN.GetSAttrV(NId, AttrType, AttrV);
   return 0;
 }

int TUndirNet::GetSAttrVN	(	const TNodeI &	NodeI,
		const TAttrType	AttrType,
		TAttrPrV &	AttrV
	)		const

inline

Gets a list of all sparse attributes of type AttrType for NodeI.

Definition at line 3113 of file network.h.

                                                                                        {
     return GetSAttrVN(NodeI.GetId(), AttrType, AttrV);
   }

PUndirNet TUndirNet::GetSmallGraph ( )

static

Returns a small network on 5 nodes and 5 edges.

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

Definition at line 1853 of file network.cpp.

                                    {
   PUndirNet Graph = TUndirNet::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 TUndirNet::HasFlag ( const TGraphFlag & Flag ) const

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

Definition at line 1659 of file network.cpp.

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

bool TUndirNet::IsEdge	(	const int &	SrcNId,
		const int &	DstNId
	)		const

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

Definition at line 1768 of file network.cpp.

                                                                  {
   if (! IsNode(SrcNId) || ! IsNode(DstNId)) return false;
   return GetNode(SrcNId).IsNbrNId(DstNId);
 }

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

inline

Tests whether ID NId is a node.

Definition at line 2932 of file network.h.

2932 { return NodeH.IsKey(NId); }

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

THash::IsKey

bool IsKey(const TKey &Key) const

Definition: hash.h:216

bool TUndirNet::IsOk ( const bool & ThrowExcept = true ) const

Checks the network data structure for internal consistency.

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

Definition at line 1802 of file network.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 PUndirNet TUndirNet::Load ( TSIn & SIn )

inlinestatic

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

Definition at line 2882 of file network.h.

2882 { return PUndirNet(new TUndirNet(SIn)); }

TUndirNet::TUndirNet

TUndirNet()

Definition: network.h:2863

PUndirNet

TPt< TUndirNet > PUndirNet

Pointer to an undirected network (TUndirNet)

Definition: network.h:2723

static PUndirNet TUndirNet::Load_V1 ( TSIn & SIn )

inlinestatic

Static constructor that loads the network from a stream SIn and returns a pointer to it. Backwards compatible.

Definition at line 2884 of file network.h.

                                       { PUndirNet Graph = PUndirNet(new TUndirNet());
     Graph->MxNId.Load(SIn); Graph->NEdges.Load(SIn); Graph->NodeH.Load(SIn); return Graph;
   }

static PUndirNet TUndirNet::New ( )

inlinestatic

Static constructor that returns a pointer to the network. Call: PUndirNet Graph = TUndirNet::New().

Definition at line 2876 of file network.h.

2876 { return new TUndirNet(); }

TUndirNet::TUndirNet

TUndirNet()

Definition: network.h:2863

static PUndirNet TUndirNet::New	(	const int &	Nodes,
		const int &	Edges
	)

inlinestatic

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

Call: PUndirNet Net = TUndirNet::New(Nodes, Edges).

Definition at line 2880 of file network.h.

2880 { return new TUndirNet(Nodes, Edges); }

TUndirNet::TUndirNet

TUndirNet()

Definition: network.h:2863

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

inline

Definition at line 2890 of file network.h.

2890 {

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

TUndirNet::NodeH

THash< TInt, TNode > NodeH

Definition: network.h:2854

TUndirNet::MxNId

TInt MxNId

Definition: network.h:2853

TUndirNet::NEdges

TInt NEdges

Definition: network.h:2853

TIntPr TUndirNet::OrderEdgeNodes	(	const int &	SrcNId,
		const int &	DstNId
	)		const

private

Definition at line 1988 of file network.cpp.

                                                                           {
   if (SrcNId < DstNId) {
     return TIntPr(SrcNId, DstNId);
   }
   return TIntPr(DstNId, SrcNId);
 }