Explore
For Enterprise
Join for Free
Log In

Arts et humanités
Business
Informatique
Science des données
Technologies de l'information
santé
Mathématiques et logique
Développement personnel
Sciences physiques et ingénierie
Sciences sociales
Apprentissage des langues
Diplômes
Certificats

Explorez l'intégralité de Coursera

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

4.14 Output a Random Graph

Loading...

C++ For C Programmers, Part A

Université de Californie à Santa Cruz

4.4 (646 notes) | 94K étudiants inscrits

This course is for experienced C programmers who want to program in C++. The examples and exercises require a basic understanding of algorithms and object-oriented software.

Visualiser le programme de cours

Compétences que vous apprendrez

Graph Theory, C++11, C++, Graph Algorithms

Avis

4.4 (646 notes)

5 stars
419 ratings
4 stars
147 ratings
3 stars
34 ratings
2 stars
20 ratings
1 star
26 ratings

AK

Jul 04, 2017

I like Prof. Ira a lot and wish to see more courses from him! I wish I was his student at SC. Best Regards to him and the Coursera team for the great work.

PK

Jul 18, 2018

I really loved this course. It is really helpul for my programming aspect. I have managed to develop my logical abilty and this course really helped me.

À partir de la leçon

Module 4

Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.

4.2 Jarnik-Prim MST11:50

4.3 Jarnik-Prim MST: Another Look11:07

4.4 Kruskal's Algorithm8:30

4.5 Overloading and Function Selection32:19

4.6 STL and STL C++1111:00

4.7 STL Example5:05

4.8 C++11 Feature: auto5:38

4.9 Vector Methods10:36

4.10 More Code8:50

4.11 C++11 Feature: for statement7:07

4.12 STL Input File11:30

4.13 Iterators Categories14:19

4.14 Output a Random Graph12:30

Enseigné par

Ira Pohl
Professor

Transcription

Okay, let's do something a little more complicated,

and something in which we've used in our homework assignments.

So in the assignments,

I talked about generating a random graph.

And the random graph has what's called a density, and

the density is roughly speaking how many edges per node are available.

So if I have a density of 0.5,

density will be between 0 and 1.

1 would mean that we have what's called the complete graph,

every possible edge is Is included in the graph.

0 would mean we would have a completely disconnected graph.

We would have nodes but no edges.

Half would mean that if I had a graph which had 100 nodes,

on average there would be 50 edges per node.

That would be a reasonably dense graph for something that large.

And it's very useful to use random generation techniques

because when you start applying graph algorithms

to hard problems, it's hard to get real world data.

So at University of California Santa Cruz,

my colleagues have a huge project in designing

the Internet in the sense of making Internet

connections reliable and optimal.

And the Internet has hundreds of millions of nodes,

or maybe even billions of nodes at this point.

And you can send packets reliably all through the Internet.

And there has to be some design criteria.

How is an organization going to build its own local Internet?

Or in the case of the military you might have to have a dynamic

net because the connections are going to involve things in

which there are catastrophic failures.

Let's say your tank is shot up.

And it was one of your Internet points.

Nowadays the battlefield is electronic.

So there's just tons of research in how to create both static and

dynamic networks that make the Internet efficient and

highly reliable and inexpensive.

And those characteristics are hard to come by.

The data's hard to come by, and so, you try to simulate it.

And frequently you simulate it with the right set of random parameters.

So here's something very basic,

and it will also show a small amount of,

uses some of the techniques we've already talked about.

We're gonna borrow stuff from the standard library.

In C++ 11, we might wanna replace rand.

rand is very basic.

And C++11, one of the places where there's significant improvement

is a new set of standard

random functions that get you all sorts of interesting characteristics.

So I hope you go and examine that.

And maybe at a later time, we'll talk a little bit about that.

And this is a simple thing that provides a probability, and

you should see why it provides a probability.

First off, rand is in the int domain.

RAND_MAX is the largest possible value that can be generated.

So this is going to be, well this is unsigned.

And this is the largest possible value.

So this is always going to be less than 1.

But if they both were in an int domain, these would always lead to 0s.

We don't want that, so we force that value into the double domain.

We cast it into the double domain.

And then this becomes a mixed computation.

And then indeed we get a fractional value, which would be between 0 and 1.

So that's the probability you want.

As a probability we want something between 0 and 1.

Here's the density.

The density we're going to get from the user, be inputted.

We want some value inputted such as 0.5.

We also want a size.

So let's say this was the default.

We ask for a size, and this could have just as well been 0.

So we're getting a new size.

Let's say we want a 100.

So we'd have to type that in.

And now we're gonna create a graph.

And we're going to use basically,

A bool matrix.

So the graph is going to have in effect a 0 if there's no edge, i and j no edge.

0, or actually false.

And if there's an edge, there's going to be a 1, i and j having an edge.

True.

We're also going to allow colors.

So that makes the problem a little more interesting.

So edges are going to be able to have colors.

Think about your navigation computer on your car.

And my navigation computer allows the streets to be freeways or local streets.

And it allows me in computing a route to say avoid freeways.

How does it know to avoid freeways?

Freeways are blue, and ordinary streets are green.

And so it's going to look at the sub graph, namely the sub graph

of edges which are only green if it wants to avoid freeways.

Recall that any time we use a random number generator we want to

do something about initializing a seed to avoid routinely

getting always the same behavior out of the program.

So this is a standard practice to seed the random number generator using

something from the real world which would start at a different value.

Here we construct the different components.

We're basically constructing 3 matrices.

So this is a cost matrix like how if i and

j at cost 5 You can think of that as 5 miles.

Here's a [INAUDIBLE].

Maybe i and j will have the color Red.

And this is whether i and j exist.

So we're building the data structure to let us

Represent the graph.

And the graph representation in this case is a matrix representation,

not the edgeless representation.

So for those of you who want,

you can try and I try to do the same thing but do it with an edge list.

Here's where we create an edge.

Think of of this as flipping a coin.

The coin is weighted to give me a probability between zero and

one and then test whether the probability is below the density.

So if density was 1, all these probabilities would be less than 1.

But if density was down near zero, then

the probabilities would largely be greater than the density.

And so, it would be a relatively sparse graph.

So, we're testing to see in the fact that this is symmetric means

that the edges are undirected.

So we're generating undirected edges

of a particular density and then, we're testing if the edge exists

So this is boolean.

Then we do a color and a cost.

We're gonna have 3 colors, so we'll use the modulo operator.

And we'll get value 0, 1, or 2.

And those'll be the equivalent of the colors.

And we'll have a cost, in this case it'll be probability 30,

so times 30, so the values of the cost,

if they're integer values will be between 0 and 29.

I don't think we can get the 30.

And then I'm going to print this to an output file and

the output file, you should try this yourself.

Take the code from the site and you'll see that you'll get

a code that has these characteristics, that will have certain costs for

each edge we'll check again to see that the edge is true

and if the edge is true then those files will list the cost and

the color will have them as output.

Okay, okay we're at the end of

Part A of this course.

I hope you've had a good time, and got to really make use of C++ and

enhance your programming skills.

You've also learned how to do things with graphs and graphs algorithms.

And then, Part B is going to be the next class.

And I hope to see many of you in part B.

And there will be more advanced parts of C++ in Part B.

And try to see yet some newer C++11 features as well,

and the chief work of Part B is to Build a Game.

To Build a Game, is a well known game.

That's Hex. And the reason Part A was so

important to this is not only that you learn how to program effectively in C++,

but Hex is a game that is well represented by graph theory.

So

all

of

this

graph

theory,

should

go

into

understanding

and

building

this

Major

project.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales