LinuxQuestions.org
Visit Jeremy's Blog.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 04-18-2008, 02:28 PM   #1
hamtavs
Member
 
Registered: Aug 2004
Location: Italy,near Milan
Distribution: red hat 9
Posts: 63

Rep: Reputation: 15
Graph data structure generation options and parametrization


Hello to everyone,

I'm looking for some suggestions for the following problem: generating a (undirected) graph instance for a NP-hard problem solver; the graph is implemented by an array of adjacency dynamic lists.

I've already wrote a simple routine to generate an instance given the number of nodes and the desired density, and it would be really nice if I could

-guarantee instance's connection without having to check it later

and ,more importantly,

- get more control on some of its topological characteristics, namely vertexes' max and min degrees, though the former is trivial to achieve.

thanks

HT
 
Old 04-18-2008, 03:44 PM   #2
Mara
Moderator
 
Registered: Feb 2002
Location: Grenoble
Distribution: Debian
Posts: 9,696

Rep: Reputation: 232Reputation: 232Reputation: 232
I can think of a simple algo:
Code:
generate first node
while there_are_more_nodes_to_generate
    choose one existing node i
    generate new node n
    connect i to n
    connect i to other nodes with some given probability
    decrease probability
done
Does it fit?
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Want to poll data from Windows server to Linux Box for MRTG Graph manoj_sin Linux - Networking 1 04-29-2008 05:46 AM
wget options for directory structure davimint Linux - Server 3 05-18-2007 10:24 PM
Data structure trie spank Programming 7 05-21-2006 07:21 AM
LXer: Putting physical data on a Web graph LXer Syndicated Linux News 0 04-28-2006 08:21 PM
gprof: gmon.out file is missing call-graph data hemk76 Programming 0 01-07-2005 11:54 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 02:45 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration