-1

I'm trying to build some network flow algorithms, and I need to represent edges in graph.

this is my Edge structure:

struct Edge{
  int from, to, flow, cap;
  Edge(int fromC, int toC, int flowC , int capC)
    : from(fromC), to(toC), flow(flowC), cap(capC)
  {};
};

then I have graph structure with adjacency list:

struct Graph {
  int N;
  vector<vector<Edge> > adjList;  // list of neighbours    

  Graph(int n) {                  // constructor
    N=n;
    adjList.resize(n);
  }
};

and then I have function to add edges to adjacency list: 

void addEdge ( Graph &G, Edge &E)
{
  G.adjList[E.from-1].push_back(E);
}

and I want to use this syntax:

Graph G = Graph(4);  // creates graph with4 vertices
addEdge(G, new Edge(2, 4, 0, 4));

but this doesn`t work… I have to change function to:

 void addEdge(Graph &G, Edge *E)

and then modify everything in function body…

My question is: Is there a way to use new in function call with references like ?:

addEdge(G, new Edge(2, 4, 0, 4));

Thank you for your answers. ( I'm new to C++, sorry if answer is obvious: No, you have to use pointers in signature & body... )

Telokis
  • 3,399
  • 14
  • 36
martinerk0
  • 403
  • 1
  • 4
  • 17
  • 1
    Why do you want to use `new` like that? – juanchopanza Mar 01 '15 at 17:48
  • because otherwise I'd have to use `Edge e =Edge(1,3,0,4); addEdge(G, e );` which are 2 lines of code, or 2m lines where m is number of lines – martinerk0 Mar 01 '15 at 17:49
  • 4
    That's a very poor reason to use dynamic allocation. What you need to do is change the function to `void addEdge(Graph &G, const Edge& E)` and then say `addEdge(G, Edge(1, 3, 0, 4));`. – juanchopanza Mar 01 '15 at 17:50

3 Answers3

2

Get rid of the new and have addEdge accept a const Edge&. This lets you simply use an automatic temporary like this:

addEdge(G, Edge(2,4,0,4));

addEdge's signature becomes void addEdge(Graph &G, const Edge &E).

Pradhan
  • 16,391
  • 3
  • 44
  • 59
0

Yes, you can write just:

addEdge(G, Edge(2,4,0,4));

But you should consider performance issues. This form creates temporary instance on the stack, so you are supposed to do a copy (push_back alreade does).

sgflt
  • 68
  • 3
  • 10
  • _"so you are supposed to do a copy"_ a _move constructor/assignment operator_ for `Edge` can finally heal this. – πάντα ῥεῖ Mar 01 '15 at 17:54
  • Yes, but it stil can produce more overhead than handling with pointer. It depends on use case what way is more suitable for solving a problem. – sgflt Mar 01 '15 at 17:58
  • _"Yes, but it stil can produce more overhead than handling with pointer."_ How actually? – πάντα ῥεῖ Mar 01 '15 at 17:59
  • For example if you need Edges outside of Graph for some reason. But you are right, you can return pointer to adjList[x] in this case. – sgflt Mar 01 '15 at 18:04
  • 1
    This is nonsense. A copy, which will probably be optimised out or replaced with a move anyway, is almost certainly cheaper here than the overhead of dynamic allocation _and_ all the locality/cache issues that come with a container of pointers. Not to mention the overhead in your code of later freeing it all, and of deep copying the vector. – Lightness Races in Orbit Mar 01 '15 at 18:08
-1

Declare addEdge to take a const reference since you're not modifying the original object.

Then you can simply do this:

void addEdge ( Graph &G, const Edge &E) { ... }
addEdge(G, Edge(2,4,0,4));

This is the preferred way in C++, since it avoids dynamic allocation.

Emil Laine
  • 41,598
  • 9
  • 101
  • 157