NCBI C++ ToolKit
convert_graph.cpp
Go to the documentation of this file.

Go to the SVN repository for this file.

1 /* $Id: convert_graph.cpp 14666 2007-07-09 13:40:22Z dicuccio $
2  * ===========================================================================
3  *
4  * PUBLIC DOMAIN NOTICE
5  * National Center for Biotechnology Information
6  *
7  * This software/database is a "United States Government Work" under the
8  * terms of the United States Copyright Act. It was written as part of
9  * the author's official duties as a United States Government employee and
10  * thus cannot be copyrighted. This software/database is freely available
11  * to the public for use. The National Library of Medicine and the U.S.
12  * Government have not placed any restriction on its use or reproduction.
13  *
14  * Although all reasonable efforts have been taken to ensure the accuracy
15  * and reliability of the software and data, the NLM and the U.S.
16  * Government do not and cannot warrant the performance or results that
17  * may be obtained by using this software or data. The NLM and the U.S.
18  * Government disclaim all warranties, express or implied, including
19  * warranties of performance, merchantability or fitness for any particular
20  * purpose.
21  *
22  * Please cite the author in any work or product based on this material.
23  *
24  * ===========================================================================
25  *
26  * Authors: Roman Katargin
27  *
28  * File Description:
29  *
30  */
31 
32 #include <ncbi_pch.hpp>
33 #include "convert_graph.hpp"
34 #include <algorithm>
35 
37 
38 size_t CConvGraph::add_edge(size_t fromVertex, size_t toVertex)
39 {
40  m_Edges.push_back(make_pair(fromVertex, toVertex));
41  return m_Edges.size() - 1;
42 }
43 
44 void CConvGraph::Dump(ostream& ostream) const
45 {
46  ostream << "Edges: " << endl;
47  ITERATE(vector<TEdge>, iter, m_Edges)
48  ostream << iter->first << " --> " << iter->second << endl;
49 }
50 
51 void CConvGraph::DumpPath(const TPath& path, ostream& ostream) const
52 {
53  for (size_t i = 0; i < path.size(); ++i) {
54  if (path[i] >= m_Edges.size()) {
55  ostream << " XXX ";
56  }
57  else {
58  if (i > 0) {
59  size_t prev_edge = path[i - 1];
60  if (prev_edge >= m_Edges.size() ||
61  m_Edges[prev_edge].second != m_Edges[i].first) {
62  ostream << " | " << m_Edges[i].first;
63  }
64  }
65  else
66  ostream << m_Edges[i].first;
67 
68  ostream << " --> " << m_Edges[i].second;
69  }
70  }
71 
72  ostream << endl;
73 }
74 
75 class DFS
76 {
77 public:
78  DFS (const vector<CConvGraph::TEdge>& edges,
79  size_t startVertex,
80  size_t endVertex,
81  vector<CConvGraph::TPath>& paths);
82 
83 private:
84  enum Color { WHITE, GRAY, BLACK };
85  typedef vector<size_t> TTypeAjacentList;
86 
87  void process_vertex(size_t vertex);
88 
89  const vector<CConvGraph::TEdge>& m_Edges;
90  vector<CConvGraph::TPath>& m_Paths;
91 
92  vector<TTypeAjacentList> m_AjacentVertices;
93 
95  vector<Color> m_Colors;
96  size_t m_EndVertex;
97 };
98 
99 static bool PCompare(const CConvGraph::TPath& p1, const CConvGraph::TPath& p2)
100  { return p1.size() < p2.size(); }
101 
102 void CConvGraph::FindPaths (size_t startVertex,
103  size_t endVertex,
104  vector<TPath>& paths) const
105 {
106  DFS(m_Edges, startVertex, endVertex, paths);
107  sort(paths.begin(), paths.end(), PCompare);
108 }
109 
110 DFS::DFS (const vector<CConvGraph::TEdge>& edges,
111  size_t startVertex,
112  size_t endVertex,
113  vector<CConvGraph::TPath>& paths) :
114  m_Edges(edges), m_Paths(paths), m_EndVertex(endVertex)
115 {
116  size_t size = 0;
117  ITERATE(vector<CConvGraph::TEdge>, iter, m_Edges)
118  size = max(size, 1 + max(iter->first, iter->second));
119 
120  if (startVertex >= size || endVertex >= size || startVertex == endVertex)
121  return;
122 
123  m_AjacentVertices.clear();
124  m_AjacentVertices.resize(size);
125 
126  size_t idx = 0;
127  ITERATE(vector<CConvGraph::TEdge>, iter, m_Edges)
128  m_AjacentVertices[iter->first].push_back(idx++);
129 
130  m_Queue.clear();
131  m_Colors.assign(size, WHITE);
132  process_vertex (startVertex);
133 }
134 
135 void DFS::process_vertex(size_t vertex)
136 {
137  if (vertex == m_EndVertex) {
138  m_Paths.push_back(m_Queue);
139  return;
140  }
141  else {
142  m_Colors[vertex] = GRAY;
143  ITERATE (TTypeAjacentList, iter, m_AjacentVertices[vertex]) {
144  size_t v2 = m_Edges[*iter].second;
145  if (m_Colors[v2] == WHITE || m_Colors[v2] == BLACK) {
146  m_Queue.push_back(*iter);
148  m_Queue.pop_back();
149  }
150  }
151  m_Colors[vertex] = BLACK;
152  }
153 }
154 
155 
vector< size_t > TPath
friend class DFS
void Dump(ostream &ostream) const
void DumpPath(const TPath &path, ostream &ostream) const
vector< TEdge > m_Edges
void FindPaths(size_t startVertex, size_t endVertex, vector< TPath > &paths) const
size_t add_edge(size_t from, size_t to)
Definition: svg.hpp:122
const vector< CConvGraph::TEdge > & m_Edges
void process_vertex(size_t vertex)
vector< CConvGraph::TPath > & m_Paths
vector< TTypeAjacentList > m_AjacentVertices
vector< Color > m_Colors
size_t m_EndVertex
vector< size_t > TTypeAjacentList
DFS(const vector< CConvGraph::TEdge > &edges, size_t startVertex, size_t endVertex, vector< CConvGraph::TPath > &paths)
CConvGraph::TPath m_Queue
static bool PCompare(const CConvGraph::TPath &p1, const CConvGraph::TPath &p2)
#define ITERATE(Type, Var, Cont)
ITERATE macro to sequence through container elements.
Definition: ncbimisc.hpp:815
const CVect2< U > & v2
Definition: globals.hpp:440
#define END_NCBI_SCOPE
End previously defined NCBI scope.
Definition: ncbistl.hpp:103
#define BEGIN_NCBI_SCOPE
Define ncbi namespace.
Definition: ncbistl.hpp:100
int i
constexpr auto sort(_Init &&init)
const struct ncbi::grid::netcache::search::fields::SIZE size
T max(T x_, T y_)
Modified on Fri Dec 01 04:48:10 2023 by modify_doxy.py rev. 669887