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.
4.14 Output a Random Graph
Loading...
En provenance du cours de University of California, Santa Cruz
C++ For C Programmers, Part A
470 notes
À partir de la leçon
Module 4
Prim’s and Kruskal’s algorithms. Use of basic Container Classes. Tripod-Container, Iterator, Algorithm.
Rencontrer les enseignants
Ira PohlProfessor
Computer Science
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.
© 2018 Coursera Inc. Tous droits réservés.
