Hi, Boost library provides adjacency matrix, adjacency list and edge
list graph representation (http://www.boost.org/doc/libs/1_35_0/libs/
graph/doc/index.html).
There are some ideas about graph representation:

1. Adjacency matrix:
//Ideas:
We can represent graph by adjacency matrix as:
-a-. int** (unsigned int**).
-b-. std::vector<std::vector<int> >.
We can reserve vector size to vertex count at graph class constructor.
And we mustn’t free allocated memory (we haven't new operator).
-c-. std::vector<int>*
-d-. std::vector<int*>
-e-. Triangle adjacency matrix for undirected graph.

//Questions:
-a-. (int**)
So, unigned int** works faster then int** (Visual Studio 2003 packed
it both to 4 bytes?!). But "int" is machine word and, maybe, it shall
work faster or equally with unsigned**
....Maybe we can collect each row size as one of the row elements?

2. Adjacency list:
//Ideas:
-a-. std::vector<std::list<CNode> >;
-b-. std::list<CNode>*
//Questions:
If we represent complete weighted graph, does list representation take
higher memory costs then adjacency matrix representation?
class CNode
{
private:
int m_nNode;
int m_nWeight;
};
/////////////////////////////////////////////////////////////////////////////////
//Questions:
1. Is graph representation hardly depends on graph properties?
2. We use here static graph model (we set vertex at graph
constructor).
class CGraph
{
public:
CGraph(int _count)
{
createNodes(_count);
}
........
};

What representation we can used to provide dynamic graph model, low
memory cost.

3. If we have 6.000.000 vertexes with weighted edges, what
representation would be optimal (edge-list)?


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Aug 6, 2:58 pm, Alexander Zezulinsky <palgol...@gmail.com> wrote:
> //Questions:
> -a-. (int**)
> So, unigned int** works faster then int** (Visual Studio 2003 packed
> it both to 4 bytes?!). But "int" is machine word and, maybe, it shall
> work faster or equally with unsigned**

Depends on CPU, but unsigned arithemitic requires less combinatorial
logic. :)

> ...Maybe we can collect each row size as one of the row elements?

I would keep the matrix itself separate. You do have C++ at your
disposal to create class representation. :)

> 2. Adjacency list:
> //Ideas:
> -a-. std::vector<std::list<CNode> >;
> -b-. std::list<CNode>*
> //Questions:
> If we represent complete weighted graph, does list representation take
> higher memory costs then adjacency matrix representation?
> class CNode
> {
> private:
> int m_nNode;
> int m_nWeight;};

Obviously, as number of nodes goes to infinity, adjacency matrix will
consume far more memory than list representation, especially if graph
is sparse.

> ///////////////////////////////////////////////////////////////////////////*//////
> //Questions:
> 1. Is graph representation hardly depends on graph properties?

I think you are asking how much implementation will vary in internal
structure depending on how the graph is intended to be used. This is a
good question. My personal preference is to Do Whatever Necessary. The
complexity of a typical graph implementation is such that the
requisite per-node overhead quickly destroys all hopes of efficieny in
terms of memory. For example, books on data structures and algorithm
often claim that the each link during execution of MST [http://
en.wikipedia.org/wiki/Minimum_spanning_tree] or other algorithm will
have a "bit" that is true or false, depending on whether that link has
already been traversed. In practice, there is no way to have only one
single "bit", but an entire word, that might or might not used to hold
other bits. Then it is discovered that, even to perform a simple
Dijkstra run, complex linkage is required. After a while, it is
realized that full structure entire classes for link/edge, node/
vertex, is best.

> 2. We use here static graph model (we set vertex at graph
> constructor).
> class CGraph
> {
> public:
> CGraph(int _count)
> {
> createNodes(_count);
> }
> .......
>
> };
>
> What representation we can used to provide dynamic graph model, low
> memory cost.

Hmm..well there is Boost :)

The low-memory cost is hard unless your per-node, per-edge information
is large to amortize structural overhead. I would recommend:

1. associative set mapping vertex identifier to vertex struct
2. associative set mapping edge identifier to edge struct
3. various internal data structures to help with graph-theoretic
algorithms (Floyd-Warshall, Dijstra), etc.

You might have discovered that so called priority-queues used in graph
algorithms is an untruth. What is really needed is someting that has
not been named yet. I called it prioritized_set<>.

> 3. If we have 6.000.000 vertexes with weighted edges, what
> representation would be optimal (edge-list)?

I would go fully-associative as described above. Make your edges fat.
Make your nodes fat. Define your edge-identifier as a class in its
own right, containing references that bind at construction time to the
nodes and edges in your graph. This will keep overhead low, but keep
your algorithms from exploding to O(n^3).

You cannot use list<> as you know, or the graph will become
intractable. You must use O[log(n)] or better structures, like map<>.

Just a note: I have yet to see an easy-to-use, generalized graph class
on the Internet. Boost graph undoubtedly works, but it is not trivial.
There is an entire book dedicated to it:

[http://www.informit.com/store/produc...bn=0201729148]

-Le Chaud Lapin-


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

I might use multimap or hash table? Map mismatchs, because of one
vertex can have some
edges. So, i can code template classes library with allocator
argument:
//With low vertexes count
- default_allocator: for directed complete unweighted/ weighted graph
use bit/byte adjacency matrix;
- triangle_allocator: for undirected unweighted/ weight graph use bit/
byte adjacency matrix;
- list_allocator: for directed/directed insufficient unweighted/
weight graph use adjacency list; (check graph density)
- maybe, edge_allocator (edge vector, edge list or edge array for some
other needs)
- edge_allocator: ?
//With high vertexes count
- boost_allocator;
- multimap_allocator; // my own

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

On Aug 7, 4:28 pm, Alexander Zezulinsky <palgol...@gmail.com> wrote:
> I might use multimap or hash table? Map mismatchs, because of one
> vertex can have some
> edges. So, i can code template classes library with allocator
> argument:
[snippage]

If I were you, I would seriously consider attemtpting to implement
Dijkstra's least-cost/least-path algorithm against your incomplete/
uncommitted graph<> before continuing. The reason is that many
descriptions of Dijkstra's algorithm, while technically correct, gloss
over some details that must inevitably rise up once you get into the
implemenation. For example, the following Wikipedia description is
correct, but there are some details, some trivial, one complex, that
will present itself when you get into the details:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

A trivial detail is that you will need a back-pointer inside whatever
structure you use for a Vertex to synthesize the least-cost path for a
run of Dijkstra.

I could tell you what the complex detail is, but that would ruin the
experience for you. ;)

As I implied before, if you get to the point where you have a graph<>
that is simple to use; allows the addition, removal, and redefinition
of edges, nodes, and links, with costs of edges, etc; and you have
implemented Dijkstra's algorithm; I think you will find that the
overhead required simply to keep O(n) manageable is so great, you will
give up all attempts to conserve space using bits. The per-struct
overhead is surprisingly high.

Please note differences between:

1. A structure on a piece of paper that can be interpreted by a human
to determine connectivity.
2. A structure in a computer that can be interpreted by a computer to
determine connectivity.
3. A structure in a computer that can be interpreted by a computer to
execute Dijkstra's and other algorithms.

I think the complexity of 3 will surprise you once you delve deep into
finding a suitable representation.

-Le Chaud Lapin-


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]