# 6771 Ass3 GDWG

[Assignment Spec](https://cgi.cse.unsw.edu.au/~cs6771/19T2/assignments/dg/index.html)

**Potential Reference Implementations**
- **without stl** [https://www.techiedelight.com/graph-implementation-c-without-using-stl/](https://www.techiedelight.com/graph-implementation-c-without-using-stl/)
- **with stl** [https://www.techiedelight.com/graph-implementation-using-stl/](https://www.techiedelight.com/graph-implementation-using-stl/)
- [https://gist.github.com/miguelgazela/4428700](https://gist.github.com/miguelgazela/4428700)

**Forum Advice:**

++Pointers++
> [color=orange] Yes, all of those smart pointers for a single node or single edge point to that single node or edge (on the heap)

> [color=orange] Rather than storing an array inside a smart pointer, we want each individual node or edge to be stored in a smart pointer
The opposite is perfectly normal, however; that is, storing smart pointers in containers.

unique_ptr + raw
shared\_ptr + weak\_ptr

> [color=orange] 
all immediate **outgoing** edges, and not **incoming** edges

> [color=orange] 
**so we can't use `std::pairs`

> [color=orange] [https://webcms3.cse.unsw.edu.au/COMP6771/19T2/forums/2730994](https://webcms3.cse.unsw.edu.au/COMP6771/19T2/forums/2730994)
important notes on pointers

> [color=orange] rn the best thing ive found is that you need to add: `using is\_transparent = std::true\_type;`to a struct for a custom comparator if you want it to compare different types

> [color=orange] [https://webcms3.cse.unsw.edu.au/COMP6771/19T2/forums/2731043](https://webcms3.cse.unsw.edu.au/COMP6771/19T2/forums/2731043)
usefulness of erase

**Notes**
Each node needs to store:
- value
- incoming edges, outgoing edges and their weights

class Edge {
    E weight;
    Vertex &dest;
}

class Vertex {
	N object;
	std::vector<Edge> destinations;
	int incoming;
	int outgoing;
}

Map object->unique ptr?

Potential Graph Representations:
- 2d vector matrix of tuples?
- InsertNode: vector<vector<N>>, just push_back to high lvl
- `DeleteNode` not enough to just delete inner level vector, also need to find all the incoming edges from other graphs...
- `replace` only data changed for one node, `MergeReplace`, all nodes of a particular data changed
- `GetConnected` needs incoming and outgoing