1 #ifndef GRAPH_OPERATIONS_H 2 #define GRAPH_OPERATIONS_H 5 #include <KrisLibrary/errors.h> 13 template <
class N1,
class E1,
class N2,
class E2>
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());
31 template <
class N1,
class E,
class N2,
class F>
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);
51 template <
class N1,
class E1,
class N2,
class E2,
class F,
class G>
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]);
59 for(
size_t i=0;i<G1.nodes.size();i++) {
61 for(G1.Begin(i,e);!e.end();e++) {
63 G2.AddEdge(i,e.target(),temp);
69 template <
class Node,
class Edge>
72 edges.resize(G.NumEdges());
74 for(
size_t i=0;i<G.nodes.size();i++) {
76 for(G.Begin(i,e);!e.end();e++) {
78 edges[k].second = e.target();
88 template <
class Node,
class Edge>
90 const std::vector<int>& nodes,
94 for(
size_t i=0;i<nodes.size();i++) {
95 Assert(0 <= nodes[i] && nodes[i] < (
int)G.nodes.size());
97 Assert(nodes[i-1] < nodes[i]);
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;
106 S.Resize(nodes.size());
107 for(
size_t i=0;i<nodes.size();i++)
108 S.nodes[i] = G.nodes[nodes[i]];
111 for(
size_t i=0;i<nodes.size();i++) {
113 S.co_edges[i].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);
128 template <
class Node,
class Edge>
133 Assert(nmin >= 0 && nmax <= (
int)G.nodes.size());
138 for(
int i=nmin;i<nmax;i++)
139 S.nodes[i-nmin] = G.nodes[i];
142 for(
int i=0;i<nmax-nmin;i++) {
144 S.co_edges[i].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);
159 template <
class Node,
class Edge>
161 Graph<std::pair<int,int>,
int>& D)
163 D.Resize(G.NumEdges());
164 std::map<std::pair<int,int>,
int> edgeMap;
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;
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);
196 template <
class Node,
class Edge>
200 D.Resize(G.NumEdges());
201 std::map<std::pair<int,int>,
int> edgeMap;
203 for(
size_t i=0;i<G.nodes.size();i++) {
205 for(G.Begin(i,e);!e.end();e++) {
207 edgeMap[std::pair<int,int>(i,e.target())] = k;
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]);
231 template <
class Node,
class Edge>
240 template <
class Node,
class Edge>
245 for(
int i=0;i<n;i++) {
252 template <
class Node,
class Edge>
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());
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
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