Wikipedia:Reference desk/Archives/Computing/2007 November 18

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

November 18

Building gnu coreutils-6.9 on Mac OS X 10.5

I don't have a lot of experience in building programs from source (none, actually). I decided to experiment by building the GNU core utilities. I downloaded 6.9 (newest version) from the gnu website. I ran the 'configure' executable and it determined that my Mac should be be able o build the core utilities. When I actually ran 'make' command it ran for a few minutes without problems. Abrubtly, it stopped and gave me the message:

Making all in lib
make all-am
make[2]: Nothing to be done for `all-am'.
Making all in src
make all-am
gcc -std=gnu99 -g -O2 -o date date.o ../lib/libcoreutils.a ../lib/libcoreutils.a
Undefined symbols:
"_rpl_putenv$UNIX2003", referenced from:
_main in date.o
ld: symbol(s) not found
collect2: ld returned 1 exit status
make[2]: *** [date] Error 1
make[1]: *** [all] Error 2
make: *** [all-recursive] Error 1

Can anyone tell me what is going wrong? I though Leopard had full Unix certification, so this should work, right?

Google _rpl_putenv and find this exchange where the same problem has been reported before. There's a patch there, which will be in the next release of coreutils. --tcsetattr (talk / contribs) 06:02, 18 November 2007 (UTC)

Thank you! Worked like a charm. Quick question: How do I build in 64 bit? I have Core 2 Duo.

I don't think you can unless you're running from a 64-bit OS. There's no 64-bit version of Mac OS X, but there are 64-bit versions of Windows and Linux you could obtain. — User:ACupOfCoffee@ 05:13, 19 November 2007 (UTC)

Actually, there has been a 64 bit version of MacOSX ever since 10.4 came out, however, it only supported the 64 bit PPC. IN 10.5, there is now support for x86_64 intel systems. I suggest that the OP read Apple's 64 Bit Transition Guide, there are some links there for how to instruct GCC to generate 64 bit objects on intel. -- JSBillings 12:37, 19 November 2007 (UTC)

Algorithm for finding cycles on directed graphs

Are there any WP articles on algorithms to find cycles in directed graphs? (I couldn't find any. The graph is currently in an adjancy matrix.) Bubba73 (talk), 07:05, 18 November 2007 (UTC)

You could just do something like a depth-first search, and when you come across the starting vertex, you have got a cycle. --Spoon! (talk) 08:16, 18 November 2007 (UTC)

Yeah, but what if the cycle does not involve your starting vertex? I think you are looking for Strongly connected component (Tarjan's strongly connected components algorithm). You can compute this in linear time. If every node is its own component, the graph is acyclic. Otherwise a cycle can be found by doing what spoon said starting at a node within a strongly connected component containing more than one vertex. Finding all cycles is more of a hassle, as there may be a lot of them (a lot = n! and some more).

The application is that there will be graphs with about 50 to 75 vertices (perhaps 100). Each vertex will have at most 20 directed edges connected to it. Quite a few will have 15 or more. For several pairs of vertices I need to see if they are in a directed cycle or not. So it sounds like what I might need to do is first find the strongly connected components and then if they are not in the same component then there is no cycle, otherwise there is, right? Bubba73 (talk), 15:34, 18 November 2007 (UTC)

Yes. A single pass over a graph suffices for all pairs in that graph.

Thanks. One little wrinkle is that cycles of length 2 may not count as cycles. Bubba73 (talk), 16:53, 18 November 2007 (UTC)

One way to do this is extend the idea of a DG to "paintable". The vertices have two states, painted and unpainted. For each root vertex in the DG, do a normal depth-first search, painting vertices as you go along. If you ever come across a vertex that has already been painted, you have a cycle. JIP | Talk 15:44, 18 November 2007 (UTC)

Now really, why do you propose a quadratic algorithm after a linear one was linked?

I don't see how my algorithm is quadratic. I've looked at the pseudocode for the Tarjan algorithm, and it seems that it has to be done for each source vertex separately. The way I see it, both algorithms are in linear time for each source vertex: they're just depth-first searches that do extra constant-time work at each vertex. If there are multiple source vertices it gets more complex though. JIP | Talk 17:03, 18 November 2007 (UTC)

A single run of Tarjan's algorithm finds all components. You do not need to rerun it for every source vertex. See the link in the article, it is much better than the article itself. —Preceding unsigned comment added by 153.96.188.2 (talk) 10:05, 19 November 2007 (UTC)

If you have control of the data structure used for the nodes of the graph, then just add a boolean "has_been_visited" which you default to 'false' in the constructor function for the class. To perform your depth-first traversal the graph call this recursive function on the root node of the graph:

 bool NodeType::isCyclic ()
 {
   if ( has_been_visited )  // If we already visited this node then it's a cyclic graph
     return true ;
   has_been_visited = true ;
   for ( int i = 0 ; i < num_child_nodes ; i++ )
     if ( child [ i ] -> isCyclic () ) // If the subgraph is cyclic then so is this one
       return true ;
   has_been_visited = false ;
   return false ;
 }

If you don't have control over the data structure then you need to create a hash table containing the addresses of the nodes you've visited and use that table to replace the 'has_been_visited' boolean.

SteveBaker (talk) 17:28, 18 November 2007 (UTC)

The algorithm I gave is a simplified version of this. It does not separately check for subgraphs, otherwise it is the same thing. JIP | Talk 17:34, 18 November 2007 (UTC)

That's not true - your approach doesn't work. Consider this directed graph:

      A
     / \
    B   C
     \ /
      D
      |
      E

(The links all point downwards). This graph doesn't have a 'cycle' because it's 'directed' - but it fails your approach because node 'D' is visited twice during the traversal. If you look at my code, you'll see that I unmark the nodes as it backs up the graph - so this graph is (correctly) returned as non-cyclic. SteveBaker (talk) 21:35, 18 November 2007 (UTC)

Thanks for your help guys - I think I can get it. I'll be working on it tomorrow. Bubba73 (talk), 01:55, 19 November 2007 (UTC)

I have a problem?

I have an Acer Aspire laptop. It has a black touch pad to move the pointer or cursor around on the screen. I could click on something by tapping the touch pad twice, and I could draw the scroller up and down by tapping twice and then move my finger up and down. It used to work, but now it doesn't move the pointer around anymore. The pointer still moves when I do it with a wireless mouse. But I want to fix the touch pad. How can I make the touch pad work again?

Hard to say; could even be broken. But for first check (I'll assume you have Windows): go to Start -> Settings -> Mouse. "Hardware" tab should say "this device is working properly". Check that the touchpad is enabled on the "Device Settings" tab. Weregerbil (talk) 11:40, 18 November 2007 (UTC)

Also make sure you haven't disabled your touchpad. Should be an option in the taskbar or in the aforementioned folder Heirware (talk) 11:46, 18 November 2007 (UTC)

In many cases the touchpad automatically disables when you plug a mouse into the computer. Try unplugging/disabling the mouse, see if that changes anything. --24.147.86.187 (talk) 16:38, 18 November 2007 (UTC)

search and replace in 1000 .txt files

Say I have 1000 . txt files in different folders, they all have different content but all have a line of text in the middle or at the end that I would like to remove to save HD space on a mp3 player. How would I go about doing this batch-style, without having to open all the folders or files individualy? ~Thank you. Keria (talk) 17:30, 18 November 2007 (UTC)

I would use UltraEdit, but there are probably a number of other editors that could do a batch find and replace. See Category:Windows text editors. --— Gadget850 (Ed) ^talk - 17:34, 18 November 2007 (UTC)

• You don't say what platform you're on, but if you're on MacOS or something Unixy, running this command will do the trick:

perl -pi -e 's/the line of text you want to remove.*\n?//' *.txt

--Sean 17:54, 18 November 2007 (UTC)

All right! Sorry yes I'm running Windows XP er ... x64. Thank you gadget I'll try that. Keria (talk) 17:59, 18 November 2007 (UTC)

Aw shoot, it looked so promissing. Ultredit doesn't work on 64bits machines. Keria (talk) 18:19, 18 November 2007 (UTC)

Well duh. Ultraedit is fantastic though --ffroth 19:45, 18 November 2007 (UTC)

The good news is that you can get perl running on XP, but getting 1000 files into the command line is dubious in XP. You may have to runit under a bash shell instead, say with cygwin. Graeme Bartlett (talk) 20:02, 18 November 2007 (UTC)

Not to nitpick the whole project, but is the amount of space to be freed worth the trouble? I can't imagine it adding up to more than 2 MB or so, which is nothing compared to the size of most MP3s. You'd probably spend your time better finding just one song you don't ever listen to and just deleting that, no? --24.147.86.187 (talk) 21:22, 18 November 2007 (UTC)

At the moment it's 5 GB (it's more than 1000 files I just used that as an example, sorry for the misunderstanding). I hope I can save at least 1 GB. If anyone has an idea I'm listening (well, reading). I tried NoteTab (freeware) but it needs to open the files to work with them so it can't handle the job. Graeme you use a lot of words I have never seen before but I'm sure I can figure it out (I don't have to bash shells, right?). Is it as complicated as it sounds? Apparently there is some complicated way to install UltraEdit on x64. Does it need to load the files to replace text in them or can it just go through them as they are sitting on the HD? Keria (talk) 22:49, 18 November 2007 (UTC)

You probably can't shave 1GiB off just by removing 1 line off every file, but if you can't find an editor that can do it, you can always install perl and run the command mentioned by User:TotoBaggins (aka Sean); or, you can install cygwin, and run these commands:

cd /path/where/you/put/the/files
ls | while read line; do sed -i "/^Your text here$/d" "${line}"; done

They basically do the same thing, but it's always better to try it out on a single file first by copying that file to a new directory, change the working directory of your command prompt (aka shell) to the same directory, and run either one of the commands to try it out on first. --antilived^{T | C | G} 23:07, 18 November 2007 (UTC)

Right. I tried it with cygwin but it doesn't go into sub-folders, it says: sed: couldn't edit <name of subfolder>: not a regular file. It didn't replace anything in the files that were in the root folder but changed them so the the note pad has trouble reading them. It replaced ^P 's by some unknown character.

The text I have to replace is of this kind of format: ^P^P^P^P^Pyadiyadiyada^P^P^P^PBlablabla for lines and lines of rubish^P^P^P where ^P is a line break. Is it possible to copy-paste it into the command window? It's really long to type and I have to enter a dozen different versions.

I'll try with perl even if it looks even more complicated. BUT: How can I go into subfolders? Does perl do it? Is there a command way of deleting all files smaller than 2KB? Is there a command for deleting empty folders? Is there a command to delete files containg a certain string of characters or by their file extension? Keria (talk) 15:17, 19 November 2007 (UTC)

find or ls -R gets you into subdirectories

find ./ -type f -size -2k -exec rm \{\} \; removes regular files smaller than 2K

find ./ -type d -exec rmdir \{\} \; removes empty directories

ls -R | while read line; do if ( grep -q "string of characters" "$line" ); then rm "$line"; fi; done remove files which contain "string of characters"

find ./ -name \*.ext -exec rm \{\} \; remove files with extenstion .ext

Untested, use at your own risk. -- Diletante (talk) 16:27, 19 November 2007 (UTC)

Thank you Diletante. That's in cygwin right?

Then find ./ -name \*old*.* -exec rm \{\} \; would remove all files with "old" in their name? Keria (talk) 16:42, 19 November 2007 (UTC)

I tried the first one find ./ -type f -size -2k -exec rm \{\} \; when I press enter a ">" symbol appears on the next line, if I press enter again it says: "find: missing argument to "-exec" Keria (talk) 16:58, 19 November 2007 (UTC)

Are you sure you typed it correctly? Try copy and paste? ls -r will list subdirectories, but won't get you in there because it doesn't give you the path to it, you have to use find instead. just replace the ls with find ./ so it becomes something like this:

find ./ | while read line; do sed -i "/^Your text here$/d" "${line}"; done

or just use the -exec argument in find

find ./ -type f -exec sed -i "/^Your text here$/d" \{\} \;

Which will remove any line that starts and ends with "Your text here". If you want to do more you need to give us more information: What exactly do you want to delete and do you want to retain empty lines in other places? A sample file would be nice is well. --antilived^{T | C | G} 22:01, 19 November 2007 (UTC)

Antilived, you are right about the ls -R, I was mistaken trying to use it like that. Keria, it seems like you aren't including the semicolon at the end. Also when you use wildcards in find you should escape them with a backslash like \* so the shell doesn't try to expand them. Same deal with the semicolon, it is an argument to find, so you don't want the shell to interpret it. -- Diletante (talk) 23:33, 19 November 2007 (UTC)

Of course I had checked again and again I had typed it correctly ... without the semicolon! Thank you Diletante you were right and thank you Antilived and everybody who helped. The -2k has been running for 5 hours now and it seems to be working. I'll try all the other commands once that one is done and report back. Cheers! Keria (talk) 16:31, 20 November 2007 (UTC)

All right after 2 days I have processed 1/10th of the files! It's going well though. Thank you very much to everybody who helped! There's only the line to delete directories that doesn't work it just returns this error for every folder: rm: cannot remove './folder/01/02': Is a directory. Keria (talk) 17:01, 22 November 2007 (UTC)

My bad I typed it wrong again. Keria (talk) 17:03, 22 November 2007 (UTC)

Standby → Shutdown

Whenever I try to put my computer on standby (or whenever it's idle long enough and automatically goes on standby), it will just shut down instead. I've tried adjusting the power scheme options, but I can't seem to find the right thing to change, because all of my adjustments have been futile. I'm running a Windows XP SP2. How can I fix this and allow my computer to go on standby instead of just shutting down? Thanks for the help. --72.69.146.66 (talk) 18:53, 18 November 2007 (UTC)

Check with your motherboard vendor and see if there is a BIOS upgrade. My MB is a five year old Abit, and I think it had the same problem until an upgrade. --— Gadget850 (Ed) ^talk - 18:55, 18 November 2007 (UTC)

Older motherboards seemed to have difficulties with going into standby. You could check the BIOS and see if there is any option in there for Power. GaryReggae (talk) 20:08, 18 November 2007 (UTC)

Second that recommendation: That's what fixed by unbelievably annoying MSI systemboard that would crash on standby. 68.39.174.238 (talk) 23:14, 24 November 2007 (UTC)

Family Tree software

Hi folks, a software question for you from a frustrated computer user.

About a couple of years ago, I purchased some software via the internet called "Family Tree Maker" ( (FTM)(version unknown), if I remember rightly, I downloaded the trial version, liked what I saw and paid for a registration code to upgrade it to the full version.

A few months ago, my computer had become virtually unusable due to Windows playing silly games and being on a constant go-slow so I backed up all my data files and reformatted and reinstalled Windows and all my software. I had forgotten about the FTM software but wasn't concerned as I had an email with the registration code and had assumed it was like most sofware of the same ilk (GameMaker for example) where if they release a new version, you are entitled to upgrade for free or a nominal fee but when I tried to find the software and reinstall it, all their website www.familytreemaker.com came up with is an entirely different new version with no option for existing users to upgrade or for acquiring previous versions. This seems like a con to me and I am very loathe to give them any more of my money as the same thing will probably happen the next time. I am also quite happy with my 'old' version and don't need any new features. I can understand them not supporting older versions any more but withdrawing something somebody has paid for is not on. If I had known, I would have tried to salvage the program files but that often doesn't work.

Does anyone know where I can download some FREEWARE family tree software? It must be able to load GEDCOM files and preferably Family Tree Maker (.FTW) files as well. I know I could Google it but I have and it comes up with a list of totally irrelevant stuff, some of which is definitely NOT Freeware and others of which include spyware, so much for the powers of Google manipulation. Alternatively, I would consider a reasonably priced (< £20/$40) paid for package if there was an assurance they wouldn't pull the rug out underneath theur loyal existing users and force them to cough up again for a new version every so often. GaryReggae (talk) 20:25, 18 November 2007 (UTC)

Try Comparison of genealogy software and Category:Free genealogy software. --— Gadget850 (Ed) ^talk - 20:45, 18 November 2007 (UTC)

Macbook video editing

I am thinking of purchasing a new computer, preferably a macintosh laptop. Due to some lack of funds, it's the cheapest macbook that is highest on my list. I would like to make some rudimentary video editing with it. Can it handle editing with Final Cut (possibly some sort of off-line editing with low resolution)? As I understand it, Apple recently upgraded the graphics capabilities of the macbooks. Will this make any difference to video editing? Do you have any recommendations? --Oskar 22:04, 18 November 2007 (UTC)

Yes it can handle Final Cut just fine, though you'll want to get some sort of monster external firewire drive for it (the scratch disk takes at least 1GB a minute or so, sometimes more). I have a MacBook bought earlier in the year (cheapest model that came with a DVD-R drive; a 2 GHz Intel Core 2 Duo, 1 GB of RAM) and it ran Final Cut Pro just wonderfully when I used it a little while back. --24.147.86.187 (talk) 23:57, 18 November 2007 (UTC)

Just as an addendum, my MacBook can even run Half-Life 2 fairly well under the Parallels Desktop virtualizer. They pack quite a wallop even under quite a lot of computational stress. --24.147.86.187 (talk) 23:38, 19 November 2007 (UTC)