32 #ifndef GRAPHLAB_LOCAL_GRAPH_OPS_HPP
33 #define GRAPHLAB_LOCAL_GRAPH_OPS_HPP
41 #include <boost/algorithm/string/predicate.hpp>
42 #include <graphlab/graph/local_graph.hpp>
44 #include <graphlab/macros_def.hpp>
48 namespace local_graph_ops {
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;
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();
81 if (indeg[destv] == 0) {
86 if (q.empty() && topsort.size() != graph.num_vertices()) {
93 template <
typename VertexType,
typename EdgeType>
94 size_t num_neighbors(
const graphlab::local_graph<VertexType, EdgeType>& graph,
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();
102 for( ; i != in_edges.end() && j != out_edges.end(); ++count) {
103 if(i->source() == j->target()) {
105 }
else if(i->source() < j->target()) {
111 for( ; i != in_edges.end(); ++i, ++count);
112 for( ; j != out_edges.end(); ++j, ++count);
118 template <
typename VertexType,
typename EdgeType>
119 void neighbors(
const graphlab::local_graph<VertexType, EdgeType>& graph,
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());
131 }
else if(i->source() < j->target()) {
132 neighbors.push_back(i->source());
135 neighbors.push_back(j->target());
139 for( ; i != in_edges.end(); ++i) neighbors.push_back(i->source());
140 for( ; j != out_edges.end(); ++j) neighbors.push_back(j->target());
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;
155 typedef typename graph_type::edge_list_type edge_list_type;
157 std::ofstream fout(filename.c_str());
158 if(!fout.good())
return false;
162 nedges += num_neighbors(graph, i);
163 fout << graph.num_vertices() <<
' ' << (nedges/2) <<
'\n';
165 std::vector<vertex_id_type> neighbor_set;
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 <<
' ';
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;
187 typedef typename graph_type::edge_list_type edge_list_type;
189 std::ofstream fout(filename.c_str());
190 if(!fout.good())
return false;
192 foreach(edge_type edge, graph.out_edges(i))
193 fout << edge.
source() <<
'\t' << edge.target() <<
'\n';
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;
206 typedef typename graph_type::edge_list_type edge_list_type;
208 std::ofstream fout(filename.c_str());
209 if(!fout.good())
return false;
214 vertex_id_type>,
size_t> edgetoid;
216 for(vertex_id_type i = 0; i < graph.num_vertices(); ++i) {
218 std::pair<vertex_id_type, vertex_id_type> e =
220 if (e.first > e.second) std::swap(e.first, e.second);
221 if (edgetoid.find(e) == edgetoid.end()) {
227 std::pair<vertex_id_type, vertex_id_type> e =
229 if (e.first > e.second) std::swap(e.first, e.second);
230 if (edgetoid.find(e) == edgetoid.end()) {
237 size_t numedges = curid;
240 fout << numedges <<
"\n\n";
241 for (
size_t i = 0;i < numedges; ++i) {
245 fout << graph.num_vertices() <<
"\n\n";
247 fout << numedges * 2 <<
"\n\n";
249 for(vertex_id_type i = 0; i < graph.num_vertices(); ++i) {
250 boost::unordered_set<size_t> adjedges;
252 std::pair<vertex_id_type, vertex_id_type> e =
254 if (e.first > e.second) std::swap(e.first, e.second);
255 adjedges.insert(edgetoid[e]);
258 std::pair<vertex_id_type, vertex_id_type> e =
260 if (e.first > e.second) std::swap(e.first, e.second);
261 adjedges.insert(edgetoid[e]);
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";
282 #include <graphlab/macros_undef.hpp>