Gabriel Bianconi

Algorithm for Finding Eulerian Paths (Python)

Posted on March 15, 2013 by Gabriel Bianconi

Udacity has excellent courses on computer science. I’m now taking my third course, Algorithms (CS215). One of the assignments of this course asked students to write a script that would find an Eulerian path in a given graph.

This topic greatly interests, so I’ve decided to research more about it. There are several solutions to the problem; I’ve implemented one based on Hierholzer’s algorithm, with some modifications to also support graphs with two nodes of odd degree. The script below successfully solved the assignment’s problem. I’ve also added comments to make it clearer.

# Copyright 2013 Gabriel Bianconi, http://www.gabrielbianconi.com/
#
# This work is licensed under the Creative Commons 
# Attribution-NonCommercial-ShareAlike 3.0 Unported License.

# Finds an Eulerian path in a given graph. Returns None if no
# such path exists.

def find_eulerian_path(graph):

    # The number of edges in the graph
    edges = len(graph)

    # Create a dictionary with the degree of each node
    degrees = {}

    for edge in graph:
        for node in edge:
            if node in degrees:
                degrees[node] += 1
            else:
                degrees[node] = 1

    # Determine how many nodes have odd degree
    odd_nodes = 0
    for node in degrees:
        if degrees[node] % 2 == 1:
            odd_nodes += 1

    # Return None if the graph doesn't contain an Eulerian path.
    # A graph only has an Eulerian path if the number of nodes
    # with odd degree is 0 or 2
    if odd_nodes != 2 and odd_nodes != 0:
        return None

    # A list of the steps of the Eulerian path
    path = []

    # If there are odd nodes, the path must start with an odd node
    for node in degrees:
        if degrees[node] % 2 == 1:
            # Start with an arbitrary path, not necessarily Eulerian
            # The first and final nodes have odd degree
            path = find_arbitrary_path(graph, node)
            break

    # If there are no odd nodes, start with an arbitrary node
    if len(path) == 0:
        path = find_arbitrary_path(graph, graph[0][0])

    # If the current path does not contain all nodes, there are missing inner, closed paths
    while len(path) < (edges + 1):

        # Determine a node which has missing edges in the path
        current_node = None
        for node in path:
            if degrees[node] > (path.count(node) + 1):
                current_node = node
                break

        # The index of this node in the path
        node_index = path.index(current_node)
        # An arbitrary, closed path containing the node with the remaining edges
        inner_path = find_arbitrary_path(graph, current_node)
        # Add the closed path to the current path
        path = path[:node_index] + inner_path + path[node_index + 1:]

    return path

# Finds an arbitrary path from a given starting node. If the starting
# node has odd degree, the path will end with a node of odd degree.
# Otherwise,the path will be closed. The used edges are removed from
# the graph variable.

def find_arbitrary_path(graph, starting_node):

    path = [starting_node]

    # If there are unused edges, find edges connected to the last node
    # and add the connected node to the path
    while len(graph):

        for i in range(len(graph)):
            if graph[i][0] == path[-1]:
                path.append(graph[i][1])
                graph.pop(i)
                break
            elif graph[i][1] == path[-1]:
                path.append(graph[i][0])
                graph.pop(i)
                break
            # If there are no such edges, the path can't be continued
            # and is returned
            elif i == len(graph) - 1:
                return path

    # If all edges have been used, return the path
    return path

# Examples:

print find_eulerian_path([(1, 2), (2, 3), (3, 1)])
print find_eulerian_path([(1, 2), (1, 3), (1, 5), (2, 3), (3, 4), (3, 5), (4, 5)])
print find_eulerian_path([(1, 2), (1, 3), (2, 4), (2, 5), (3, 4), (4, 5)])
print find_eulerian_path([(1, 13), (1, 6), (6, 11), (3, 13),
    (8, 13), (0, 6), (8, 9),(5, 9), (2, 6), (6, 10), (7, 9),
    (1, 12), (4, 12), (5, 14), (0, 1),  (2, 3), (4, 11), (6, 9),
    (7, 14), (10, 13)])

100

101

102

103

104

105

106

107

108

# This work is licensed under the Creative Commons

# Attribution-NonCommercial-ShareAlike 3.0 Unported License.

# Finds an Eulerian path in a given graph. Returns None if no

# such path exists.

def find_eulerian_path(graph):

# The number of edges in the graph

edges = len(graph)

# Create a dictionary with the degree of each node

degrees = {}

for edge in graph:

for node in edge:

if node in degrees:

degrees[node] += 1

else:

degrees[node] = 1

# Determine how many nodes have odd degree

odd_nodes = 0

for node in degrees:

if degrees[node] % 2 == 1:

odd_nodes += 1

# Return None if the graph doesn't contain an Eulerian path.

# A graph only has an Eulerian path if the number of nodes

# with odd degree is 0 or 2

if odd_nodes != 2 and odd_nodes != 0:

return None

# A list of the steps of the Eulerian path

path = []

# If there are odd nodes, the path must start with an odd node

for node in degrees:

if degrees[node] % 2 == 1:

# Start with an arbitrary path, not necessarily Eulerian

# The first and final nodes have odd degree

path = find_arbitrary_path(graph, node)

break

# If there are no odd nodes, start with an arbitrary node

if len(path) == 0:

path = find_arbitrary_path(graph, graph[0][0])

# If the current path does not contain all nodes, there are missing inner, closed paths

while len(path) < (edges + 1):

# Determine a node which has missing edges in the path

current_node = None

for node in path:

if degrees[node] > (path.count(node) + 1):

current_node = node

break

# The index of this node in the path

node_index = path.index(current_node)

# An arbitrary, closed path containing the node with the remaining edges

inner_path = find_arbitrary_path(graph, current_node)

# Add the closed path to the current path

path = path[:node_index] + inner_path + path[node_index + 1:]

return path

# Finds an arbitrary path from a given starting node. If the starting

# node has odd degree, the path will end with a node of odd degree.

# Otherwise,the path will be closed. The used edges are removed from

# the graph variable.

def find_arbitrary_path(graph, starting_node):

path = [starting_node]

# If there are unused edges, find edges connected to the last node

# and add the connected node to the path

while len(graph):

for i in range(len(graph)):

if graph[i][0] == path[-1]:

path.append(graph[i][1])

graph.pop(i)

break

elif graph[i][1] == path[-1]:

path.append(graph[i][0])

graph.pop(i)

break

# If there are no such edges, the path can't be continued

# and is returned

elif i == len(graph) - 1:

return path

# If all edges have been used, return the path

return path

# Examples:

print find_eulerian_path([(1, 2), (2, 3), (3, 1)])

print find_eulerian_path([(1, 2), (1, 3), (1, 5), (2, 3), (3, 4), (3, 5), (4, 5)])

print find_eulerian_path([(1, 2), (1, 3), (2, 4), (2, 5), (3, 4), (4, 5)])

print find_eulerian_path([(1, 13), (1, 6), (6, 11), (3, 13),

(8, 13), (0, 6), (8, 9),(5, 9), (2, 6), (6, 10), (7, 9),

(1, 12), (4, 12), (5, 14), (0, 1), (2, 3), (4, 11), (6, 9),

(7, 14), (10, 13)])

Posted in Programming | Leave a comment

Mobile Web vs. Mobile Apps: A solution?

Posted on December 25, 2012 by Gabriel Bianconi

iphones

Will apps remain leaders of the mobile market, or will they be replaced by the mobile web? This question is nowadays producing one of the most heated discussions among mobile developers.

Last week, Fred Wilson encouraged readers of his blog to discuss this topic. I was going to comment on the post, but I realized that it’d be possible to expand it into a blog post. There is no consensus about this topic, and I’m not giving a definitive solution. Instead, I’ll point out some characteristics of each of these technologies and leave the conclusion to the reader. In fact, I believe that the optimal solution depends on the product. As pretty much anything else, the mobile web has positive and negative elements.

Positive:

Fast, seamless updates

Websites usually can be updated by simply uploading new files to the server. However, if you need to update an app, it needs to be submitted for review again. For instance, this often takes 1-2 weeks in Apple’s App Store. In fact, some updates get rejected and it’s necessary to resubmit the app for review. By removing the need for external review, you can push updates much faster. When a product is still under development, this perk is especially helpful.

If there’s a bug on your product, the update delay of an app review might cause you to lose users and get bad reviews. Also, I personally hate when apps ask to be updated frequently. However, web products don’t need this.

(Theoretical) reduction of development costs and time

If you want your app to be available for different devices (thus expanding the potential market), you’ll need to create multiple versions of the product. However, websites are accessible by any modern phone with internet access. By reducing the need for multiple versions, development costs and time would be reduced significantly.

I know this point is debatable, since mobile browsers aren’t equal. The website will probably be rendered differently in each device. This may be acceptable in may cases, but in some this must be avoided.

No guidelines (almost)

Apps need to conform with the App Store’s guidelines. However, if your product is on the web, it won’t be reviewed, so there are no guidelines (as long as the product is legal, of course).

Negative:

Phone features

Apps can access the phone’s accelerometer, contacts, dialing, etc. However, websites don’t have access to these features. Thus, if they are required for your product, mobile web is a no-no for you.

Speed

Apps will have a lot of information stored on the phone, so they’ll usually run much faster than a website. Where mobile internet connections are notoriously slow, e.g. in developing countries, this might make your product unusable. If your product takes minutes to load, the user will probably give up before he or she starts using it.

Accessibility

When a user downloads an app, his phone will automatically add an icon to the home screen. However, this does not happen with websites, which are thus more likely to be forgotten. It’s possible to bookmark the pages, but there’s no guarantee that users will do it (and it adds complexity to the process). Therefore, apps will probably have a much higher user retention rate than websites.

Technology adoption

Users are getting used to download apps, but they aren’t to the mobile web. If your target audience is tech-friendly, this is no problem. However, if you are dealing with people who aren’t inclined to adopt new technologies, this might increase the difficulty in getting users.

App store promotion

When an app becomes featured on the App Store, thousands of users will download it for this reason. Although this is rare, it has helped some obscure apps to become well-known. For now, there is no replacement (that is popular enough) for this, so you might lose some promotion (if you were lucky enough to be featured).

The Solution:

I believe there is no definitive solution. This will depend on the needs of the product. However, an interesting approach would be mixing these technologies. For instance, you could create an app that loads most of its content from the web. In this way, you’d get the benefits of fast, seamless updates of a website, while maintaining some functions of an app, such as app store promotion and accessibility. In fact, development costs and time would be relatively low, since part of the product will be compatible with multiple devices.

Developers should consider these points before choosing a platform. Depending on the product, certain platforms will be more beneficial. There isn’t only one general optimal solution.

Picture credit to Ricky Romero, licensed under the CC terms.

Posted in Technology | Leave a comment

Finding the Period of the Decimal Expansion of 1/n

Posted on November 29, 2012 by Gabriel Bianconi

When I was solving Project Euler’s problem 26, I had to find a way to obtain the period of the the decimal expansion of $1/n$ for various integer values of $n$ . I first thought of comparing strings of digits along the decimal expansion to see if they repeated; however, this solution was neither clever nor efficient. With this in mind, I set out to find a better method for this problem.

After some research, I came across something I had never heard about in my high school math classes. The smallest integer exponent $e$ such that $b^e \equiv 1 \ (\textrm{mod} \ n)$ is called the multiplicative order of $b \ (\textrm{mod} \ n)$ .

This value has an interesting property. The multiplicative order of $10 \ (\textrm{mod} \ n)$ is equal to the period of the decimal expansion of $1/n$ . Note that this only works when $n$ is relatively prime to 10, i.e. when $n$ is not divisible by 2 or 5.

Consider a few examples:

n	1/n	Period	Multiplicative Order of 10 (mod n)
$3$	$0. \overline{3}$	$1$	$10^1 \equiv 1 \ (\textrm{mod} \ 3) \therefore e=1$
$7$	$0. \overline{142857}$	$6$	$10^6 \equiv 1 \ (\textrm{mod} \ 7) \therefore e=6$
$9$	$0. \overline{1}$	$1$	$10^1 \equiv 1 \ (\textrm{mod} \ 9) \therefore e=1$
$11$	$0. \overline{09}$	$2$	$10^2 \equiv 1 \ (\textrm{mod} \ 11) \therefore e=2$
$13$	$0. 0\overline{769230}$	$6$	$10^6 \equiv 1 \ (\textrm{mod} \ 13) \therefore e=6$

Honestly, I don’t know why this property works, but it allowed me to solve the problem using an algorithm that was much faster (and clever) than my previous. If you want to look deeper into it, check the links below.

References & Further Resources

Posted in Mathematics | Leave a comment

Why Ask.com Will Fail in Brazil

Posted on August 6, 2012 by Gabriel Bianconi

Ask.com has launched a landing page for Brazilian users in order to get a share of the 80 million Brazilian internet users. However, Ask.com’s operations targeted at Brazilian users is severely flawed. Unless Ask.com changes how it operates, it is very likely to fail in Brazil, which, as mentioned before, has a huge market.

The first major problem is Ask.com’s landing page for Brazilian users. The image below shows the American landing page and the Brazilian landing page.

The American landing page (above) and the Brazilian landing page (below)

The differences between both pages are clearly visible. The American page is filled with valuable content, including an interactive quiz. However, the Brazilian version is not even related to questions, which should be one of the most important features of the other page. The Brazilian page is very weak and not likely to be competitive with Google for general searches. The main twist, which could be a great feature, was left aside.

Even Ask.com’s search feature is poorer in the Brazilian version. It has no internal QA system, no search terms suggestions and no search options such as image search. Moreover, the amount of ads in the Brazilian page is higher than in the American version. But most importantly, most results are generally not relevant. A search for Olimpíadas (Olympics in Portuguese) gives poor results, excluding two Wikipedia pages in the middle. Therefore, the only feature that the Brazilian version has is also greatly flawed.

The Brazilian version is not under construction, for Ask.com is advertising their page for Brazilian users. Nonetheless, their ads are also faulty. Refer to the ad below, which I saw on Youtube in July 2012:

This ad appeared on Youtube in July 2012

The sentence “Onde foi Marisa Monte nasceu?” is grammatically incorrect. It is a word-by-word translation from “Where was Marisa Monte born?”, but the correct version should be “Onde nasceu Marisa Monte?” (or other correct variation). Moreover, the call-to-action used in this ad is written in English. It would be much more effective to write it in Portuguese (“Descubra”) since many Brazilian do not speak English. It is also strange that part of the ad is written in Portuguese, while another part is written in English. At last, the picture in the background is from an American birth certificate, which may also not be familiar to many Brazilian users (a Brazilian birth certificate could be used instead). These changes would greatly increase the quality (and thus the conversions) of this ad.

Therefore, the Brazilian version of Ask.com’s website is much weaker than the original version. The only feature it has, search, is also worse than in the American version. Furthermore, Ask.com’s ads are faulty and contain translation problems. Therefore, unless Ask.com changes how it operates in Brazil, it is very likely to fail in attracting Brazilian users.

Posted in Business | Leave a comment

4 Lessons from Stanford’s Online Technology Entrepreneurship Course

Posted on July 10, 2012 by Gabriel Bianconi

In March 2012 I started to participate in an online Technology Entrepreneurship course by Stanford University. Before joining this course, I had little experience in entrepreneurship and it has helped to learn much about this. Here are the most important lessons I learned during this course:

1. The importance of a motivated team

This was the first thing I learned. The teams for the first two assignments were not chosen by the students, so I was assigned to a team of 10 random people. All the other members of my team did not really want to participate in this course. Some had signed up for curiosity, some did not have enough time anymore, and some were unreachable. I tried to engage them into discussion for the activities, but I was unsuccessful.

The deadline was near, so I finished the project by myself and submitted it. I learned from doing it, but I am sure that I could have learned much more if the other team members had participated. Luckily, my team for the startup project (the most important part of the course) is very active. Although our product is not finished (I will write about this in another post), I have learned much from these interactions.

2. International teams are a double-edged sword

My team for the startup project initially had 8 members from different countries: Brazil, China, Equador, India, Ireland, Latvia, Singapore, and United States. Having an international and multicultural team has many benefits, but it can be problematic too. The most evident issue is communication; it is hard for me, located in Brazil, to chat in real-time with someone from Asia. Moreover, being unable to talk face-to-face to other team members (except in Skype) makes the project more complicated. In order to overcome this communication problem, we are using many tools, such as Facebook Groups (chatting and messaging), Trello (task management) and Skype (real-time conversation).

However, this feature of our team has positive aspects too. Most notably, each of us have knowledge and experience that others do not have. We can learn much from others in this way. Also, this allows us to be at different parts of the world without big costs – which is especially helpful for an early-stage startup. It was a very interesting experience for me to work in such a group.

3. Startups can avoid costs with creativity and determination

As an early-stage startup without funding, it is fundamental to be able to cut costs. There are times when this is hard. But with creativity and determination, many costs can be avoided. For example, we needed a tool for task management and messaging. The most popular tool for this is probably Basecamp by 37signals, but it would cost us at least $20/month. Therefore, we decided that we should search for other tools. In the end, we found Trello, which is free and managed to solve our problem efficiently. The only cost that we had so far was the domain name, which costs less than $10/year.

4. Learning by doing is very efficient

The lectures by Prof. Eesley were superb and filled with relevant content. However, I feel that most of what I have learned did not come from there, but from the projects and assignments. Trying something by yourself is very rewarding and I feel that I learned much about entrepreneurship by trying to launch a startup. The best way of learning something is by trying to do it, even if you fail at first.

Posted in Entrepreneurship | Leave a comment

Algorithm for Finding Eulerian Paths (Python)

Mobile Web vs. Mobile Apps: A solution?

Positive:

Negative:

The Solution:

Finding the Period of the Decimal Expansion of 1/n

References & Further Resources

Why Ask.com Will Fail in Brazil

4 Lessons from Stanford’s Online Technology Entrepreneurship Course

1. The importance of a motivated team

2. International teams are a double-edged sword

3. Startups can avoid costs with creativity and determination

4. Learning by doing is very efficient

Archives

Recent Posts

Categories