Homework program that looks like a graphing problem, need some guidance

[ancient quarry]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

[ancient quarry]

How to Ask A Programming Question

Anyone can ask a question in our programming channels. Following the guide Writing The Perfect Question is recommended.

What To Post

State your problem clearly and provide all necessary details:

• the relevant portion of your code, or all of it
• the expected output
• the actual output (or the full error) 🏆 Gold Standard: Minimal Reproducible Example

Where To Post

Provide the relevant code in the message, and format it nicely with a code block*. If it's too much for one message, you can upload it:

• Compiler Explorer for most C/C++ snippets
• OnlineGDB for interaction, debugging ⛔ Do not post screenshots, let alone photos of your screen!

* Use /code if you don't know how to format code blocks

[ancient quarry]

@clear copper

Please Do Not Delete Posts!

Please don't delete forum posts. They can be helpful to refer to later and other members can learn from them. In the future you can use !solved to close a post and mark a post as solved.

[clear copper]

I'm struggling to write a program that utilizes graphs. From my understanding, this is what I need to do and what the restrictions are. Given a network of up to 26 nodes (named A to Z), where every pair of nodes may be connected
or disconnected, I need to write a program to draw the network in a two-dimensional diagram. A node may
be connected to at most 4 other nodes. Input from the keyboard the number of nodes in the network
then on separate lines input the pairs (edges) with capital letters. Assume the pairs are not sorted and
convert to proper case. Output to the screen an ASCII drawing showing the actual links between the
nodes. Nodes are given by the capital letters A to Z. Use '-', a dash, for horizontal links and a vertical
bar '|' for vertical links. The links should have horizontal and vertical lines that do not bend and have a
non-zero length. Spaces can be added provided they don't disfigure the picture. My program can currently detect cycles, and tell 'em the nodes that are apart of them, but I have no clue how to output what I need to. I'm lost. I appreciate any and all advice!

[vernal swan]

let's say you have

if the links are supposed to be drawn as horizontal or vertical only, no bending

then drawing this is physcally impossible

contact your foolish teacher and ask him about this graph

@clear copper

[vernal swan]

@clear copper

[clear copper]

Alright will do

[vernal swan]

the only possible graph that can be drawn like this is a square grid

[clear copper]

I will clarify with him what he wants

[clear copper]

See exactly what you're saying. I messaged him just now, would you like me to @ you once he responds?

[vernal swan]

k

[clear copper]

Should I take down the other then? Don't know how to, but I meant to

Post that is

[vernal swan]

go there and type !solved

[clear copper]

Alrighty

Unreal how much everyone in my course is struggling, this is a fundamentals course for god's sake 😳

[vernal swan]

why hasn't anyone in your class reported that graphs are impossible to draw like this lmfao

[clear copper]

No clue. To be frank, I feel silly for not seeing that

[vernal swan]

oh and graphs shouldn't even be a part of an introduction course

cause no one taught you graph algos like BFS

and DFS

the worst thing they can throw at you should be recursive functions

[clear copper]

Well, our prof posted the material for graphs, including DFS and BFS. Just didn't really teach it

[vernal swan]

🤣

[clear copper]

We did do recursion before this, as well as hash tables and sorting algorithms. Made a program using recursion 😃 was pretty fun

Unnecessary, but fun. Loops are way better

[clear copper]

@vernal swan he responded, says we can use '/' and '' to connect nodes as well

[vernal swan]

lmfao

well...

that is still broken

because

if I have one node, and it has more than 8 neighbours

then you physically cannot have straight lines

for the edges

[clear copper]

Max of 4 edges on each node, did I not say that?

[vernal swan]

BRUH

NO YOU DID NOT

[clear copper]

Yes I did! I just looked!😂

[vernal swan]

k

well...

that is still broken

because

if I have

[clear copper]

Oh no😭

[vernal swan]

this

oh wait

[clear copper]

That seems doable

Difficult though

[vernal swan]

A------B
| \  / |                  
|  /\  |                   
|/    \|            
C------D                

ughhhhhhhhhhhhhhhhhhhhhhhhh

wait...

[clear copper]

He just has to be able to tell that the nodes are connecting, doesn't NOT have to be perfect

Does*

[clear copper]

I think I'm boned

[vernal swan]

this guys I a piece of shit I swear to god

I bet he can't even solve his own homework

[clear copper]

Probably not, he's given some other really shitty programs in the past

Should I go into cpp text and see if anyone else wants to hop in on this too? Maybe more minds will make this easier

[vernal swan]

so, if 4 is the limit...

can you draw this with straight lines?

😄

which is isomorphic to this

[clear copper]

Oh wow uhhh hm

That looks god awful

I don't think that's possible

[vernal swan]

ok, let me ask you, how many points to you lose if you skip this homework?

[clear copper]

I lose 6 points on my semester average

He does give partial credit though

Generously, so could make it work for more simple cases

[vernal swan]

well... how are you going to detect that some graph is impossible to draw with straight lines?

😄

this is suicide

[clear copper]

Since edges cannot cross, I'd assume he wouldn't use inputs that require crossing edges

Let's assume input is friendly to the program

[vernal swan]

🤣

[clear copper]

Lol, don't know what else to say

[vernal swan]

oh and not to mention that a single possible to draw graph

can be drawn in multiple ways, not just the 4 rotations

cause you know, there are isomorphic grahs

[vernal swan]

yeah, this is a goddamn nightmare, I know

make some hardcoded graphs eazy to draw, write your program, submit that sh*t and that's it

[clear copper]

Orientation doesn't matter, as long as the nodes are connected

[clear copper]

Oh no😭

[vernal swan]

no, I mean like

[clear copper]

May be the only option I have

[vernal swan]

these 3 are the same graph

due to isomorphism

and you can even abuse this in all 8 directions for the center node

🙂

literally the worst homework

assignment

[clear copper]

Sooooo I shouldn't do it?

Here's the example run he gave

[vernal swan]

yes pls

farm points from other homeworks

not this one

[clear copper]

This is my last program of the semester, before the final 😭 I suppose I can do the extra credit on the quiz to try and make up for this

[clear copper]

Damn this problem is really that awful? I'm in fundamentals gad damn it 😂

[vernal swan]

the only f*cking place where this thing has a use case

is

git branch visualization

a.k.a.

this ASCII shit

AND THEY DO NOT USE STRAIGHT LINES FOR THE EDGES OF THE GRAPH

[clear copper]

🥴😂

[vernal swan]

oh and

in real life

people use graphviz

to generate a PDF with the graph drawn

read from some text file

[clear copper]

So I will never use this ever

[vernal swan]

not f*cking ASCII

[vernal swan]

yes

[clear copper]

That's really cool, I'm so glad my professor is teaching us practical applications of code 🙂

Even for a challenge problem this seems extreme

[clear copper]

Anyone else want to take a look at this problem?

[rancid tree]

drag your prof's ass to a fucking court or something

this is the worst assignment I've ever heard of, especially considering you're taking an introductory course

I'm taking this way more seriously than I really should but for real this is the kind of shit that drives people away from computer science

no matter how you break down the problem here, there isn't one subproblem that is trivial to solve

[blissful ivy]

oop

[clear copper]

Should I just fight for partial credit then and call it quits?

[rancid tree]

tbh yeah, this is just too hard if you're getting started with C++ of all languages

as kolio said already I'm 100% sure that knobhead of a prof can't even write something that works as requested

[clear copper]

Is it even possible in C++? I mean I'm sure you saw what Kolio was mentioning earlier, he made it out to be that way

Ok I gotcha

[rancid tree]

that example run he gave you he typed out manually

[clear copper]

Dang 😦 was hoping to be able to do it

[rancid tree]

anything is possible, given enough width that nightmare of a git graph shown in the above screenshot could even make sense

it's just not fit at all for an introductory course

[clear copper]

With that, can I safely assume that I am incapable of writing such a program with the knowledge I have at this point? Even if I wanted to grind it out?

[rancid tree]

you always could, but in my opinion it's hard in several distinct ways

[clear copper]

This is something I'd like to revisit at some point then, do it for fun once I'm proficient

[rancid tree]

it all boils down to computing how the vertices should be placed on your 2d drawing, and there is one immediate solution and a less immediate one:

• you arrange them in a circle, and you're certain that no two edges will ever overlap, but they're going to be absolutely painful to draw
• you arrange them in a lattice of some sort, but you have to find an arrangement such that no two edges find themselves overlapping: for planar graphs this is a hard problem on its own, and for non-planar graphs there will be at least two edges crossing so the optimal solution is to find the arrangement that minimizes edge-crossing which is even harder, and even then you're back to the nightmarish edge-drawing from the circle method with no guarantee that two edges don't overlap

[clear copper]

😐

[rancid tree]

your prof is an asshole

[clear copper]

My origin thought process was to find biggest cycle, graph it, find the next biggest cycle, graph that inside the that, etc. but this only covers a limited amount of possibilities

I want to call him out, but I'm sure I'll get some bs response like "you're in programming fundamentals 3, you should know how to create user friendly output "

[rancid tree]

lol yeah sure is this computer science or ux design

what a dickhead

in a freaking console

[clear copper]

What would you do? Fight for partial or see the head chair of the CS department after confronting the prof?

[rancid tree]

you can't really confront him imo, your experience as a student backed by some stranger's opinion on the internet doesn't weigh nearly enough to matter

[clear copper]

Fair

[rancid tree]

do what you can and see where it gets you

what's your experience with C++ and programming/algorithms in general so far?

[clear copper]

Arrays, some STL (vectors, maps, and some other basic things), sorting algos, lists, Binary Trees, hash tables, graphs, recursion

Classes, structs

Files, and probably some other smaller bits

[rancid tree]

okay that's a fair bit of the basics at least

[clear copper]

We finished the textbook this semester and I thought was all you could do with it 😭

Thought that*

Didn't realize there is so much more

[rancid tree]

yeah you're never quite done with CS :p

[clear copper]

If I want to get ahead, what should I start learning next?

[rancid tree]

here's how I would go about it:

• decide on a canvas size (simply define some compile-time constants somewhere)
• make a 2d array of the canvas size (use std::arrays) and fill it with spaces
• write a function that takes in a number of vertices and a canvas size, and which spits out a vector containing the coordinates for those vertices arranged in a circle
• write the vertices at their respective coordinates in your canvas
• for each edge:
  • compute the angle at which it will be drawn
  • depending on it, find the best character to use to draw that edge
  • find the cells which the edge traverses
    • you can brute-force your way into this by looping over the whole canvas and finding out whether each cell is traversed
    • or you can start from one vertex and iteratively find which neighbour cell in the canvas should be drawn next
    • (those two ways will produce different results and I'd personally go with the first)
  • write the edge character in those cells

it's not perfect but it's the most straight-forward and somewhat working solution that I can think of

and again some of those steps are far from trivial

[clear copper]

Would you mind me @ing you if I get stuck or need some guidance?

[rancid tree]

not at all

though it's half past 2 over there so imma go to sleep :p

[clear copper]

Sounds good, get some rest 👍🏻

[clear copper]

@rancid tree hey there, I know I am a bit late but exams caught me. How would I know where to place the vertices in the canvas? How should I go about deciding where to position them?

[rancid tree]

that's the whole issue

as hinted above, it's trivial to arrange them in a circle and you're guaranteed that no two edges overlap, but drawing edges then becomes hard because they can be at any angle

the other solution is to find an arrangement of the vertices on a lattice such that no two edges overlap

edges are trivial to draw on a lattice but finding such an arrangement is quite complex and there's no guarantee that one exists by the aforementioned criteria

tl;dr: arrange your vertices in a circle and figure out drawing the edges the best you can

[clear copper]

Gotcha, I meant more in scope of how to arrange them in a circle. Shortly after asking, I felt dumb after realizing it does not matter 😭

[rancid tree]

Basic trig should get you there

Try to figure it out yourself, but if you get stuck:
||A point at angle θ on a circle of radius r has coordinates (r.cosθ, r.sinθ)||

[clear copper]

@rancid tree Looks like I've got it figured out! Thank you so much for your help! It's not perfect but will get me points, last program of the semester 😁

[ancient quarry]

@clear copper Has your question been resolved? If so, run !solved :)

[clear copper]

!solved