Re: Graph representation
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/product.aspx?isbn=0201729148]
-Le Chaud Lapin-
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]