Okay, I'm not great with ADT's, and I've recently posted a a topic on the matter, but I'm trying to develop a graph, I've found one or two ways online, and one way wasn't formally a data structure, not really, it would just make you think it was by printing things out in an unusual way, basically. I'm struggling to find an implementation of a graph data structure that I find fairly simple, I'm able to find some that are really complex and quite advanced, but I'm trying to make one as simple as possible.
I'd like to know if you guys have any ideas or any copies of how to make a super simplistic an minimalist graph?
I guess a good starting point would probably be to have a class called 'node', and that class would possess properties (local variables) called 'edges' which are just references/pointers to other instances of 'node'. That way you can have a one-to-one, or many-to-many (and the inbetween) connections of a graph. It is a similar idea to an implementation of a tree but I guess there are no restriction on root/branch/leaf nodes, only nodes and edges.
I understand that, I don't know why I just seem to be lacking an idea of how to actually implement it, and one thing that I seem to be struggling with is the fact that I've been given the task to only allow nodes to connect together. I simply mean that the connection between nodes needs the be multi-directional, you cannot have A node connect with B node, but have B node not connect with A node as an example.
I also seem to be struggling to think of the mechanics I need to do, I basically need to build a social media application in Java, based around the graph data structure. I.e.
Send and receive notifications, and all of that.
I think that one good way for me to try and tackle this would be to think in depth about how the likes of Facebook works?
FYI. Sorry if I have or have not already mentioned this, but this is simply a task for a university assignment, so I really do not want a straight forward answer, but possibly some hints and tips at most. I mean if you were to give me the solution, I wouldn't learn and develop my skills as a programmer, which is a terrible idea in my personal opinion.
Well to achieve the symmetry of nodes being the neighbours of their neighbours, you just start by creating however many nodes you need. Then, pairwise, if there is an edge between them (i.e. they become 'friends), you just update both nodes' 'neighbours' or 'edges' (probably a list of connections, ArrayList perhaps in Java) with each other's references.
I would create a struct called node and then everytime you add a edge to the struct do reloc on its memory to add add more to addresses to other structs.
Yeah I'm going to have to collaborate with others in my class while doing this, and I'm confident with many of us working on the same thing, we'll be able to conquer the problem. But I'd like to be able to do this myself in advanced to working with others, and yeah, an ArrayList in Java seems to be used more often for the likes of data structures, unless you know exactly how many items/pieces of data/objects will be processed through your data structure.
Nah, assembly. Just kidding, I'm struggling in Java, can't imagine how I'd manage in assembly or C, but assembly seems worse than C in terms of difficulty for beginners. - FYI, I am a total beginner, if I haven't already mentioned that.
The two classic ways of implementing a graph are: adjacency list (which is implemented as an array with |V| elements, in which each element is a list representing the set of neighbors of a vertex in the graph) and adjacency matrix. Each one has its advantages and trade-offs. Which one to use depends on the nature of the graph.
You either want an undirected graph or symmetric directed graph. I think you want the former.
If you want a challange, implement your own data structures, don't use the one that the language provides, unless you want to squeeze as much efficiency as possible.
I read the main method and it contained an object to read text from a .txt file and print it, and he had structured his data in this file in such a way that this object would print lines where it looked like 2 nodes had an edge. But there was no actual code for adding any edges, he was basically using something like this:
I'm actually only looking up other people's examples just to get a better idea of how to do it myself, obviously I'd try to make mine as bespoke as possible, so that I understand how it works, in great detail. But I'm really not sure at the moment on how to tackle it, but I am getting there, or so I feel like I'm getting there to say the very least.
If you have a link, pass it along. Anyway, graphs can be stored in a plain text file, using a graph description language (see .dot notation). It's just a convenient way to store a graph so it's easier to populate the data structure.
Unless you have an undiscovered brilliant idea you'll end up implementing it in a known way :D You can tweak the implementation to reduce the cost of some operation, that you can do.
I'm not gonna lie, because after I had inspected it, I just totally threw away the code and I don't remember the link, could have a look in history at some point. And with my very own implementation, the data will be stored in a ,txt file.
Well fingers crossed i guess? :')
I just want to make my own version that's as simple as possible, or at least I find it as simple as possible, then if it works well, I guess I could put it online to see what other's have to say? - I mean it it's bad I'd actually appreciate the constructive feedback, I wouldn't appreciate people just saying it's bad without suggestion on how to improve it though. I'd also appreciate other people's opinions, I find with programming it's always best to see how others think, as well as learning your own habits and thoughts?
I won't be and I know it will without a doubt be far from the best, simply due to the fact that I am a beginner really, I mean I've got a year experience of actual OOP style coding, so y'know. I'd appreciate people pointing pin holes in my work so I can become a better all round developer.
Hey, I know this isn't my own solution, but this seems like a very simplistic implementation:
I've developed a little bit on this, as it's so simple straight out of the box, only feature that I need to develop onto this is relational symmetry, meaning when n1 has an edge with let's say n2, n2 also has an edge with n1.
If you have an undirected graph (like the one in the picture), if a node ais connected (or adjacent) to a node b, then b is also connected to a. You just have to code it.
Also you may soon realize that this way of creating a graph will explode in your face, when you have graphs with hundreds or thausands of nodes:
GraphNode n1 = new GraphNode(1);
GraphNode n2 = new GraphNode(2);
GraphNode n3 = new GraphNode(3);
GraphNode n4 = new GraphNode(4);
GraphNode n5 = new GraphNode(5);
GraphNode n6 = new GraphNode(6);
GraphNode n7 = new GraphNode(7);
n1.neighbors = new GraphNode[] {n2, n4, n5};
n2.neighbors = new GraphNode[] {n1, n3, n4};
n3.neighbors = new GraphNode[] {n2, n4, n7};
n4.neighbors = new GraphNode[] {n1, n2, n3, n5, n6, n7};
n5.neighbors = new GraphNode[] {n1, n4, n6};
n6.neighbors = new GraphNode[] {n4, n5, n7};
n7.neighbors = new GraphNode[] {n3, n4, n6};
The most logical solution would be to use an array of nodes, so you've (kinda) implemented an adjacency list.
Yeah, whilst in university today, I thought of a way to implement the symmetric relationship for the edges, I can implement that and then to take it a step further, I can then set up a system where each node needs to agree to a relationship. Kinda like how the mechanics of a friend request on Facebook works, one node will send another a request, and the other needs to accept for the relationship to be set up. I'm sure I'll find a way to do it, I'm sure I won't have much difficulty in doing that, I also have to try and implement file I/O somewhere, again nothing hard. I've done it plenty of times before, I'm sure if I take my time and review previous work, I'm sure it'll be great.
Once I've got my basic system working, shall I post the code here so you can review it? - With an example of the file I/O implemented too? - Only issue is that I'm not 100% sure how long this will take me to do.
Feel free to post your code. Also if you have a github account or an account on another version control service, it may be good to keep the code there if you want other people to contribute and to keep track of the changes.