KrisLibrary  1.0.0
Operations.h
1 #ifndef GRAPH_OPERATIONS_H
2 #define GRAPH_OPERATIONS_H
3 
4 #include "Graph.h"
5 #include <KrisLibrary/errors.h>
6 #include <vector>
7 #include <set>
8 #include <map>
9 
10 namespace Graph {
11 
13 template <class N1,class E1,class N2,class E2>
15 {
16  G2.Cleanup();
17  G2.Resize(G1.nodes.size());
18  for(size_t i=0;i<G1.nodes.size();i++) {
20  for(G1.Begin(i,e);!e.end();e++) {
21  G2.AddEdge(i,e.target());
22  }
23  }
24 }
25 
31 template <class N1,class E,class N2,class F>
32 void Transform(const Graph<N1,E>& G1,F f,Graph<N2,E>& G2)
33 {
34  G2.Cleanup();
35  G2.Resize(G1.nodes.size());
36  for(size_t i=0;i<G1.nodes.size();i++)
37  f(G1.nodes[i],G2.nodes[i]);
38  for(size_t i=0;i<G1.nodes.size();i++) {
40  for(G1.Begin(i,e);!e.end();e++) {
41  G2.AddEdge(i,e.target(),*e);
42  }
43  }
44 }
45 
51 template <class N1,class E1,class N2,class E2,class F,class G>
52 void Transform(const Graph<N1,E1>& G1,F f,G g,Graph<N2,E2>& G2)
53 {
54  G2.Cleanup();
55  G2.Resize(G1.nodes.size());
56  for(size_t i=0;i<G1.nodes.size();i++)
57  f(G1.nodes[i],G2.nodes[i]);
58  E2 temp;
59  for(size_t i=0;i<G1.nodes.size();i++) {
61  for(G1.Begin(i,e);!e.end();e++) {
62  g(*e,temp);
63  G2.AddEdge(i,e.target(),temp);
64  }
65  }
66 }
67 
69 template <class Node,class Edge>
70 void GetEdges(const Graph<Node,Edge>& G, std::vector<std::pair<int,int> >& edges)
71 {
72  edges.resize(G.NumEdges());
73  int k=0;
74  for(size_t i=0;i<G.nodes.size();i++) {
76  for(G.Begin(i,e);!e.end();e++) {
77  edges[k].first = i;
78  edges[k].second = e.target();
79  k++;
80  }
81  }
82 }
83 
88 template <class Node,class Edge>
90  const std::vector<int>& nodes,
92 {
93  //sanity check
94  for(size_t i=0;i<nodes.size();i++) {
95  Assert(0 <= nodes[i] && nodes[i] < (int)G.nodes.size());
96  if(i!=0)
97  Assert(nodes[i-1] < nodes[i]);
98  }
99 
100  //inverse node map
101  std::vector<int> nodeMap(G.nodes.size(),-1);
102  for(size_t i=0;i<nodes.size();i++)
103  nodeMap[nodes[i]]=(int)i;
104 
105  //copy nodes
106  S.Resize(nodes.size());
107  for(size_t i=0;i<nodes.size();i++)
108  S.nodes[i] = G.nodes[nodes[i]];
109 
110  //copy edges
111  for(size_t i=0;i<nodes.size();i++) {
112  S.edges[i].clear();
113  S.co_edges[i].clear();
114  }
115  S.edgeData.clear();
116  for(size_t i=0;i<nodes.size();i++) {
118  for(G.Begin(nodes[i],e);!e.end();e++) {
119  if(nodeMap[e.target()] != -1) {
120  S.AddEdge(i,nodeMap[e.target()],*e);
121  }
122  }
123  }
124 }
125 
128 template <class Node,class Edge>
130  int nmin,int nmax,
131  Graph<Node,Edge>& S)
132 {
133  Assert(nmin >= 0 && nmax <= (int)G.nodes.size());
134  Assert(nmax >= 0);
135 
136  //copy nodes
137  S.Resize(nmax-nmin);
138  for(int i=nmin;i<nmax;i++)
139  S.nodes[i-nmin] = G.nodes[i];
140 
141  //copy edges
142  for(int i=0;i<nmax-nmin;i++) {
143  S.edges[i].clear();
144  S.co_edges[i].clear();
145  }
146  S.edgeData.clear();
147  for(int i=nmin;i<nmax;i++) {
149  for(G.Begin(i,e);!e.end();e++) {
150  if(e.target() >= nmin && e.target() < nmax) {
151  S.AddEdge(i-nmin,e.target()-nmin,*e);
152  }
153  }
154  }
155 }
156 
159 template <class Node,class Edge>
161  Graph<std::pair<int,int>,int>& D)
162 {
163  D.Resize(G.NumEdges());
164  std::map<std::pair<int,int>,int> edgeMap;
165  int k=0;
166  for(size_t i=0;i<G.nodes.size();i++) {
168  for(G.Begin(i,e);!e.end();e++) {
169  D.nodes[k].first = i;
170  D.nodes[k].second = e.target();
171  edgeMap[D.nodes[k]] = k;
172  k++;
173  }
174  }
175 
176  for(size_t i=0;i<G.nodes.size();i++) {
178  for(G.Begin(i,e);!e.end();e++) {
179  std::pair<int,int> source(i,e.target());
180  int sourceIndex = edgeMap[source];
181  int vertex=e.target();
183  for(G.Begin(vertex,e2);!e2.end();e2++) {
184  std::pair<int,int> target(vertex,e2.target());
185  Assert(edgeMap.count(target)!=0);
186  int targetIndex = edgeMap[target];
187  if(targetIndex != sourceIndex)
188  D.AddEdge(sourceIndex,targetIndex,vertex);
189  }
190  }
191  }
192 }
193 
196 template <class Node,class Edge>
198  Graph<Edge,Node>& D)
199 {
200  D.Resize(G.NumEdges());
201  std::map<std::pair<int,int>,int> edgeMap;
202  int k=0;
203  for(size_t i=0;i<G.nodes.size();i++) {
205  for(G.Begin(i,e);!e.end();e++) {
206  D.nodes[k] = *e;
207  edgeMap[std::pair<int,int>(i,e.target())] = k;
208  k++;
209  }
210  }
211 
212  for(size_t i=0;i<G.nodes.size();i++) {
214  for(G.Begin(i,e);!e.end();e++) {
215  std::pair<int,int> source(i,e.target());
216  int sourceIndex = edgeMap[source];
217  int vertex=e.target();
219  for(G.Begin(vertex,e2);!e2.end();e2++) {
220  std::pair<int,int> target(vertex,e2.target());
221  Assert(edgeMap.count(target)!=0);
222  int targetIndex = edgeMap[target];
223  if(targetIndex != sourceIndex)
224  D.AddEdge(sourceIndex,targetIndex,G.nodes[vertex]);
225  }
226  }
227  }
228 }
229 
231 template <class Node,class Edge>
232 void Get1Ring(const Graph<Node,Edge>& G,int node,std::set<int>& ring)
233 {
234  std::set<int> nodes;
235  nodes.insert(node);
236  Get1Ring(G,nodes,ring);
237 }
238 
240 template <class Node,class Edge>
241 void GetNRing(const Graph<Node,Edge>& G,int node,int n,std::set<int>& ring)
242 {
243  std::set<int> nodes;
244  nodes.insert(node);
245  for(int i=0;i<n;i++) {
246  Get1Ring(G,nodes,ring);
247  swap(nodes,ring);
248  }
249 }
250 
252 template <class Node,class Edge>
253 void Get1Ring(const Graph<Node,Edge>& G,const std::set<int>& nodes,std::set<int>& ring)
254 {
255  for(std::set<int>::const_iterator i=nodes.begin();i!=nodes.end();i++) {
257  for(G.Begin(*i,e);!e.end();++e) {
258  if(nodes.count(e.target())==0)
259  ring.insert(e.target());
260  }
261  }
262 }
263 
264 } //namespace Graph
265 
266 #endif
Definition: Edge.h:28
void GetNRing(const Graph< Node, Edge > &G, int node, int n, std::set< int > &ring)
Returns the undirected n-ring of the given node.
Definition: Operations.h:241
void CopyStructure(const Graph< N1, E1 > &G1, Graph< N2, E2 > &G2)
Copies the edge structure of G1 to G2 without setting its data.
Definition: Operations.h:14
void GetEdges(const Graph< Node, Edge > &G, std::vector< std::pair< int, int > > &edges)
Gets a list of edges.
Definition: Operations.h:70
void Transform(const Graph< N1, E > &G1, F f, Graph< N2, E > &G2)
Transforms a graph G1 to G2 using the function f to transform nodes from G1 to G2.
Definition: Operations.h:32
void Get1Ring(const Graph< Node, Edge > &G, int node, std::set< int > &ring)
Returns the undirected 1-ring of the given node.
Definition: Operations.h:232
void GetDualGraphCopy(const Graph< Node, Edge > &G, Graph< Edge, Node > &D)
Creates the dual graph of G and copies the data.
Definition: Operations.h:197
Namespace for all classes and functions in the Graph subdirectory.
Definition: ApproximateShortestPaths.h:7
Definition: Edge.h:88
void GetDualGraph(const Graph< Node, Edge > &G, Graph< std::pair< int, int >, int > &D)
Creates the dual graph of G. The dual references into the graph.
Definition: Operations.h:160
Basic template graph structure.
Definition: Graph.h:47
void GetSubGraph(const Graph< Node, Edge > &G, const std::vector< int > &nodes, Graph< Node, Edge > &S)
Creates the subgraph S of G induced by picking the nodes in nodes.
Definition: Operations.h:89