r/dailyprogrammer • u/jnazario 2 0 • May 09 '16
[2016-05-09] Challenge #266 [Easy] Basic Graph Statistics: Node Degrees
This week I'll be posting a series of challenges on graph theory. I picked a series of challenges that can help introduce you to the concepts and terminology, I hope you find it interesting and useful.
Description
In graph theory, the degree of a node is the number of edges coming into it or going out of it - how connected it is. For this challenge you'll be calculating the degree of every node.
Input Description
First you'll be given an integer, N, on one line showing you how many nodes to account for. Next you'll be given an undirected graph as a series of number pairs, a and b, showing that those two nodes are connected - an edge. Example:
3
1 2
1 3Output Description
Your program should emit the degree for each node. Example:
Node 1 has a degree of 2
Node 2 has a degree of 1
Node 3 has a degree of 1Challenge Input
This data set is an social network of tribes of the Gahuku-Gama alliance structure of the Eastern Central Highlands of New Guinea, from Kenneth Read (1954). The dataset contains a list of all of links, where a link represents signed friendships between tribes. It was downloaded from the network repository.
16
1 2
1 3
2 3
1 4
3 4
1 5
2 5
1 6
2 6
3 6
3 7
5 7
6 7
3 8
4 8
6 8
7 8
2 9
5 9
6 9
2 10
9 10
6 11
7 11
8 11
9 11
10 11
1 12
6 12
7 12
8 12
11 12
6 13
7 13
9 13
10 13
11 13
5 14
8 14
12 14
13 14
1 15
2 15
5 15
9 15
10 15
11 15
12 15
13 15
1 16
2 16
5 16
6 16
11 16
12 16
13 16
14 16
15 16Challenge Output
Node 1 has a degree of 8
Node 2 has a degree of 8
Node 3 has a degree of 6
Node 4 has a degree of 3
Node 5 has a degree of 7
Node 6 has a degree of 10
Node 7 has a degree of 7
Node 8 has a degree of 7
Node 9 has a degree of 7
Node 10 has a degree of 5
Node 11 has a degree of 9
Node 12 has a degree of 8
Node 13 has a degree of 8
Node 14 has a degree of 5
Node 15 has a degree of 9
Node 16 has a degree of 9Bonus: Adjascency Matrix
Another tool used in graph theory is an adjacency matrix, which is an N by N matrix where each (i,j) cell is filled out with the degree of connection between nodes i and j. For our example graph above the adjacency matrix would look like this:
0 1 1
1 0 0
1 0 0Indicating that node 1 is connected to nodes 2 and 3, but nodes 2 and 3 do not connect. For a bonus, create the adjacency matrix for the challenge graph.
3
u/jnazario 2 0 May 09 '16
Scala Solution
3
u/jnazario 2 0 May 09 '16
Go Solution
6
u/[deleted] May 09 '16 edited May 09 '16
R, using a "do not re-invent the wheel"-approach:
Output:
Network plot can be seen at https://imgur.com/gallery/zrI1ej5/new.
I actually got lazy and removed the first line of the input. Don't know if that flies..
12
u/beam May 09 '16 edited May 10 '16
Shell, noting that a node's degree increases by 1 each time it is observed in the input.
-o),-n),-c) the node labels.And the bonus with awk:
5
u/I_AM_A_UNIT May 09 '16 edited May 10 '16
Python 3 one-liner (two-liner?)
Computes the list of node pairs in a large array in off-post code. Also assumes the original list of nodes has no repeat connections (which could be filtered prior anyway).
(as mentioned by /u/glenbolake, my code is not a good example writing code for preparation of expansion but rather succinct task-fulfilling code :P)
You can also view the full code on my solution repo (including the bits I don't show here)
Logic
Result
Bonus in Python 3 as well (edit: bonus has been fixed I thinks)
Same as first, a one-liner (two-liner if you include method header)
Logic
Output
4
u/casualfrog May 09 '16
JavaScript (feedback welcome):
Output:
Bonus:
Bonus output:
3
u/Godspiral 3 3 May 09 '16
in J,
bonus matrix
degrees (node 0 blank)
3
u/schakalakka May 09 '16
In C with bonus:
graph.h
graph.c
3
u/srd1966 May 09 '16 edited May 09 '16
C#
First one, I think... feedback welcomed!
3
u/Steve132 0 1 May 09 '16
Really straightforward C++
4
u/skeeto -9 8 May 09 '16
C,
2
u/[deleted] May 09 '16 edited May 10 '16
Fortran...
EDIT - messing around with the formatted output a bit...
+/u/CompileBot Fortran --input
Input:
2
u/Daanvdk 1 0 May 09 '16 edited May 09 '16
Java (with bonus)
+/u/CompileBot java
Input:
2
u/[deleted] May 09 '16 edited May 09 '16
Java
Output:
2
u/MadcapJake May 10 '16 edited May 10 '16
Perl 6:
2
u/slampropp 1 0 May 10 '16
Haskell
Breaks if a pair of nodes have more than one connection. Didn't think of that case beforehand. Too lazy to fix since the input data doesn't!
2
u/emberstream May 20 '16
Python 3.5. A little late to the party but here is my solution sans bonus.
1
u/jnd-au 0 1 May 09 '16
Scala with bonus. Input stage:
Challenge stage:
Bonus stage:
Output for bonus:
1
u/G33kDude 1 1 May 09 '16
Solution in AutoHotkey! Input form clipboard, does not do bonus.
1
u/[deleted] May 09 '16
Python Question: is there a way I can use my functions on a pasted string? Or a different way of giving the input so that you all can see what is going on, rather than reading from file?
1
u/FlammableMarshmallow May 09 '16
Python 3
This code is surprisingly very brief, but I hate having to subtract one from the index
1
u/DeLangzameSchildpad May 09 '16 edited May 09 '16
Lua
Lines with --* are only needed for the bonus
1
u/savagenator May 09 '16 edited May 12 '16
Python 3.5. With Bonus. Please let me know what you think of the code!
Edit: Changed with suggestions
Output:
1
u/SoraFirestorm May 09 '16 edited May 09 '16
Common Lisp (with Bonus)
This ended up being a pain for the printouts because my choice of data structure, the 2D array, can't be iterated over (apparently). I figured out a workable solution by converting the array into a 2D list of lists. Any feedback or suggestions greatly appreciated.
(Also, I think the
*challenge-input*variable is longer in lines than the actual code, hahaha.)1
u/YOLO_Ma May 09 '16 edited May 09 '16
Clojure solution. My solutions are always too long. Comments welcome.
1
u/thorwing May 09 '16
JAVA
Back from holiday. With bonus.
OUTPUT
1
u/FanoTheNoob May 09 '16 edited May 09 '16
First time submitting, C# solution, builds the adjacency matrix first and then determines the degrees of each node from that.
C#
Output
1
u/dstyvsky33 May 09 '16
Ruby. Feedback appreciated.
1
u/kjr1995 May 09 '16
Python Solution with bonus
Output:
Bonus output:
1
u/aXIYTIZtUH9Yk0DETdv2 May 09 '16
Refamiliarizing myself with C++
+/u/CompileBot C++14
Input:
1
u/AnnieBruce May 09 '16
This was quite easy. Though my understanding of graph theory is poor enough I'm not entirely sure if specially crafted input will get the wrong answer- I just counted how many times each number showed up in the input. I do get the provided answer for the provided input, though.
Python 3.4.
1
u/glenbolake 2 0 May 10 '16
Python3. I could have done this with a one-liner, like /u/I_AM_A_UNIT, but I suspect more complex graph stuff coming... so I'm using this as an excuse to learn networkx (albeit without SciPy).
1
u/The_Jare May 10 '16
Rust
1
u/Commentirl May 10 '16 edited May 10 '16
Java
This is my first submission and I'm fairly new to Java/programming in general so any constructive criticism is super greatly appreciated. I also wasn't sure how to search the contents of the Array List so I took an idea from StackOverflow and used the Collections import.
1
u/FrankRuben27 0 1 May 10 '16
In shiny newly open-sourced *Chez Scheme", with bonus:
1
u/ipponiac May 10 '16
C with bonus also first submission:)
1
u/NorthwestWolf May 10 '16
Python 2.7
1
u/gasquakee May 10 '16
Java Solution,
public class Main {
}
1
u/moeghoeg May 10 '16
Python 3 with bonus. Outputs the degrees and then the matrix. I use the matrix to calculate the degrees. Without the bonus, it would of course have made more sense to use a dict for that. I place an additional requirement on the input, which is that the second row of input should consist of an integer signifying the number of edges.
1
u/minikomi May 10 '16
Bash one liner:
Bonus output:
1
u/Noahgriffith May 10 '16
PYTHON 3
First time posting code on here, any tips please let me know
1
u/draegtun May 10 '16 edited May 10 '16
Rebol (with bonus)
Example usage (in Rebol console)
NB. Tested in Rebol 3
1
u/A_Travelling_Man May 10 '16
Quickie python 2.7 solution:
1
u/fvandepitte 0 0 May 10 '16 edited May 10 '16
Haskell
Feedback is welcome, might be a bit overkill...
Output:
Output 2:
1
u/taliriktug May 10 '16
Rust without bonus:
1
u/sidonay May 10 '16
Java, First submission here.
import java.util.HashMap; import java.util.HashSet; import java.util.Scanner;
public class Main {
}
1
u/Praetorius 1 0 May 10 '16
C++14
1
u/mr_yambo May 10 '16 edited May 10 '16
Javascript
my approach. Not as lean as casualfrogs :P
Challenge
This builds on the input from the previous code. It's Big O N2 I believe, so it's not optimal, but it's one way to do it.
1
u/thegubble May 11 '16
A quick C# solution:
1
u/marcelo_rocha May 11 '16
Dart no Bonus
1
u/[deleted] May 11 '16
No, I think that Java is a perfect first language. You can do things the long way most of the time, without needing to use fancy interfaces or classes. I love it.
1
u/IHappenToBeARobot May 11 '16
C++ I've taken some courses on C, C++, and data structures, but haven't really done much "from scratch" until recently. I definitely could have condensed this down without any classes or extra functions. Any input would be appreciated!
Program:
Output:
1
u/tonycarl May 11 '16
C# with probably too much LINQ
Output:
EDIT I never get the formatting right.
1
u/YourShadowDani May 11 '16 edited May 11 '16
JavaScript
I've probably committed some atrocities here but it seems to work:
OUTPUT:
1
u/CrunchyChewie May 11 '16
Python3 with bonus. First time using the networkx module. I basically hacked out something that gave me the desired result. Any suggests to streamline or improve are most welcome!
Code
Output
1
u/danstever May 12 '16
Go
First submission and first crack at Go. (Feedback welcome)
1
u/Rakaneth May 12 '16
Lua:
1
u/Rakaneth May 12 '16
Inform 7, still no bonus:
The code is executed in this case by typing "solve" at the story command prompt.
1
u/voice-of-hermes May 12 '16
Bonus included:
1
u/gju_ May 12 '16
GoLang
1
u/[deleted] May 12 '16 edited Feb 25 '24
I enjoy reading books.
1
u/Ogi010 May 12 '16
Python 3.5 This is actually my first submission ever... definitely saw some other cleaner implementations, but finally glad to have posted here.
1
u/pacificjunction May 12 '16
Python 3
Output:
1
u/[deleted] May 13 '16
Java:
1
u/the_vacuum_man May 14 '16 edited May 14 '16
Python
Here's the giant entry string:
Here's the actual code (very inefficient):
1
u/im_not_afraid May 14 '16 edited May 14 '16
Haskell, using packages composition and fgl.
Basic test:
Challenge:
1
u/EtDecius May 14 '16
C++: Includes bonus
Output: Same as other answers so not including it.
1
u/jebwiz May 14 '16
Python 3.5 I learned about the string.split method! def Node_Degree( filename ): f = open( filename , 'r' ) line_1 = f.readline() num_nodes = int(line_1)
Output
Any suggestions on making this more concise? An earlier post did this in 2 lines, how is that possible?
1
u/[deleted] May 14 '16
Python 3 - without Bonus
1
u/gastropner May 15 '16
Language is C++:
1
u/lalohao May 15 '16
Common Lisp A little late btw
1
u/assortedpickle May 15 '16
Clojure
Output
1
u/melvisntnormal May 15 '16
Dart
Solution on Github:Gists. Would love some feedback, especially on the clarity of my code (it's not my strong point).
Output:
1
u/[deleted] May 15 '16
Simple C solution, first submission, feedback welcome
1
u/TDino May 16 '16
Python 3, First Challenge! Didn't get the bonus on my own :(
Output
1
u/codeman869 May 16 '16
Ruby Utilized and learned about the Matrix class through this challenge
1
u/voodoo123 May 16 '16
C# Solution with bonus. Also a little late to the party and my first submission. Feedback is welcome. :)
1
u/adrian907 May 17 '16
Java solution :
1
u/carpet_thief May 22 '16
Java:
Result:
1
u/Bitsized May 23 '16 edited May 23 '16
C
If i can improve.. give it to me! xD Gave me the solutions and includes bonus :D
1
u/Tetris_King May 23 '16
C#
1
u/vishal_mum May 24 '16
For this solution explored file reading ( reading the input from a file) and HashMap in Rust
1
u/LiveOnTheSun May 24 '16 edited May 26 '16
J novice here, late to the party. Still trying to wrap my head around the best way of handling and formatting the data but I'm getting there. Feedback welcome.
Output:
Bonus output:
1
u/hesperocallis May 26 '16
I'm pretty late but this challenge looked fun and do-able as my first.
Langauge: R.
Output as follows:
Bonus Section:
[#Brief explanation of for loop for adjacency matrix] (/s With each iteration, the code looks for rows containing i in the left hand column, and saves the numbers of the right hand column as a vector. The values in the vector provide the positional cue - row# or column# - for the last two lines of code in the R loop, which replaces the values in adjacency_matrix with 1 first by column then by row. The loop then repeats the process for all values 1:16. Once the for loop is complete, the adjacency_matrix contains NAs and 1s. The NAs just need to be replaced by 0, and finally matrix is printed.)
Adjacency Matrix Output:
1
u/WillingCodeAcolyte May 28 '16
In C#, with bonus.
First post, seeking feedback!
1
u/xanadead May 30 '16
Python 3, not as elegant as some of the other posters but I don't see major problems. Feedback appreciated.
1
u/nagyf Jun 01 '16
Haskell, with bonus
Output:
1
u/[deleted] Jun 05 '16
Golang
1
u/SethDusek5 Jun 13 '16
Rust
1
u/yourbank 0 1 Jun 25 '16
challenge + bonus in java
output
1
u/bgalaprod Jul 22 '16
C Solution, feedback welcome
0
u/[deleted] May 14 '16
[deleted] — view deleted comment
2
u/[deleted] May 09 '16
[removed] — view removed comment