Problems relating to graph theory

learn more… | top users | synonyms

4
votes
10answers
383 views

Find all reachable nodes in a graph

You are given a directed graph in an adjacency dictionary format. This can be whatever format is most natural for your language. For instance, in python, this would be a dictionary with keys of nodes ...
9
votes
11answers
963 views

Calculate your stack exchange reputation

Background: I often find that, when browsing a Stackexchange site, I begin to wonder how people get the amount of reputation that they have. I know I can always count on codegolf SE to solve my ...
6
votes
4answers
290 views

Wireless Keyboard Inteference

Initech are setting up an office of 36 employees in a soul-crushingly efficient square of cubicles, 6 desks long and 6 desks deep. Management has bought wireless keyboards in bulk from a cheap, ...
3
votes
5answers
666 views

Alex the Truck Driver

Alex is a Truck Driver who wants to find the quickest way to deliver goods to multiple cities. He knows the distances between his destinations, but you need to write a program to help him find the ...
3
votes
3answers
232 views

Determine number of unconnected components

You are given a graph represented through an adjacency list. For example, the input 1-2 2-3 3-4 4-1 would correspond to the graph with nodes 1, 2, 3 and 4, where 1 is connected to 2, 2 is connected ...
8
votes
3answers
826 views

Score a game of Go

Scoring a Go game is a task that is not all too easy. In the past there have been several debates about how to design rules to cover all the strange corner cases that may occur. Luckily, in this task ...
9
votes
11answers
970 views

City names game

If you like, write a program which sorts cities according to the rules of city name game. Each name of the city should start from the last letter in the previous city name. E.g. Lviv -> v -> ...
1
vote
1answer
627 views

Calculate Network Average Clustering Coefficient

The clustering coefficient of a graph (or network) is a: measure of degree to which nodes in a graph tend to cluster together The Wikipedia article gives a much better description of how ...
6
votes
3answers
466 views

Shortest route through a one-way system

My home town, Rhyl, has a one-way traffic system which seems to have been designed to keep people away from their destination for as long as possible. Your task, should you choose to attempt it, is to ...
5
votes
2answers
172 views

BWInf 2011, question 5: Twin towns

This is a challenge that was originally a tas for the German Bundeswettbewerb Informatik (federal competition of computer science [?]), a competition for highschool students. As opposed to the ...
14
votes
9answers
1k views

Choose Your Own Adventure

Choose Your Own Adventure books are a form of interactive literature where the reader must make decisions that affect the outcome of the story. At certain points in the story, the reader has multiple ...
2
votes
0answers
445 views

Traffic light synchronization problem [closed]

I'm not a 100% sure if this qualifies under this stack exchange; however, I asked this question on the stats stackexchange with no answers. I wonder if you can solve it: Traffic light synchronization ...
11
votes
4answers
614 views

Help Mr Jones to enjoy his bicycle round-trip

Mr Jones wants to do a round-trip on his bicycle. He wants to visit several cities in arbitrary order, but his route must not cross it self, since he hates to be at the same place twice in his ...
6
votes
1answer
441 views

Shortest path in a graph

Write a program to take a graph (from either standard input or a file, your choice) and find a shortest path in the graph. Graphs are specified using the following format: A---S F--T | / \ | | / ...