GraphLab: Distributed Graph-Parallel API  2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
local_graph_ops.hpp
1 /**
2  * Copyright (c) 2009 Carnegie Mellon University.
3  * All rights reserved.
4  *
5  * Licensed under the Apache License, Version 2.0 (the "License");
6  * you may not use this file except in compliance with the License.
7  * You may obtain a copy of the License at
8  *
9  * http://www.apache.org/licenses/LICENSE-2.0
10  *
11  * Unless required by applicable law or agreed to in writing,
12  * software distributed under the License is distributed on an "AS
13  * IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
14  * express or implied. See the License for the specific language
15  * governing permissions and limitations under the License.
16  *
17  * For more about this software visit:
18  *
19  * http://www.graphlab.ml.cmu.edu
20  *
21  */
22 
23 
24 /**
25  * \file graph_ops.hpp
26  *
27  * This file supports basic graph io operations to simplify reading
28  * and writing adjacency structures from files.
29  *
30  */
31 
32 #ifndef GRAPHLAB_LOCAL_GRAPH_OPS_HPP
33 #define GRAPHLAB_LOCAL_GRAPH_OPS_HPP
34 
35 
36 
37 #include <iostream>
38 #include <fstream>
39 #include <string>
40 
41 #include <boost/algorithm/string/predicate.hpp>
42 #include <graphlab/graph/local_graph.hpp>
43 
44 #include <graphlab/macros_def.hpp>
45 namespace graphlab {
46 
47 
48  namespace local_graph_ops {
49 
50 
51  /**
52  * builds a topological_sort of the graph returning it in topsort.
53  *
54  * \param[out] topsort Resultant topological sort of the graph vertices.
55  *
56  * function will return false if graph is not acyclic.
57  */
58  template <typename VertexType, typename EdgeType>
59  bool topological_sort(const graphlab::local_graph<VertexType, EdgeType>& graph,
60  std::vector<vertex_id_type>& topsort) {
61  typedef graphlab::local_graph<VertexType, EdgeType> graph_type;
62  topsort.clear();
63  topsort.reserve(graph.num_vertices());
64  std::vector<size_t> indeg;
65  indeg.resize(graph.num_vertices());
66  std::queue<vertex_id_type> q;
67  for (size_t i = 0;i < graph.num_vertices(); ++i) {
68  indeg[i] = graph.get_in_edges(i).size();
69  if (indeg[i] == 0) {
70  q.push(i);
71  }
72  }
73 
74  while (!q.empty()) {
75  vertex_id_type v = q.front();
76  q.pop();
77  topsort.push_back(v);
78  foreach(typename graph_type::edge_type edge, graph.get_out_edges(v)) {
79  vertex_id_type destv = edge.target();
80  --indeg[destv];
81  if (indeg[destv] == 0) {
82  q.push(destv);
83  }
84  }
85  }
86  if (q.empty() && topsort.size() != graph.num_vertices()) {
87  return false;
88  }
89  return true;
90  } // end of topological sort
91 
92 
93  template <typename VertexType, typename EdgeType>
94  size_t num_neighbors(const graphlab::local_graph<VertexType, EdgeType>& graph,
95  vertex_id_type& vid) {
96  typedef graphlab::local_graph<VertexType, EdgeType> graph_type;
97  typename graph_type::edge_list_type in_edges = graph.in_edges(vid);
98  typename graph_type::edge_list_type out_edges = graph.out_edges(vid);
99  typename graph_type::edge_list_type::const_iterator i = in_edges.begin();
100  typename graph_type::edge_list_type::const_iterator j = out_edges.begin();
101  size_t count = 0;
102  for( ; i != in_edges.end() && j != out_edges.end(); ++count) {
103  if(i->source() == j->target()) {
104  ++i; ++j;
105  } else if(i->source() < j->target()) {
106  ++i;
107  } else {
108  ++j;
109  }
110  }
111  for( ; i != in_edges.end(); ++i, ++count);
112  for( ; j != out_edges.end(); ++j, ++count);
113  return count;
114  } // end of num_neighbors
115 
116 
117 
118  template <typename VertexType, typename EdgeType>
119  void neighbors(const graphlab::local_graph<VertexType, EdgeType>& graph,
120  const vertex_id_type vid,
121  std::vector<vertex_id_type>& neighbors ) {
122  typedef graphlab::local_graph<VertexType, EdgeType> graph_type;
123  typename graph_type::edge_list_type in_edges = graph.in_edges(vid);
124  typename graph_type::edge_list_type out_edges = graph.out_edges(vid);
125  typename graph_type::edge_list_type::const_iterator i = in_edges.begin();
126  typename graph_type::edge_list_type::const_iterator j = out_edges.begin();
127  while(i != in_edges.end() && j != out_edges.end()) {
128  if(i->source() == j->target()) {
129  neighbors.push_back(i->source());
130  ++i; ++j;
131  } else if(i->source() < j->target()) {
132  neighbors.push_back(i->source());
133  ++i;
134  } else {
135  neighbors.push_back(j->target());
136  ++j;
137  }
138  }
139  for( ; i != in_edges.end(); ++i) neighbors.push_back(i->source());
140  for( ; j != out_edges.end(); ++j) neighbors.push_back(j->target());
141  } // end of neighbors
142 
143 
144 
145 
146 
147 
148 
149 
150  template <typename VertexType, typename EdgeType>
151  bool save_metis_structure(const std::string& filename,
152  const graphlab::local_graph<VertexType, EdgeType>& graph) {
153  typedef graphlab::local_graph<VertexType, EdgeType> graph_type;
154  typedef typename graph_type::edge_type edge_type;
155  typedef typename graph_type::edge_list_type edge_list_type;
156 
157  std::ofstream fout(filename.c_str());
158  if(!fout.good()) return false;
159  // Count the number of actual edges
160  size_t nedges = 0;
161  for(vertex_id_type i = 0; i < graph.num_vertices(); ++i)
162  nedges += num_neighbors(graph, i);
163  fout << graph.num_vertices() << ' ' << (nedges/2) << '\n';
164  // Save the adjacency structure
165  std::vector<vertex_id_type> neighbor_set;
166  for(vertex_id_type i = 0; i < graph.num_vertices(); ++i) {
167  neighbors(graph, i, neighbor_set);
168  for(size_t j = 0; j < neighbor_set.size(); ++j) {
169  fout << (neighbor_set[j] + 1);
170  if(j + 1 < neighbor_set.size()) fout << ' ';
171  }
172  fout << '\n';
173  }
174  fout.close();
175  return true;
176  } // end of save metis
177 
178 
179 
180 
181 
182  template <typename VertexType, typename EdgeType>
183  bool save_edge_list_structure(const std::string& filename,
184  const graphlab::local_graph<VertexType, EdgeType>& graph) {
185  typedef graphlab::local_graph<VertexType, EdgeType> graph_type;
186  typedef typename graph_type::edge_type edge_type;
187  typedef typename graph_type::edge_list_type edge_list_type;
188 
189  std::ofstream fout(filename.c_str());
190  if(!fout.good()) return false;
191  for(vertex_id_type i = 0; i < graph.num_vertices(); ++i)
192  foreach(edge_type edge, graph.out_edges(i))
193  fout << edge.source() << '\t' << edge.target() << '\n';
194  fout.close();
195  return true;
196  } // end of save metis
197 
198 
199 
200 
201  template <typename VertexType, typename EdgeType>
202  bool save_zoltan_hypergraph_structure(const std::string& filename,
203  const graphlab::local_graph<VertexType, EdgeType>& graph) {
204  typedef graphlab::local_graph<VertexType, EdgeType> graph_type;
205  typedef typename graph_type::edge_type edge_type;
206  typedef typename graph_type::edge_list_type edge_list_type;
207 
208  std::ofstream fout(filename.c_str());
209  if(!fout.good()) return false;
210 
211  // ok. I need to uniquely number each edge.
212  // how?
213  boost::unordered_map<std::pair<vertex_id_type,
214  vertex_id_type>, size_t> edgetoid;
215  size_t curid = 0;
216  for(vertex_id_type i = 0; i < graph.num_vertices(); ++i) {
217  foreach(const typename graph_type::edge_type& edge, graph.in_edges(i)) {
218  std::pair<vertex_id_type, vertex_id_type> e =
219  std::make_pair(edge.source(), edge.target());
220  if (e.first > e.second) std::swap(e.first, e.second);
221  if (edgetoid.find(e) == edgetoid.end()) {
222  edgetoid[e] = curid;
223  ++curid;
224  }
225  }
226  foreach(const typename graph_type::edge_type& edge, graph.out_edges(i)) {
227  std::pair<vertex_id_type, vertex_id_type> e =
228  std::make_pair(edge.source(), edge.target());
229  if (e.first > e.second) std::swap(e.first, e.second);
230  if (edgetoid.find(e) == edgetoid.end()) {
231  edgetoid[e] = curid;
232  ++curid;
233  }
234  }
235  }
236 
237  size_t numedges = curid;
238  // each edge is a vertex, each vertex is an edge
239  // a pin is total adjacency of a hyper edge
240  fout << numedges << "\n\n";
241  for (size_t i = 0;i < numedges; ++i) {
242  fout << i+1 << "\n";
243  }
244  fout << "\n";
245  fout << graph.num_vertices() << "\n\n";
246 
247  fout << numedges * 2 << "\n\n";
248  // loop over the "hyperedge" and write out the edges it is adjacent to
249  for(vertex_id_type i = 0; i < graph.num_vertices(); ++i) {
250  boost::unordered_set<size_t> adjedges;
251  foreach(const typename graph_type::edge_type& edge, graph.in_edges(i)) {
252  std::pair<vertex_id_type, vertex_id_type> e =
253  std::make_pair(edge.source(), edge.target());
254  if (e.first > e.second) std::swap(e.first, e.second);
255  adjedges.insert(edgetoid[e]);
256  }
257  foreach(const typename graph_type::edge_type& edge, graph.out_edges(i)) {
258  std::pair<vertex_id_type, vertex_id_type> e =
259  std::make_pair(edge.source(), edge.target());
260  if (e.first > e.second) std::swap(e.first, e.second);
261  adjedges.insert(edgetoid[e]);
262  }
263  // write
264  std::vector<size_t> adjedgesvec;
265  std::copy(adjedges.begin(), adjedges.end(),
266  std::inserter(adjedgesvec, adjedgesvec.end()));
267  fout << i+1 << " " << adjedgesvec.size() << "\t";
268  for (size_t j = 0;j < adjedgesvec.size(); ++j) {
269  fout << adjedgesvec[j] + 1;
270  if (j < adjedgesvec.size() - 1) fout << "\t";
271  }
272  fout << "\n";
273  }
274  fout.close();
275  return true;
276  } // end of save_zoltan_hypergraph_structure
277 
278 
279 
280  }; // end of graph ops
281 }; // end of namespace graphlab
282 #include <graphlab/macros_undef.hpp>
283 
284 #endif
285 
286 
287 
288 
289