Talk to me about graphs

Talk to me about graphs

Attached: SPT.gif (350x350, 349K)

Other urls found in this thread:

springer.com/us/book/9781846289699
twitter.com/AnonBabble

they're gay

you stop that shit, right now

Attached: graph.png (265x190, 8K)

springer.com/us/book/9781846289699

This book

Take formal math book about it, no CS tier book

>2018
>not using hypergraphs
lmao edgelet

Are they actually useful? Or are they one of those "cool in theory, but useless IRL" sort of things?
Also, are they coded in an object-oriented way, or are they just algorithms to do over lists?

My garbage collector uses them

by "object-oriented way" I mean, are you actually creating node objects, edge objects, etc...? Or are you more just using the graph as a visual way to represent connections between a more efficient data structure like a list or something?

Garbage collector fag here. It's not just a list. There are numerous possible invariants over graphs. You can say a graph is acyclic, bidirectional, complete, multipartite, and so on, and these qualities determine which algorithms are applicable. Don't just hand me a list and say "here's a graph." Get specific.

Find a max-flow, NOW!

Attached: crow-with-knife.jpg (500x827, 119K)

From 9 to 5, btw.

I feel like the nodes are pointless. Since an edge has a FROM and a TO component, it seems pointless to actually create the node because you could just reference the edges TO component.

What if you want to know every edge that points to a node without crawling?

So the edge needs to store which node it's pointing to, and the node needs to store which edges it has coming from and to it? That seems redundant.

They're a very fundamental model used for lots of things. Anything involving dependencies (like a build system or advanced type checkers), distance optimization (think finding the fastest route in Google Maps), analyzing all sorts of networks (be they comprised of computers, people, locations). And that's just scratching the surface with some general applications.

Bloat.

I have a question about A* vs Dijkstra's algorithm.
In all the examples of A* I've seen, it seems to be used in the context of a grid-like situation, and it calculates a heuristic distance-from-target that basically makes sense in the context of a physical layout of nodes.
However, what if the graph we're working with has nodes that aren't markers for physical locations, but with nodes acting as conceptual ideas? For example, what if nodes are something abstract like SKILLS, TALENTS, or TECHNOLOGIES, or something like that? They still have weighted edges which might determine how long it would take to develop said node's TECH or whatever. Is Dijkstra's algorithm better in this context because there's no real heuristic that better informs the path choosing how it might choose edges to investigate? Sorry if this doesn't make sense, but I'm reading about these algorithms while drunk.

It depends on the algorithm. In many cases, a matrix or list representation is all you need. In my garbage collector, I need flags on my nodes, so they are reified. The edges are represented simply as indices (in the nursery) or pointers (in the old space).

A* requires a heuristic function, and that heuristic function has to satisfy some properties to guarantee improved performance over a simpler method. It's easy to show that the Euclidean distance between nodes in a graph of locations with distances between them is a good heuristic function that improves performance over Dijkstra. In the general case where you don't have a heuristic function, Dijkstra is your best bet for single-source shortest paths.

Looks pretty cool. According to the free sample, more "walkthrough examples" would be nice. I like when books hold me by my hand and show me how to warm up and get started solving problems related.

Graph is most used math object on computer science, usually computer science end up begin almost induction over Graph.

Schedule begin graph(Operative system,reserve system,compilers,networks,processor).

Combinarics or space search problems formulate as graph problems.

A* is just Dijkstra's algorithm with a heuristic, that's it

Treewidth decompositions are cool.

Attached: tree_decomp.png (495x657, 56K)

>computer science is not computer programming: the post

Just the thread i need.
I have a 3D triangle mesh, i have specific edges marked with yellow in pic related. If the mesh was a graph, what algorithm could i use to connect the yellow edges to each other with the least amount of non yellow edges to form the largest possible loop?
Is there an algorithm for this?

Attached: it wont fit oneechan.png (850x894, 237K)

Subjectively easiest and most intuitive of higher mathematics.
Doing a grad course in Ramsey Theory right now also writing an academic report on double cycle cover conjecture

t. mathematician

You mean 9 to 6? 5 is not a sink in this network.

Anyways by the MFMC theorem {9, 2, 3, 4, 10} and {6, 1, 5, 7, 8} is a min cut with val 20.

You can make them ironically or unironically in Javascript.

Are you a real edge-lord?

you need to define your problem more for starters
also there are green and yellow edges in that picture

>it wont fit oneechan
>oneechan
I think your oneechan is actually an oniichan

Right, im colorblind, they all look yellow to me, no joke.

>you need to define your problem more for starters
Like what? I think the problem is pretty clear. Connect the colored segments with the least amount of edges from the graph to form a continuous loop. And form the largest loop possible so the algorithm is forced not to produce a 3 edge triangle.

I dont know what it means, im not a dweeb. Atleast i hope im not.

least amount of edges and largest loop possible is a conflict of goals, because you can make a larger loop by using more edges
and seeing there's edges all over the place, your'e going to have many loops, so which loop counts?

Yeah, it's not clearly defined. Would this problem statement describe your problem?
Each yellow/green edge is worth 10 points. each gray edge -1 points. Find the loop with the highest score.

>graphs
>Are they actually useful?
I'm a tier 0 Java dev without a degree, but this is just another level. I can actually believe this was asked in earnest, so consider me baited if not.

>conflict of goals
The algorithm would want to increase the loop size (largest loop), but it is constrained by the amount of edges it can use (least amount of edges).
>you can make a larger loop by using more edges
True but the goal is to use the least amount of additional edges.

>Find the loop with the highest score.
Yeah something like that. I imagined like pic related.


Is there an algorithm like this out in the world of graphs?

Attached: looptyloop.png (1052x606, 12K)

the algorithm is simple you just havent defined the conditions
either one constraint takes presidence over the other or you have a weight system
and you need to define what loop you're looking for, there are already loops in that image, so what loop gets counted? the innermost or outmost? in that case you need to pick a point on the graph that is the center, you could do a loop that connects every edge but that wouldnt really make sense seeing it crosses over itself

graphs aren't tech mate, maybe there is tech to produce them but them alone are not you turbofaggot

now shut up with your graphs and shit

surfP(x,y) {A, B, C, D}
surfC(x,y) {AB, CD, AC, BD}
surfC2(x,y) {ABCD}
f(x,y){

}
b0(p1, p2, x);
b1(p1,p2,p3, x);