NCBI C++ ToolKit
links.hpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 #ifndef ALGO_COBALT___LINKS__HPP
2 #define ALGO_COBALT___LINKS__HPP
3 
4 /* $Id: links.hpp 62914 2014-05-15 18:31:47Z ucko $
5 * ===========================================================================
6 *
7 * PUBLIC DOMAIN NOTICE
8 * National Center for Biotechnology Information
9 *
10 * This software/database is a "United States Government Work" under the
11 * terms of the United States Copyright Act. It was written as part of
12 * the author's offical duties as a United States Government employee and
13 * thus cannot be copyrighted. This software/database is freely available
14 * to the public for use. The National Library of Medicine and the U.S.
15 * Government have not placed any restriction on its use or reproduction.
16 *
17 * Although all reasonable efforts have been taken to ensure the accuracy
18 * and reliability of the software and data, the NLM and the U.S.
19 * Government do not and cannot warrant the performance or results that
20 * may be obtained by using this software or data. The NLM and the U.S.
21 * Government disclaim all warranties, express or implied, including
22 * warranties of performance, merchantability or fitness for any particular
23 * purpose.
24 *
25 * Please cite the author in any work or product based on this material.
26 *
27 * ===========================================================================*/
28 
29 /*****************************************************************************
30 
31 File name: links.hpp
32 
33 Author: Greg Boratyn
34 
35 Contents: Interface for CLinks class: Distance matrix represented as a graph
36 
37 ******************************************************************************/
38 
39 /// @file links.hpp
40 
41 #include <corelib/ncbiobj.hpp>
43 #include <list>
44 
45 
47 BEGIN_SCOPE(cobalt)
48 
49 
50 /// Set of edges with weights between nodes represented by zero-based positive
51 /// integers
53 {
54 public:
55 
56  /// Single link
57  struct SLink {
58  int first; ///< Node
59  int second; ///< Node
60  double weight; ///< Edge weight
61 
62  /// Constructor
63  SLink(int f, int s, double w) : first(f), second(s), weight(w) {}
64 
65  /// Less then operator for sorting links by weights
66  bool operator<(const SLink& link) const {return weight < link.weight;}
67  };
68 
69  typedef list<SLink>::const_iterator SLink_CI;
70 
71 public:
72 
73  /// Constructor
74  /// @param num_elements Number of nodes (not necessary connected) [in]
75  /// [in] table
76  ///
77  CLinks(Uint4 num_elements)
78  : m_NumElements(num_elements),
79  m_IsSorted(false),
80  m_MaxWeight(0.0)
81  {}
82 
83  /// Destructor
84  ~CLinks();
85 
86  /// Add link
87  /// @param first Node number [in]
88  /// @param second Node number [in]
89  /// @param weight Link weight [in]
90  ///
91  /// The links are assumed to be undirected. All nodes are stored such that
92  /// first < second, if the inputs are different the nodes will be swaped.
93  /// The method does not check whether given link already exists. Adding
94  /// two links between the same nodes may cause unexpected results.
95  void AddLink(int first, int second, double weight);
96 
97  /// Check if link exists between given two nodes
98  /// @param first Node number [in]
99  /// @param second Node number [in]
100  /// @return True if link exists, false otherwise
101  ///
102  /// The link is checked by doing binary search in sorted list of links
103  bool IsLink(int first, int second) const;
104 
105  /// Check if links exist between all pairs of elemens from two sets.
106  /// Existence of links whithin the sets is not checked.
107  /// @param first List of elements for the first set [in]
108  /// @param second List of elements for the second set [in]
109  /// @param dist Average distance between elements of the two sets [out]
110  /// @return true if links between all pairs exist, false otherwise
111  ///
112  /// The existance of a link is checked by doing binary search in sorted
113  /// list of links
114  bool IsLink(const vector<int>& first, const vector<int>& second,
115  double& dist) const;
116 
117  /// Check whether the links are sorted according to weights
118  /// @return True if links are sorted, false otherwise
119  ///
120  bool IsSorted(void) const {return m_IsSorted;}
121 
122  /// Sort links according to weights in ascending order
123  ///
124  void Sort(void);
125 
126  /// Get number of nodes
127  /// @return Number of nodes
128  ///
129  Uint4 GetNumElements(void) const {return m_NumElements;}
130 
131  /// Get number of links
132  /// @return Number of links
133  ///
134  Uint4 GetNumLinks(void) const {return m_NumLinks;}
135 
136  /// Get maximum weight over all links
137  /// @return Maxium weight
138  ///
139  double GetMaxWeight(void) const {return m_MaxWeight;}
140 
141  /// Get iterator pointing to the first link
142  /// @return Link iterator
143  ///
144  SLink_CI begin(void) const {return m_Links.begin();}
145 
146  /// Get iterator pointing behind the last link
147  /// @return Link iterator
148  ///
149  SLink_CI end(void) const {return m_Links.end();}
150 
151 private:
152  /// Forbid copy constructor
153  CLinks(const CLinks& links);
154 
155  /// Forbid assignment operator
156  CLinks& operator=(const CLinks& links);
157 
158  /// Initialize secondary list of link pointers
159  void x_InitLinkPtrs(void);
160 
161  /// Check if link exists by searching list of link pointers sorted by
162  /// node indexes
163  /// @param first Node number [in]
164  /// @param second Node number [in]
165  /// @return True if link exists, false otherwise
166  bool x_IsLinkPtr(int first, int second) const;
167 
168  /// Get link by node ids
169  /// @param first First node
170  /// @param second Second node
171  /// @return Pointer to the link or NULL if link does not exist
172  const CLinks::SLink* x_GetLink(int first, int second) const;
173 
174 protected:
175 
176  /// Links
177  list<SLink> m_Links;
178 
179  /// Pointers to links in m_Links sorted according to node indexes;
180  /// used for checks whether a link exists
181  vector<SLink*> m_LinkPtrs;
182 
183  /// Number of nodes
185 
186  /// Number of links
188 
189  /// Is list of links sorted
191 
192  /// Maximym weight in the list
193  double m_MaxWeight;
194 };
195 
196 
197 /// Exceptions for CLinks class
199 {
200 public:
201 
202  /// Error codes
203  enum EErrCode {
205  eInvalidNode, ///< Invalid node index
207 
208  };
209 
211 };
212 
213 
214 END_SCOPE(cobalt)
216 
217 #endif // ALGO_COBALT___LINKS__HPP
Exceptions for CLinks class.
Definition: links.hpp:199
EErrCode
Error codes.
Definition: links.hpp:203
@ eInvalidNode
Invalid node index.
Definition: links.hpp:205
NCBI_EXCEPTION_DEFAULT(CLinksException, CException)
CObject –.
Definition: ncbiobj.hpp:180
#define false
Definition: bool.h:36
static DLIST_TYPE *DLIST_NAME() first(DLIST_LIST_TYPE *list)
Definition: dlist.tmpl.h:46
static FILE * f
Definition: readconf.c:23
uint32_t Uint4
4-byte (32-bit) unsigned integer
Definition: ncbitype.h:103
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define END_SCOPE(ns)
End the previously defined scope.
Definition: ncbistl.hpp:75
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
#define BEGIN_SCOPE(ns)
Define a new scope.
Definition: ncbistl.hpp:72
#define NCBI_COBALT_EXPORT
Definition: ncbi_export.h:977
n font weight
Compressed bitset (entry point to bm.h)
Portable reference counted smart and weak pointers using CWeakRef, CRef, CObject and CObjectEx.
Modified on Fri Sep 20 14:57:25 2024 by modify_doxy.py rev. 669887